← All setups

Strongly Convex Composite Finite Sums

Descriptions may be stale. Consult the linked Lean sources.

Strongly Convex Composite Finite Sums

We minimize F(x)=n−1∑i=1nfi(x)+r(x) on a real Hilbert space E, where n≥1, the functions fi:E→R are convex with L-Lipschitz gradients, and r:E→R is μ-strongly convex, with L,μ>0. A given point x0∈E satisfies F(x0)−F(x⋆)≤Δ for a global minimizer x⋆ and Δ≥0. The oracle returns component gradients and exact proximal minimizers of r. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap and EP[F(x¯)−F(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈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; the component functions and regularizer are accessed through the oracle.

Our assumptions:

Assumption 1 (Convex smooth components). Each fi is Fréchet differentiable on E. For every i∈{1,…,n}, x,y∈E, and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y),∥∇fi(x)−∇fi(y)∥≤L∥x−y∥.

Assumption 2 (Strongly convex regularizer and proximal access). For every x,y∈E and t∈[0,1], r((1−t)x+ty)≤(1−t)r(x)+tr(y)−μ2t(1−t)∥x−y∥2. There is a map p:R×E×E→E such that, for every a>0 and z,g∈E, p(a,z,g)∈argminv∈E{∥v−z∥22a+⟨g,v−z⟩+r(v)}.

Assumption 3 (Initial objective gap). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,F(x0)−F(x⋆)≤Δ.

A component-gradient query specifies i∈{1,…,n} and x∈E; the oracle returns ∇fi(x) at x. A proximal query specifies a∈R and z,g∈E; the oracle returns p(a,z,g). Its minimization property is required only for a>0. Each query of either kind counts as one call toward a shared oracle-call budget.

After the allotted 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, minimize F(x)=n−1∑i=1nfi(x)+ψ(x), with n≥1, convex differentiable L-smooth components, and an everywhere finite μ-strongly convex regularizer. Exact component gradients and exact proximal minimizers are available. Assume L,μ,ε>0, Δ≥0, and a minimizer x⋆ with F(x0)−F(x⋆)≤Δ. Target: ∫[F(x^(ω))−F(x⋆)]dP(ω)≤ε, where P is the algorithm’s random-sampling law.

Comparison for CompositeFiniteSumStronglyConvex.
Result Oracle complexity Novelty Limitations
(1) KatyushaCompositeStronglyConvex (Ours) (review) O((n+nL/μ)log⁡(1+Δ/ε))
(2) Katyusha (Allen-Zhu 2018), Theorem 2.1, Option I; E=Rd O((n+nL/μ)log⁡(1+Δ/ε)) (1): Matches known rate on Rd, including μ>L. Formalization with an explicit deterministic call budget; scope extends to real Hilbert spaces. (1): Requires everywhere finite ψ, excluding indicator constraints; worse numerical constants.

Abbr: n: component count; L: component-gradient Lipschitz constant; μ: regularizer strong-convexity modulus; Δ: initial-gap bound; ε: target expected gap. Costs count component-gradient and proximal calls in total, including full-gradient refreshes; log is natural logarithm.

Allen-Zhu, Zeyuan. 2018. “Katyusha: The First Direct Acceleration of Stochastic Gradient Methods.” Journal of Machine Learning Research 18 (221): 1–51. https://jmlr.org/papers/v18/16-410.html.

Lean setup