← All setups

Online Metric Accelerated — Diagonal Smooth Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Diagonal Smooth Strongly Convex Minimization · Lean proof

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.

Proved result

2⋅(d+1+⌈log2⁡(Δε)⌉+⋅⌈24⋅1μ+log2⁡(d)+2⌉++(d⋅⌈−log2⁡(μ)⌉++1)⋅⌈110⋅d2⋅(1+log⁡(2⋅d))2⋅1μ⌉+)

OracleTemplate.Convergence LongTails.Setups.DiagonalSmoothStronglyConvex.spec
  OracleTemplate.OnlineMetricAccelerated.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.