Provable Reduction in Communication Rounds for Non-Smooth Convex Federated Learning
This addresses communication bottlenecks in federated learning for distributed systems, providing theoretical guarantees where they were previously lacking, though it appears incremental as it builds on projection-efficient methods.
The paper tackles the problem of communication efficiency in federated learning for non-smooth convex problems without data heterogeneity assumptions, proposing FedMLS which achieves an ε-suboptimal solution in O(1/ε) communication rounds with O(1/ε²) stochastic subgradient calls.
Multiple local steps are key to communication-efficient federated learning. However, theoretical guarantees for such algorithms, without data heterogeneity-bounding assumptions, have been lacking in general non-smooth convex problems. Leveraging projection-efficient optimization methods, we propose FedMLS, a federated learning algorithm with provable improvements from multiple local steps. FedMLS attains an $ε$-suboptimal solution in $\mathcal{O}(1/ε)$ communication rounds, requiring a total of $\mathcal{O}(1/ε^2)$ stochastic subgradient oracle calls.