A Caltech Library Service

Convergent First-Order Methods for Bi-level Optimization and Stackelberg Games

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)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Maheshwari, Chinmay0000-0003-3596-2851
Ratliff, Lillian0000-0001-8936-0229
Mazumdar, Eric0000-0002-1815-269X
Record Number:CaltechAUTHORS:20230316-204025426
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:120100
Deposited By: George Porter
Deposited On:16 Mar 2023 23:02
Last Modified:16 Mar 2023 23:02

Repository Staff Only: item control page