Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances

Abstract

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.

References in corpus (4)

• Explaining and Harnessing Adversarial Examples
• Theoretically Principled Trade-off between Robustness and Accuracy
• Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
• Efficient Algorithms for Smooth Minimax Optimization

Cited by in corpus (16)

• Learning to Continuously Optimize Wireless Resource in a Dynamic Environment: A Bilevel Optimization Perspective
• Learning to Continuously Optimize Wireless Resource In Episodically Dynamic Environment
• Consensus-Based Optimization for Saddle Point Problems
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Generative Minimization Networks: Training GANs Without Competition
• Can FSK Be Optimised for Integrated Sensing and Communications?
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Low-rank Matrix Recovery With Unknown Correspondence
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• Heterogeneously-Distributed Joint Radar Communications: Bayesian Resource Allocation
• Output Perturbation for Differentially Private Convex Optimization: Faster and More General
• Maximin Optimization for Binary Regression
• Pure Characteristics Demand Models and Distributionally Robust Mathematical Programs with Stochastic Complementarity Constraints
• Robust MIMO Radar Waveform-Filter Design for Extended Target Detection in the Presence of Multipath
• MIMO Radar Waveform-Filter Design for Extended Target Detection from a View of Games
• Near-Field Secure Beamfocusing With Receiver-Centered Protected Zone