mlsanityData to 14 Oct 2026

Fully First-Order Methods for Decentralized Bilevel Optimization

arXiv 2410.19319 ↗First posted 25 Oct 2024math.OC cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis showing that for n agents collaboratively solving the DSBO problem, the sample complexity of finding an ε-stationary point in our algorithm is O(n-1ε-7), which matches the currently best-known results of the single-agent counterpart with linear speedup. The numerical experiments demonstrate both the communication and training efficiency of our algorithm.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 54 of its 75 references that are in the map. First posted on arXiv 25 Oct 2024.

Builds on

54 of 75 references.

References · 54

  1. 2016Learning to learn by gradient descent by gradient descentcited by 620
  2. 2019Meta-Learning with Implicit Gradientscited by 525
  3. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
  4. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  5. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 360
  6. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 304
  7. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  8. 2018Approximation Methods for Bilevel Programmingcited by 236
  9. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
  10. 2016Hyperparameter optimization with approximate gradientcited by 233
  11. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  12. 2020On the Iteration Complexity of Hypergradient Computationcited by 155
38 more
  1. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 150
  2. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  3. 2018D2: Decentralized Training over Decentralized Datacited by 140
  4. 2017A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applicationscited by 129
  5. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 112
  6. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 111
  7. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
  8. 2018Distributed Stochastic Gradient Tracking Methodscited by 106
  9. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
  10. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 101
  11. 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 100
  12. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  13. 2019Generalized Inner Loop Meta-Learningcited by 93
  14. 2018Communication Compression for Decentralized Trainingcited by 88
  15. 2022Decentralized Training of Foundation Models in Heterogeneous Environmentscited by 87
  16. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  17. 2020learn2learn: A Library for Meta-Learning Researchcited by 69
  18. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 69
  19. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  20. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 63
  21. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  22. 2019Torchmeta: A Meta-Learning library for PyTorchcited by 52
  23. 2022Will Bilevel Optimizers Benefit from Loopscited by 36
  24. 2020Decentralized gradient methods: does topology matter?cited by 35
  25. 2021On the Convergence Theory for Hessian-Free Bilevel Algorithmscited by 35
  26. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  27. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  28. 2022Decentralized Bilevel Optimizationcited by 23
  29. 2022Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexitycited by 21
  30. 2020Multi-consensus Decentralized Accelerated Gradient Descentcited by 20
  31. 2021Optimal Gradient Tracking for Decentralized Optimizationcited by 18
  32. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  33. 2024Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysiscited by 15
  34. 2023SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learningcited by 14
  35. 2021BAGUA: Scaling up Distributed Learning with System Relaxationscited by 13
  36. 2024On the Complexity of First-Order Methods in Stochastic Bilevel Optimizationcited by 12
  37. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  38. 2023A Single-Loop Algorithm for Decentralized Bilevel Optimizationcited by 7

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noisecited by 1