Skip navigation
Please use this identifier to cite or link to this item:
Title: Greedy Adversarial Equilibrium and Other Local Optima for Nonconvex-Nonconcave Min-Max Optimization
Authors: Peng, Michael
Advisors: Lee, Jason D.
Department: Mathematics
Class Year: 2021
Abstract: Min-max optimization of an objective function f : X × Y → R that is neither convex nor concave in either argument has attracted much attention in recent years due to its broad range of applications, particularly in training neural networks in an adversarial setting. Unfortunately, outside of the convex-concave setting, many traditional algorithms fail to converge, and it is unclear as to what even qualifies as a good notion of optimality. To this end, we study two common notions of local optima in this setting: local Nash equilibrium and local min-max points, providing proofs of some of their respective properties as well as corresponding algorithms and complexity results. We present greedy adversarial equilibrium, initially introduced by Keswani et al., as an alternative framework for nonconvex-nonconcave min-max optimization and prove convergence results for a corresponding training algorithm. Assuming access to deterministic zeroth and first-order oracles, we attain a tighter bound than Keswani et al. on the number of oracle evaluations required by the algorithm to achieve convergence with high probability.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat 
PENG-MICHAEL-THESIS.pdf338.63 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.