Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds
Abstract
We establish tight polynomial tolerance bounds for stochastic second-order stationarity when each fresh oracle response is a derivative of one common random scalar loss. For a population objective F with Lipschitz gradient and Hessian, the target is |∇ F(x)|≤ ε and λmin(∇2 F(x))≥ −γ, with independent tolerances ε,γ>0. Under bounded gradient variance and almost-surely bounded Hessian error, the minimax number of fresh gradient or Hessian-vector-product calls is Θ̃ (ε−3+γ−5). The characterization fixes positive gap, smoothness, and noise parameters, suppresses logarithmic factors, and allows dimension to grow within an explicit polynomial envelope. The upper bound removes the mixed term ε−2γ−2 from the earlier fresh-HVP guarantee. Direct random-line Hessian estimates and a dyadic gradient tracker separate gradient drift from randomly signed curvature motion. The lower bound realizes the endpoint costs through globally defined smooth random losses: a smooth partition localizes scalar noise without a chain-length penalty, while exact cancellation limits the information in the entire response. Consequently, the same tolerance exponents hold even for joint value, gradient, and full-Hessian responses with bounded value variance. For a population Hessian with Hölder exponent ν∈(0,1], fresh gradient/HVP complexity becomes Θ̃ (ε−3+γ−(3+2/ν)) under the corresponding dimension envelope.
Related
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
- Achieving Directional-Stationarity from a Single Random Direction Step
- Statistical Learning of Conditional Single-Index U-Processes Under Local Stationarity and Missing-At-Random Functional Responses
- Matching Complexity for Second-Order Stationary Point with Sample Reuse
- The terminal leave in random greedy hypergraph matching
BibTeX
@misc{wu2026secondorder,
title = {{Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds}},
author = {Wendao Wu and Haihan Zhang and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.28238},
eprint = {2609.28238},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28238},
}
RIS
TY - UNPB
TI - Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds
AU - Wendao Wu
AU - Haihan Zhang
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.28238
UR - https://arxiv.org/abs/2609.28238
AB - We establish tight polynomial tolerance bounds for stochastic second-order stationarity when each fresh oracle response is a derivative of one common random scalar loss. For a population objective F with Lipschitz gradient and Hessian, the target is |∇ F(x)|≤ ε and λ_min(∇^2 F(x))≥ −γ, with independent tolerances ε,γ>0. Under bounded gradient variance and almost-surely bounded Hessian error, the minimax number of fresh gradient or Hessian-vector-product calls is Θ̃ (ε^−3+γ^−5). The characterization fixes positive gap, smoothness, and noise parameters, suppresses logarithmic factors, and allows dimension to grow within an explicit polynomial envelope. The upper bound removes the mixed term ε^−2γ^−2 from the earlier fresh-HVP guarantee. Direct random-line Hessian estimates and a dyadic gradient tracker separate gradient drift from randomly signed curvature motion. The lower bound realizes the endpoint costs through globally defined smooth random losses: a smooth partition localizes scalar noise without a chain-length penalty, while exact cancellation limits the information in the entire response. Consequently, the same tolerance exponents hold even for joint value, gradient, and full-Hessian responses with bounded value variance. For a population Hessian with Hölder exponent ν∈(0,1], fresh gradient/HVP complexity becomes Θ̃ (ε^−3+γ^−(3+2/ν)) under the corresponding dimension envelope.
ER -