We study the problem of minimizing the expectation of smooth nonconvex functions with the help of several parallel workers whose role is to compute stochastic gradients. In particular, we focus on the challenging situation where the workers’ compute times are arbitrarily heterogeneous and random. In the simpler regime characterized by arbitrarily heterogeneous but deterministic compute times, Tyurin and Richtárik (NeurIPS 2023) recently designed the first theoretically optimal asynchronous SGD method, called Rennala SGD, in terms of a novel complexity notion called time complexity. The starting point of our work is the observation that Rennala SGD can have arbitrarily bad performance in the presence of random compute times – a setting it was not designed to handle. To advance our understanding of stochastic optimization in this challenging regime, we propose a new asynchronous SGD method, for which we coin the name MindFlayer SGD. Our theory and empirical results demonstrate the superiority of MindFlayer SGD over existing baselines, including Rennala SGD, in cases when the noise is heavy tailed.
@article{maranjyan2024mindflayer,title={MindFlayer: Efficient Asynchronous Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times},author={Maranjyan, Artavazd and Omar, Omar Shaikh and Richt{\'a}rik, Peter},journal={arXiv preprint arXiv:2410.04285},url={https://arxiv.org/abs/2410.04285},year={2024}}
LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression
Laurent Condat, Artavazd Maranjyan, and Peter Richtárik
In Distributed optimization and Learning, and even more in the modern framework of federated learning, communication, which is slow and costly, is critical. We introduce LoCoDL, a communication-efficient algorithm that leverages the two popular and effective techniques of Local training, which reduces the communication frequency, and Compression, in which short bitstreams are sent instead of full-dimensional vectors of floats. LoCoDL works with a large class of unbiased compressors that includes widely-used sparsification and quantization methods. LoCoDL provably benefits from local training and compression and enjoys a doubly-accelerated communication complexity, with respect to the condition number of the functions and the model dimension, in the general heterogenous regime with strongly convex functions. This is confirmed in practice, with LoCoDL outperforming existing algorithms.
@article{condat2024locodl,title={LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression},author={Condat, Laurent and Maranjyan, Artavazd and Richt{\'a}rik, Peter},journal={arXiv preprint arXiv:2403.04348},year={2024},}
2023
Menshov-Type Theorem for Divergence Sets of Sequences of Localized Operators
Martin Grigoryan, Anna Kamont, and Artavazd Maranjyan
Journal of Contemporary Mathematical Analysis (Armenian Academy of Sciences), 2023
@article{grigoryan2023menshov,title={Menshov-Type Theorem for Divergence Sets of Sequences of Localized Operators},journal={Journal of Contemporary Mathematical Analysis (Armenian Academy of Sciences)},author={Grigoryan, Martin and Kamont, Anna and Maranjyan, Artavazd},volume={58},number={2},pages={81--92},year={2023},publisher={Springer}}
2022
Gradskip: Communication-accelerated local gradient methods with better computational complexity
Artavazd Maranjyan, Mher Safaryan, and Peter Richtárik
We study a class of distributed optimization algorithms that aim to alleviate high communication costs by allowing clients to perform multiple local gradient-type training steps prior to communication. In a recent breakthrough, Mishchenko et al. (2022) proved that local training, when properly executed, leads to provable communication acceleration, and this holds in the strongly convex regime without relying on any data similarity assumptions. However, their ProxSkip method requires all clients to take the same number of local training steps in each communication round. We propose a redesign of the original ProxSkip method, allowing clients with “less important” data to get away with fewer local training steps without impacting the overall communication complexity of the method. In particular, we prove that our modified method, GradSkip, converges linearly under the same assumptions and has the same accelerated communication complexity, while the number of local gradient steps can be reduced relative to a local condition number. We further generalize our method by extending the randomness of probabilistic alternations to arbitrary unbiased compression operators and by considering a generic proximable regularizer. This generalization, which we call GradSkip+, recovers several related methods in the literature as special cases. Finally, we present an empirical study on carefully designed toy problems that confirm our theoretical claims.
@article{maranjyan2022gradskip,title={Gradskip: Communication-accelerated local gradient methods with better computational complexity},author={Maranjyan, Artavazd and Safaryan, Mher and Richt{\'a}rik, Peter},journal={arXiv preprint arXiv:2210.16402},url={https://arxiv.org/abs/2210.16402},year={2022},}
2021
On the divergence of Fourier series in the general Haar system
@article{grigoryan2021divergence,title={On the divergence of Fourier series in the general Haar system},author={Grigoryan, Martin and Maranjyan, Artavazd},journal={Armenian Journal of Mathematics},volume={13},number={6},pages={1--10},year={2021}}
ON THE UNCONDITIONAL CONVERGENCE OF FABER-SCHAUDER SERIES IN L\^{1}
Tigran M Grigoryan, and Artavazd Maranjyan
Proceedings of the YSU A: Physical and Mathematical Sciences, 2021
@article{grigoryan2021unconditional,title={ON THE UNCONDITIONAL CONVERGENCE OF FABER-SCHAUDER SERIES IN $ L\^{}$\{$1$\}$ $},author={Grigoryan, Tigran M and Maranjyan, Artavazd},journal={Proceedings of the YSU A: Physical and Mathematical Sciences},volume={55},number={1 (254)},pages={12--19},year={2021}}