← All setups

Zeroth Order Matrix Generalized Accelerated — Zeroth-Order Matrix-Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Zeroth-Order Matrix-Smooth Convex Minimization · Lean proof

Zeroth-Order Matrix-Smooth Convex Minimization

We consider minimizing a twice differentiable convex function f:Rd→R, where d≥1. The function f is matrix (L0,L1)-smooth, with L0>0 and L1≥0, relative to an unknown positive definite matrix H bounded above by the identity and satisfying tr(H)≤r, where r>0. A given point x0 satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆, with R,Δ>0. The oracle returns the scalar f(x) at x. For ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ over the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean inner product ⟨⋅,⋅⟩ and its induced norm ∥⋅∥. The algorithm receives d,L0,L1,r,R,Δ,ε,δ, and x0; the matrix H and the minimizer are not supplied.

Our assumptions:

Assumption 1 (Convexity and differentiability). The function f is differentiable everywhere, its gradient is differentiable everywhere, and f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈Rd,t∈[0,1].

Assumption 2 (Matrix generalized smoothness). There exists a symmetric matrix H∈Rd×d and a constant μ>0 such that μ∥v∥2≤⟨Hv,v⟩≤∥v∥2for every v∈Rd,tr(H)≤r. Write ∥v∥H=⟨Hv,v⟩ and ∥g∥H−1=⟨H−1g,g⟩. The Hessian, viewed as a linear operator on Rd, satisfies ⟨∇2f(x)v,w⟩≤(L0+L1∥∇f(x)∥H−1)∥v∥H∥w∥H,x,v,w∈Rd.

Assumption 3 (Initial distance and objective gap). There exists a global minimizer x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Function-value queries may be made at any point of Rd. After the allotted calls, the output x¯∈Rd must be measurable and satisfy P(f(x¯)−f(x⋆)>ε)≤δ, where P is the law of the algorithm’s randomness.

Proved result

⌈−log2⁡(δ)⌉+⋅(4⋅⌈510⋅d⋅(r+1)⋅L0⋅R2ε+1300⋅(r+1+L1⋅R⋅(d⋅r+1))⋅log⁡(exp⁡(1)+8⋅Δε)⌉++1)

OracleTemplate.Convergence LongTails.Setups.ZerothOrderMatrixGeneralizedSmooth.spec
  OracleTemplate.MatrixGeneralizedZO.budget

Relevant previous results

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