Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization
Grigory Malinovsky
cs.LG, math.OC
Submitted: 2026-08-06
Updated: 2026-08-10
Comments: thesis, 7 chapters
Code: https://github.com/sunildkumar/lora_from_scratch
License: http://creativecommons.org/licenses/by/4.0/
The gist: Machine learning and optimization have advanced together, with practical demands motivating new theory and theoretical breakthroughs enabling new applications.
Terminology
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.
Sources
- Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation
- Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning
- On the Convergence of SGD with Biased Gradients
- Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates
- Distributed Deep Learning Using Volunteer Computing-Like Paradigm
- signSGD with Majority Vote is Communication Efficient And Fault Tolerant
- LoRA Learns Less and Forgets Less
- On the Outsized Importance of Learning Rates in Local Update Methods
- On Large-Cohort Training for Federated Learning
- Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
- MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization
- RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates
- Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
- TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participation
- MAST: Model-Agnostic Sparsified Training
- Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction
- Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization
- EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback
- Secure Distributed Training at Scale
- Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks