Stochastic Smoothed AGDA under Two-Sided PL
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Smoothed AGDA under Two-Sided PL
We consider
The optimization problem is
Our assumptions:
Assumption 1 (Partial-gradient smoothness). Each
partial function is Fréchet differentiable everywhere. For all
Assumption 2 (Two-sided Polyak–Łojasiewicz
inequalities). For every
Assumption 3 (Initial potential). The given starting
pair satisfies
Assumption 4 (Stochastic partial-gradient oracle).
There is a probability distribution
Our result is algorithm-specific: we analyze stochastic smoothed
AGDA. Its tuning parameters are
For the output rule, draw
The output must be measurable, its combined primal suboptimality and
inner-maximization error must be integrable, and it must satisfy
Results
Real inner-product spaces
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticTwoSidedPLSmoothedAgda (Ours) (review) | |||
| (2) Derived bound: restarted Smoothed-AGDA (Yang et al. 2022), Thm. 4.1 plus two-sided PL; Euclidean spaces | Conditional on deterministic expected-gap bounds remaining valid at random restart points. |
(1): Matches
deterministic rate; extends |
(1): Extra factor |
| (3) Stoc-AGDA (Yang et al. 2020), Thm. 3.3; Euclidean spaces, attained minima and a saddle point | (1): Noise term smaller
by |
(1): Random second-half
iterate instead of last iterate; needs |
|
| (4) Warm-started Stoc-AGDA (Yang et al. 2020), Thms. 3.1, 3.3 and Remark 3; Euclidean spaces, attained minima and a saddle point | Includes the constant-step warm start; uses the common initial bound
|
(1): Deterministic term
|
(1): Random iterate
instead of last iterate. Noise term loses when |
| (5) FESS-GDA (Shen et al. 2024),
Thm. 3.5, |
Distance target: |
(1): Scope: no saddle-point existence assumption. No established complexity comparison across these accuracy criteria. | (1): Does not provide the distance guarantee of (5). |
Abbr: