Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization

arXiv cs.LG Papers
distributed-optimization federated-learning communication-efficiency optimization-theory arxiv

Summary

This thesis tackles seven challenges in distributed and federated optimization, introducing methods like ProxSkip and Variance Reduced ProxSkip, and establishing theoretical foundations for communication-efficient, robust, and practical algorithms.

arXiv:2608.06563v1 Announce Type: new Abstract: Machine learning and optimization have advanced together, with practical demands motivating new theory and theoretical breakthroughs enabling new applications. Modern large-scale training relies on classical optimization principles, but the constraints of distributed systems require these foundations to be reconsidered. This thesis addresses seven challenges at the intersection of theory and practice, focusing on key bottlenecks in federated learning and distributed optimization. First, we introduce ProxSkip and prove that local gradient steps can accelerate communication, providing a theoretical foundation for this widely used heuristic. Second, we develop Variance Reduced ProxSkip, which eliminates the neighborhood error of stochastic local updates while balancing communication and local computation. Third, we show that local steps retain their communication acceleration under partial client participation. Fourth, we prove that server-side stepsizes and sampling without replacement improve convergence in heterogeneous settings. Fifth, for Random Reshuffling, we demonstrate that compressing gradient differences rather than gradients yields better theoretical and practical performance. Sixth, we establish that Byzantine robustness and partial participation can be achieved simultaneously using gradient-difference clipping. Finally, we develop the first theoretical framework for low-rank adaptation based on randomized asymmetric chains, providing new insights into fine-tuning large models. Across these contributions, we introduce novel algorithmic frameworks, establish sharp guarantees under realistic assumptions, and support the theory with numerical experiments.
Original Article
View Cached Full Text

Cached at: 08/10/26, 08:02 AM 

# Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization
Source: [https://arxiv.org/abs/2608.06563](https://arxiv.org/abs/2608.06563)
[View PDF](https://arxiv.org/pdf/2608.06563)

> Abstract:Machine learning and optimization have advanced together, with practical demands motivating new theory and theoretical breakthroughs enabling new applications\. Modern large\-scale training relies on classical optimization principles, but the constraints of distributed systems require these foundations to be reconsidered\. This thesis addresses seven challenges at the intersection of theory and practice, focusing on key bottlenecks in federated learning and distributed optimization\. First, we introduce ProxSkip and prove that local gradient steps can accelerate communication, providing a theoretical foundation for this widely used heuristic\. Second, we develop Variance Reduced ProxSkip, which eliminates the neighborhood error of stochastic local updates while balancing communication and local computation\. Third, we show that local steps retain their communication acceleration under partial client participation\. Fourth, we prove that server\-side stepsizes and sampling without replacement improve convergence in heterogeneous settings\. Fifth, for Random Reshuffling, we demonstrate that compressing gradient differences rather than gradients yields better theoretical and practical performance\. Sixth, we establish that Byzantine robustness and partial participation can be achieved simultaneously using gradient\-difference clipping\. Finally, we develop the first theoretical framework for low\-rank adaptation based on randomized asymmetric chains, providing new insights into fine\-tuning large models\. Across these contributions, we introduce novel algorithmic frameworks, establish sharp guarantees under realistic assumptions, and support the theory with numerical experiments\.

## Submission history

From: Grigory Malinovsky \[[view email](https://arxiv.org/show-email/de962595/2608.06563)\] **\[v1\]**Thu, 6 Aug 2026 20:20:52 UTC \(8,021 KB\)

Similar Articles