← All setups

Black Box Diagonal Acceleration — Hidden Diagonal Curvature Minimization

Descriptions may be stale. Consult the linked Lean sources.

Hidden Diagonal Curvature Minimization · Lean proof

Hidden Diagonal Curvature Minimization

We consider minimizing a differentiable function f:Rd→R, where d≥1, with a given starting point x0∈Rd. For hidden weights w1,…,wd>0, its first-order remainder lies between μ∥y−x∥w2/2 and ∥y−x∥w2/2, where ∥v∥w2=∑i=1dwivi2 and 0<μ≤1. A global minimizer x⋆ satisfies f(x0)−f(x⋆)≤Δ, with Δ≥0. The oracle returns (f(x),∇f(x)) at x. For ε>0, the goal is 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 algorithm receives only d and x0; the weights w1,…,wd, relative curvature parameter μ, initial gap bound Δ, and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Diagonal curvature bounds). The function f is differentiable everywhere. 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 (Initial objective gap). There exists x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,f(x0)−f(x⋆)≤Δ.

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

Proved result

d+1+⌈21⋅2μ⋅(log⁡(1+Δμ2⋅ε)+(d+1)⋅(3+−log2⁡(μ))4)⌉+

OracleTemplate.Convergence LongTails.Setups.DiagonalSmoothStronglyConvexBlackBox.spec
  OracleTemplate.BlackBoxDiagonal.budget

Relevant previous results

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