mlsanityData to 7 Oct 2026

Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction

arXiv 2205.01608 ↗First posted 3 May 2022cs.LG math.OCcited by 20

Not on the map. Why?

Abstract (arXiv)

Bilevel Optimization has witnessed notable progress recently with new emerging efficient algorithms and has been applied to many machine learning tasks such as data cleaning, few-shot learning, and neural architecture search. However, little attention has been paid to solve the bilevel problems under distributed setting. Federated learning (FL) is an emerging paradigm which solves machine learning tasks over distributed-located data. FL problems are challenging to solve due to the heterogeneity and communication bottleneck. However, it is unclear how these challenges will affect the convergence of Bilevel Optimization algorithms. In this paper, we study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm and we show it requires O(ε-2) number of iterations to reach an ε-stationary point. Then we propose FedBiOAcc to accelerate FedBiO with the momentum-based variance-reduction technique under the stochastic scenario. We show FedBiOAcc has complexity of O(ε-1.5). Finally, we validate our proposed algorithms via the important Fair Federated Learning task. More specifically, we define a bilevel-based group fair FL objective. Our algorithms show superior performances compared to other baselines in numerical experiments.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 50 of its 71 references that are in the map. First posted on arXiv 3 May 2022.

Builds on

50 of 71 references.

References · 50

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  3. 2016Equality of Opportunity in Supervised Learningcited by 2,000
  4. 2018DARTS: Differentiable Architecture Searchcited by 1,782
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  6. 2018Federated Learning with Non-IID Datacited by 1,099
  7. 2019Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classificationcited by 836
  8. 2020Ditto: Fair and Robust Federated Learning Through Personalizationcited by 665
  9. 2019Agnostic Federated Learningcited by 451
  10. 2018Adaptive Federated Learning in Resource Constrained Edge Computing Systemscited by 408
  11. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  12. 2019Fair Resource Allocation in Federated Learningcited by 389
38 more
  1. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  2. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  3. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
  4. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  5. 2019PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Searchcited by 265
  6. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  7. 2016Hyperparameter optimization with approximate gradientcited by 231
  8. 2018Approximation Methods for Bilevel Programmingcited by 231
  9. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  10. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 174
  11. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 151
  12. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  13. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  14. 2019SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentumcited by 121
  15. 2020Meta-Transfer Learning for Zero-Shot Super-Resolutioncited by 116
  16. 2021FairFed: Enabling Group Fairness in Federated Learningcited by 114
  17. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  18. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  19. 2021Distributionally Robust Federated Averagingcited by 104
  20. 2020Fairness-aware Agnostic Federated Learningcited by 87
  21. 2018Stochastic Hyperparameter Optimization through Hypernetworkscited by 72
  22. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  23. 2019ES-MAML: Simple Hessian-Free Meta Learningcited by 57
  24. 2020Mitigating Bias in Federated Learningcited by 56
  25. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  26. 2021Addressing Algorithmic Disparity and Performance Inconsistency in Federated Learningcited by 50
  27. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  28. 2019AdversarialNAS: Adversarial Neural Architecture Search for GANscited by 38
  29. 2019Penalty Method for Inversion-Free Deep Bilevel Optimizationcited by 33
  30. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  31. 2020Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guaranteecited by 27
  32. 2019Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraintscited by 18
  33. 2018Transfer Learning with Neural AutoMLcited by 15
  34. 2021Unified Group Fairness on Federated Learningcited by 15
  35. 2020Meta-CoTGAN: A Meta Cooperative Training Paradigm for Improving Adversarial Text Generationcited by 11
  36. 2020AlphaGAN: Fully Differentiable Architecture Search for Generative Adversarial Networkscited by 10
  37. 2021Federating for Learning Group Fair Modelscited by 9
  38. 2021The Minimax Complexity of Distributed Optimizationcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 11; 2023: 7; 2024: 1; 2025: 0; 2026: 1.

20 papers.

Sort:

By area:

  1. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  2. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  3. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  4. 2022An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identificationcited by 14
  5. 2023SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learningcited by 14
  6. 2022Asynchronous Distributed Bilevel Optimizationcited by 13
  7. 2023Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiationcited by 13
  8. 2022Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximizationcited by 11
  9. 2022Communication-Efficient Robust Federated Learning with Noisy Labelscited by 11
  10. 2022Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimizationcited by 10
  11. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 8
  12. 2022Federated Learning on Adaptively Weighted Nodes by Bilevel Optimizationcited by 6
8 more
  1. 2022Fast Adaptive Federated Bilevel Optimizationcited by 6
  2. 2022FedGRec: Federated Graph Recommender System with Lazy Update of Latent Embeddingscited by 4
  3. 2022A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programmingcited by 2
  4. 2022Decentralized Hyper-Gradient Computation over Time-Varying Directed Networkscited by 1
  5. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  6. 2023On the Communication Complexity of Decentralized Stochastic Bilevel Optimizationcited by 0
  7. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
  8. 2026AsynDBT: Asynchronous Distributed Bilevel Tuning for efficient In-Context Learning with Large Language Modelscited by 0