Faster subgradient methods for functions with Hölderian growth
From MaRDI portal
(Redirected from Publication:2297653)
Abstract: The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with H"olderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain region including the optimal set, with error of the order of the stepsize. Second, if appropriate problem parameters are known, we derive a decaying stepsize which obtains a much faster convergence rate than is suggested by the classical result for the subgradient method. Thirdly we develop a novel "descending stairs" stepsize which obtains this faster convergence rate and also obtains linear convergence for the special case of weakly sharp functions. We also develop an adaptive variant of the "descending stairs" stepsize which achieves the same convergence rate without requiring an error bound constant which is difficult to estimate in practice.
Recommendations
- On Convergence Properties of a Subgradient Method
- Subgradient methods for sharp weakly convex functions
- A subgradient method with non-monotone line search
- General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
- Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity
Cites work
- ``Efficient subgradient methods for general convex optimization
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A Geometrically Convergent Subgradient Optimization Method for Nonlinearly Constrained Convex Programs
- A three-operator splitting scheme and its optimization applications
- A unified approach to error bounds for structured convex optimization problems
- Activity identification and local linear convergence of forward-backward-type methods
- An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in R^n
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Asymptotic analysis of high-dimensional LAD regression with Lasso smoother
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
- Convergence rate of incremental subgradient algorithms
- Convex analysis and monotone operator theory in Hilbert spaces
- Coordinate descent algorithms for lasso penalized regression
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Error bounds in mathematical programming
- Faster subgradient methods for functions with Hölderian growth
- Finite termination of the proximal point algorithm
- First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
- Global error bounds for piecewise convex polynomials
- scientific article; zbMATH DE number 4015993 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 2155014 (Why is no real title available?)
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- Nonlinear programming methods in the presence of noise
- On convergence rates of subgradient optimization methods
- On proximal subgradient splitting method for minimizing the sum of two nonsmooth convex functions
- On the convergence rate for stochastic approximation in the nonsmooth setting
- Online Learning with Kernels
- Robust Stochastic Approximation Approach to Stochastic Programming
- RSG: Beating Subgradient Method without Smoothness and Strong Convexity
- The L₁ penalized LAD estimator for high dimensional linear regression
- The effect of deterministic noise in subgradient methods
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Weak Sharp Minima in Mathematical Programming
- Weak sharp minima revisited. I: Basic theory
Cited in
(24)- Subgradient methods for sharp weakly convex functions
- Convergence results of a new monotone inertial forward-backward splitting algorithm under the local Hölder error bound condition
- Faster subgradient methods for functions with Hölderian growth
- A simple nearly optimal restart scheme for speeding up first-order methods
- General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
- On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients
- On Convergence Properties of a Subgradient Method
- Exact penalties for decomposable convex optimization problems
- On the simplicity and conditioning of low rank semidefinite programs
- An optimal-storage approach to semidefinite programming using approximate complementarity
- Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity
- Accelerate stochastic subgradient method by leveraging local growth condition
- Radial duality. II: Applications and algorithms
- A strict complementarity approach to error bound and sensitivity of solution of conic programs
- Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
- A subgradient method with constant step-size for \(\ell_1\)-composite optimization
- Stochastic algorithms with geometric step decay converge linearly on sharp functions
- Tight analyses for subgradient descent. I: Lower bounds
- A superlinearly convergent subgradient method for sharp semismooth problems
- Some primal-dual theory for subgradient methods for strongly convex optimization
- A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth
- Hypodifferentials of nonsmooth convex functions and their applications to nonsmooth convex optimization
- Forward-backward algorithms for weakly convex problems
- Convergence rates of subgradient methods for quasi-convex optimization problems
This page was built for publication: Faster subgradient methods for functions with Hölderian growth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297653)
