Non-convex Min-Max Optimization: Applications, Challenges, and Recent
  Theoretical Advances
  The min-max optimization problem, also known as the saddle point problem, is
a classical optimization problem which is also studied in the context of
zero-sum games. Given a class of objective functions, the goal is to find a
value for the argument which leads to a small objective value even for the
worst case function in the given class. Min-max optimization problems have
recently become very popular in a wide range of signal and data processing
applications such as fair beamforming, training generative adversarial networks
(GANs), and robust machine learning, to just name a few. The overarching goal
of this article is to provide a survey of recent advances for an important
subclass of min-max problem, where the minimization and maximization problems
can be non-convex and/or non-concave. In particular, we will first present a
number of applications to showcase the importance of such min-max problems;
then we discuss key theoretical challenges, and provide a selective review of
some exciting recent theoretical and algorithmic advances in tackling
non-convex min-max problems. Finally, we will point out open questions and
future research directions.
