RSG: Beating Subgradient Method without Smoothness and Strong Convexity

zbMATH Open1444.90092arXiv1512.03107MaRDI QIDQ4558142FDOQ4558142

Qihang Lin, Tianbao Yang

Publication date: 21 November 2018

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• Sparse inverse covariance estimation with the graphical lasso
• Primal-dual subgradient methods for convex problems
• Robust Stochastic Approximation Approach to Stochastic Programming
• Convex Analysis
• A coordinate gradient descent method for nonsmooth separable minimization
• 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
• Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
• Clarke Subgradients of Stratifiable Functions
• Error bounds in mathematical programming
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Global error bounds for piecewise convex polynomials
• Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms
• Finite termination of the proximal point algorithm
• Weak Sharp Minima in Mathematical Programming
• Weak Sharp Minima: Characterizations and Sufficient Conditions
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
• An optimal algorithm for stochastic strongly-convex optimization
• Error bounds and convergence analysis of feasible descent methods: A general approach
• On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Weak sharp minima revisited. II: Application to linear regularity and error bounds
• Hölder Metric Subregularity with Applications to Proximal Point Method
• Weak sharp minima revisited. III: Error bounds for differentiable convex inclusions
• Characterization of the equivalence of robustification and regularization in linear and matrix regression
• Second-order growth, tilt stability, and metric regularity of the subdifferential
• Higher-order metric subregularity and its applications
• Error bounds and Hölder metric subregularity
• On the Asymptotically Well Behaved Functions and Global Error Bound for Convex Polynomials
• On the convergence of the coordinate descent method for convex differentiable minimization
• Error Bounds for Convex Polynomials
• Robust Regression and Lasso
• Convergence Results for Projected Line-Search Methods on Varieties of Low-Rank Matrices Via Łojasiewicz Inequality
• From error bounds to the complexity of first-order descent methods for convex functions
• Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
• Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
• A unified approach to error bounds for structured convex optimization problems
• Learning with Submodular Functions: A Convex Optimization Perspective
• New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure
• ``Efficient” Subgradient Methods for General Convex Optimization
• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• An efficient primal dual prox method for non-smooth optimization
• Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity

Cited In (19)

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

Uses Software

• glasso

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• An aggregate subgradient method for nonsmooth and nonconvex minimization 👍 👎
• An approximate subgradient algorithm for unconstrained nonsmooth, nonconvex optimization 👍 👎
• Subgradient method for nonconvex nonsmooth optimization 👍 👎
• An aggregate subgradient methods for nonsmooth constrained minimization 👍 👎
• A Riemannian BFGS Method Without Differentiated Retraction for Nonconvex Optimization Problems 👍 👎
• Weak subgradient method for solving nonsmooth nonconvex optimization problems 👍 👎

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)