Convex Minimization with Symmetric Remainders
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Symmetric Remainders
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function
Assumption 2 (Initial distance). There exists
Assumption 3 (Sampling and oracle). There is a
probability measure
Assumption 4 (Symmetric remainder and quantile
bound). For every
After the allotted oracle calls, the output
Results
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) QuantileRemainderMinimaxConvex
(Ours) |
|||
| (2) Clipped-SSTM/SMoM
(Puchkin et al.
2024), Cor. 5.8, Eq. (117). Derived bound;
density/convolution-tail subclass, |
Fixed |
(1) Scope: quantile-only
noise admits atoms and symmetric backgrounds without any positive
moment. Removes (2)’s density and convolution bound
|
(1): expectation, not
(2)’s high probability. On the overlap, fixed positive
parameters and |
| (3) Clipped-SSTM/median
(Puchkin et al.
2024), Prop. 4.1 + Thm. 5.7. Derived bound; |
Probability |
(1) Scope: at |
(1): expectation instead
of (3)’s high probability; noise-scale term |
Abbr: Costs count raw stochastic-gradient calls,
including batches.