← All setups

Diagonal Smooth Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Diagonal Smooth Strongly Convex Minimization

We consider minimizing a differentiable function f:Rd→R, where d≥1. For hidden weights wi>0, define ∥v∥w2=∑i=1dwivi2. In this norm, f is 1-smooth and μ-strongly convex, with hidden μ∈(0,1]. Its known minimum value f⋆=f(x⋆) is attained at a global minimizer x⋆. A given starting point x0 satisfies f(x0)−f⋆≤Δ, where Δ≥0. The oracle returns (f(x),∇f(x)) at x. For ε>0, the goal is an output x¯ satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). The inner product ⟨⋅,⋅⟩ and gradient are Euclidean; the weighted norm specifies the quadratic bounds below. The algorithm receives only d, x0, and f⋆; the weights w=(wi)i=1d, strong convexity parameter μ, initial gap bound Δ, and tolerance ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Diagonal smoothness and strong convexity). The function f is differentiable everywhere on Rd. For every x,y∈Rd, f(y)≤f(x)+⟨∇f(x),y−x⟩+12∥y−x∥w2,f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥w2.

Assumption 2 (Attained minimum and initial gap). There exists x⋆∈Rd such that f(x⋆)=f⋆≤f(x)for every x∈Rd,f(x0)−f⋆≤Δ.

Queries may be made at any point of Rd, with each query returning both the exact function value and the exact gradient. After the allotted oracle calls, the output x¯∈Rd must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

Differentiable f:Rd→R, d≥1, satisfies μ2∥y−x∥w2≤f(y)−f(x)−⟨∇f(x),y−x⟩≤12∥y−x∥w2 for all x,y, with unknown wi>0 and 0<μ≤1. A minimizer x⋆ exists, its value f⋆ is known, and f(x0)−f⋆≤Δ, Δ≥0. The target is f(x^)−f(x⋆)≤ε, ε>0, deterministically, using exact (f,∇f) calls. In (1), updates use only d,x0,f⋆; the stopping budget uses μ,Δ,ε.

Comparison for DiagonalSmoothStronglyConvex.
Result Oracle complexity Novelty Limitations
(1) OnlineMetricAccelerated (Ours) (⋆⋆⋆) (review) O((κ⋆+log⁡(2d))ℓ+H)
(2) Derived bound: secant diagonal + restarted AGD (Roulet and d’Aspremont 2019, Prop. 4.1) O(d+κ⋆ℓ). Secants si=∂if(x0+ei)−∂if(x0); μwi≤si≤wi. (1): κ⋆ instead of κ⋆ in the accuracy term; total gain when κ⋆≫log⁡(2d) and ℓ≫H/κ⋆. (1): larger warm-up at moderate accuracy or large d; larger leading constants.
(3) Ellipsoid multidimensional backtracking (Kunstner et al. 2023, Thm. 5.3, Prop. 3.2) O(dκ⋆ℓ+d[1+log+⁡(L/α0)]), including rejected trials. Initial ellipsoid must contain an optimal diagonal preconditioner. (1): leading coefficient κ⋆+log⁡(2d) instead of dκ⋆; asymptotic gain approaches dκ⋆ when κ⋆≫log⁡(2d). Removes initial-guess logarithm. (1) needs f⋆; adds H warm-up. Total saving requires sufficiently small ε.
(4) Lookahead OSGM-R (Gao et al. 2025, Eq. (5), Thms. 6.1–6.2) O(min{κEℓ,
κF[ℓ+L2∥L−1I−PF∥F2]}). P1=L−1I; two gradient evaluations per iteration, counted as paired calls.
(1): κ⋆+log⁡(2d) instead of κF in the accuracy term; gain for κF≍κ⋆≫log2⁡(2d) and sufficiently small ε. Warm-up independent of weight spread. (1) can lose when full-matrix scaling gives κF≪κ⋆, or when the κEℓ branch is small.
(5) Euclidean AGD + known-value restarts (Roulet and d’Aspremont 2019, Prop. 4.1) O(κEℓ). κE≤κ⋆maxiwi/miniwi; equality is possible. (1): gain for κE≫κ⋆+log2⁡(2d) and ℓ≫H/κE, including sufficiently anisotropic worst-case instances. (1) pays H; can lose when Euclidean conditioning is already favorable.

Abbr: ∥v∥w2=∑iwivi2; κ⋆=1/μ; ℓ=1+log+⁡(Δ/ε); log+⁡t=max{0,log⁡t} for t>0, log+⁡0=0; H=d2log2⁡(2d)κ⋆(1+dlog⁡κ⋆). L,m are Euclidean smoothness and strong-convexity constants, κE=L/m; κF and PF are the optimal full-matrix condition number and corresponding scaling in (4). ∥⋅∥F is the Frobenius norm; I is the identity; ei is the ith coordinate vector; α0 is the initial ellipsoid parameter in (3); AGD denotes accelerated gradient descent.

Gao, Wenzhi, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. 2025. Gradient Methods with Online Scaling Part I. Theoretical Foundations. https://doi.org/10.48550/arXiv.2505.23081.
Kunstner, Frederik, Victor S. Portella, Mark Schmidt, and Nick Harvey. 2023. Searching for Optimal Per-Coordinate Step-Sizes with Multidimensional Backtracking. https://doi.org/10.48550/arXiv.2306.02527.
Roulet, Vincent, and Alexandre d’Aspremont. 2019. Sharpness, Restart and Acceleration. https://doi.org/10.48550/arXiv.1702.03828.

Lean setup