# Gradient Sliding for Composite Optimization

arXiv: https://arxiv.org/abs/1406.0919 · HTML: https://mlsanity.com/paper/1406.0919/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2014.

## Built on by (most cited first, 14 of 14)

- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm](https://mlsanity.com/paper/2106.11577/) (2021)
- [Decentralized Personalized Federated Learning for Min-Max Problems](https://mlsanity.com/paper/2106.07289/) (2021)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Optimal Methods for Convex Risk Averse Distributed Optimization](https://mlsanity.com/paper/2203.05117/) (2022)
- [Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers](https://mlsanity.com/paper/2410.01979/) (2024)
- [An Optimal Algorithm for Strongly Convex Min-min Optimization](https://mlsanity.com/paper/2212.14439/) (2022)
- [Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity](https://mlsanity.com/paper/2405.16126/) (2024)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems](https://mlsanity.com/paper/2601.08614/) (2026)

## Abstract (arXiv)

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 cal O(1/√ε) gradient evaluations for the smooth component in order to find an ε-solution for the composite problem, while still maintaining the optimal cal O(1/ε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 cal O (log (1/ε)) and cal O(1/ε), 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.