← All setups

Quadratic Finite-Sum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Quadratic Finite-Sum Minimization

We consider minimizing f=n−1∑i=1nfi on a real Hilbert space E, where n≥1 and each fi:E→R is quadratic. Component Hessians have operator norm at most L>0, and their average is bounded below by μI, where 0<μ≤L and I is the identity on E. A given point x0∈E satisfies ∥x0−x⋆∥≤R for the minimizer x⋆, with R≥0 and ∥∇fi(x⋆)∥≤G for G≥0. The oracle returns ∇fi(x) at a queried pair (i,x). For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

Write the component objectives and their average as fi(x)=12⟨x,Aix⟩+⟨bi,x⟩,i=1,…,n,f(x)=1n∑i=1nfi(x), where each Ai:E→E is a bounded linear operator and bi∈E. The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E, n, L, μ, R, G, ε, and x0; the operators Ai and vectors bi are accessed through the oracle.

Our assumptions:

Assumption 1 (Component curvature and strong convexity). For every i∈{1,…,n}, the operator Ai is symmetric and bounded by L: ⟨Aix,y⟩=⟨x,Aiy⟩,x,y∈E,∥Ai∥op≤L. The average curvature satisfies 1n∑i=1n⟨x,Aix⟩≥μ∥x∥2,x∈E.

Assumption 2 (Initial distance and component gradients). There exists x⋆∈E such that ∑i=1n(Aix⋆+bi)=0,∥x0−x⋆∥≤R,∥Aix⋆+bi∥≤G,i=1,…,n. The curvature condition makes x⋆ the unique global minimizer of f.

At any selected index i∈{1,…,n} and point x∈E, the oracle returns the exact component gradient ∇fi(x)=Aix+bi. After the allotted component-gradient calls, the output x¯ must be measurable, its objective gap must be integrable under P, and it must satisfy EP[f(x¯)−f(x⋆)]≤ε.

Results

On a real Hilbert space with its Borel measurable structure, let F(x)=n−1∑i=1n(⟨x,Aix⟩/2+⟨bi,x⟩), where n≥1, Ai=Ai∗, ∥Ai∥≤L, and n−1∑iAi⪰μI, with 0<μ≤L. Components may be indefinite. A minimizer x∗ satisfies ∥x0−x∗∥≤R and maxi∥Aix∗+bi∥≤G, with R,G≥0. The exact oracle returns Aix+bi; n,L,μ,R,G,ε are supplied. Target: E[F(xout)−F(x∗)]≤ε. Row (1) constructs constant-step random reshuffling with independent uniform permutations per epoch; the setup imposes no algorithm restriction. Comparisons below use 0<ε<LR2.

Quadratic finite sums: comparison for QuadraticFiniteSum.
Result Oracle complexity Novelty Limitations
(1) RandomReshufflingQuadratic (Ours) (review) O(n+[nLμ+L3/2Gμ2ε
+(n2L3G2μ4ε)1/3]ℓ)
(2) AGD (Bubeck 2015, Thm. 3.18) O(n+nL/μℓ) (1): No established improvement. (1): nL/μ instead of nL/μ, plus heterogeneity terms; needs G additionally. Expected rather than deterministic accuracy.
(3) Katyusha X (Allen-Zhu 2018, Cor. 4.4, v1); finite-dimensional restriction, b=1, ℓ1=ℓ2=L O((n+n3/4L/μ)ℓ) expected calls (1): Deterministic budget instead of expected cost. Scope: Hilbert-space statement; the dimension extension is formal. (1): On finite-dimensional overlap, nL/μ≥n3/4L/μ, with additional G-dependent terms.
(4) RandomShuffle (Ahn et al. 2020, App. B, Lemmas 6–8, v2); derived bound, finite-dimensional restriction O(n+[nLμmax{1,Lnμ}
+L3/2Gμ2ε
+(n2L3G2log⁡nμ4ε)1/3]ℓ)
(1): Method-specific transient gain L/(nμ) when L>36nμ, G≤nμε/L. Removes (log⁡n)1/3 from the cubic-root term for growing n; no class-wide acceleration.

Abbr: ℓ=log⁡(1+LR2/ε); L bounds component operator norms, μ is average strong convexity, R is initial distance, and G bounds component gradients at x∗. Costs count component-gradient calls, including full-gradient snapshots; one full gradient costs n calls. Expectation in (1) is over the epoch permutations. AGD denotes accelerated gradient descent.

Ahn, Kwangjun, Chulhee Yun, and Suvrit Sra. 2020. SGD with Shuffling: Optimal Rates Without Component Convexity and Large Epoch Requirements. https://doi.org/10.48550/arXiv.2006.06946.
Allen-Zhu, Zeyuan. 2018. Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization. https://doi.org/10.48550/arXiv.1802.03866.
Bubeck, Sébastien. 2015. “Convex Optimization: Algorithms and Complexity.” Foundations and Trends in Machine Learning 8 (3–4): 231–358. https://doi.org/10.1561/2200000050.

Lean setup