Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization

DOI10.1137/18M1192536MaRDI QIDQ5242931zbMATH OpenOpenAlexWikidataFDO

Authors Guanghui Lan, Yu Yang

Publication date 8 November 2019

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

accelerationfinite-sum optimizationmultiblock optimizationnonconvex optimizationstochastic algorithms

Mathematics Subject Classification ID

Numerical methods based on nonlinear programming (49M37) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26)

Abstract: In this paper, we present new stochastic methods for solving two important classes of nonconvex optimization problems. We first introduce a randomized accelerated proximal gradient (RapGrad) method for solving a class of nonconvex optimization problems consisting of the sum of $m$ component functions, and show that it can significantly reduce the number of gradient computations especially when the condition number $L/mu$ (i.e., the ratio between the Lipschitz constant and negative curvature) is large. More specifically, RapGrad can save up to $calO(sqrtm)$ gradient computations than existing deterministic nonconvex accelerated gradient methods. Moreover, the number of gradient computations required by RapGrad can be $calO(m^{f}rac16L^{f}rac12/m{u}^{f}rac12)$ (at least $calO(m^{f}rac23)$) times smaller than the best-known randomized nonconvex gradient methods when $L/mugem$. Inspired by RapGrad, we also develop a new randomized accelerated proximal dual (RapDual) method for solving a class of multi-block nonconvex optimization problems coupled with linear constraints. We demonstrate that RapDual can also save up to a factor of $calO(sqrtm)$ projection subproblems than its deterministic counterpart, where $m$ denotes the number of blocks. To the best of our knowledge, all these complexity results associated with RapGrad and RapDual seem to be new in the literature. We also illustrate potential advantages of these algorithms through our preliminary numerical experiments.

Recommendations

• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Block stochastic gradient iteration for convex and nonconvex optimization
• Accelerated methods for nonconvex optimization
• Accelerated stochastic algorithms for convex-concave saddle-point problems
• Accelerated stochastic variance reduction for a class of convex optimization problems
• An accelerated method for derivative-free smooth stochastic convex optimization
• Stochastic block mirror descent methods for nonsmooth and stochastic optimization
• A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization
• An inexact accelerated stochastic ADMM for separable convex optimization

Cites work

• A general theory of concave regularization for high-dimensional sparse estimation problems
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Accelerated methods for nonconvex optimization
• An introduction to statistical learning. With applications in R
• An optimal randomized incremental gradient method
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• Deep learning
• Generalized uniformly optimal methods for nonlinear programming
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Introductory lectures on convex optimization. A basic course.
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Nearly unbiased variable selection under minimax concave penalty
• Stochastic block mirror descent methods for nonsmooth and stochastic optimization
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties

Cited in

(11)

• Stochastic accelerated alternating direction method of multipliers with importance sampling
• Accelerated methods with fastly vanishing subgradients for structured non-smooth minimization
• Parallel sequential Monte Carlo for stochastic gradient-free nonconvex optimization
• Accelerated randomized mirror descent algorithms for composite non-strongly convex optimization
• Accelerated block-coordinate relaxation for regularized optimization
• A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming
• Random gradient extrapolation for distributed and stochastic optimization
• Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes
• Recent Theoretical Advances in Non-Convex Optimization
• First-order methods for nonsmooth nonconvex functional constrained optimization with or without Slater points
• A unified mini-batch stochastic accelerated method for nonconvex stochastic programming

Describes a project that uses

Uses Software

• NC-OPT
• ISLR

This page was built for publication: Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization

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