Federated Optimization of Smooth Loss Functions
IEEE Transactions on Information Theory · 2023-12 · 69 (12) · 7836-7866
DOI: 10.1109/tit.2023.3317168 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2023-12. Verfasst von Ali Jadbabaie und 2 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 95 Literaturangaben. Gefördert von: Office of Naval Research, Army Research Office (ARO) Multidisciplinary University Research Initiatives (MURI) program, National Science Foundation (NSF) Transdisciplinary Research In Principles Of Data Science (TRIPODS) under the Foundations of Data Science Institute.
Abstract (Originalsprache)
In this work, we study empirical risk minimization (ERM) within a federated learning framework, where a central server seeks to minimize an ERM objective function using $n$ samples of training data that is stored across $m$ clients and the server. The recent flurry of research in this area has identified the Federated Averaging ( $\mathtt{FedAve} $ ) algorithm as the staple for determining $\epsilon $ -approximate solutions to the ERM problem. Similar to standard optimization algorithms, e.g., stochastic gradient descent, the convergence analysis of $\mathtt{FedAve} $ and its variants only relies on smoothness of the loss function in the optimization parameter. However, loss functions are often very smooth in the training data too. To exploit this additional smoothness in data in a federated learning context, we propose the Federated Low Rank Gradient Descent (FedLRGD) algorithm. Since smoothness in data induces an approximate low rank structure on the gradient of the loss function, our algorithm first performs a few rounds of communication between the server and clients to learn weights that the server can use to approximate clients’ gradients using its own gradients. Then, our algorithm solves the ERM problem at the server using an inexact gradient descent method. To theoretically demonstrate that FedLRGD can have superior performance to $\mathtt{FedAve} $ , we present a notion of federated oracle complexity as a counterpart to canonical oracle complexity in the optimization literature. Under some assumptions on the loss function, e.g., strong convexity and smoothness in the parameter, $\eta $ -Hölder class smoothness in the data, etc., we prove that the federated oracle complexity of $LRGD $ scales like $\phi m (p/\epsilon)^{\Theta (d/\eta)}$ and that of $\mathtt{FedAve} $ scales like $\phi m (p / \epsilon)^{3/4}$ (neglecting typically sub-dominant factors), where $\phi \gg 1$ is the ratio of client-to-server communication time to gradient computation time, $p$ is the parameter dimension, and $d$ is the data dimension. Then, we show that when $d$ is small compared to $n$ and the loss function is sufficiently smooth in the data, i.e., $\eta = \Theta (d)$ , FedLRGD beats $\mathtt{FedAve} $ in federated oracle complexity. Finally, in the course of analyzing FedLRGD, we also establish a general result on low rank approximation of smooth latent variable models.
Förderung
- Office of Naval Research
- Army Research Office (ARO) Multidisciplinary University Research Initiatives (MURI) program
- National Science Foundation (NSF) Transdisciplinary Research In Principles Of Data Science (TRIPODS) under the Foundations of Data Science Institute
Zitieren
APA
Jadbabaie, A., Makur, A., & Shah, D. (2023). Federated Optimization of Smooth Loss Functions. IEEE Transactions on Information Theory, 69(12), 7836-7866. https://doi.org/10.1109/tit.2023.3317168
Vancouver
Jadbabaie A, Makur A, Shah D. Federated Optimization of Smooth Loss Functions. IEEE Transactions on Information Theory. 2023;69(12):7836-7866. doi:10.1109/tit.2023.3317168
BibTeX
@article{Jadbabaie2023,
author = {Jadbabaie, Ali and Makur, Anuran and Shah, Devavrat},
title = {Federated Optimization of Smooth Loss Functions},
journal = {IEEE Transactions on Information Theory},
year = {2023},
volume = {69},
number = {12},
pages = {7836--7866},
doi = {10.1109/tit.2023.3317168}
}
EUVIMED