Stochastic Generalized Smooth Composite Minimization
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Generalized Smooth Composite Minimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and generalized smoothness).
The function
Assumption 2 (Bregman geometry and exact proximal
access). There is an open convex set
Assumption 3 (Initial bounds and a minimizer). The
given point satisfies
Assumption 4 (Stochastic derivative oracle). There
is a probability measure
Both types of query count toward the same total oracle-call budget.
The output
Results
Minimize lastIterate satisfies
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticGeneralizedMirrorAccelerated
(Ours) |
|||
| (2) Clip-SSTM (El Bakkali El Kadi and Gorbunov 2026), Thm. 2, Rem. 1; derived sufficient budget | (1): Scope extends to arbitrary norms, composite objectives and boundary minimizers. Matches polynomial rate structure on the Euclidean unconstrained overlap, up to logarithms. | ||
| (3) (LongTails 2026), repository overlap | (1): General norms;
confidence-log exponent |
(1): Finite dimension;
updates need |
|
| (4) Clipped accelerated SMD (Nguyen et al. 2023), Thm. D.1(1) | (1): Scope extends to
|
(1): Extra logarithmic
overhead and initial-gap transient; needs |
|
| (5) Clipped accelerated SMD (Nguyen et al. 2023), Thm. D.1(2) | (1): Scope extends to generalized smoothness, composite objectives and arbitrary constrained minimizers. | (1): Requires a preset
horizon; (5) permits unknown |
Abbr: