mlsanityData to 7 Oct 2026

Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods

arXiv 2207.02829 ↗First posted 6 Jul 2022math.OC cs.DS cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

This paper introduces textitonline bilevel optimization in which a sequence of time-varying bilevel problems is revealed one after the other. We extend the known regret bounds for online single-level algorithms to the bilevel setting. Specifically, we provide new notions of textitbilevel regret, develop an online alternating time-averaged gradient method that is capable of leveraging smoothness, and give regret bounds in terms of the path-length of the inner and outer minimizer sequences.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 59 of its 119 references that are in the map. First posted on arXiv 6 Jul 2022.

Builds on

59 of 119 references.

References · 59

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2016Matching Networks for One Shot Learningcited by 2,246
  3. 2018DARTS: Differentiable Architecture Searchcited by 1,782
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  6. 2018Meta-learning with differentiable closed-form solverscited by 395
  7. 2019Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAMLcited by 359
  8. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  9. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 303
  10. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  11. 2016Hyperparameter optimization with approximate gradientcited by 231
  12. 2018Approximation Methods for Bilevel Programmingcited by 231
38 more
  1. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  2. 2018Online Learning: A Comprehensive Surveycited by 203
  3. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  4. 2013Non-stationary Stochastic Optimizationcited by 173
  5. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  6. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 151
  7. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  8. 2019Online Meta-Learningcited by 137
  9. 2018Adaptive Online Learning in Dynamic Environmentscited by 130
  10. 2017A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applicationscited by 126
  11. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  12. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  13. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  14. 2015Strongly Adaptive Online Learningcited by 102
  15. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  16. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  17. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  18. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 78
  19. 2020learn2learn: A Library for Meta-Learning Researchcited by 69
  20. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  21. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 65
  22. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  23. 2022AutoBalance: Optimized Loss Functions for Imbalanced Datacited by 49
  24. 2016Improved Dynamic Regret for Non-degenerate Functionscited by 46
  25. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  26. 2017Tracking the Best Expert in Non-stationary Stochastic Environmentscited by 35
  27. 2020Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functionscited by 33
  28. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
  29. 2021Stateful Strategic Regressioncited by 32
  30. 2019Online Non-Convex Learning: Following the Perturbed Leader is Optimalcited by 31
  31. 2019DADAM: A Consensus-based Distributed Adaptive Gradient Method for Online Optimizationcited by 30
  32. 2019Online Forecasting of Total-Variation-bounded Sequencescited by 30
  33. 2020Minimizing Dynamic Regret and Adaptive Regret Simultaneouslycited by 30
  34. 2017Efficient Regret Minimization in Non-Convex Gamescited by 28
  35. 2020Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guaranteecited by 27
  36. 2018Learning in Non-convex Games with an Optimization Oraclecited by 24
  37. 2019Adaptive Regret of Convex and Smooth Functionscited by 24
  38. 2019Dynamic Local Regret for Non-convex Online Forecastingcited by 17

50 most cited of 59 All 59 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 3; 2025: 1; 2026: 7.

14 papers.

Sort:

  1. 2024Gradient-Variation Online Learning under Generalized Smoothnesscited by 11
  2. 2023Non-Convex Bilevel Optimization with Time-Varying Objective Functionscited by 8
  3. 2026Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variationscited by 5
  4. 2024Improving SAM Requires Rethinking its Optimization Formulationcited by 4
  5. 2025Online Decision-Focused Learningcited by 4
  6. 2023Fair Canonical Correlation Analysiscited by 3
  7. 2024Online Nonconvex Bilevel Optimization with Bregman Divergencescited by 2
  8. 2026Non-Stationary Functional Bilevel Optimizationcited by 2
  9. 2026Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimizationcited by 1
  10. 2026Online Learning with Gradient-Variation Interval Regretcited by 1
  11. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  12. 2026Fully First-Order Algorithms for Online Bilevel Optimizationcited by 0
2 more
  1. 2026IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedbackcited by 0
  2. 2026Beyond Post-Hoc Temperature Scaling: Bilevel Optimization for LLM Calibrationcited by 0