Introduction

Bilevel optimization is a special kind of optimization where one problem is embedded (nested) within another. The outer optimization task is commonly referred to as the upper-level optimization task, and the inner optimization task is commonly referred to as the lower-level optimization task. These problems involve two kinds of variables, referred to as the upper-level variables and the lower-level variables[1].

[1] Wikipedia

A Spotlight on Our Lab’s Research

[1] A paper on Robust Beamforming for Downlink Multi-Cell Systems: A Bilevel Optimization Perspective is accepted by AAAI 2024

[2] A paper on provably convergent federated trilevel learning is accepted by AAAI 2024

[3] A papper on asynchronous distributed bilevel optimization is accepted by ICLR 2023

[4] A paper on distributed distributionally robust optimization with non-convex objectives is accepted by NeurIPS 2022

A Review on Bilevel Optimization

2024

Updating…

2023

[1] ICLR - Jiao Y, Yang K, Wu T, et al. Asynchronous Distributed Bilevel Optimization[J]. arXiv preprint arXiv:2212.10048, 2022. [Paper 📝 | Code 💻]

[2] ICML - Liu Z, Zhang X, Khanduri P, et al. Prometheus: Taming Sample and Communication Complexities in Constrained Decentralized Stochastic Bilevel Learning[C]//International Conference on Machine Learning. 2023. [Paper 📝]

[3] ICML - Hu Q, Qiu Z H, Guo Z, et al. Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization[J]. arXiv preprint arXiv:2305.18730, 2023. [Paper 📝]

[4] ICML - Chen X, Huang M, Ma S, et al. Decentralized stochastic bilevel optimization with improved per-iteration complexity[C]//International Conference on Machine Learning. PMLR, 2023: 4641-4671. [Paper 📝]

[5] ICML - Li J, Yu J, Liu B, et al. Achieving hierarchy-free approximation for bilevel programs with equilibrium constraints[C]//International Conference on Machine Learning. PMLR, 2023: 20312-20335. [Paper 📝]

[6] ICML - Kwon J, Kwon D, Wright S, et al. A fully first-order method for stochastic bilevel optimization[C]//International Conference on Machine Learning. PMLR, 2023: 18083-18113. [Paper 📝]

[7] ICML - Huang F. On momentum-based gradient methods for bilevel optimization with nonconvex lower-level[J]. arXiv preprint arXiv:2303.03944, 2023. [Paper 📝]

[8] ICML - Lu S. Bilevel Optimization with Coupled Decision-Dependent Distributions[C]//International Conference on Machine Learning. 2023. [Paper 📝]

[9] ICML - Khanduri P, Tsaknakis I, Zhang Y, et al. Linearly constrained bilevel optimization: A smoothed implicit gradient approach[J]. 2023. [Paper 📝]

[10] ICML - Huang M, Zhang D, Ji K. Achieving linear speedup in non-iid federated bilevel learning[J]. arXiv preprint arXiv:2302.05412, 2023. [Paper 📝]

2022

[1] NeurIPS - Jiao Y, Yang K, Song D. Distributed Distributionally Robust Optimization with Non-Convex Objectives[C]//Advances in Neural Information Processing Systems. [Paper 📝]

[2] The Visual Computer - Gao J, Liu X, Liu R, et al. Learning adaptive hyper-guidance via proxy-based bilevel optimization for image enhancement[J]. The Visual Computer, 2022: 1-14. [Paper 📝]

[3] IEEE Transactions on Pattern Analysis and Machine Intelligence - Liu R, Mu P, Yuan X, et al. A general descent aggregation framework for gradient-based bi-level optimization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 45(1): 38-57. [Paper 📝]

[4] Mathematical Programming - Ye J J, Yuan X, Zeng S, et al. Difference of convex algorithms for bilevel programs with applications in hyperparameter selection[J]. Mathematical Programming, 2022: 1-34. [Paper 📝 | Code 💻]

[5] Journal of Machine Learning Research - Ji K, Liang Y. Lower bounds and accelerated algorithms for bilevel optimization[J]. Journal of Machine Learning Research, 2022, 23: 1-56. [Paper 📝]

[6] AISTATS - Chen T, Sun Y, Xiao Q, et al. A single-timescale method for stochastic bilevel optimization[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2022: 2466-2488. [Paper 📝]

[7] INFORMS Annual Meeting - Gu A, Lu S, Ram P, et al. Robust Multi-objective Bilevel Optimization With Applications In Machine Learning[C]//INFORMS Annual Meeting. 2022. [Paper 📝]

[8] ICML - Zhang Y, Zhang G, Khanduri P, et al. Revisiting and advancing fast adversarial training through the lens of bi-level optimization[C]//International Conference on Machine Learning. PMLR, 2022: 26693-26712. [Paper 📝 | Code 💻]

[9] ICASSP - Taneja V, Chen P Y, Yao Y, et al. When Does Backdoor Attack Succeed in Image Reconstruction? A Study of Heuristics vs. Bi-Level Solution[C]//ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022: 4398-4402. [Paper 📝]

[10] NeurIPS - Lu S, Zeng S, Cui X, et al. A Stochastic Linearized Augmented Lagrangian Method for Decentralized Bilevel Optimization[C]//Advances in Neural Information Processing Systems. 2022. [Paper 📝]

[11] Liu Z, Zhang X, Khanduri P, et al. INTERACT: achieving low sample and communication complexities in decentralized bilevel learning over networks[C]//Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing. 2022: 61-70.

[12] Xing P, Lu S, Wu L, et al. BiG-Fed: Bilevel Optimization enhanced graph-aided federated learning[J]. IEEE Transactions on Big Data, 2022.

[13] Lu S, Cui X, Squillante M S, et al. Decentralized bilevel optimization for personalized client learning[C]//ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022: 5543-5547.

[14] Vicol P, Lorraine J P, Pedregosa F, et al. On implicit bias in overparameterized bilevel optimization[C]//International Conference on Machine Learning. PMLR, 2022: 22234-22259.

[15] Li J, Gu B, Huang H. A fully single loop algorithm for bilevel optimization without hessian inverse[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(7): 7426-7434.

[16] Gao L L, Ye J, Yin H, et al. Value function based difference-of-convex algorithm for bilevel hyperparameter selection problems[C]//International Conference on Machine Learning. PMLR, 2022: 7164-7182.

[17] Tarzanagh D A, Li M, Thrampoulidis C, et al. FedNest: Federated bilevel, minimax, and compositional optimization[C]//International Conference on Machine Learning. PMLR, 2022: 21146-21179.

[18] Bagherian M, Tarzanagh D A, Dinov I, et al. A Bilevel Optimization Method for Tensor Recovery Under Metric Learning Constraints[J]. arXiv preprint arXiv:2209.00545, 2022.

[19] Huang F, Li J, Gao S, et al. Enhanced Bilevel Optimization via Bregman Distance[C]//Advances in Neural Information Processing Systems. 2022.

[20] Liu R, Ma L, Yuan X, et al. Task-oriented convex bilevel optimization with latent feasibility[J]. IEEE Transactions on Image Processing, 2022, 31: 1190-1203.

[21] Zhang Y, Yao Y, Ram P, et al. Advancing Model Pruning via Bi-level Optimization[C]//Annual Conference on Neural Information Processing Systems. 2022.

[22] Yang S, Zhang X, Wang M. Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks[C]//Advances in Neural Information Processing Systems.

2021

[1] Liu R, Liu Y, Zeng S, et al. Towards gradient-based bilevel optimization with non-convex followers and beyond[J]. Advances in Neural Information Processing Systems, 2021, 34: 8662-8675.

[2] Liu R, Gao J, Zhang J, et al. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 44(12): 10045-10067.

[3] Liu R, Liu X, Yuan X, et al. A value-function-based interior-point method for non-convex bi-level optimization[C]//International Conference on Machine Learning. PMLR, 2021: 6882-6892.

[4] Liu R, Liu X, Yuan X, et al. A Hessian-free interior-point method for non-convex bilevel optimization[C]//International Conference on Machine Learning. 2021.

[5] Sow D, Ji K, Liang Y. On the Convergence Theory for Hessian-Free Bilevel Algorithms[C]//Advances in Neural Information Processing Systems. 2021.

[6] Ji K, Yang J, Liang Y. Bilevel optimization: Convergence analysis and enhanced design[C]//International conference on machine learning. PMLR, 2021: 4882-4892.

[7] Yang J, Ji K, Liang Y. Provably faster algorithms for bilevel optimization[J]. Advances in Neural Information Processing Systems, 2021, 34: 13670-13682.

[8] Gu A, Lu S, Ram P, et al. Nonconvex min-max bilevel optimization for task robust meta learning[C]//International Conference on Machine Learning. 2021.

[9] Chen T, Sun Y, Yin W. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems[J]. Advances in Neural Information Processing Systems, 2021, 34: 25294-25307.

[10] Borsos Z, Tagliasacchi M, Krause A. Semi-supervised batch active learning via bilevel optimization[C]//ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021: 3495-3499.

[11] Shi W, Gu B. Improved Penalty Method via Doubly Stochastic Gradients for Bilevel Hyperparameter Optimization[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(11): 9621-9629.

[12] Ghosh A, Lan A. BOBCAT: Bilevel Optimization-Based Computerized Adaptive Testing[C]//International Joint Conference on Artificial Intelligence. 2021.

[13] Khanduri P, Zeng S, Hong M, et al. A near-optimal algorithm for stochastic bilevel optimization via double-momentum[J]. Advances in neural information processing systems, 2021, 34: 30271-30283.

2020

[1] Dempe S, Gadhi N, El Idrissi M. Optimality conditions in terms of convexificators for a bilevel multiobjective optimization problem[J]. Optimization, 2020, 69(7-8): 1811-1830.

[2] Bae J, Grosse R B. Delta-stn: Efficient bilevel optimization for neural networks using structured response jacobians[J]. Advances in Neural Information Processing Systems, 2020, 33: 21725-21737.

[3] Borsos Z, Mutny M, Krause A. Coresets via bilevel optimization for continual learning and streaming[J]. Advances in Neural Information Processing Systems, 2020, 33: 14879-14890.

[4] Grazzi R, Franceschi L, Pontil M, et al. On the iteration complexity of hypergradient computation[C]//International Conference on Machine Learning. PMLR, 2020: 3748-3758.

2019

[1] Dempe S, Franke S. Solution of bilevel optimization problems using the KKT approach[J]. Optimization, 2019, 68(8): 1471-1489.

[2] Sinha A, Soun T, Deb K. Using Karush-Kuhn-Tucker proximity measure for solving bilevel optimization problems[J]. Swarm and evolutionary computation, 2019, 44: 496-510.

2018

[1] Franceschi L, Frasconi P, Salzo S, et al. Bilevel programming for hyperparameter optimization and meta-learning[C]//International Conference on Machine Learning. PMLR, 2018: 1568-1577.

[2] Frecon J, Salzo S, Pontil M. Bilevel learning of the group lasso structure[J]. Advances in neural information processing systems, 2018, 31.

[3] Ghadimi S, Wang M. Approximation methods for bilevel programming[J]. arXiv preprint arXiv:1802.02246, 2018.

[4] Mackay M, Vicol P, Lorraine J, et al. Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions[C]//International Conference on Learning Representations. 2018.

2017

[1] Sinha A, Malo P, Deb K. A review on bilevel optimization: From classical to evolutionary approaches and applications[J]. IEEE Transactions on Evolutionary Computation, 2017, 22(2): 276-295.

[2] Islam M M, Singh H K, Ray T, et al. An enhanced memetic algorithm for single-objective bilevel optimization problems[J]. Evolutionary computation, 2017, 25(4): 607-642.

Before

[1] Dempe S, Kalashnikov V, Pérez-Valdés G A, et al. Bilevel programming problems[J]. Energy Systems. Springer, Berlin, 2015, 10: 978-3.

[2] Sinha A, Malo P, Deb K, et al. Solving bilevel multicriterion optimization problems with lower level decision uncertainty[J]. IEEE Transactions on Evolutionary Computation, 2015, 20(2): 199-217.

[3] Sinha A, Malo P, Deb K. An improved bilevel evolutionary algorithm based on quadratic approximations[C]//2014 IEEE congress on evolutionary computation (CEC). IEEE, 2014: 1870-1877.

[4] Alizadeh S M, Marcotte P, Savard G. Two-stage stochastic bilevel programming over a transportation network[J]. Transportation Research Part B: Methodological, 2013, 58: 92-105.

[5] Dempe S, Zemkoho A B. The bilevel programming problem: reformulations, constraint qualifications and optimality conditions[J]. Mathematical Programming, 2013, 138: 447-473.

[6] Deb K, Sinha A. An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm[J]. Evolutionary computation, 2010, 18(3): 403-449.

[7] Dempe S, Dutta J, Mordukhovich B S. New necessary optimality conditions in optimistic bilevel programming[J]. Optimization, 2007, 56(5-6): 577-604.

[8] Colson B, Marcotte P, Savard G. An overview of bilevel optimization[J]. Annals of operations research, 2007, 153: 235-256.

[9] Dempe S. Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints[J]. Optimization, 2003, 52(3): 333-359.

[10] Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bilevel programming[J]. SIAM Journal on scientific and Statistical Computing, 1992, 13(5): 1194-1217.

Major Researchers

  • Risheng Liu、Zhouchen Lin、Zhixun Su、Mu Pan
  • Xiaoming Yuan、Jin Zhang
  • Yingbing Liang、Lifeng Lai、Kaiyi Ji、Shiqiam Ma、Krishna Balasubramanian
  • Mengdi Wang
  • Tianyi Chen、Wotao Yin、Parikshit Ram、Georgios B. Giannakis、Donald Goldfarb
  • Sijia Liu、Songtao Lu、Mingyi Hong、Jia (Kevin) Liu、Prashant Khanduri
  • Andreas Krause、Zalán Borsos
  • Heng Huang、Bin Gu
  • Andrew S. Lan、Aritra Ghosh
  • Massimiliano Pontil、Luca Franceschi、Saverio Salzo
  • Joshua Welch、Davoud Ataee Tarzanagh、Ivo Dinov、Qi Long
  • Stephan Dempe、Alain Zemkoho、Viacheslav Kalashnikov
  • Gilles Savard、Patrice Marcotte
  • Ankur Sinha、Pekka Malo、 Kalyanmoy Deb
  • Yibing Lv