Convex Ball Proximal Minimization
Descriptions may be stale. Consult the linked Lean sources.
Convex Ball Proximal Minimization
We minimize a convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and closed epigraph). The
set
Assumption 2 (Initialization and minimizer). The
given starting point satisfies
Assumption 3 (Exact ball proximal oracle). For every
query
Our formulation is algorithm-specific: we analyze ball proximal
iteration with fixed radius
The required accuracy is
Results
In a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) BallProximalSharpProfile
(Ours) |
|||
| (2) BallProximalGaussian (Ours) (review) | |||
| (3) (Richtárik and Li 2026), Thm. 3.4, (42)–(43) | (1): Same order;
uniformly no larger budget than (43). At |
(2): Gaussian relaxation loses the sharper rational guarantee in (42). | |
| (4) (Richtárik and Li 2026), Rem. 3.5 | Fixed |
(1): Sharp leading
constant via supporting worst-case characterization. At |
(1): No finite-step
dominance; (4) is exact at |
| (5) (Richtárik and Li 2026), Thm. 4.5 | Exact minimizer. |
(1),
(2): Lower target-accuracy cost when |
(1),
(2): Worse when |
| (6) (Gruntkowska et al. 2025), Thm. 8.1(iii), Cor. 8.2 | (1),
(2): |
Abbr: