← All setups

Coordinate-Smooth Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

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

Results

Differentiable f:Rd→R, d≥1, is μ-strongly convex in the Euclidean norm and satisfies f(x+tei)≤f(x)+t∂if(x)+Lit2/2 for every x,i,t. A minimizer x⋆ satisfies f(x0)−f(x⋆)≤Δ, with Li≥μ>0, Δ≥0, and ε>0. Queries return exact ∂if(x); Li,μ,Δ,ε,x0 are supplied. Target: E[f(yK)−f(x⋆)]≤ε.

Exact coordinate-oracle complexity for CoordinateSmoothStronglyConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedCoordinateStronglyConvex (Ours) (review) O(∑i=1dLi/μ[1+log⁡(1+Δ/ε)])
(2) NU_ACDM (Allen-Zhu et al. 2016, arXiv v3, Theorem 5.1, β=0) O(∑i=1dLi/μ[1+log⁡(1+Δ/ε)]) (1): Matches known rate; Lean formalization. The coordinate upper model gives no scope extension; tuning knowledge and expected last-iterate guarantee are unchanged. (1): Worse constants from integer-rounded sampling weights and a smaller coupling parameter.

Abbr: Costs count individual partial-derivative queries. ei: coordinate unit vector; Li: coordinate smoothness constants; μ: strong-convexity modulus; Δ: initial-gap bound; yK: returned iterate; E: expectation over coordinate sampling; log: natural logarithm.

Allen-Zhu, Zeyuan, Zheng Qu, Peter Richtárik, and Yang Yuan. 2016. “Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling.” In Proceedings of the 33rd International Conference on Machine Learning, edited by Maria Florina Balcan and Kilian Q. Weinberger, vol. 48. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v48/allen-zhuc16.html.

Lean setup