TL;DR
This paper introduces DEPOSITUM, a novel algorithm for decentralized federated learning (DFL) that tackles complex, non-convex optimization problems with non-smooth components. By combining gradient tracking with momentum, DEPOSITUM effectively handles data heterogeneity, reduces communication overhead through local updates, and achieves theoretical guarantees for convergence and linear speedup, outperforming existing methods in experiments.
What Problem Does This Paper Address?
Traditional federated learning (FL) relies on a central server to coordinate model training across clients. This creates a single point of failure and a potential communication bottleneck. Decentralized FL (DFL) aims to overcome these limitations by allowing clients to communicate directly with their neighbors. However, many real-world machine learning tasks involve objective functions that are not only non-convex but also include non-smooth regularization terms (e.g., for sparsity). Solving these "non-convex composite optimization problems" in a decentralized setting (DNCFL) is a challenging and underexplored area. Existing DFL methods often struggle with data heterogeneity (where client data distributions differ significantly), leading to "client drift" and slower convergence.
Methods
DEPOSITUM builds upon proximal stochastic gradient tracking (DSGT) to address DNCFL. Key innovations include:
- Gradient Tracking: Clients use a tracking variable to approximate the global gradient, mitigating the impact of data heterogeneity without requiring strong assumptions about data distribution.
- Momentum Integration: The algorithm incorporates momentum (either Polyak's or Nesterov's) into the proximal gradient descent step. This helps reduce the variance introduced by stochastic gradients, leading to faster convergence and improved stability.
- Local Updates: DEPOSITUM supports multiple local client updates between communication rounds. This significantly reduces the communication burden, a critical factor in large-scale distributed systems.
- Proximal Operator: The algorithm is designed to handle non-smooth, weakly convex regularization terms by leveraging their proximal operators.
The theoretical analysis shows that DEPOSITUM can achieve an expected $\epsilon$-stationary point with $\mathcal{O}(1/\epsilon^2)$ iteration complexity and that consensus and gradient estimation errors decrease at a sublinear rate of $\mathcal{O}(1/T)$. Crucially, with appropriate parameter tuning, it can achieve network-independent linear speedup.
Datasets
The paper evaluates DEPOSITUM on several standard datasets:
- A9A
- MNIST
- Extended MNIST (EMNIST)
- Fashion MNIST (FMNIST)
- CIFAR-10
These datasets cover various data formats, including tabular, grayscale images, and color images, and are used with different model architectures.
Key Insights and Ideas
- DFL for Non-Convex Composite Problems is Crucial: The paper highlights that many practical ML problems fall into the DNCFL category, making this research highly relevant.
- Momentum and Gradient Tracking are a Powerful Combination: By synergistically combining these two techniques, DEPOSITUM effectively tackles both data heterogeneity and the variance of stochastic gradients.
- Local Updates are Key for Efficiency: The ability to perform multiple local updates before communication is essential for reducing communication costs in decentralized settings.
- Theoretical Guarantees are Achievable: The paper provides strong theoretical backing for DEPOSITUM's convergence and speedup, which is vital for practical deployment.
- Network Topology Matters, but Less Than Expected: While a complete graph offers theoretical advantages, the experimental results suggest that DEPOSITUM performs well across different topologies, demonstrating robustness.
Key Results
- Convergence: DEPOSITUM achieves an expected $\epsilon$-stationary point with $\mathcal{O}(1/\epsilon^2)$ iteration complexity. Consensus and gradient estimation errors decrease at a sublinear rate of $\mathcal{O}(1/T)$.
- Linear Speedup: With proper parameter selection, DEPOSITUM can achieve network-independent linear speedup, meaning convergence improves proportionally with the number of clients.
- Experimental Performance: DEPOSITUM consistently outperforms baseline decentralized FL algorithms (FedMiD, FedDR, FedADMM) across various datasets, models, and data distributions, achieving higher accuracy. The paper demonstrates the impact of hyperparameters like step size and momentum, showing that momentum generally improves performance.
Limitations and Future Work
- Theoretical Assumptions: While DEPOSITUM relaxes assumptions on data heterogeneity compared to some prior work, it still relies on L-smoothness for local functions and p-weakly convexity for the non-smooth term.
- Parameter Tuning: Achieving optimal performance, particularly linear speedup, requires careful tuning of parameters like step sizes ($\alpha$, $\beta$) and momentum coefficients ($\gamma$).
- Future Work: The authors suggest integrating advanced security mechanisms and developing privacy-preserving and Byzantine-resilient variants of the algorithm. Exploring more general non-convexity conditions and asynchronous updates could also be promising directions.
Summary updated