RSG: Beating Subgradient Method without Smoothness and Strong Convexity

zbMATH Open1444.90092MaRDI QIDQ4558142FDOQ4558142

Authors Tianbao Yang, Qihang Lin

Publication date 21 November 2018

Full work available at URL https://arxiv.org/abs/1512.03107

zbMATH Keywords

machine learningsubgradient methodlocal error boundimproved convergence

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25)

Abstract: In this paper, we study the efficiency of a {�f R}estarted {�f S}ub{�f G}radient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an $epsilon$-optimal solution with a lower complexity than the SG method. In particular, we first show that RSG can reduce the dependence of SG's iteration complexity on the distance between the initial solution and the optimal set to that between the $epsilon$-level set and the optimal set {multiplied by a logarithmic factor}. Moreover, we show the advantages of RSG over SG in solving three different families of convex optimization problems. (a) For the problems whose epigraph is a polyhedron, RSG is shown to converge linearly. (b) For the problems with local quadratic growth property in the $epsilon$-sublevel set, RSG has an $O(frac1epsilonlog(frac1epsilon))$ iteration complexity. (c) For the problems that admit a local Kurdyka-L ojasiewicz property with a power constant of $$, RSG has an $$ iteration complexity. The novelty of our analysis lies at exploiting the lower bound of the first-order optimality residual at the $epsilon$-level set. It is this novelty that allows us to explore the local properties of functions (e.g., local quadratic growth property, local Kurdyka-L ojasiewicz property, more generally local error bound conditions) to develop the improved convergence of RSG. { We also develop a practical variant of RSG enjoying faster convergence than the SG method, which can be run without knowing the involved parameters in the local error bound condition.} We demonstrate the effectiveness of the proposed algorithms on several machine learning tasks including regression, classification and matrix completion.

Recommendations

• A subgradient method for unconstrained nonconvex nonsmooth optimization
• An approximate subgradient algorithm for unconstrained nonsmooth, nonconvex optimization
• Subgradient method for nonconvex nonsmooth optimization
• scientific article; zbMATH DE number 3910168
• Weak subgradient method for solving nonsmooth nonconvex optimization problems
• An aggregate subgradient method for nonsmooth and nonconvex minimization
• Publication:3471857
• A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems
• scientific article; zbMATH DE number 727769
• An aggregate subgradient methods for nonsmooth constrained minimization

Cites work

• scientific article; zbMATH DE number 6378119 (Why is no real title available?)
• scientific article; zbMATH DE number 4015993 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 3232960 (Why is no real title available?)
• scientific article; zbMATH DE number 3304564 (Why is no real title available?)
• A coordinate gradient descent method for nonsmooth separable minimization
• A unified approach to error bounds for structured convex optimization problems
• An efficient primal dual prox method for non-smooth optimization
• Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
• Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
• Characterization of metric regularity of subdifferentials
• Characterization of the equivalence of robustification and regularization in linear and matrix regression
• Clarke Subgradients of Stratifiable Functions
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality
• Convex Analysis
• Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
• Error Bounds for Convex Polynomials
• Error bounds and Hölder metric subregularity
• Error bounds and convergence analysis of feasible descent methods: A general approach
• Error bounds in mathematical programming
• Error bounds, quadratic growth, and linear convergence of proximal methods
• 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
• From error bounds to the complexity of first-order descent methods for convex functions
• Global error bounds for piecewise convex polynomials
• Higher-order metric subregularity and its applications
• Hölder metric subregularity with applications to proximal point method
• Introductory lectures on convex optimization. A basic course.
• Learning with submodular functions: a convex optimization perspective
• Local strong convexity and local Lipschitz continuity of the gradient of convex functions
• New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure
• Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity
• On the Asymptotically Well Behaved Functions and Global Error Bound for Convex Polynomials
• On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
• On the convergence of the coordinate descent method for convex differentiable minimization
• Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
• Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
• Primal-dual subgradient methods for convex problems
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
• Robust Regression and Lasso
• Robust Stochastic Approximation Approach to Stochastic Programming
• Second-order growth, tilt stability, and metric regularity of the subdifferential
• Smooth minimization of non-smooth functions
• Sparse inverse covariance estimation with the graphical lasso
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Weak Sharp Minima in Mathematical Programming
• Weak Sharp Minima: Characterizations and Sufficient Conditions
• Weak sharp minima revisited. I: Basic theory
• Weak sharp minima revisited. II: Application to linear regularity and error bounds
• Weak sharp minima revisited. III: Error bounds for differentiable convex inclusions
• ``Efficient subgradient methods for general convex optimization

Cited in

(19)

• Stochastic algorithms with geometric step decay converge linearly on sharp functions
• Randomized smoothing variance reduction method for large-scale non-smooth convex optimization
• General convergence analysis of stochastic first-order methods for composite optimization
• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• General Hölder smooth convergence rates follow from specialized rates assuming growth bounds
• Subgradient methods for sharp weakly convex functions
• A simple nearly optimal restart scheme for speeding up first-order methods
• Faster first-order primal-dual methods for linear programming using restarts and sharpness
• The geometric median and applications to robust mean estimation
• Distributed accelerated gradient methods with restart under quadratic growth condition
• Faster subgradient methods for functions with Hölderian growth
• New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
• Mini-batch stochastic subgradient for functional constrained optimization
• On finite termination of an inexact proximal point algorithm
• The method of codifferential descent for convex and global piecewise affine optimization
• Radial duality. II: Applications and algorithms
• The gradient projection algorithm for a proximally smooth set and a function with Lipschitz continuous gradient
• On optimal universal first-order methods for minimizing heterogeneous sums
• Accelerate stochastic subgradient method by leveraging local growth condition

Describes a project that uses

Uses Software

• glasso

This page was built for publication: RSG: Beating Subgradient Method without Smoothness and Strong Convexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558142)