Linearly Decaying SGD for Sampled Losses
Descriptions may be stale. Consult the linked Lean sources.
Linearly Decaying SGD for Sampled Losses
We minimize
The optimization problem is
Our assumptions:
Assumption 1 (Sample convexity and smoothness). For
every
Assumption 2 (Initial distance and noise at a
minimizer). There exists
Queries may be made at any point of
Our result is algorithm-specific: we analyze linearly decaying SGD.
The method chooses a deterministic scale
The output must be measurable under
Results
On a separable real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) LinearDecaySgdLastIterate (Ours) (review) | |||
| (2) SHB-IMA (Sebbouh et al. 2021, Thm. G.1, Cor. G.2) | Finite-dimensional restriction; tuned, known horizon. |
(1): Matches known rate
and tuning information, using plain SGD instead of momentum; extends
|
|
| (3) Constant-step SGD (Attia et al. 2025, Thm. 2) | Finite-dimensional restriction; tuned step. |
(1): Removes |
|
| (4) Constant-step SGD, derived bound (Garrigos et al. 2025, Thm. 3.1) | Hilbert space; tuned using |
(1): Removes |
|
| (5) Constant-step SGD (Garrigos et al. 2025, Cor. 3.4) | Step |
(1): At |
(1) needs |
| (6) Averaged SGD (Attia et al. 2025, App. B, Thm. 8) | Finite-dimensional restriction; tuned step. |
(1): Matches known rate with the last iterate instead of an average; extends to Hilbert space. | |
| (7) Linear-decay SGD (Liu and Zhou 2026, Thm. 3.4) | Unconstrained smooth specialization in |
(1): Replaces |
(1) requires per-sample convexity and smoothness; does not cover constraints or composite terms. Classes are incomparable. |
Abbr: SGD: stochastic gradient descent; SHB-IMA:
stochastic heavy ball in iterate-moving-average form.