Terminal Clipping for Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Terminal Clipping for Convex Minimization
We consider minimizing a measurable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and initial distance). The
set
Assumption 2 (Stochastic subgradients). Let
Assumption 3 (Exact projection). A projection query
at any
Our formulation is algorithm-specific: we analyze terminal clipping
with projected stochastic subgradient updates. For a nonnegative
threshold
The required output is measurable and belongs to
Results
Measurable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ClippedBgLastIterate
(Ours) |
|||
| (2) Projected Halpern (Alacaoglu et al. 2026, Thm. 3.6); derived bound via Markov | (1): On the same moment class, logarithmic instead of polynomial confidence cost; removes the accuracy logarithm at fixed confidence. Comparison is specifically with Markov conversion. | (1) needs a fixed horizon instead of an anytime schedule; substantially larger proved numerical constants. | |
| (3) Clipped SGD (Liu and Zhou 2023,
Thm. 3), |
Special case: |
(1): Matches this rate
for |
(1): The |
| (4) Distance-adaptive
clipped SGD (Liu and Zhou
2023, Thm. 6), |
Special case: |
(1): Last iterate instead of a selected weighted average; extends to non-Lipschitz objectives with growing moments. | (1) is not
distance-adaptive: |
Abbr:
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (5) SGD (Liu and Zhou 2026, Thm. 3.5) | Special case: |
(1): Extends the high-probability last-iterate guarantee to finite second moments and non-Lipschitz objectives with growing moments. | On the overlap, |
| (6) Clipped SGD (Chezhegov et al. 2026, Thm. 1,
Cor. 1), |
Special case: |
(1): With |
(1) loses anytime tuning
and coverage of |
Abbr: