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
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Strong convexity). For every
Assumption 3 (Minimizer and initial gap). There
exists
Our result is algorithm-specific: we analyze normalized SAM with a
fixed step size
Proved result
OracleTemplate.Convergence LongTails.Setups.NormalizedSamStronglyConvex.spec
LongTails.Theorems.NormalizedSamStronglyConvex.budgetRelevant previous results
- Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear Convergence of Gradient
and Proximal-Gradient Methods Under the Polyak–Łojasiewicz
Condition. 2016, preprint v1. Complexity:
exact-gradient oracle calls using gradient descent for deterministic , when ; zero calls suffice when .