# Federated Optimization of Smooth Loss Functions

arXiv: https://arxiv.org/abs/2201.01954 · HTML: https://mlsanity.com/paper/2201.01954/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 108 references that are in the map.
- First posted on arXiv 6 Jan 2022.

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Prevalence of Neural Collapse during the terminal phase of deep learning training](https://mlsanity.com/paper/2008.08186/) (2020)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Empirical Analysis of the Hessian of Over-Parametrized Neural Networks](https://mlsanity.com/paper/1706.04454/) (2017)
- [Gradient Descent Happens in a Tiny Subspace](https://mlsanity.com/paper/1812.04754/) (2018)
- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [One-Shot Federated Learning](https://mlsanity.com/paper/1902.11175/) (2019)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization](https://mlsanity.com/paper/1908.09375/) (2019)
- [Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity](https://mlsanity.com/paper/2012.14453/) (2020)
- [Federated Learning with Only Positive Labels](https://mlsanity.com/paper/2004.10342/) (2020)
- [Analytic Insights into Structure and Rank of Neural Network Hessian Maps](https://mlsanity.com/paper/2106.16225/) (2021)
- [Dissecting Hessian: Understanding Common Structure of Hessian in Neural Networks](https://mlsanity.com/paper/2010.04261/) (2020)
- [Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization](https://mlsanity.com/paper/1805.10222/) (2018)
- [Estimating network edge probabilities by neighborhood smoothing](https://mlsanity.com/paper/1509.08588/) (2015)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [On Robustness of Principal Component Regression](https://mlsanity.com/paper/1902.10920/) (2019)
- [Faster On-Device Training Using New Federated Momentum Algorithm](https://mlsanity.com/paper/2002.02090/) (2020)
- [Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation](https://mlsanity.com/paper/2006.06135/) (2020)
- [Balancing Communication and Computation in Distributed Optimization](https://mlsanity.com/paper/1709.02999/) (2017)
- [Low-rank Gradient Approximation For Memory-Efficient On-device Training of Deep Neural Network](https://mlsanity.com/paper/2001.08885/) (2020)
- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)

## Built on by (most cited first, 6 of 6)

- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [Byzantine-Robust Federated Linear Bandits](https://mlsanity.com/paper/2204.01155/) (2022)
- [Communication-Efficient Federated Low-Rank Update Algorithm and its Connection to Implicit Regularization](https://mlsanity.com/paper/2409.12371/) (2024)
- [Gradient Descent for Low-Rank Functions](https://mlsanity.com/paper/2206.08257/) (2022)
- [Byzantine-Robust and Communication-Efficient Distributed Training: Compressive and Cyclic Gradient Coding](https://mlsanity.com/paper/2603.28780/) (2026)
- [On the Oracle Complexity of Interpolation-Based Gradient Descent](https://mlsanity.com/paper/2606.19878/) (2026)

## Abstract (arXiv)

In this work, we study empirical risk minimization (ERM) within a federated learning framework, where a central server minimizes an ERM objective function using training data that is stored across m clients. In this setting, the Federated Averaging (FedAve) algorithm is the staple for determining ε-approximate solutions to the ERM problem. Similar to standard optimization algorithms, the convergence analysis of FedAve 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, we propose the Federated Low Rank Gradient Descent (FedLRGD) algorithm. Since smoothness in data induces an approximate low rank structure on the loss function, our method first performs a few rounds of communication between the server and clients to learn weights that the server can use to approximate clients' gradients. Then, our method solves the ERM problem at the server using inexact gradient descent. To show that FedLRGD can have superior performance to FedAve, we present a notion of federated oracle complexity as a counterpart to canonical oracle complexity. Under some assumptions on the loss function, e.g., strong convexity in parameter, η-H"older smoothness in data, etc., we prove that the federated oracle complexity of FedLRGD scales like φ m(p/ε)Theta(d/η) and that of FedAve scales like φ m(p/ε)3/4 (neglecting sub-dominant factors), where φgg 1 is a "communication-to-computation ratio," p is the parameter dimension, and d is the data dimension. Then, we show that when d is small and the loss function is sufficiently smooth in the data, FedLRGD beats FedAve in federated oracle complexity. Finally, in the course of analyzing FedLRGD, we also establish a result on low rank approximation of latent variable models.