← All setups

Stochastic Generalized Smooth Composite Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Generalized Smooth Composite Minimization

We consider minimizing F=f+ψ over a convex set Q in a finite-dimensional real normed space E. The function f:E→R is convex and (L0,L1)-smooth, with L0>0 and L1≥0, and ψ:E→R is convex on Q. A given starting point has bounded objective gap and Bregman divergence to a minimizer x⋆∈Q. The oracle returns unbiased stochastic derivatives with independent samples and bounded αth error moments, 1<α≤2, or exact Bregman proximal points. For ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying x¯∈Q and F(x¯)−F(x⋆)≤ε with probability at least 1−δ.

The optimization problem is minx∈QF(x),F(x)=f(x)+ψ(x). Write E∗ for the continuous dual of E, equipped with its induced operator norm ∥⋅∥op. Let Ω be the measurable sample space. The algorithm receives E, Ω, the starting point x0, and the parameters L0>0,L1≥0,R>0,Δ>0,G≥0,σ≥0,1<α≤2,ε>0,0<δ<1. The instance supplies the objective and proximal geometry through the oracle described below.

Our assumptions:

Assumption 1 (Convexity and generalized smoothness). The function f is convex and Fréchet differentiable on E, with continuous derivative df:E→E∗. For every x,y∈E and M∈R, ∥df(x+θ(y−x))∥op≤Mfor all θ∈[0,1]⟹∥df(x)−df(y)∥op≤(L0+L1M)∥x−y∥. The set Q⊆E is convex and Borel measurable. The function ψ is measurable on E and convex on Q.

Assumption 2 (Bregman geometry and exact proximal access). There is an open convex set U⊆E and a function h:E→R that is Fréchet differentiable on U. For z∈U and u∈E, define Dh(u,z)=h(u)−h(z)−dh(z)[u−z]. The divergence satisfies Dh(u,z)≥12∥u−z∥2,z∈Q∩U,u∈Q. An exact proximal map T:R×E×E∗→E is supplied. For every a>0, z∈Q∩U, and v∈E∗, T(a,z,v)∈Q∩U,T(a,z,v)∈argminu∈Q{a(v[u−z]+ψ(u))+Dh(u,z)}. The map on R×E×E∗ given by (a,z,v)⟼{T(a,z,v),a>0,x0,a≤0 is measurable.

Assumption 3 (Initial bounds and a minimizer). The given point satisfies x0∈Q∩U. There exists x⋆∈Q such that F(x⋆)≤F(x)for every x∈Q,Dh(x⋆,x0)≤R2/2,F(x0)−F(x⋆)≤Δ,∥df(x⋆)∥op≤G.

Assumption 4 (Stochastic derivative oracle). There is a probability measure μ on Ω and a jointly measurable map g:E×Ω→E∗. For every x∈Q, the map g(x,⋅) is Bochner integrable, the random variable ∥g(x,ξ)−df(x)∥opα is integrable for ξ∼μ, and Eξ∼μ[g(x,ξ)]=df(x),Eξ∼μ[∥g(x,ξ)−df(x)∥opα]≤σα. The sample sequence (ξk)k≥0 has a joint probability law ν on ΩN under which its coordinates are measurable, mutually independent, and each distributed according to μ. This sequence is independent of the algorithm’s randomness. At call k, a derivative query at x∈E returns g(x,ξk); a proximal query (a,z,v)∈R×E×E∗ returns T(a,z,v).

Both types of query count toward the same total oracle-call budget. The output x¯∈E must be measurable and satisfy P(x¯∉Q or F(x¯)−F(x⋆)>ε)≤δ, where P is the joint law of the algorithm’s randomness and the sample sequence.

Results

Minimize F=f+ψ over convex measurable Q in a finite-dimensional normed space. The globally convex differentiable f has continuous derivative and satisfies ∥df(x)−df(y)∥∗≤(L0+L1supz∈[x,y]∥df(z)∥∗)∥x−y∥ on the whole space. The measurable ψ is convex on Q. A differentiable mirror map on open convex U satisfies Dh(u,z)≥∥u−z∥2/2 for u∈Q, z∈Q∩U; measurable exact composite Bregman-prox updates stay in Q∩U, and x0∈Q∩U. A minimizer x∗∈Q satisfies 2Dh(x∗,x0)≤R2, F(x0)−F(x∗)≤Δ, ∥df(x∗)∥∗≤G. Jointly measurable stochastic gradients use IID samples with law μ under probability P, with integrable gradients and central moments, ∫g(x,ω)dμ=df(x) and ∫∥g(x,ω)−df(x)∥∗αdμ≤σα on Q. Here L0,R,Δ,ε>0, L1,G,σ≥0, 1<α≤2, 0<δ<1. All displayed parameters are supplied to (1). Target: the constructed algorithm’s lastIterate satisfies P{x∉Q or F(x)−F(x∗)>ε}≤δ.

Sufficient oracle budgets for StochasticGeneralizedMirror.
Result Oracle complexity Novelty Limitations
(1) StochasticGeneralizedMirrorAccelerated (Ours) (⋆⋆⋆) (review) O(S[1+log⁡(S/δ)]2) total stochastic-gradient and exact Bregman-prox calls, including pilot batches.
(2) Clip-SSTM (El Bakkali El Kadi and Gorbunov 2026), Thm. 2, Rem. 1; derived sufficient budget O(SE[1+log⁡(SE/δ)]2) gradient calls. Euclidean, Q=E, ψ=0, G=0, L1>0. (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 O(2128/(α−1)SCCC2+1/(α−1)) total gradient and Euclidean-prox calls; Hilbert geometry. (1): General norms; confidence-log exponent 2 instead of 2+1/(α−1); removes exponential prefactor from nonstatistical terms. Entropy-simplex example (σ=0, ε=d−1, R2=2log⁡d, G=2log⁡d, fixed δ): O(dlog7/2⁡d) versus Euclidean upper-bound curvature term Ω(dlog⁡d). (1): Finite dimension; updates need G, previously budget-only. Transient logarithms incomparable; L1σR2/ε was already dominated.
(4) Clipped accelerated SMD (Nguyen et al. 2023), Thm. D.1(1) O(γ[1+L0R2/ε+6241/(α−1)B]) gradient/prox calls. Known horizon; L1=0, ψ=0, df(x∗)=0. (1): Scope extends to L1>0, composite objectives and constrained minimizers with df(x∗)≠0. (1): Extra logarithmic overhead and initial-gap transient; needs Δ,G in addition.
(5) Clipped accelerated SMD (Nguyen et al. 2023), Thm. D.1(2) O(N) gradient/prox calls; sufficient horizon
N≥γ(1+L0R2/ε),N(1+log⁡N)2/(α−1)≥12481/(α−1)γB.
L1=0, ψ=0, df(x∗)=0.
(1): Scope extends to generalized smoothness, composite objectives and arbitrary constrained minimizers. (1): Requires a preset horizon; (5) permits unknown T. Needs Δ,G in addition.

Abbr: Dh(u,z)=h(u)−h(z)−dh(z)[u−z]; ∥⋅∥∗ is the dual norm; B=(σR/ε)α/(α−1); γ=1+log⁡(1/δ); N≥1 is a sufficient horizon. S=1+(1+L1R)[1+log⁡(1+Δ/ε)]+(L0+L1G)R2/ε+2561/(α−1)B. SE=1+(1+L1R)[1+log⁡(1+L1R)+log⁡(1+Δ/(L0R2))]+L0R2/ε+5121/(α−1)B. SC=1+(L0+L1σ+L1G)R2/ε+(1+L1R)log⁡(2+(1+L1R)Δ/(L0R2))+B; CC=log⁡((8+L1R+(L0+L1σ+L1G)R2/ε+Δ/(L0R2)+σR/ε)/δ).

El Bakkali El Kadi, Taha, and Eduard Gorbunov. 2026. Acceleration Survives Heavy Tails and Generalized Smoothness. https://doi.org/10.48550/arXiv.2610.23301.
LongTails: StochasticCompositeGeneralizedAccelerated. 2026. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/StochasticCompositeGeneralizedAccelerated.lean.
Nguyen, Ta Duy, Thien Hang Nguyen, Alina Ene, and Huy Le Nguyen. 2023. “Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise.” Advances in Neural Information Processing Systems 36: 24191–222. https://doi.org/10.52202/075280-1052.

Lean setup