← All setups

Normalized Sam Strongly Convex — Normalized SAM for Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Normalized SAM for Strongly Convex Minimization · Lean proof

Normalized SAM for Strongly Convex Minimization

We consider minimizing a differentiable function f:E→R on a real Hilbert space E using normalized sharpness-aware minimization (SAM). The function is μ-strongly convex with L-Lipschitz gradient, where 0<μ≤L. A given starting point x0∈E satisfies f(x0)−f(x⋆)≤Δ for a global minimizer x⋆ and Δ≥0. The oracle returns ∇f(x) at x. With perturbation radius ρ>0 and tolerance ε>0, the goal is a last iterate x¯ satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The algorithm receives E, L, μ, ρ, x0, Δ, and ε.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Strong convexity). For every x,y∈E, f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥2.

Assumption 3 (Minimizer and initial gap). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,f(x0)−f(x⋆)≤Δ.

Our result is algorithm-specific: we analyze normalized SAM with a fixed step size η>0, chosen from the available inputs, and the prescribed radius ρ. Starting from the given x0, the method uses two successive gradient queries per iteration: gt=∇f(xt),ut={gt/∥gt∥,gt≠0,0,gt=0,yt=xt+ρut,xt+1=xt−η∇f(yt),t=0,1,2,…. Queries may be made at any point of E. The step size remains constant throughout the run. For an oracle-call budget N∈{0,1,2,…}, the output is x¯=x⌊N/2⌋. If N is odd, the final call evaluates the gradient at the current iterate without completing another update. The required accuracy is f(x¯)−f(x⋆)≤εP-a.s.

Proved result

2⋅⌈(2⋅Lμ+2⋅L2⋅ρμ⋅μ⋅ε)⋅log⁡(1+Δε)⌉+

OracleTemplate.Convergence LongTails.Setups.NormalizedSamStronglyConvex.spec
  LongTails.Theorems.NormalizedSamStronglyConvex.budget

Relevant previous results