# Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 55 references that are in the map.
- First posted on arXiv 30 May 2022.

## Builds on (most cited first, 30 of 30)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond](https://mlsanity.com/paper/1908.02246/) (2019)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions](https://mlsanity.com/paper/1803.06600/) (2018)
- [Primal-dual accelerated gradient methods with small-dimensional relaxation oracle](https://mlsanity.com/paper/1809.05895/) (2018)
- [On Accelerated Methods for Saddle-Point Problems with Composite Structure](https://mlsanity.com/paper/2103.09344/) (2021)
- [Accelerated gradient sliding for structured convex optimization](https://mlsanity.com/paper/1609.04905/) (2016)
- [Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization](https://mlsanity.com/paper/1911.07363/) (2019)
- [Newton Method over Networks is Fast up to the Statistical Precision](https://mlsanity.com/paper/2102.06780/) (2021)
- [An Accelerated Second-Order Method for Distributed Stochastic Optimization](https://mlsanity.com/paper/2103.14392/) (2021)
- [Generalizing the optimized gradient method for smooth convex minimization](https://mlsanity.com/paper/1607.06764/) (2016)
- [Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization](https://mlsanity.com/paper/1911.10645/) (2019)
- [Oracle Complexity Separation in Convex Optimization](https://mlsanity.com/paper/2002.02706/) (2020)
- [Decentralized Personalized Federated Learning for Min-Max Problems](https://mlsanity.com/paper/2106.07289/) (2021)
- [Adaptive Third-Order Methods for Composite Convex Optimization](https://mlsanity.com/paper/2202.12730/) (2022)
- [On the Optimal Combination of Tensor Optimization Methods](https://mlsanity.com/paper/2002.01004/) (2020)
- [High-order methods beyond the classical complexity bounds, II: inexact high-order proximal-point methods with segment search](https://mlsanity.com/paper/2109.12303/) (2021)
- [Mirror-prox sliding methods for solving a class of monotone variational inequalities](https://mlsanity.com/paper/2111.00996/) (2021)

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

- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities](https://mlsanity.com/paper/2206.09446/) (2022)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Optimal Data Splitting in Distributed Optimization for Machine Learning](https://mlsanity.com/paper/2401.07809/) (2024)
- [Local Methods with Adaptivity via Scaling](https://mlsanity.com/paper/2406.00846/) (2024)
- [SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities](https://mlsanity.com/paper/2210.05994/) (2022)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums](https://mlsanity.com/paper/2606.15832/) (2026)

## Abstract (arXiv)

We study structured convex optimization problems, with additive objective r:=p + q, where r is (μ-strongly) convex, q is Lq-smooth and convex, and p is Lp-smooth, possibly nonconvex. For such a class of problems, we proposed an inexact accelerated gradient sliding method that can skip the gradient computation for one of these components while still achieving optimal complexity of gradient calls of p and q, that is, O(√Lp/μ) and O(√Lq/μ), respectively. This result is much sharper than the classic black-box complexity O(√(Lp+Lq)/μ), especially when the difference between Lq and Lq is large. We then apply the proposed method to solve distributed optimization problems over master-worker architectures, under agents' function similarity, due to statistical data similarity or otherwise. The distributed algorithm achieves for the first time lower complexity bounds on it both communication and local gradient calls, with the former having being a long-standing open problem. Finally the method is extended to distributed saddle-problems (under function similarity) by means of solving a class of variational inequalities, achieving lower communication and computation complexity bounds.