Descriptions may be stale. Consult the linked Lean sources.
Terminal Clipping for
Convex Minimization
We consider minimizing a measurable convex function over a closed
convex set , with a given within distance of a minimizer . The oracle returns stochastic
subgradient estimates from
independent samples with law
, or exact projections onto
. Their means are subgradients on
, and , where . Projected clipped updates must
return a measurable terminal iterate satisfying with
probability at least ,
where and .
The optimization problem is Here is a
nonnegative integer, and and denote the Euclidean inner
product and norm. The algorithm receives and
accesses the objective and constraint set through the oracle.
Our assumptions:
Assumption 1 (Convexity and initial distance). The
set is
closed and convex, , and
is measurable on . For all and , There
exists such that
Assumption 2 (Stochastic subgradients). Let be a probability measure on a
measurable sample space . The
map
is jointly measurable. For every , is Bochner
integrable and is
integrable under . Its mean
satisfies the subgradient inequality and its second moment satisfies The oracle samples form a sequence of measurable, mutually
independent random variables, each with law . This sequence is independent of the
algorithm’s randomness. At call ,
a subgradient query at returns
.
Assumption 3 (Exact projection). A projection query
at any returns
, where is
measurable and satisfies
Our formulation is algorithm-specific: we analyze terminal clipping
with projected stochastic subgradient updates. For a nonnegative
threshold , define The method starts at the given , with initial output and first query a subgradient query
at . It alternates subgradient
and projection queries. Before receiving the subgradient reply at
iteration , it selects a step size
and threshold using its available history and
internal randomness. The updates are The output remains after the subgradient reply and
becomes after the
projection reply; the next query is a subgradient query at . Both query types count toward a
single total oracle-call budget. Thus each completed update uses two
calls. With a budget of
calls, the terminal output is ; an
unmatched final subgradient call leaves it unchanged.
The required output is measurable and belongs to for every realization. Its accuracy
requirement is where is the
joint law of the oracle samples and the independent algorithm
randomness.