A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting

Alexander Tyurin; Peter Richtárik

NeurIPS 2023poster6 citations

A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting

Abstract

We present a new method that includes three key components of distributed optimization and federated learning: variance reduction of stochastic gradients, partial participation, and compressed communication. We prove that the new method has optimal oracle complexity and state-of-the-art communication complexity in the partial participation setting. Regardless of the communication compression feature, our method successfully combines variance reduction and partial participation: we get the optimal oracle complexity, never need the participation of all nodes, and do not require the bounded gradients (dissimilarity) assumption.

Nonconvex OptimizationPartial ParticipationVariance ReductionCompressed CommunicationDistributed Optimization

BibTeX

@inproceedings{
tyurin2023a,
title={A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting},
author={Alexander Tyurin and Peter Richt{\'a}rik},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=loxinzXlCx}
}