mlsanityData to 7 Oct 2026

FedNest: Federated Bilevel, Minimax, and Compositional Optimization

arXiv 2205.02215 ↗First posted 4 May 2022cs.LG math.OCcited by 60

Not on the map. Why?

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.

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

Builds on

70 of 115 references.

References · 70

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  4. 2019Advances and Open Problems in Federated Learningcited by 3,021
  5. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  6. 2018DARTS: Differentiable Architecture Searchcited by 1,782
  7. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  8. 2020Adaptive Federated Optimizationcited by 1,036
  9. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  10. 2019Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classificationcited by 836
  11. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  12. 2018Local SGD Converges Fast and Communicates Littlecited by 595
38 more
  1. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  2. 2021Federated Learning Based on Dynamic Regularizationcited by 555
  3. 2019Agnostic Federated Learningcited by 451
  4. 2018Adaptive Federated Learning in Resource Constrained Edge Computing Systemscited by 408
  5. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  6. 2018Meta-learning with differentiable closed-form solverscited by 395
  7. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  8. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 303
  9. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
  10. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  11. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  12. 2016Hyperparameter optimization with approximate gradientcited by 231
  13. 2018Approximation Methods for Bilevel Programmingcited by 231
  14. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  15. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  16. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  17. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  18. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 151
  19. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  20. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  21. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  22. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  23. 2017A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applicationscited by 126
  24. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  25. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  26. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  27. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  28. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  29. 2021Distributionally Robust Federated Averagingcited by 104
  30. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  31. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  32. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  33. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  34. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  35. 2020FedGAN: Federated Generative Adversarial Networks for Distributed Datacited by 89
  36. 2019First Analysis of Local GD on Heterogeneous Datacited by 80
  37. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 78
  38. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75

50 most cited of 70 All 70 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 12; 2023: 26; 2024: 10; 2025: 6; 2026: 6.

60 papers.

Sort:

By area:

  1. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  2. 2023Recent Advances on Federated Learning: A Systematic Surveycited by 40
  3. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  4. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  5. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  6. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  7. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16
  8. 2022Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methodscited by 14
  9. 2023SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learningcited by 14
  10. 2022Asynchronous Distributed Bilevel Optimizationcited by 13
  11. 2023Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiationcited by 13
  12. 2023Federated Multi-Objective Learningcited by 11
38 more
  1. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  2. 2022Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimizationcited by 10
  3. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  4. 2023Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problemscited by 9
  5. 2023Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problemscited by 8
  6. 2023Federated Compositional Deep AUC Maximizationcited by 8
  7. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 8
  8. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  9. 2022Federated Learning on Adaptively Weighted Nodes by Bilevel Optimizationcited by 6
  10. 2022Fast Adaptive Federated Bilevel Optimizationcited by 6
  11. 2023Provably Convergent Federated Trilevel Learningcited by 6
  12. 2022Adaptive Federated Minimax Optimization with Lower Complexitiescited by 5
  13. 2023A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Conditioncited by 5
  14. 2024Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysiscited by 5
  15. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  16. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  17. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  18. 2025A First-order Generative Bilevel Optimization Framework for Diffusion Modelscited by 4
  19. 2023Fair Canonical Correlation Analysiscited by 3
  20. 2024Review of Mathematical Optimization in Federated Learningcited by 3
  21. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 3
  22. 2025Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescited by 3
  23. 2022Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimizationcited by 2
  24. 2022A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programmingcited by 2
  25. 2023Federated Automatic Differentiationcited by 2
  26. 2023Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimizationcited by 2
  27. 2023Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimizationcited by 2
  28. 2022Decentralized Hyper-Gradient Computation over Time-Varying Directed Networkscited by 1
  29. 2023FedPop: Federated Population-based Hyperparameter Tuningcited by 1
  30. 2023FedDRO: Federated Compositional Optimization for Distributionally Robust Learningcited by 1
  31. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  32. 2024Fully First-Order Methods for Decentralized Bilevel Optimizationcited by 1
  33. 2024Exploring the Generalization Capabilities of AID-based Bi-level Optimizationcited by 1
  34. 2026A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimizationcited by 1
  35. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  36. 2023Achieving Linear Speedup in Decentralized Stochastic Compositional Minimax Optimizationcited by 0
  37. 2023Federated Multi-Level Optimization over Decentralized Networkscited by 0
  38. 2023On the Communication Complexity of Decentralized Stochastic Bilevel Optimizationcited by 0

50 most cited of 60 All 60 (JSON)