Matching Complexity for Second-Order Stationary Point with Sample Reuse
Abstract
We consider stochastic nonconvex optimization with sample-wise Lipschitz gradients and Hessians, and reusable opaque sample handles. Gradient and complete-Hessian evaluations are charged separately, including both endpoints of a same-sample difference. For fixed positive problem parameters and in the high-dimensional worst case, we prove that the minimax total derivative-query complexity of finding an (ε,γ)-second-order stationary point is Θ̃(ε−3+γ−3). The upper bound combines curvature-first randomly signed negative-curvature steps with binary-ancestor derivative estimators; a truncated increment estimate charges predictable drift linearly and martingale motion quadratically. The curvature lower bound uses a deterministic smooth bounded-gradient chain, a radial barrier, and a random rotation. The new first-order lower bound is specifically robust to persistent sample reuse and to complete-Hessian access. It uses a slowly parameterized conservative sign chain, a third-order reverse stick-breaking localization inequality, and stateful relative-entropy accounting for reusable handles. Thus the total rate is near-optimally matched for every relation between ε and γ.
Related
- Second-Order Flows for Approaching Stationary Points via the SAV-E Approach
- On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
- Viscosity-variational inequality solutions of fully nonlinear second-order stationary mean field games with nonseparable and nondifferentiable Hamiltonians
- Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities
- Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds
BibTeX
@misc{chen2026matching,
title = {{Matching Complexity for Second-Order Stationary Point with Sample Reuse}},
author = {Qian Chen and Wendao Wu and Haihan Zhang and Chenheng Zhang and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16832},
eprint = {2610.16832},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16832},
}
RIS
TY - UNPB
TI - Matching Complexity for Second-Order Stationary Point with Sample Reuse
AU - Qian Chen
AU - Wendao Wu
AU - Haihan Zhang
AU - Chenheng Zhang
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.16832
UR - https://arxiv.org/abs/2610.16832
AB - We consider stochastic nonconvex optimization with sample-wise Lipschitz gradients and Hessians, and reusable opaque sample handles. Gradient and complete-Hessian evaluations are charged separately, including both endpoints of a same-sample difference. For fixed positive problem parameters and in the high-dimensional worst case, we prove that the minimax total derivative-query complexity of finding an (ε,γ)-second-order stationary point is Θ̃(ε^−3+γ^−3). The upper bound combines curvature-first randomly signed negative-curvature steps with binary-ancestor derivative estimators; a truncated increment estimate charges predictable drift linearly and martingale motion quadratically. The curvature lower bound uses a deterministic smooth bounded-gradient chain, a radial barrier, and a random rotation. The new first-order lower bound is specifically robust to persistent sample reuse and to complete-Hessian access. It uses a slowly parameterized conservative sign chain, a third-order reverse stick-breaking localization inequality, and stateful relative-entropy accounting for reusable handles. Thus the total rate is near-optimally matched for every relation between ε and γ.
ER -