Maheshwari, Chinmay and Sasty, S. Shankar and Ratliff, Lillian and Mazumdar, Eric (2023) Convergent First-Order Methods for Bi-level Optimization and Stackelberg Games. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20230316-204025426
![]() |
PDF
- Submitted Version
See Usage Policy. 307kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20230316-204025426
Abstract
We propose an algorithm to solve a class of bi-level optimization problems using only first-order information. In particular, we focus on a class where the inner minimization has unique solutions. Unlike contemporary algorithms, our algorithm does not require the use of an oracle estimator for the gradient of the bi-level objective or an approximate solver for the inner problem. Instead, we alternate between descending on the inner problem using naïve optimization methods and descending on the upper-level objective function using specially constructed gradient estimators. We provide non-asymptotic convergence rates to stationary points of the bi-level objective in the absence of convexity of the closed-loop function and further show asymptotic convergence to only local minima of the bi-level problem. The approach is inspired by ideas from the literature on two-timescale stochastic approximation algorithms.
Item Type: | Report or Paper (Discussion Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||
ORCID: |
| ||||||||
Record Number: | CaltechAUTHORS:20230316-204025426 | ||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20230316-204025426 | ||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||
ID Code: | 120100 | ||||||||
Collection: | CaltechAUTHORS | ||||||||
Deposited By: | George Porter | ||||||||
Deposited On: | 16 Mar 2023 23:02 | ||||||||
Last Modified: | 16 Mar 2023 23:02 |
Repository Staff Only: item control page