Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity

Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, Gesualdo Scutari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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 Lpsmooth, 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, (Equation presented) and (Equation presented), respectively. This result is much sharper than the classic black-box complexity (Equation presented), especially when the difference between Lp 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 both communication and local gradient calls, with the former having being a longstanding 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.
Original languageEnglish (US)
Title of host publication36th Conference on Neural Information Processing Systems, NeurIPS 2022
PublisherNeural information processing systems foundation
ISBN (Print)9781713871088
StatePublished - Jan 1 2022


Dive into the research topics of 'Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity'. Together they form a unique fingerprint.

Cite this