← All setups

Random Reshuffling Quadratic — Quadratic Finite-Sum Minimization

Descriptions may be stale. Consult the linked Lean sources.

Quadratic Finite-Sum Minimization · Lean proof

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⋆)]≤ε.

Proved result

n⋅⌈(64⋅Lμ+128⋅L⋅L⋅Gn⋅μ2⋅ε+8⋅(L3⋅G2n⋅μ4⋅ε)13)⋅log⁡(1+L⋅R2ε)⌉+

OracleTemplate.Convergence LongTails.Setups.QuadraticFiniteSum.spec OracleTemplate.QuadraticFiniteSum.budget

Relevant previous results