CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20230316-204025426

[img] 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:
URLURL TypeDescription
http://arxiv.org/abs/2302.01421arXivDiscussion Paper
ORCID:
AuthorORCID
Maheshwari, Chinmay0000-0003-3596-2851
Ratliff, Lillian0000-0001-8936-0229
Mazumdar, Eric0000-0002-1815-269X
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