Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01vt150n35s
 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. URI: http://arks.princeton.edu/ark:/88435/dsp01vt150n35s Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat