Distance Growing Subgradient Upper Bound — Convex Minimization with Distance-Dependent Subgradient Moments
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Distance-Dependent Subgradient Moments · Lean proof
Convex
Minimization with Distance-Dependent Subgradient Moments
We minimize a real-valued function that is convex on a closed convex set
in -dimensional Euclidean space. A given
lies within distance of a minimizer on . The oracle returns either an exact
projection onto or a random
vector drawn using a fresh independent sample. At each , this vector has a subgradient
mean relative to and second
moment at most ,
where . For and , the goal is a
measurable output
satisfying with
probability at least .
The optimization problem is The algorithm receives the dimension , the starting point
, and the parameters . Both query
types accept any point in and share a single call
budget.
Our assumptions:
Assumption 1 (Convexity and initial distance). The
function is Borel
measurable. On the closed convex set , it satisfies
for every and . The point belongs to , and there exists such that .
Assumption 2 (Subgradient mean and second moment).
Let be
independent measurable samples with common law on a measurable space , independent of the algorithm’s
randomness. A subgradient query at on call returns , where
is jointly measurable. For each and , the
vector is Bochner
integrable and is
integrable. Writing ,
we require
A projection query at returns the Euclidean
projection . This map is
measurable, takes values in , and
satisfies After the allotted calls, the output must be measurable and belong to
for every realization. Under the
joint law of the samples and the
algorithm’s randomness, it must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.DistanceGrowingSubgradient.spec
LongTails.Theorems.DistanceGrowingSubgradientUpperBound.budget
Relevant previous results
- Yair Carmon and Oliver Hinder. The Price of Adaptivity in
Stochastic Convex Optimization. 2024 (COLT, full proof in arXiv v1).
Complexity: total oracle calls for
averaged clipped SGD when , with one
stochastic subgradient and one projection onto
per step. Here bounds the root
second moment at every query in .
- Daniela Angela Parletta, Andrea Paudice, Massimiliano Pontil, and
Saverio Salzo. High
Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed
Noise. 2024 (journal version, first preprint 2022). Complexity:
total oracle calls for the
averaged clipped projected subgradient method on when , with one
stochastic subgradient and one projection onto per step. The diameter is at most
, and bounds both the Lipschitz constant on
and the oracle standard
deviation there.