Optimal Convergence Rates for the Proximal Bundle Method
From MaRDI portal
Publication:6155876
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.
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
Cites work
- scientific article; zbMATH DE number 4015993 (Why is no real title available?)
- scientific article; zbMATH DE number 3559294 (Why is no real title available?)
- scientific article; zbMATH DE number 3577030 (Why is no real title available?)
- scientific article; zbMATH DE number 477581 (Why is no real title available?)
- scientific article; zbMATH DE number 2084780 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- A Linearization Algorithm for Nonsmooth Minimization
- A Proximal Bundle Method with Approximate Subgradient Linearizations
- A Proximal Bundle Variant with Optimal Iteration-Complexity for a Large Range of Prox Stepsizes
- A Spectral Bundle Method for Semidefinite Programming
- A \(\mathcal{VU}\)-algorithm for convex minimization
- A doubly stabilized bundle method for nonsmooth convex optimization
- A family of variable metric proximal methods
- A filter proximal bundle method for nonsmooth nonconvex constrained optimization
- A modification and an extension of Lemarechal’s algorithm for nonsmooth minimization
- A new infeasible proximal bundle algorithm for nonsmooth nonconvex constrained optimization
- A parallel bundle framework for asynchronous subspace optimization of nonsmooth convex functions
- A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information
- A proximal bundle method for nonsmooth nonconvex functions with inexact information
- A proximity control algorithm to minimize nonsmooth and nonconvex semi-infinite maximum eigenvalue functions
- A redistributed proximal bundle method for nonconvex optimization
- A science fiction story in nonsmooth optimization originating at IIASA
- A second-order bundle method to minimize the maximum eigenvalue function.
- A simple nearly optimal restart scheme for speeding up first-order methods
- An Algorithm for Constrained Optimization with Semismooth Functions
- An Infeasible Bundle Method for Nonsmooth Convex Constrained Optimization without a Penalty Function or a Filter
- An aggregate subgradient method for nonsmooth convex minimization
- An asynchronous bundle-trust-region method for dual decomposition of stochastic mixed-integer programming
- An infeasible bundle method for nonconvex constrained optimization with application to semi-infinite programming problems
- Asynchronous level bundle methods
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
- Convergence of some algorithms for convex minimization
- Convex proximal bundle methods in depth: a unified analysis for inexact oracles
- Divide to conquer: decomposition methods for energy optimization
- Efficiency of proximal bundle methods
- Gradient methods with memory
- Introductory lectures on convex optimization. A basic course.
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Methods of descent for nondifferentiable optimization
- New variants of bundle methods
- Non-smooth non-convex Bregman minimization: unification and new algorithms
- Nonlinear optimization.
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- On approximations with finite precision in bundle methods for nonsmooth optimization
- Pegasos: primal estimated sub-gradient solver for SVM
- Proximal bundle methods for nonsmooth DC programming
- Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities
- Proximity control in bundle methods for convex nondifferentiable minimization
- Rate of convergence of the bundle method
- Representations of quasi-Newton matrices and their use in limited memory methods
- Stochastic model-based minimization of weakly convex functions
- Target radius methods for nonsmooth convex optimization
- Variable metric bundle methods: From conceptual to implementable forms
- Weak Sharp Minima in Mathematical Programming
Cited in
(10)- General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- Provably faster gradient descent via long steps
- Rate of convergence of the bundle method
- Approximations in proximal bundle methods and decomposition of convex programs
- Implementation of an oracle-structured bundle method for distributed optimization
- A single cut proximal bundle method for stochastic convex composite optimization
- Linear convergence of the derivative-free proximal bundle method on convex nonsmooth functions, with application to the derivative-free \(\mathcal{VU}\)-algorithm
- An asynchronous proximal bundle method
- On optimal universal first-order methods for minimizing heterogeneous sums
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)
