Descriptions may be stale. Consult the linked Lean sources.
Clipped Subgradients
with Heavy-Tailed Noise
We consider minimizing a possibly nonconvex function over a closed convex set
in a finite-dimensional real
inner product space . The function
is -weakly convex, with , and admits bounded
subgradients and a lower bound with controlled gap at a given starting
point. The oracle returns unbiased stochastic subgradients with a
bounded centered moment of order , or exact projections onto
. Projected clipped subgradient
updates must produce a measurable feasible output satisfying ,
where , minimizes over , and expectation averages sampling
and algorithm randomness.
The optimization problem is The norm is induced by the inner product on . Fix parameters
The algorithm receives , the
measurable sample space ,
these parameters, and the starting point ; the objective, feasible set, and
sampling distribution are accessed through the oracle.
Our assumptions:
Assumption 1 (Weak convexity and initial gap). The
set is closed and
convex, and . There is a
map such that, for every
, There is a lower bound satisfying
Assumption 2 (Heavy-tailed stochastic subgradients).
There are a probability distribution on and a jointly measurable map . For every , the random vector is Bochner integrable and is integrable
under , with Oracle samples are measurable, mutually
independent, and each has law .
Their joint law is independent of the algorithm’s randomness. At call
, a subgradient query at returns .
Assumption 3 (Exact projection). Projection queries
at any return , where is measurable and satisfies
The task is algorithm-specific: we analyze projected clipped
subgradient descent with a constant step size and clipping threshold.
The algorithm chooses , , and from its inputs. Starting from
the given , it alternates a
stochastic subgradient query and a projection query: Each completed update uses two oracle calls, one of
each kind, counted together. For a total budget , let be the number of
completed updates. Independently of the samples, draw uniformly from . The output rule is Thus a budget of calls produces a uniformly selected
iterate from . An
unpaired final subgradient query does not change the output.
Accuracy is measured by a proximal residual. Success requires the
existence of a map
satisfying, for every , The output must be measurable
and belong to for every
realization. For every such proximal map , the squared residual must be
integrable and satisfy where
is the joint law of the independent index and oracle samples.