← All setups

Katyusha Composite Strongly Convex — Strongly Convex Composite Finite Sums

Descriptions may be stale. Consult the linked Lean sources.

Strongly Convex Composite Finite Sums · Lean proof

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

Proved result

108⋅(n+⌈n⋅Lμ⌉+)⋅clog2(⌈14⋅Δε⌉+)

OracleTemplate.Convergence LongTails.Setups.CompositeFiniteSumStronglyConvex.spec OracleTemplate.Katyusha.budget

Relevant previous results

  • Zeyuan Allen-Zhu. Katyusha: The First Direct Acceleration of Stochastic Gradient Methods. 2017 (STOC; journal version read: 2018; preprint v1: 2016). Complexity: O((n+nL/μ)(1+log⁡(Δ/ε))) exact component-gradient and proximal oracle calls, including full-gradient computations, for E[F(x)−F(x∗)]≤ε in Rd, with fixed cost and 0<ε<Δ; algorithm: Katyusha.
  • Xun Qian, Zheng Qu, Peter Richtárik. L-SVRG and L-Katyusha with Arbitrary Sampling. 2021 (journal version). Complexity: O(n+(n+nL/μ)(1+log⁡(Δ/ε))) expected exact component-gradient and proximal oracle calls, including initialization and full-gradient refreshes, for E[F(x)−F(x∗)]≤ε in Rd, using uniform singleton sampling and refresh probability 1/n, with 0<ε<Δ; algorithm: L-Katyusha.