# A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes

arXiv: https://arxiv.org/abs/2003.11457 · HTML: https://mlsanity.com/paper/2003.11457/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2020.

## Built on by (most cited first, 7 of 7)

- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)
- [Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization](https://mlsanity.com/paper/2111.15645/) (2021)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Regions](https://mlsanity.com/paper/2507.19465/) (2025)

## Abstract (arXiv)

This paper presents a proximal bundle variant, namely, the relaxed proximal bundle (RPB) method, for solving convex nonsmooth composite optimization problems. Like other proximal bundle variants, RPB solves a sequence of prox bundle subproblems whose objective functions are regularized composite cutting-plane models. Moreover, RPB uses a novel condition to decide whether to perform a serious or null iteration which does not necessarily yield a function value decrease. Optimal iteration-complexity bounds for RPB are established for a large range of prox stepsizes, both in the convex and strongly convex settings. To the best of our knowledge, this is the first time that a proximal bundle variant is shown to be optimal for a large range of prox stepsizes. Finally, iteration-complexity results for RPB to obtain iterates satisfying practical termination criteria, rather than near optimal solutions, are also derived.