Accelerate stochastic subgradient method by leveraging local growth condition

DOI10.1142/S0219530519400050MaRDI QIDQ5236746zbMATH OpenOpenAlexWikidataFDO

Authors Yi Xu, Qihang Lin, Tianbao Yang

Publication date 10 October 2019

Published in Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationlocal growth conditionstochastic subgradient

Mathematics Subject Classification ID

Applications of stochastic analysis (to PDEs, etc.) (60H30) Stochastic programming (90C15) Convex programming (90C25)

Abstract: In this paper, a new theory is developed for first-order stochastic convex optimization, showing that the global convergence rate is sufficiently quantified by a local growth rate of the objective function in a neighborhood of the optimal solutions. In particular, if the objective function $F(mathbfw)$ in the $epsilon$-sublevel set grows as fast as $|mathbfw-mathbf{w}_{\ast }{|}_2^{1/heta}$, where $mathbf{w}_{\ast }$ represents the closest optimal solution to $mathbfw$ and $hetain(0,1]$ quantifies the local growth rate, the iteration complexity of first-order stochastic optimization for achieving an $epsilon$-optimal solution can be $widetildeO(1/epsilo{n}^{2(1-heta)})$, which is optimal at most up to a logarithmic factor. To achieve the faster global convergence, we develop two different accelerated stochastic subgradient methods by iteratively solving the original problem approximately in a local region around a historical solution with the size of the local region gradually decreasing as the solution approaches the optimal set. Besides the theoretical improvements, this work also includes new contributions towards making the proposed algorithms practical: (i) we present practical variants of accelerated stochastic subgradient methods that can run without the knowledge of multiplicative growth constant and even the growth rate $heta$; (ii) we consider a broad family of problems in machine learning to demonstrate that the proposed algorithms enjoy faster convergence than traditional stochastic subgradient method. We also characterize the complexity of the proposed algorithms for ensuring the gradient is small without the smoothness assumption.

Recommendations

• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity
• scientific article; zbMATH DE number 5221408
• Faster subgradient methods for functions with Hölderian growth
• Convergence rate analysis of projected stochastic subgradient method using conjugate gradient-like direction

Cites work

• A proximal stochastic gradient method with progressive variance reduction
• A unified approach to error bounds for structured convex optimization problems
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• An efficient primal dual prox method for non-smooth optimization
• Are Loss Functions All the Same?
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Classification with a reject option using a hinge loss
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Convergence rates of kernel conjugate gradient for random design regression
• Convex analysis and monotone operator theory in Hilbert spaces
• Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
• Dual averaging methods for regularized stochastic learning and online optimization
• Error bounds and convergence analysis of feasible descent methods: A general approach
• Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
• From error bounds to the complexity of first-order descent methods for convex functions
• Global error bounds for piecewise convex polynomials
• scientific article; zbMATH DE number 6378119 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Linear convergence of first order methods for non-strongly convex optimization
• Local strong convexity and local Lipschitz continuity of the gradient of convex functions
• Monotone Operators and the Proximal Point Algorithm
• On the convergence of the coordinate descent method for convex differentiable minimization
• On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
• Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• Stochastic model-based minimization of weakly convex functions
• The optimal L_pnorm estimator in linear regression models
• The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Thresholded spectral algorithms for sparse approximations
• Validation analysis of mirror descent stochastic approximation method

Cited in

(4)

• Adaptivity of stochastic gradient methods for nonconvex optimization
• On the adaptivity of stochastic gradient-based optimization
• Adaptive restart of accelerated gradient methods under local quadratic growth condition
• scientific article; zbMATH DE number 5221408 (Why is no real title available?)

Describes a project that uses

Uses Software

• Saga

This page was built for publication: Accelerate stochastic subgradient method by leveraging local growth condition

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