# FeDXL: Provable Federated Learning for Deep X-Risk Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 71 references that are in the map.
- First posted on arXiv 26 Oct 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [CheXpert: A Large Chest Radiograph Dataset with Uncertainty Labels and Expert Comparison](https://mlsanity.com/paper/1901.07031/) (2019)
- [MedMNIST v2 -- A large-scale lightweight benchmark for 2D and 3D biomedical image classification](https://mlsanity.com/paper/2110.14795/) (2021)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Sampling Matters in Deep Embedding Learning](https://mlsanity.com/paper/1706.07567/) (2017)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning](https://mlsanity.com/paper/2008.03606/) (2020)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Federated Unsupervised Representation Learning](https://mlsanity.com/paper/2010.08982/) (2020)
- [Large-scale Robust Deep AUC Maximization: A New Surrogate Loss and Empirical Studies on Medical Image Classification](https://mlsanity.com/paper/2012.03173/) (2020)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [CNN Image Retrieval Learns from BoW: Unsupervised Fine-Tuning with Hard Examples](https://mlsanity.com/paper/1604.02426/) (2016)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [On Symmetric Losses for Learning from Corrupted Labels](https://mlsanity.com/paper/1901.09314/) (2019)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)

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

- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Federated Compositional Deep AUC Maximization](https://mlsanity.com/paper/2304.10101/) (2023)
- [Frequency-Semantic Enhanced Variational Autoencoder for Zero-Shot Skeleton-based Action Recognition](https://mlsanity.com/paper/2506.22179/) (2025)
- [Federated Conditional Stochastic Optimization](https://mlsanity.com/paper/2310.02524/) (2023)
- [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023)
- [Communication-Efficient Federated Group Distributionally Robust Optimization](https://mlsanity.com/paper/2410.06369/) (2024)
- [FedNE: Surrogate-Assisted Federated Neighbor Embedding for Dimensionality Reduction](https://mlsanity.com/paper/2409.11509/) (2024)
- [Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations](https://mlsanity.com/paper/2512.01213/) (2025)
- [Communication-Efficient Federated AUC Maximization with Cyclic Client Participation](https://mlsanity.com/paper/2601.01649/) (2026)
- [Provably Communication-Efficient and Privacy-Preserving Federated Graph Neural Networks](https://mlsanity.com/paper/2605.26243/) (2026)
- [DeFiRank: Federated Pairwise Ranking for Governance in Decentralized Financial Networks](https://mlsanity.com/paper/2610.12916/) (2026)

## Abstract (arXiv)

In this paper, we tackle a novel federated learning (FL) problem for optimizing a family of X-risks, to which no existing FL algorithms are applicable. In particular, the objective has the form of mathbb Ez~ S1 f(mathbb Ez'~ S2 ℓ(w; z, z')), where two sets of data S1, S2 are distributed over multiple machines, ℓ(·) is a pairwise loss that only depends on the prediction outputs of the input data pairs (z, z'), and f(·) is possibly a non-linear non-convex function. This problem has important applications in machine learning, e.g., AUROC maximization with a pairwise loss, and partial AUROC maximization with a compositional loss. The challenges for designing an FL algorithm for X-risks lie in the non-decomposability of the objective over multiple machines and the interdependency between different machines. To this end, we propose an active-passive decomposition framework that decouples the gradient's components with two types, namely active parts and passive parts, where the active parts depend on local data that are computed with the local model and the passive parts depend on other machines that are communicated/computed based on historical models and samples. Under this framework, we develop two provable FL algorithms (FeDXL) for handling linear and nonlinear f, respectively, based on federated averaging and merging. We develop a novel theoretical analysis to combat the latency of the passive parts and the interdependency between the local model parameters and the involved data for computing local gradient estimators. We establish both iteration and communication complexities and show that using the historical samples and models for computing the passive parts do not degrade the complexities. We conduct empirical studies of FeDXL for deep AUROC and partial AUROC maximization, and demonstrate their performance compared with several baselines.