← All setups

Accelerated Coordinate Strongly Convex — Coordinate-Smooth Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Coordinate-Smooth Strongly Convex Minimization · Lean proof

Coordinate-Smooth Strongly Convex Minimization

We consider minimizing a differentiable, μ-strongly convex function f:Rd→R, where d≥1, with coordinate smoothness constants Li≥μ>0 for i=1,…,d. A given starting point x0 satisfies f(x0)−f(x⋆)≤Δ, where Δ≥0 and x⋆ is a global minimizer. At a query (i,x), the oracle returns the scalar ∇if(x), the ith gradient coordinate. For ε>0, the goal is a measurable output x¯∈Rd with integrable objective gap satisfying EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean inner product and norm, and write ei for the ith standard basis vector. The algorithm receives d, (Li)i=1d, μ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Coordinate smoothness). The function f is differentiable everywhere. For every x∈Rd, i∈{1,…,d}, and t∈R, f(x+tei)≤f(x)+t∇if(x)+Li2t2.

Assumption 2 (Strong convexity). For every x,y∈Rd, f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥2.

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

Coordinate queries may be made at any point of Rd. After the allotted oracle 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

2⋅(∑i=0d−1max{1,⌈L(i)μ⌉+})⋅clog2(⌈2⋅Δε⌉+)

OracleTemplate.Convergence LongTails.Setups.CoordinateSmoothStronglyConvex.spec
  OracleTemplate.AcceleratedCoordinate.budget

Relevant previous results

  • Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, Yang Yuan. Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling. 2016 (ICML; full preprint v3, May 2016; first preprint December 2015). Complexity: O((∑i=1dLi/μ)(1+log⁡(Δ/ε))) fixed exact coordinate-gradient oracle calls for E[f(yT)−f(x∗)]≤ε, using NU_ACDM, when 0<ε<Δ; initialization requires no oracle calls, and zero calls suffice when ε≥Δ.