CaltechAUTHORS
  A Caltech Library Service

Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization

Maheshwari, Chinmay and Chiu, Chih-Yuan and Mazumdar, Eric and Sastry, S. Shankar and Ratliff, Lillian J. (2021) Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20210903-213714292

[img] PDF - Submitted Version
See Usage Policy.

838kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210903-213714292

Abstract

Min-max optimization is emerging as a key framework for analyzing problems of robustness to strategically and adversarially generated data. We propose a random reshuffling-based gradient free Optimistic Gradient Descent-Ascent algorithm for solving convex-concave min-max problems with finite sum structure. We prove that the algorithm enjoys the same convergence rate as that of zeroth-order algorithms for convex minimization problems. We further specialize the algorithm to solve distributionally robust, decision-dependent learning problems, where gradient information is not readily available. Through illustrative simulations, we observe that our proposed approach learns models that are simultaneously robust against adversarial distribution shifts and strategic decisions from the data sources, and outperforms existing methods from the strategic classification literature.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2106.09082arXivDiscussion Paper
ORCID:
AuthorORCID
Mazumdar, Eric0000-0002-1815-269X
Ratliff, Lillian J.0000-0001-8936-0229
Record Number:CaltechAUTHORS:20210903-213714292
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210903-213714292
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110725
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:07 Sep 2021 16:14
Last Modified:07 Sep 2021 19:35

Repository Staff Only: item control page