Optimal Convergence Rates for the Proximal Bundle Method
From MaRDI portal
(Redirected from 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
- 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 Linearization Algorithm for Nonsmooth Minimization
- 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 Proximal Bundle Method with Approximate Subgradient Linearizations
- A Proximal Bundle Variant with Optimal Iteration-Complexity for a Large Range of Prox Stepsizes
- 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
- A Spectral Bundle Method for Semidefinite Programming
- An aggregate subgradient method for nonsmooth convex minimization
- An Algorithm for Constrained Optimization with Semismooth Functions
- 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
- An Infeasible Bundle Method for Nonsmooth Convex Constrained Optimization without a Penalty Function or a Filter
- 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
- 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?)
- 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
(17)- Approximations in proximal bundle methods and decomposition of convex programs
- Rate of convergence of the bundle method
- General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
- A Proximal Bundle Variant with Optimal Iteration-Complexity for a Large Range of Prox Stepsizes
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- On optimal universal first-order methods for minimizing heterogeneous sums
- Linear convergence of the derivative-free proximal bundle method on convex nonsmooth functions, with application to the derivative-free \(\mathcal{VU}\)-algorithm
- Provably faster gradient descent via long steps
- A single cut proximal bundle method for stochastic convex composite optimization
- Implementation of an oracle-structured bundle method for distributed optimization
- An asynchronous proximal bundle method
- Proximal oracles for optimization and sampling
- Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods
- An overview and comparison of spectral bundle methods for primal and dual semidefinite programs
- Discrete level-bundle method for mean-CVaR portfolio optimization with cardinality constraint
- A proximal-type method for nonsmooth and nonconvex constrained minimization problems
- Structured nonsmooth optimization using functional encoding and branching information
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)
