← All setups

Normalized SAM for Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Differentiable f on a complete real inner-product space, with L-Lipschitz gradient, μ-strong convexity, a minimizer x⋆, and f(x0)−f(x⋆)≤Δ; 0<μ≤L, ρ>0, Δ≥0, ε>0. Exact gradients are available. The setup requires constant-step normalized SAM with radius ρ and last-state output. Result (1) uses η=(2L+2L2ρ/με)−1 and guarantees f(xK)−f(x⋆)≤ε deterministically.

Normalized SAM on strongly convex objectives: NormalizedSamStronglyConvex.
Result Oracle complexity Novelty Limitations
(1) NormalizedSamStronglyConvex (Ours) (review) O(1+[κ+κ3/2ρL/ε]ℓ)
(2) Normalized SAM (Si and Yun 2023, App. B.2, Eq. (6)). Derived bound; E=Rd.

O(1+[κ+κ5/2ρL/ε]ℓ)

Retuned constant step; best-iterate gap.

(1): radius term smaller by κ; total factor Θ(κ) when ρ≥με/L, Δ≥ε. Last instead of best iterate; gradient-based selection already costs only an extra O(log⁡κ) factor. Same order for bounded κ.
(3) GD (Karimi et al. 2016, Thm. 1). E=Rd; problem-class comparison without the SAM restriction. O(1+κℓ) (1): No established improvement. (1) adds κ3/2ρL/εℓ; dominant when ρ≫με/L. Two gradient calls per step instead of one.
(4) AGD (Nesterov 2018, sec. 2.2, Thm. 2.2.1, Lem. 2.2.4). E=Rd; problem-class comparison without the SAM restriction. O(1+κℓ) (1): No established improvement. (1) has κ instead of κ, plus the radius term; at least a κ cost gap when Δ≥ε.

Abbr: κ=L/μ; ℓ=log⁡(1+Δ/ε); Δ is the supplied initial-gap bound; ρ is the perturbation radius; K is the iteration count. Costs count exact gradient calls, including two per SAM step. SAM: sharpness-aware minimization; GD: gradient descent; AGD: accelerated gradient descent.

Karimi, Hamed, Julie Nutini, and Mark Schmidt. 2016. Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition. https://doi.org/10.48550/arXiv.1608.04636.
Nesterov, Yurii. 2018. Lectures on Convex Optimization. 2nd ed. Vol. 137. Springer Optimization and Its Applications. Springer. https://doi.org/10.1007/978-3-319-91578-4.
Si, Dongkuk, and Chulhee Yun. 2023. Practical Sharpness-Aware Minimization Cannot Converge All the Way to Optima. https://doi.org/10.48550/arXiv.2306.09850.

Lean setup