# FedNest: Federated Bilevel, Minimax, and Compositional Optimization

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- Builds on 70 of its 115 references that are in the map.
- First posted on arXiv 4 May 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)

## Built on by (most cited first, 30 of 60)

- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Recent Advances on Federated Learning: A Systematic Survey](https://mlsanity.com/paper/2301.01299/) (2023)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity](https://mlsanity.com/paper/2210.12839/) (2022)
- [Achieving Linear Speedup in Non-IID Federated Bilevel Learning](https://mlsanity.com/paper/2302.05412/) (2023)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm](https://mlsanity.com/paper/2401.16164/) (2024)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning](https://mlsanity.com/paper/2305.19442/) (2023)
- [Asynchronous Distributed Bilevel Optimization](https://mlsanity.com/paper/2212.10048/) (2022)
- [Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiation](https://mlsanity.com/paper/2302.04969/) (2023)
- [Federated Multi-Objective Learning](https://mlsanity.com/paper/2310.09866/) (2023)
- [FeDXL: Provable Federated Learning for Deep X-Risk Optimization](https://mlsanity.com/paper/2210.14396/) (2022)
- [Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimization](https://mlsanity.com/paper/2211.07096/) (2022)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneity](https://mlsanity.com/paper/2305.18285/) (2023)
- [Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problems](https://mlsanity.com/paper/2302.06701/) (2023)
- [Federated Compositional Deep AUC Maximization](https://mlsanity.com/paper/2304.10101/) (2023)
- [Fast Adaptive Federated Bilevel Optimization](https://mlsanity.com/paper/2211.01122/) (2022)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Federated Learning on Adaptively Weighted Nodes by Bilevel Optimization](https://mlsanity.com/paper/2207.10751/) (2022)
- [Provably Convergent Federated Trilevel Learning](https://mlsanity.com/paper/2312.11835/) (2023)
- [Adaptive Federated Minimax Optimization with Lower Complexities](https://mlsanity.com/paper/2211.07303/) (2022)
- [A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2306.02422/) (2023)
- [Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis](https://mlsanity.com/paper/2410.05140/) (2024)
- [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimization](https://mlsanity.com/paper/2311.00944/) (2023)
- [A First-order Generative Bilevel Optimization Framework for Diffusion Models](https://mlsanity.com/paper/2502.08808/) (2025)

## Abstract (arXiv)

Standard federated optimization methods successfully apply to stochastic problems with single-level structure. However, many contemporary ML problems -- including adversarial robustness, hyperparameter tuning, and actor-critic -- fall under nested bilevel programming that subsumes minimax and compositional optimization. In this work, we propose fedblo: A federated alternating stochastic gradient method to address general nested problems. We establish provable convergence rates for fedblo in the presence of heterogeneous data and introduce variations for bilevel, minimax, and compositional optimization. fedblo introduces multiple innovations including federated hypergradient computation and variance reduction to address inner-level heterogeneity. We complement our theory with experiments on hyperparameter & hyper-representation learning and minimax optimization that demonstrate the benefits of our method in practice. Code is available at https://github.com/ucr-optml/FedNest.