Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
From MaRDI portal
Publication:2515032
Abstract: The main goal of this paper is to develop uniformly optimal first-order methods for convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. By incorporating a multi-step acceleration scheme into the well-known bundle-level method, we develop an accelerated bundle-level (ABL) method, and show that it can achieve the optimal complexity for solving a general class of black-box CP problems without requiring the input of any smoothness information, such as, whether the problem is smooth, nonsmooth or weakly smooth, as well as the specific values of Lipschitz constant and smoothness level. We then develop a more practical, restricted memory version of this method, namely the accelerated prox-level (APL) method. We investigate the generalization of the APL method for solving certain composite CP problems and an important class of saddle-point problems recently studied by Nesterov [Mathematical Programming, 103 (2005), pp 127-152]. We present promising numerical results for these new bundle-level methods applied to solve certain classes of semidefinite programming (SDP) and stochastic programming (SP) problems.
The author considers is the convex programming problem (CP) \[ f^{\ast }:=\min_{x\in X}f\left( x\right) , \] where \(X\) is a convex compact set and \(f:X\rightarrow \mathbb{R}\) is a closed function. The author develops uniformly optimal first-order methods for (CP). By incorporating a multistep acceleration scheme into the well-known bundle-level method, he develops an accelerated bundle-level method, and shows that it can achieve the optimal complexity for solving a general class of black-box CP problems without requiring the input of any smoothness information. The author develops a more practical, restricted memory version of this method, namely the accelerated prox-level (APL) method. He investigate the generalization of this method, namely the USL method, for solving certain composite CP problems and an important class of saddle-point problems. Finally, the author shows the advantages of the APL and USL methods over some existing first-order methods for solving certain classes of semidefinite programming and stochastic programming problems.
Recommendations
- Fast bundle-level methods for unconstrained and ball-constrained convex optimization
- Accelerated bundle level methods with inexact oracle
- Acceleration techniques for level bundle methods in weakly smooth convex constrained optimization
- Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities
- Level bundle-like algorithms for convex optimization
Cites work
- A proximal method for composite minimization
- A Spectral Bundle Method for Semidefinite Programming
- An aggregate subgradient method for nonsmooth convex minimization
- An optimal method for stochastic composite optimization
- Approximate level method for nonsmooth convex minimization
- Decomposition algorithms for stochastic programming on a computational grid
- Excessive Gap Technique in Nonsmooth Convex Minimization
- First-Order Methods for Sparse Covariance Selection
- First-order methods of smooth convex optimization with inexact oracle
- scientific article; zbMATH DE number 4079168 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3559294 (Why is no real title available?)
- Inexact bundle methods for two-stage stochastic programming
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Introductory lectures on convex optimization. A basic course.
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Monte Carlo bounding techniques for determinig solution quality in stochastic programs
- NESTA: A fast and accurate first-order method for sparse recovery
- New variants of bundle methods
- Newton's method for convex programming and Tschebyscheff approximation
- Non-Euclidean restricted memory level method for large-scale convex optimization
- Nonlinear optimization.
- On parallel complexity of nonsmooth convex optimization
- Optimal methods of smooth convex minimization
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities
- Proximity control in bundle methods for convex nondifferentiable minimization
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth minimization of non-smooth functions
- Smooth Optimization Approach for Sparse Covariance Selection
- Smoothing technique and its applications in semidefinite optimization
- The Cutting-Plane Method for Solving Convex Programs
- The empirical behavior of sampling methods for stochastic programming
- Validation analysis of mirror descent stochastic approximation method
Cited in
(52)- Special backtracking proximal bundle method for nonconvex maximum eigenvalue optimization
- Optimal subgradient algorithms for large-scale convex optimization in simple domains
- Accelerated first-order methods for hyperbolic programming
- Conditional gradient type methods for composite nonlinear and stochastic optimization
- Target radius methods for nonsmooth convex optimization
- Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
- Dynamic stochastic approximation for multi-stage stochastic optimization
- Acceleration techniques for level bundle methods in weakly smooth convex constrained optimization
- A new restricted memory level bundle method for constrained convex nonsmooth optimization
- On stochastic accelerated gradient with convergence rate
- Accelerated gradient sliding for structured convex optimization
- A multi-step doubly stabilized bundle method for nonsmooth convex optimization
- Fast gradient descent for convex minimization problems with an oracle producing a ( , L)-model of function at the requested point
- A class of exact penalty functions and penalty algorithms for nonsmooth constrained optimization problems
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Optimal subgradient methods: computational properties for large-scale linear inverse problems
- Generalized uniformly optimal methods for nonlinear programming
- Rate of convergence of the bundle method
- An optimal subgradient algorithm with subspace search for costly convex optimization problems
- Fast bundle-level methods for unconstrained and ball-constrained convex optimization
- General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- OSGA: a fast subgradient algorithm with optimal complexity
- A proximal method for composite minimization
- On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients
- A level-set method for convex optimization with a feasible solution path
- Efficient algorithms for distributionally robust stochastic optimization with discrete scenario support
- A Proximal Bundle Variant with Optimal Iteration-Complexity for a Large Range of Prox Stepsizes
- Accelerated bundle level methods with inexact oracle
- On stochastic accelerated gradient with convergence rate of regression learning
- Inexact proximal stochastic second-order methods for nonconvex composite optimization
- An accelerated linearized alternating direction method of multipliers
- A Bundle Method for a Class of Bilevel Nonsmooth Convex Minimization Problems
- Inexact model: a framework for optimization and variational inequalities
- A Trust-region Method for Nonsmooth Nonconvex Optimization
- Universal Conditional Gradient Sliding for Convex Optimization
- Optimal Methods for Convex Risk-Averse Distributed Optimization
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
- Optimal Convergence Rates for the Proximal Bundle Method
- Block mirror stochastic gradient method for stochastic optimization
- On optimal universal first-order methods for minimizing heterogeneous sums
- Optimization on a finer scale: bounded local subgradient variation perspective
- Universal subgradient and proximal bundle methods for convex and strongly convex hybrid composite optimization
- Proximal oracles for optimization and sampling
- Discrete level-bundle method for mean-CVaR portfolio optimization with cardinality constraint
- Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
- Optimal methods for convex nested stochastic composite optimization
- A restricted memory quasi-Newton bundle method for nonsmooth optimization on Riemannian manifolds
- Complexity and numerical experiments of a new adaptive generic proximal bundle method
- A simple uniformly optimal method without line search for convex optimization
- Variational properties of decomposable functions. I: Strict epi-calculus and applications
- Level bundle-like algorithms for convex optimization
This page was built for publication: Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515032)
