← All setups

Finite-Sum Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Nonconvex Optimization

We consider minimizing F(x)=n−1∑i=1nfi(x) on a real Hilbert space E, where n≥1 and the differentiable components fi:E→R may be nonconvex. Their gradients satisfy a mean-square Lipschitz bound with constant L>0. At a given starting point x0∈E, the objective lies within Δ≥0 of a global lower bound. The oracle returns ∇fi(x) at a queried index i and point x. For ε>0, the goal is a measurable output x¯∈E with EP[∥∇F(x¯)∥2]≤ε2, where P is the law of the algorithm’s randomness.

The optimization problem is infx∈EF(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with a measurable structure. The algorithm receives E, n, L, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Mean-square smoothness). Each component fi is Fréchet differentiable everywhere on E, and 1n∑i=1n∥∇fi(x)−∇fi(y)∥2≤L2∥x−y∥2,x,y∈E. Consequently, the objective gradient is ∇F(x)=1n∑i=1n∇fi(x).

Assumption 2 (Lower bound and initial gap). There exists ℓ∈R such that F(x)≥ℓfor every x∈E,F(x0)−ℓ≤Δ.

Queries may use any index i∈{1,…,n} and any point x∈E; each query returns one exact component gradient. After the allotted oracle calls, the output x¯ must be measurable, its squared gradient norm must be integrable under P, and it must satisfy EP[∥∇F(x¯)∥2]≤ε2.

Results

On a real Hilbert space E equipped with a measurable structure, let F=n−1∑i=1nfi, with differentiable fi and n≥1. Assume n−1∑i∥∇fi(x)−∇fi(y)∥2≤L2∥x−y∥2 for all x,y, and F≥ℓ with F(x0)−ℓ≤Δ, where L>0, Δ≥0. The oracle returns exact component gradients. For ε>0, the target is a measurable output X with integrable squared gradient and ∫∥∇F(X(ω))∥2dP(ω)≤ε2, where P is the algorithm’s randomization law. Convexity and attainment of the infimum are not assumed.

Finite-sum nonconvex optimization under mean-squared smoothness (FiniteSumSmoothNonconvex).
Result Oracle complexity Novelty Limitations
(1) RecursiveGradientNonconvex (Ours) (review) O(n+nLΔε2) deterministic calls.
(2) Minibatch SARAH (Nguyen et al. 2019, Thm. 2, Cor. 3). E=Rd. O(n+nLΔε2) deterministic calls; batch and epoch lengths ≍n. (1): Matches known rate, formalized in Lean. Scope: Hilbert spaces. With-replacement instead of without-replacement batches; no rate or tuning-knowledge improvement.
(3) SpiderBoost (Wang et al. 2020, Thm. 1; App. G, Thm. 9). E=Rd; each ∇fi is L-Lipschitz. O(n+nLΔε2) deterministic calls; squared-gradient guarantee from App. G. (1): Scope: mean-squared smoothness instead of componentwise smoothness; Hilbert spaces. Matches rate on the common setup. The smoothness relaxation is already covered by (2).
(4) PAGE (Li et al. 2021, Thm. 1, Cor. 2; App. A.1, Eq. (23)). E=Rd; F∗=minF in the stated gap. O(n+nLΔε2) expected calls; squared-gradient guarantee from App. A.1. (1): Deterministic rather than expected call budget, at matched order on the common setup; this budget guarantee already holds for (2).

Abbr: n: number of components; L: mean-squared smoothness bound; ℓ: objective lower bound; Δ: initial gap bound; ε: root-mean-square gradient tolerance. Calls count individual component-gradient evaluations, including full refreshes and two evaluations per sampled difference. Prior-work gaps are bounded by Δ on the common setup; ≍ denotes equality up to universal factors.

Li, Zhize, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. 2021. “PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.” In Proceedings of the 38th International Conference on Machine Learning, edited by Marina Meila and Tong Zhang, vol. 139. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v139/li21a.html.
Nguyen, Lam M., Marten van Dijk, Dzung T. Phan, Phuong Ha Nguyen, Tsui-Wei Weng, and Jayant R. Kalagnanam. 2019. Finite-Sum Smooth Optimization with SARAH. https://doi.org/10.48550/arXiv.1901.07648.
Wang, Zhe, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. 2020. SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms. https://doi.org/10.48550/arXiv.1810.10690.

Lean setup