Separable Noise Linf Smooth Lower Bound — High-Dimensional Stationarity with Separable Noise
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Stationarity with Separable Noise · Lean proof
High-Dimensional Stationarity with Separable Noise
We seek a stationary point of a differentiable, possibly nonconvex
objective
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Stochastic gradients with separable
noise). On call
After the allotted oracle calls, the output
Proved result
OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalSeparableNoiseLinfSmooth.spec
LongTails.Theorems.SeparableNoiseLinfSmoothLowerBound.budgetRelevant previous results
- Ruichen Jiang, Devyani Maladkar, and Aryan Mokhtari. Provable
Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in
Stochastic Non-Convex Optimization. 2025 (COLT). Complexity:
stochastic gradient calls for constant-step SGD in the one-dimensional specialization, for and with universal . - Hongyi Tao, Dingzhi Yu, and Lijun Zhang. When and Why SignSGD
Outperforms SGD: A Theoretical Study Based on ℓ₁-norm Lower Bounds.
2026 (arXiv v1). Complexity:
individual stochastic gradient calls for constant-step minibatch SignSGD to attain , with for coordinate standard-deviation bounds and calls for steps of batch size .