← All setups

Generalized Smooth Convex Mirror Geometry

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Convex Mirror Geometry

We minimize a differentiable convex function f:E→R on a finite-dimensional real normed space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0. A differentiable mirror function ψ:E→R induces a Bregman divergence Bψ dominating half the squared norm. A given point x0∈E satisfies Bψ(x⋆,x0)≤D and f(x0)−f(x⋆)≤Δ for a minimizer x⋆, where D,Δ>0. The oracle returns exact derivatives and Bregman proximal minimizers. For ε>0, the goal is f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). Write E∗ for the continuous dual of E. Derivatives ∇f(x) and ∇ψ(x) belong to E∗, and their norms are the induced operator norms ∥⋅∥op. Define Bψ(u,z)=ψ(u)−ψ(z)−∇ψ(z)[u−z]. The algorithm receives E, L0, L1, D, Δ, and x0; the tolerance ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Convexity and generalized smoothness). The function f is everywhere Fréchet differentiable, its derivative is continuous, and f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,t∈[0,1]. Its (L0,L1)-smoothness means that, for every x,y∈E and M∈R, ∥∇f(x+θ(y−x))∥op≤Mfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥op≤(L0+L1M)∥x−y∥.

Assumption 2 (Mirror geometry and proximal access). The function ψ is everywhere Fréchet differentiable and satisfies Bψ(y,x)≥12∥y−x∥2,x,y∈E. For every z∈E and v∈E∗, a selected proximal minimizer exists: proxψ(z,v)∈argminu∈E⁡{v[u]+Bψ(u,z)}.

Assumption 3 (Initial bounds). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,Bψ(x⋆,x0)≤D,f(x0)−f(x⋆)≤Δ.

The oracle returns ∇f(x) at x. It also returns proxψ(z,v) on a query (z,v)∈E×E∗. Both types of queries are exact, may be made anywhere in their stated domains, and count toward a single total oracle-call budget.

After the allotted calls, the output x¯∈E must satisfy f(x¯)−f(x⋆)≤εP-a.s., where the global minimizer x⋆ is fixed independently of the algorithm’s randomness.

Results

Convex differentiable f:E→R on a finite-dimensional real normed space, with continuous gradient satisfying ∥g(x)−g(y)∥∗≤(L0+L1M)∥x−y∥ whenever ∥g∥∗≤M on [x,y]. A differentiable mirror satisfies Bψ(u,z)≥∥u−z∥2/2; exact gradient and Bregman-prox oracles are supplied. A minimizer x∗ satisfies Bψ(x∗,x0)≤D and f(x0)−f(x∗)≤Δ, with L0,D,Δ,ε>0, L1≥0. Target: f(xK)−f(x∗)≤ε almost surely.

Comparison for MirrorGeneralizedSmooth.
Result Oracle complexity Novelty Limitations
(1) DynamicMirrorGeneralizedAcceleration (Ours) (⋆⋆⋆) (review) O(1+L0D/ε+(1+L1D)log⁡(2+Δ/ε)) gradient + prox calls; two gradients and one prox per iteration.
(2) Accelerated mirror descent (Yu et al. 2026), Thm. 3.7 O(1+HDεmax{1,DH/G}) gradient + prox calls, specialized to the affine link on E. (1): L0=D=Δ=1, L1=q≥1: O(q3/2ε−1/2) becomes O(ε−1/2+qlog⁡(2+1/ε)). At L1=0, removes certificate factor (L0D/Δ)1/4 when L0D>Δ. (1): affine links and unconstrained domains only; three calls per iteration instead of two.
(3) AGD (Tyurin 2026), Thm. 4.3; Euclidean quadratic mirror O(1+L0D/ε+L1Dlog+⁡min{L12Δ/L0,Δ/ε}+log+⁡(Δ/(L0D))) gradient calls; Γ0≍Δ/R2 tuning. (1): scope extends Euclidean geometry to arbitrary norms with strongly convex mirrors; matches the accelerated accuracy exponent. (1): lacks logarithm saturation below ε=L0/L12. Only affine links.
(4) (Rudomanov et al. 2026), Thm. 3.7; Euclidean quadratic mirror O(1+L0D/ε+(1+L1D)log⁡(2+L1D)) gradient calls. (1): scope extends Euclidean geometry to arbitrary norms with strongly convex mirrors. (1): needs Δ; worse transient when log⁡(Δ/ε)≫log⁡(2+L1D).

Abbr: Bψ(u,z)=ψ(u)−ψ(z)−⟨∇ψ(z),u−z⟩; H=L0+L12Δ, G=L1Δ+L0Δ; log+⁡t=max{0,log⁡t}, with log+⁡0=0. Euclidean comparisons use R2=2D. Γ0 is the initial gap-to-squared-distance tuning parameter.

Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026. Descending Everest, Part i: Oracle Complexity of Convex Optimization Under (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2610.21461.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2508.06884.
Yu, Dingzhi, Wei Jiang, Hongyi Tao, Yuanyu Wan, and Lijun Zhang. 2026. Mirror Descent Under Generalized Smoothness. https://doi.org/10.48550/arXiv.2502.00753.

Lean setup