← All setups

Power Geometry with Relative Errors

Descriptions may be stale. Consult the linked Lean sources.

Power Geometry with Relative Errors

We consider minimizing a differentiable convex function f:E→R on a finite-dimensional real normed space E. Its derivative Df is L-Lipschitz, with L>0. At a given point x0∈E, the squared norm is differentiable and satisfies a power-type curvature bound with exponent p>2 and constant c>0. A global minimizer x⋆ satisfies ∥x0−x⋆∥≤R, where R≥0. The oracle returns a dual vector g with ∥g−Df(x)∥op≤α∥Df(x)∥op at x, where 0≤α≤1/4. For ε>0, the goal is f(x¯)−f(x⋆)≤ε almost surely for an output x¯∈E under the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). Write E∗ for the continuous dual of E and ∥⋅∥op for its induced operator norm. Define ψ(x)=12∥x−x0∥2. The algorithm receives E, L, α, p, c, and x0; the radius R and tolerance ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Power geometry). The function ψ is Fréchet differentiable everywhere, and for every x,y∈E, c∥y−x∥p(∥y−x0∥+∥x−x0∥)p−2≤ψ(y)−ψ(x)−Dψ(x)[y−x]. The fraction is defined to be zero when x=y=x0.

Assumption 2 (Convexity and smoothness). The function f is Fréchet differentiable everywhere. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥Df(x)−Df(y)∥op≤L∥x−y∥.

Assumption 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x⋆−x0∥≤R.

Assumption 4 (Relative-error oracle). Queries may be made at any point x∈E. Every oracle reply g∈E∗ satisfies ∥g−Df(x)∥op≤α∥Df(x)∥op. This bound holds for every query history and every realization of the oracle randomness. Replies may depend on the history, and oracle randomness across calls may be dependent. The algorithm’s randomness is independent of the oracle randomness.

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

Results

In a finite-dimensional real normed space, f is differentiable and convex, ∥Df(x)−Df(y)∥∗≤L∥x−y∥, and a global minimizer satisfies ∥x∗−x0∥≤R. Here L,c>0, p>2, R≥0, and 0≤α≤1/4. The differentiable function ψ(x)=∥x−x0∥2/2 satisfies Dψ(y,x)≥c∥y−x∥p/(∥y−x0∥+∥x−x0∥)p−2 for all x,y (zero at x=y=x0). Every oracle reply obeys ∥g−Df(x)∥∗≤α∥Df(x)∥∗, allowing biased, call-dependent errors. Target: f(xK)−f(x∗)≤ε, ε>0, almost surely under every execution law; the constructed squared-norm dual-averaging output satisfies it for every seed.

Power-geometry acceleration with relative gradient error. PowerGeometryRelativeErrorConvex.
Result Oracle complexity Novelty Limitations
(1) PowerGeometryRelativeErrorAcceleration (Ours) (⋆⋆⋆) (review) O(1+(CT)p/(p+2)+α2T) gradient calls.
(2) (d’Aspremont et al. 2016), Cor. 4.10, §5.1.2 Op(1+Tp/(p+2)) exact-gradient calls. Special case: ℓpd, α=0, optimization on Bp(x0,R) containing a global minimizer. (1): extends to biased relative error; matches the exact-gradient rate for fixed p. Updates need neither R, ε, nor horizon; the stopping budget still does. (1) has larger p-dependent constants; on ℓpd, C=p(p−1)27(p−2)/2 (1536 at p=4).
(3) Derived bound: (Vasin and Gasnikov 2026), Thm. 7.2

O(1+(dsT+αd3sT)

⋅[1+log⁡(d2sT)]) gradient calls. On ℓpd via Euclidean conversion, with d2sT>1 and dsα≤1/3.

(1): dimension-free; for fixed p and d≳Tp/(p+2), removes dimension factors and logarithm, with α2T instead of αd3sT. At p=4, d=T2, α=T−1/6≤1/4: O(1+T2/3); (3) is inapplicable. (1) loses at α=0, fixed p,d, T→∞: Tp/(p+2) versus T(1+log⁡T). At d=1, excludes 1/4<α≤1/3.
(4) SODA (Pethick 2026), Cor. 3.2 Op,τq(1+Tp/(p+2)+(σqR/ε)p) stochastic-gradient calls, one per step. On ℓpd: unbiased gradients with q-moment gradient variation (Assumptions 3–4); expected objective gap ≤ε. (1): matches the rate on the exact-gradient overlap; removes R from updates. Covers arbitrary relative bias with pathwise accuracy; no stochastic-rate comparison outside that overlap. (1) does not cover additive heavy-tailed noise allowed by (4); the noisy oracle models are incomparable.

Abbr: T=LR2/ε; C=max{1,32(p−2)/2/c}; Dψ(y,x)=ψ(y)−ψ(x)−Dψ(x)[y−x]; ∥⋅∥∗ is the dual norm. For ℓpd, d is dimension, s=1/2−1/p, and c=22−p/[p(p−1)] is admissible. Op permits constants depending on fixed p. In (4), q=p/(p−1); σq and τq≥1 are the additive scale and multiplicative factor in the Lq gradient-variation bound; Op,τq permits dependence on these subscripts.

d’Aspremont, Alexandre, Cristóbal Guzmán, and Martin Jaggi. 2016. Optimal Affine Invariant Smooth Minimization Algorithms. https://doi.org/10.48550/arXiv.1301.0465.
Pethick, Thomas. 2026. When to Use What Schatten-p Norm in Deep Learning? https://doi.org/10.48550/arXiv.2606.15268.
Vasin, Artem, and Alexander Gasnikov. 2026. Lower and Upper Bounds of the Convergence Rate of Gradient Methods with Composite Noise in Gradient. https://doi.org/10.48550/arXiv.2603.12376.

Lean setup