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
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
Results
Differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) NormalizedSamStronglyConvex (Ours) (review) | |||
| (2) Normalized SAM (Si and Yun 2023,
App. B.2, Eq. (6)). Derived bound; |
Retuned constant step; best-iterate gap. |
(1): radius term smaller
by |
|
| (3) GD (Karimi et al. 2016,
Thm. 1). |
(1): No established improvement. | (1) adds |
|
| (4) AGD (Nesterov 2018, sec. 2.2,
Thm. 2.2.1, Lem. 2.2.4). |
(1): No established improvement. | (1) has |
Abbr: