Approximation Methods for Bilevel Programming

By Saeed Ghadimi, Mengdi Wang. 2018

388 citations recorded by the source corpus.

In this paper, we study a class of bilevel programming problem where the inner objective function is strongly convex. More specifically, under some mile assumptions on the partial derivatives of both inner and outer objective functions, we present an approximation algorithm for solving this class of problem and provide its finite-time convergence analysis under different convexity assumption on the outer objective function. We also present an accelerated variant of this method which improves the rate of convergence under convexity assumption. Furthermore, we generalize our results under stochastic setting where only noisy information of both objective functions is available. To the best of our knowledge, this is the first time that such (stochastic) approximation algorithms with established iteration complexity (sample complexity) are provided for bilevel programming.

Subfields: Computational Theory and Mathematics, Management Science and Operations Research, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Reza Haffari
2. Zalán Borsos
3. Xiaojun Chang
4. Andreas Krause
5. Steven W. Su
6. Mojm'ir Mutn'y
7. Junjie Yang
8. Miao Zhang

In Management Science and Operations Research

1. Reza Haffari
2. Zalán Borsos
3. Xiaojun Chang
4. Andreas Krause
5. Steven W. Su
6. Mojm'ir Mutn'y
7. Junjie Yang
8. Miao Zhang

In Numerical Analysis

1. Reza Haffari
2. Xiaojun Chang
3. Andreas Krause
4. Steven W. Su
5. Junjie Yang
6. Miao Zhang
7. Kaiyi Ji
8. Shirui Pan

Citations in the corpus

• Coresets via Bilevel Optimization for Continual Learning and Streaming (2020, background): “While this heuristic may be converging only to a stationary point [24], such solutions are successful in many applications [45, 51].”
• Bilevel Optimization: Convergence Analysis and Enhanced Design (2020, methodology): “…(AID-BiO with a constant number of inner-loop steps as in our analysis), AID-BiO-increasing (AID-BiO with an increasing number of inner-loop steps under analysis in Ghadimi & Wang 2018), and two popular meta-learning algorithms MAML 2 (Finn et al., 2017) and ANIL 3 (Raghu et al., 2019).”
• iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients (2021, background): “Lemma 3 Neumann series (Lorraine et al., 2020) 1 Similar assumptions are also considered in (Couellan & Wang, 2016; Ghadimi & Wang, 2018; Grazzi et al., 2020b;a).”