Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
Abstract
We establish a randomized first-order lower bound for finding an ε-stationary point, |∇ f(x)|≤ ε, of a nonconvex function with initial gap at most Δ, L1-Lipschitz gradient, and L2-Lipschitz Hessian. Each oracle call returns the exact function value and gradient. Let Qrand,FO∞(ε;Δ,L1,L2) denote the minimax number of calls, maximized over finite dimensions, for arbitrary adaptive randomized algorithms with per-instance success probability at least 2/3. In the regime ε≲ L12/L2 and ΔL21/2ε−3/2≳ 1, we prove $ Q_{\mathrm{rand},\mathrm{FO}}^{\infty}(ε;Δ,L_1,L_2) \ge c\,ΔL_1^{1/2}L_2^{1/4}ε^{-7/4}, $ where c>0 is an absolute constant. This matches the deterministic restarted accelerated-gradient upper bound of Li and Lin (2023) and extends the sharp deterministic lower bound of Zhou (2026) to unrestricted randomized algorithms. Thus, randomization does not improve the high-dimensional worst-case query rate. The construction keeps quadratic curvature visible while revealing the forcing directions sequentially. Large eigenspaces limit preprocessing, and a scheduled-disclosure coupling makes each fresh direction incur a separate cost.
Related
- Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
- Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization
- Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
BibTeX
@misc{zhang2026matching,
title = {{Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization}},
author = {Haihan Zhang and Wendao Wu 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.2610.00245},
eprint = {2610.00245},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00245},
}
RIS
TY - UNPB
TI - Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
AU - Haihan Zhang
AU - Wendao Wu
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.2610.00245
UR - https://arxiv.org/abs/2610.00245
AB - We establish a randomized first-order lower bound for finding an ε-stationary point, |∇ f(x)|≤ ε, of a nonconvex function with initial gap at most Δ, L_1-Lipschitz gradient, and L_2-Lipschitz Hessian. Each oracle call returns the exact function value and gradient. Let Q_rand,FO^∞(ε;Δ,L_1,L_2) denote the minimax number of calls, maximized over finite dimensions, for arbitrary adaptive randomized algorithms with per-instance success probability at least 2/3. In the regime ε≲ L_1^2/L_2 and ΔL_2^1/2ε^−3/2≳ 1, we prove $ Q_{\mathrm{rand},\mathrm{FO}}^{\infty}(ε;Δ,L_1,L_2) \ge c\,ΔL_1^{1/2}L_2^{1/4}ε^{-7/4}, $ where c>0 is an absolute constant. This matches the deterministic restarted accelerated-gradient upper bound of Li and Lin (2023) and extends the sharp deterministic lower bound of Zhou (2026) to unrestricted randomized algorithms. Thus, randomization does not improve the high-dimensional worst-case query rate. The construction keeps quadratic curvature visible while revealing the forcing directions sequentially. Large eigenspaces limit preprocessing, and a scheduled-disclosure coupling makes each fresh direction incur a separate cost.
ER -