← All setups

Quantile Remainder Minimax Convex — Convex Minimization with Symmetric Remainders

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Symmetric Remainders · Lean proof

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.

Proved result

(1+⌈4⋅L⋅R2ε+32768⋅(d⋅R⋅(2⋅L⋅R+r)ε+8⋅d⋅M⋅R2ε2)2⌉+)⋅(1+⌈log⁡(1+512⋅(d⋅R⋅(2⋅L⋅R+r)ε+8⋅d⋅M⋅R2ε2))log⁡(2)⌉+)

OracleTemplate.Convergence LongTails.Setups.QuantileSymmetricRemainderConvex.spec
  LongTails.Theorems.QuantileRemainderMinimaxConvex.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.