← All setups

Composite Generalized Smooth Minimization

Descriptions may be stale. Consult the linked Lean sources.

Composite Generalized Smooth Minimization

We minimize F=f+h over a convex set Q in a real Hilbert space E, where f,h:E→R. The function f is convex and (L0,L1)-smooth, with L0>0 and L1≥0; h admits bounded supporting subgradients on Q. A given point x0∈Q has bounded distance and objective gap to a minimizer x⋆, where the gradient of f is bounded. Oracles return exact gradients of f, bounded subgradients of h, and exact projections onto Q. For ε>0, the goal is x¯∈Q with F(x¯)−F(x⋆)≤ε almost surely under P, the joint law of algorithm and oracle randomness.

More precisely, define F(x)=f(x)+h(x) and consider minx∈QF(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, x0, and all parameters L0,L1,M,R,Δ,G,ε, whose ranges are L0,R,Δ,ε>0,L1,M,G≥0. The functions and feasible set are accessed through the three oracles described below.

Our assumptions:

Assumption 1 (Convexity and feasibility). The set Q⊆E is convex and x0∈Q. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Generalized smoothness). The function f is Fréchet differentiable everywhere on E, with continuous gradient. Its (L0,L1)-smoothness means that, for every x,y∈E and B∈R, ∥∇f(x+θ(y−x))∥≤Bfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥≤(L0+L1B)∥x−y∥.

Assumption 3 (Solution and initial bounds). There exists x⋆∈Q such that F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ,∥∇f(x⋆)∥≤G.

Assumption 4 (Oracle access). The gradient oracle returns ∇f(x) at x∈E. At each u∈Q, every reply s∈E of the subgradient oracle satisfies ∥s∥≤M,h(u)+⟨s,v−u⟩≤h(v)for every v∈Q. These conditions hold for every query history and every realization of oracle randomness. Subgradient queries outside Q carry no guarantee. At any w∈E, the projection oracle returns a point p∈Q satisfying ∥w−p∥≤∥w−u∥for every u∈Q.

Gradient, subgradient, and projection calls are counted separately. Oracle randomness may be dependent across calls, and subgradient replies may depend on the query history; the algorithm’s randomness is independent of the oracle’s randomness. After the allotted calls, the output must satisfy x¯∈Q,F(x¯)−F(x⋆)≤εP-a.s.

Results

Minimize F=f+h over convex Q in a real Hilbert space. The convex differentiable f has continuous gradient and satisfies ∥∇f(x)−∇f(y)∥≤[L0+L1supz∈[x,y]∥∇f(z)∥]∥x−y∥ on the whole space. Oracles supply exact gradients, exact projections onto Q, and possibly adversarial vectors s(u) with ∥s(u)∥≤M and h(v)≥h(u)+⟨s(u),v−u⟩ for u,v∈Q. There is x⋆∈arg⁡minQF with x0∈Q, ∥x0−x⋆∥≤R, F(x0)−F(x⋆)≤Δ, and ∥∇f(x⋆)∥≤G. Here L0,R,Δ,ε>0 and L1,M,G≥0. Target: a feasible output x with F(x)−F(x⋆)≤ε almost surely.

Gradient sliding for SlidingGeneralizedSmooth.
Result Oracle complexity Novelty Limitations
(1) GeneralizedGradientSliding (Ours) (⋆⋆⋆) (review)

Total: O(AR2/ε+(1+L1R)ℓ+M2R2/ε2).

Gradients: O(AR2ε+(1+L1R)ℓ).

G is used only in the gradient-count cap.

(2) Gradient sliding (Lan 2016), Cor. 1(a), arXiv v2. Derived bound: finite-dimensional localization to X=Q∩B―(x0,2R).

Total: O(1+Ae3L1RR2ε+M2R2ε2).

Gradients: O(1+Ae3L1RR2ε).

Uses L=Ae3L1R and exact ΠX; at L1=0, use X=Q, L=L0.

(1): gradient saving e3L1R/2 when L1R≫1 and AR2/ε≫(1+L1R)ℓ; total saving additionally requires M2R2/ε2≪AR2/ε. Only ΠQ needed. Matches leading rate for L1R≲1; scope extends global smoothness. (1): extra ℓ term at L1=0; no Bregman geometry or additional simple prox term.
(3) Normalized subgradient (Grimmer 2019), Thm. 2, arXiv v3. Derived bound, E=Rd; best iterate selected using F values.

Total and gradients: O(1+(G+M)2R2/ε2+AR2/ε+L12R2).

Includes ∇f, h′ and ΠQ calls, plus F values for selection; ΠQ is unnecessary when Q=E.

(1): gradients ε−1/2 instead of ε−2 for fixed parameters, G+M>0; no F values. Total gains can occur for constrained G≫M. For Q=E, take G=M: matched total order unless εA≫M2 or εL1≫M; initialization can mask gains. (1): updates additionally need L0,L1,M,Δ,ε; (3) needs only R,T. Initialization term (1+L1R)ℓ exceeds L12R2 when ℓ≫L1R≥1.

Abbr: A=L0+L1G; ℓ=1+log(1+(1+L1R)Δ/(L0R2)); ΠC is exact Euclidean projection onto C; h′ denotes a returned subgradient; T is the iteration horizon in (3). Total cost counts all primitive oracle calls.

Grimmer, Benjamin. 2019. “Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity.” SIAM Journal on Optimization 29 (2): 1350–65. https://doi.org/10.1137/18M117306X.
Lan, Guanghui. 2016. “Gradient Sliding for Composite Optimization.” Mathematical Programming 159 (1–2): 201–35. https://doi.org/10.1007/s10107-015-0955-5.

Lean setup