Gradient sliding for composite optimization

DOI10.1007/S10107-015-0955-5MaRDI QIDQ312670zbMATH OpenOpenAlexFDO

Authors Guanghui Lan

Publication date 16 September 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

complexityconvex programmingdata analysisgradient slidingNesterov's method

Mathematics Subject Classification ID

Numerical methods based on nonlinear programming (49M37) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22) Convex programming (90C25)

Abstract: We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the computation of the gradient for the smooth component from time to time. As a consequence, these algorithms require only $calO(1/sqrtepsilon)$ gradient evaluations for the smooth component in order to find an $epsilon$-solution for the composite problem, while still maintaining the optimal $calO(1/epsilo{n}^2)$ bound on the total number of subgradient evaluations for the nonsmooth component. We then present a stochastic counterpart for these algorithms and establish similar complexity bounds for solving an important class of stochastic composite optimization problems. Moreover, if the smooth component in the composite function is strongly convex, the developed gradient sliding algorithms can significantly reduce the number of graduate and subgradient evaluations for the smooth and nonsmooth component to $calO(log(1/epsilon))$ and $calO(1/epsilon)$, respectively. Finally, we generalize these algorithms to the case when the smooth component is replaced by a nonsmooth one possessing a certain bi-linear saddle point structure.

Recommendations

• Accelerated gradient sliding for structured convex optimization
• Gradient methods for minimizing composite functions
• A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization
• A smoothing stochastic gradient method for composite optimization
• Conditional gradient sliding for convex optimization

Cites work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Accelerated and inexact forward-backward algorithms
• An optimal method for stochastic composite optimization
• Bregman Monotone Optimization Algorithms
• scientific article; zbMATH DE number 6253954 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• Introductory lectures on convex optimization. A basic course.
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
• Proximal Minimization Methods with Generalized Bregman Functions
• Smooth minimization of non-smooth functions
• Solving variational inequalities with stochastic mirror-prox algorithm
• Sparsity and Smoothness Via the Fused Lasso
• Tensor Decompositions and Applications
• Validation analysis of mirror descent stochastic approximation method

Cited in

(29)

• Combining search directions using gradient flows
• Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
• Oracle complexity separation in convex optimization
• Accelerated gradient sliding for structured convex optimization
• A multi-step doubly stabilized bundle method for nonsmooth convex optimization
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Accelerated gradient sliding for minimizing a sum of functions
• Communication-efficient algorithms for decentralized and stochastic optimization
• Conditional gradient sliding for convex optimization
• A smoothing stochastic gradient method for composite optimization
• New results on subgradient methods for strongly convex optimization problems with a unified analysis
• Gradient methods for minimizing composite functions
• Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints
• Efficient algorithms for distributionally robust stochastic optimization with discrete scenario support
• Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation
• Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm
• Stochastic conditional gradient++: (Non)convex minimization and continuous submodular maximization
• On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
• A multilevel proximal gradient algorithm for a class of composite optimization problems
• A dual approach for optimal algorithms in distributed optimization over networks
• Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
• Universal Conditional Gradient Sliding for Convex Optimization
• Optimal Methods for Convex Risk-Averse Distributed Optimization
• Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
• Recent theoretical advances in decentralized distributed convex optimization
• Complementary composite minimization, small gradients in general norms, and applications
• One-point feedback for composite optimization with applications to distributed and federated learning
• Optimal methods for convex nested stochastic composite optimization
• Dual smoothing for decentralized optimization

This page was built for publication: Gradient sliding for composite optimization

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