Optimal Convergence Rates for the Proximal Bundle Method
From MaRDI portal
Publication:6155876
DOI10.1137/21M1428601zbMATH Open1519.90167arXiv2105.07874OpenAlexW3162304593MaRDI QIDQ6155876FDOQ6155876
Authors: Mateo Díaz, Benjamin Grimmer 
Publication date: 7 June 2023
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: We study convergence rates of the classic proximal bundle method for a variety of nonsmooth convex optimization problems. We show that, without any modification, this algorithm adapts to converge faster in the presence of smoothness or a H"older growth condition. Our analysis reveals that with a constant stepsize, the bundle method is adaptive, yet it exhibits suboptimal convergence rates. We overcome this shortcoming by proposing nonconstant stepsize schemes with optimal rates. These schemes use function information such as growth constants, which might be prohibitive in practice. We provide a parallelizable variant of the bundle method that can be applied without prior knowledge of function parameters while maintaining near-optimal rates. The practical impact of this scheme is limited since we incur a (parallelizable) log factor in the complexity. These results improve on the scarce existing convergence rates and provide a unified analysis approach across problem settings and algorithmic details. Numerical experiments support our findings.
Full work available at URL: https://arxiv.org/abs/2105.07874
Recommendations
- Rate of convergence of the bundle method
- A modified proximal gradient method and its convergence rate
- An implementable bundle method for nonsmooth convex optimization
- Convergence of the proximal bundle algorithm for nonsmooth nonconvex optimization problems
- A proximal bundle method for nonsmooth and nonconvex constrained optimization
Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)
Cites Work
- Pegasos: primal estimated sub-gradient solver for SVM
- Title not available (Why is that?)
- Introductory lectures on convex optimization. A basic course.
- A Spectral Bundle Method for Semidefinite Programming
- Convergence of some algorithms for convex minimization
- Representations of quasi-Newton matrices and their use in limited memory methods
- A family of variable metric proximal methods
- Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities
- Methods of descent for nondifferentiable optimization
- An aggregate subgradient method for nonsmooth convex minimization
- A redistributed proximal bundle method for nonconvex optimization
- Nonlinear optimization.
- Title not available (Why is that?)
- Title not available (Why is that?)
- A proximity control algorithm to minimize nonsmooth and nonconvex semi-infinite maximum eigenvalue functions
- Proximity control in bundle methods for convex nondifferentiable minimization
- Variable metric bundle methods: From conceptual to implementable forms
- New variants of bundle methods
- A doubly stabilized bundle method for nonsmooth convex optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Convex proximal bundle methods in depth: a unified analysis for inexact oracles
- An Infeasible Bundle Method for Nonsmooth Convex Constrained Optimization without a Penalty Function or a Filter
- A Proximal Bundle Method with Approximate Subgradient Linearizations
- On approximations with finite precision in bundle methods for nonsmooth optimization
- Divide to conquer: decomposition methods for energy optimization
- Weak Sharp Minima in Mathematical Programming
- An Algorithm for Constrained Optimization with Semismooth Functions
- A proximal bundle method for nonsmooth nonconvex functions with inexact information
- A science fiction story in nonsmooth optimization originating at IIASA
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
- A \(\mathcal{VU}\)-algorithm for convex minimization
- A modification and an extension of Lemarechal’s algorithm for nonsmooth minimization
- Efficiency of proximal bundle methods
- Title not available (Why is that?)
- A second-order bundle method to minimize the maximum eigenvalue function.
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- A Linearization Algorithm for Nonsmooth Minimization
- A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information
- Proximal bundle methods for nonsmooth DC programming
- A simple nearly optimal restart scheme for speeding up first-order methods
- An infeasible bundle method for nonconvex constrained optimization with application to semi-infinite programming problems
- Target radius methods for nonsmooth convex optimization
- Rate of convergence of the bundle method
- A new infeasible proximal bundle algorithm for nonsmooth nonconvex constrained optimization
- A filter proximal bundle method for nonsmooth nonconvex constrained optimization
- Non-smooth non-convex Bregman minimization: unification and new algorithms
- Stochastic model-based minimization of weakly convex functions
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- An asynchronous bundle-trust-region method for dual decomposition of stochastic mixed-integer programming
- Asynchronous level bundle methods
- A parallel bundle framework for asynchronous subspace optimization of nonsmooth convex functions
- A Proximal Bundle Variant with Optimal Iteration-Complexity for a Large Range of Prox Stepsizes
- Gradient methods with memory
Cited In (9)
- Approximations in proximal bundle methods and decomposition of convex programs
- Provably faster gradient descent via long steps
- On optimal universal first-order methods for minimizing heterogeneous sums
- A single cut proximal bundle method for stochastic convex composite optimization
- General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
- Implementation of an oracle-structured bundle method for distributed optimization
- An asynchronous proximal bundle method
- Rate of convergence of the bundle method
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
This page was built for publication: Optimal Convergence Rates for the Proximal Bundle Method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6155876)
