Convergence Guarantees for the Broximal Point Method under Perturbations
Abstract
The Broximal Point Method (BPM) of Gruntkowska et al. (2025) comes with strong guarantees for convex optimization: under convexity alone, it terminates after finitely many steps and converges linearly in function value, with bounds that do not depend on the condition number or on any other regularity property of the objective. Each iteration, however, requires the exact minimization of the objective over a ball, which is generally intractable. As a first step toward implementable variants, we study the method when these subproblems are solved only approximately. We introduce and analyze Inexact BPM, which replaces the exact broximal point by an approximation and makes no assumption on how this approximation is obtained. Under summable or sufficiently small errors, we bound the number of iterations needed to reach a neighborhood of the set of minimizers, and these bounds remain independent of the regularity of the objective. Under the weaker requirement that the errors stay below the ball radius, we prove sublinear convergence in function value for the exact broximal points underlying the perturbed iterates, valid until the target neighborhood is reached, and we recover linear rates under bounded sublevel sets or strong convexity.
Related
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Operator Calculus for Population-Based Optimization: Modular Convergence and Finite-Population Guarantees
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- Enhanced convergence guarantees of score-based generative models in 𝒲2-distance beyond log-concavity
BibTeX
@misc{abdikarimova2026convergence,
title = {{Convergence Guarantees for the Broximal Point Method under Perturbations}},
author = {Alina Abdikarimova and Ammar Mahran and Peter Richtárik},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01933},
eprint = {2611.01933},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01933},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Convergence Guarantees for the Broximal Point Method under Perturbations
AU - Alina Abdikarimova
AU - Ammar Mahran
AU - Peter Richtárik
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01933
UR - https://arxiv.org/abs/2611.01933
AB - The Broximal Point Method (BPM) of Gruntkowska et al. (2025) comes with strong guarantees for convex optimization: under convexity alone, it terminates after finitely many steps and converges linearly in function value, with bounds that do not depend on the condition number or on any other regularity property of the objective. Each iteration, however, requires the exact minimization of the objective over a ball, which is generally intractable. As a first step toward implementable variants, we study the method when these subproblems are solved only approximately. We introduce and analyze Inexact BPM, which replaces the exact broximal point by an approximation and makes no assumption on how this approximation is obtained. Under summable or sufficiently small errors, we bound the number of iterations needed to reach a neighborhood of the set of minimizers, and these bounds remain independent of the regularity of the objective. Under the weaker requirement that the errors stay below the ball radius, we prove sublinear convergence in function value for the exact broximal points underlying the perturbed iterates, valid until the target neighborhood is reached, and we recover linear rates under bounded sublevel sets or strong convexity.
ER -