Gradient Tracking for High Dimensional Federated Optimization

Abstract

In this paper, we study the (decentralized) distributed optimization problem with high-dimensional sparse structure. Building upon the FedDA algorithm, we propose a (Decentralized) FedDA-GT algorithm, which combines the \textbf{gradient tracking} technique. It is able to eliminate the heterogeneity among different clients' objective functions while ensuring a dimension-free convergence rate. Compared to the vanilla FedDA approach, (D)FedDA-GT can significantly reduce the communication complexity, from $O(s^2\log d/{\epsilon }^{3/2})$ to a more efficient $O(s^2\log d/\epsilon )$. In cases where strong convexity is applicable, we introduce a multistep mechanism resulting in the Multistep ReFedDA-GT algorithm, a minor modified version of FedDA-GT. This approach achieves an impressive communication complexity of $O\left(s\log d\log \frac{1}{\epsilon }\right)$ through repeated calls to the ReFedDA-GT algorithm. Finally, we conduct numerical experiments, illustrating that our proposed algorithms enjoy the dual advantage of being dimension-free and heterogeneity-free.