Federated Frank-Wolfe Algorithm
This addresses the need for efficient, privacy-preserving algorithms in federated learning for constrained problems, particularly when projections are costly, representing an incremental improvement over existing methods.
The paper tackles the problem of constrained machine learning in federated learning by proposing a Federated Frank-Wolfe Algorithm (FedFW), which achieves an ε-suboptimal solution within O(ε⁻²) iterations for smooth convex objectives and O(ε⁻³) for smooth non-convex objectives, with empirical validation on multiple tasks.
Federated learning (FL) has gained a lot of attention in recent years for building privacy-preserving collaborative learning systems. However, FL algorithms for constrained machine learning problems are still limited, particularly when the projection step is costly. To this end, we propose a Federated Frank-Wolfe Algorithm (FedFW). FedFW features data privacy, low per-iteration cost, and communication of sparse signals. In the deterministic setting, FedFW achieves an $\varepsilon$-suboptimal solution within $O(\varepsilon^{-2})$ iterations for smooth and convex objectives, and $O(\varepsilon^{-3})$ iterations for smooth but non-convex objectives. Furthermore, we present a stochastic variant of FedFW and show that it finds a solution within $O(\varepsilon^{-3})$ iterations in the convex setting. We demonstrate the empirical performance of FedFW on several machine learning tasks.