← All setups

Convex Minimization with Symmetric Remainders

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Symmetric Remainders

We consider minimizing a differentiable convex function f:Rd→R, where d≥1, with an L-Lipschitz gradient, L>0. A given point x0 lies within distance R>0 of a global minimizer x⋆. The oracle returns g(x,ξ) at x, using independent samples ξ from a fixed probability distribution. Each coordinate error has a distribution decomposable into a symmetric measure and a centered remainder with bounded second moment, together with a uniform tail-quantile bound; the symmetric component may be heavy-tailed. For ε>0, the goal is a measurable output x¯ with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over oracle and algorithm randomness.

The optimization problem is minx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. Fix a measurable sample space Ω and noise parameters r>0 and M≥0. The algorithm receives d, Ω, x0∈Rd, L, R, r, M, and ε.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is differentiable everywhere, and for every x,y∈Rd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

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

Assumption 3 (Sampling and oracle). There is a probability measure ν on Ω and a jointly measurable map g:Rd×Ω→Rd. At call k≥0, a query x∈Rd receives g(x,ξk). Under a joint probability law Q on ΩN, the coordinate samples ξk are measurable, mutually independent, and each has distribution ν. Algorithm randomness is independent of this sample sequence.

Assumption 4 (Symmetric remainder and quantile bound). For every x∈Rd and i∈{1,…,d}, let μx,i be the distribution of the scalar error gi(x,ξ)−[∇f(x)]i for ξ∼ν. There exist finite nonnegative Borel measures Sx,i and Ax,i on R such that μx,i=Sx,i+Ax,i,Sx,i(B)=Sx,i(−B)for every Borel B⊆R, where −B={−z:z∈B}. The functions z↦z and z↦z2 are integrable with respect to Ax,i, and ∫RzdAx,i(z)=0,∫Rz2dAx,i(z)≤M,μx,i({z∈R:|z|>r})≤164.

After the allotted oracle calls, the output x¯∈Rd must be measurable, its objective gap must be integrable, and it must satisfy EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the algorithm randomness and the oracle sample sequence.

Results

Convex differentiable f:Rd→R has L-Lipschitz gradient and a minimizer x⋆ with ∥x0−x⋆∥≤R. The jointly measurable oracle uses IID samples. For every point and coordinate, the noise law μ=S+A has nonnegative measures S,A, reflection-symmetric S, ∫zdA=0, ∫z2dA≤M, and μ{|z|>r}≤1/64; the stated remainder integrals are integrable. Here d≥1, L,R,r,ε>0, M≥0. Target: measurable output x^ with integrable gap and ∫[f(x^)−f(x⋆)]dP≤ε under the execution law P.

Quantile-controlled symmetric-remainder noise: QuantileSymmetricRemainderConvex.
Result Oracle complexity Novelty Limitations
(1) QuantileRemainderMinimaxConvex (Ours) (⋆⋆) (review) O([1+LR2/ε+Q2]⋅[1+log⁡(1+Q)])
(2) Clipped-SSTM/SMoM (Puchkin et al. 2024), Cor. 5.8, Eq. (117). Derived bound; density/convolution-tail subclass, β≥1; (p(u)−p(−u))/2 centered, absolute second moment ≤M.

OB,β,θ([1+M+dMRε]⋅[1+LR2ε+dR2ε2]ℓ2)

Fixed B,β,θ>0; probability 1−δ.

(1) Scope: quantile-only noise admits atoms and symmetric backgrounds without any positive moment. Removes (2)’s density and convolution bound s∗k(u)≤Bk/(k(β+1)/β+|u|1+β). (1): expectation, not (2)’s high probability. On the overlap, fixed positive parameters and ε→0: ε−4 versus ε−3, up to logarithms; remainder-dominated ratio dMR/ε.
(3) Clipped-SSTM/median (Puchkin et al. 2024), Prop. 4.1 + Thm. 5.7. Derived bound; M=0, symmetric densities p(u)≤B/(1∨|u|1+β), β>0.

O(m[1+LR2ε+dmVR2ε2]ℓ3)

Probability 1−δ.

(1) Scope: at M=0, replaces (3)’s polynomial density tails with a quantile. Matches the ε−2 power, up to logarithms, for fixed remaining parameters. (1): expectation instead of (3)’s high probability; noise-scale term (LR+r)2 includes L2R2.

Abbr: Costs count raw stochastic-gradient calls, including batches. Q=dR(LR+r)/ε+dMR2/ε2; m=1+⌈3/β⌉, V=max{1,(4B/β)2/β}. δ∈(0,1) is failure probability; ℓj=1+log⁡((2+LR2/ε+vjR2/ε2)/δ), v2=d, v3=dmV. B,β are uniform coordinate density-tail constants; θ is Gaussian smoothing scale; the subscript on OB,β,θ permits dependence on these fixed constants. s(u)=(p(u)+p(−u))/2; ∗ denotes convolution.

Puchkin, Nikita, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. 2024. “Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems.” In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, edited by Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, vol. 238. Proceedings of Machine Learning Research. PMLR. https://doi.org/10.48550/arXiv.2311.04161.

Lean setup