Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization
The ProxSkip algorithm for distributed optimization is gaining increasing attention due to its proven benefits in accelerating communication complexity while maintaining robustness against data heterogeneity. However, existing analyses of ProxSkip are limited to the strongly convex setting and do not achieve linear speedup, where convergence performance increases linearly with respect to the number of nodes. So far, questions remain open about how ProxSkip behaves in the non-convex setting and whether linear speedup is achievable. In this paper, we revisit distributed ProxSkip and address both questions. We demonstrate that the leading communication complexity of ProxSkip is $\mathcal{O}(\frac{p\sigma^2}{n\epsilon^2})$ for non-convex and convex settings, and $\mathcal{O}(\frac{p\sigma^2}{n\epsilon})$ for the strongly convex setting, where $n$ represents the number of nodes, $p$ denotes the probability of communication, $\sigma^2$ signifies the level of stochastic noise, and $\epsilon$ denotes the desired accuracy level. This result illustrates that ProxSkip achieves linear speedup and can asymptotically reduce communication overhead proportional to the probability of communication. Additionally, for the strongly convex setting, we further prove that ProxSkip can achieve linear speedup with network-independent stepsizes.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationFederated LearningStochastic OptimizationSimilar Papers 제목 키워드 기반
Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning
We study distributed optimization methods based on the {\em local training (LT)} paradigm: achieving communication efficiency by performing richer local gradient-based training on the clients before parameter averaging. …
Distributed OptimizationFederated LearningSparse-ProxSkip: Accelerated Sparse-to-Sparse Training in Federated Learning
In Federated Learning (FL), both client resource constraints and communication costs pose major problems for training large models. In the centralized setting, sparse training addresses resource constraints, while in the…
Federated LearningFaster Distributed Deep Net Training: Computation and Communication Decoupled Stochastic Gradient Descent
With the increase in the amount of data and the expansion of model scale, distributed parallel training becomes an important and successful technique to address the optimization challenges. Nevertheless, although distrib…
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
Recent developments on large-scale distributed machine learning applications, e.g., deep neural networks, benefit enormously from the advances in distributed non-convex optimization techniques, e.g., distributed Stochast…
BIG-bench Machine LearningAchieving Linear Speedup in Decentralized Stochastic Compositional Minimax Optimization
The stochastic compositional minimax problem has attracted a surge of attention in recent years since it covers many emerging machine learning models. Meanwhile, due to the emergence of distributed data, optimizing this …
imbalanced classification