Distributed and Stochastic Optimization Methods with Gradient Compression and Local Steps
This work addresses scalability and robustness issues in distributed machine learning, offering incremental advancements in optimization algorithms for large-scale and heterogeneous data settings.
The thesis tackled the problem of improving the efficiency and convergence of distributed and stochastic optimization methods by introducing new theoretical frameworks for error compensation and local updates, resulting in over 20 new methods with linear convergence and complexity bounds that outperform previous best-known results.
In this thesis, we propose new theoretical frameworks for the analysis of stochastic and distributed methods with error compensation and local updates. Using these frameworks, we develop more than 20 new optimization methods, including the first linearly converging Error-Compensated SGD and the first linearly converging Local-SGD for arbitrarily heterogeneous local functions. Moreover, the thesis contains several new distributed methods with unbiased compression for distributed non-convex optimization problems. The derived complexity results for these methods outperform the previous best-known results for the considered problems. Finally, we propose a new scalable decentralized fault-tolerant distributed method, and under reasonable assumptions, we derive the iteration complexity bounds for this method that match the ones of centralized Local-SGD.