Convex Minimization with Affine Moments
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Affine Moments
We minimize 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 affine moment bound).
There exist a probability measure
Queries may be made at any point of
Results
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RecursiveAffineMomentAcceleration
(Ours) |
|||
| (2) AffineMomentAcceleration
(Ours) |
|||
| (3) Clip-SSTM (Nekrasova et al. 2026), Thm. 5.2, Cor. I.2; finite-moment specialization | (1): for fixed (2): relative term |
(1), (2)
require global smoothness and finite moments; (3)
permits local smoothness and weak tails. (1) pays |
|
| (4) RCSAG (Lobanov et al.
2026), Thm. 9; |
(1): same relative-term exponent gain as against (3), under the stated regime. (2): |
(1), (2)
exclude generalized smoothness and gap-dependent noise.
(1) loses logarithmic confidence dependence; at |
|
| (5) AGNES (Gupta et al. 2024),
Thm. 3 + Markov; |
(2): confidence cost
|
(2) adds three
logarithmic factors to the expected-accuracy rate. (1)
pays |
|
| (6) Clipped-SSTM (Sadiev et al. 2023),
Thm. 3.2; |
(1),
(2): no established improvement on |
(2): |
Abbr: