← All setups

Convex Ball Proximal Minimization

Descriptions may be stale. Consult the linked Lean sources.

Convex Ball Proximal Minimization

We minimize a convex function f:E→R over a convex set C in a finite-dimensional real inner-product space E, with closed constrained epigraph. A given x0∈C satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a minimizer x⋆∈C, where R≥0 and Δ>0. At x∈C, the oracle returns an exact minimizer over {z∈C:∥z−x∥≤t}, where t>0. Ball proximal iteration must return x¯∈C with f(x¯)−f(x⋆)≤ε almost surely under P, the law of oracle randomness, for ε>0.

The optimization problem is minx∈Cf(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, t, R, Δ, ε, and x0; the set C and function f are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and closed epigraph). The set C⊆E is convex, and for all x,y∈C and λ∈[0,1], f((1−λ)x+λy)≤(1−λ)f(x)+λf(y). The constrained epigraph {(x,a)∈E×R:x∈C, f(x)≤a} is closed in E×R.

Assumption 2 (Initialization and minimizer). The given starting point satisfies x0∈C. There exists x⋆∈C such that f(x⋆)≤f(x)for every x∈C,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 3 (Exact ball proximal oracle). For every query x∈C, every oracle reply y satisfies y∈C,∥y−x∥≤t,f(y)≤f(z)for all z∈C with ∥z−x∥≤t. These conditions hold for every query history and every realization of the oracle randomness. The oracle may select among multiple minimizers using that history and randomness.

Our formulation is algorithm-specific: we analyze ball proximal iteration with fixed radius t. Starting at the given x0, each step queries the oracle at the current iterate and replaces it by the returned point: xk+1∈argminz∈C∥z−xk∥≤tf(z),k=0,…,K−1. Here K≥0 is the integer oracle-call budget, each step uses one call, and the output is the last iterate x¯=xK. All queries therefore lie in C.

The required accuracy is x¯∈C,f(x¯)−f(x⋆)≤εP-a.s. The minimizer x⋆ is fixed independently of the oracle randomness.

Results

In a finite-dimensional real inner-product space, f is convex on C and its epigraph restricted to C is closed. A minimizer x⋆∈C exists, x0∈C, ∥x0−x⋆∥≤R, and f(x0)−f(x⋆)≤Δ, with R≥0 and t,Δ,ε>0. The setup fixes xk+1∈arg⁡minz∈C,∥z−xk∥≤tf(z) and last-iterate output. Each step costs one exact ball-oracle call. Target: xK∈C and f(xK)−f(x⋆)≤ε for every admissible tie breaking (hence almost surely).

Exact ball-proximal complexity for ConvexBallProximal.
Result Oracle complexity Novelty Limitations
(1) BallProximalSharpProfile (Ours) (⋆⋆) (review) O(1+min{R2t2,Rth(r)})
(2) BallProximalGaussian (Ours) (review) O(1+min{R2t2,Rtℓ})
(3) (Richtárik and Li 2026), Thm. 3.4, (42)–(43) O(1+min{R2t2,Rtℓ}) (1): Same order; uniformly no larger budget than (43). At r=1/5, R/t=1000: 842 versus 897 calls. (2): Matches known rate; Lean formalization. (2): Gaussian relaxation loses the sharper rational guarantee in (42).
(4) (Richtárik and Li 2026), Rem. 3.5 O(1+Rt(1−r2)log⁡(1/r))
Fixed 0<r<1, R/t→∞; implicit finite-step bound.
(1): Sharp leading constant via supporting worst-case characterization. At r=1/5, R/t=1000: 842 versus ≈879 calls; gain vanishes as r→0. (1): No finite-step dominance; (4) is exact at K=1. (2): Weaker gap guarantee.
(5) (Richtárik and Li 2026), Thm. 4.5 O(1+min{R2t2,CdRt})
Exact minimizer.
(1), (2): Lower target-accuracy cost when 1≪ℓ≪min{Cd,R/t}: (R/t)ℓ versus min{(R/t)2,CdR/t}. (1), (2): Worse when Cd≪min{ℓ,R/t}; (5) attains the exact optimum.
(6) (Gruntkowska et al. 2025), Thm. 8.1(iii), Cor. 8.2 O(1+min{R2t2,ℓlog⁡(1+t/R)})
R>0.
(1), (2): ℓ instead of ℓ when 1≪ℓ≪R/t; total saving Θ(ℓ), already achieved by (3).

Abbr: r=ε/Δ, ℓ=log+⁡(Δ/ε), log+⁡u=max{0,log⁡u}; h(r)=(1−r)+ for r≥1/2 and h(r)=log⁡(1/r) for 0<r<1/2; (u)+=max{0,u}. d=dim⁡E; Cd is the dimension-dependent self-contracted-curve length constant (C1=2, Cd=4d(1+4d)d for d≥2). Costs count exact ball-oracle calls; log is natural. Numerical comparisons retain the original budgets’ constants.

Gruntkowska, Kaja, Hanmin Li, Aadi Rane, and Peter Richtárik. 2025. The Ball-Proximal (="Broximal") Point Method: A New Algorithm, Convergence Theory, and Applications. https://arxiv.org/abs/2502.02002v2.
Richtárik, Peter, and Hanmin Li. 2026. A Sharper Theory of Ball-Proximal Optimization: Convergence and Radius Selection. https://arxiv.org/abs/2609.35147v1.

Lean setup