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

2020/06/30 by Meisam Razaviyayn, Tianjian Huang, Songtao Lu +3 · 116 citations
Computer Science · Engineering · Mathematics · #Adversarial Robustness in Machine Learning #Adversarial system #Algorithm #Artificial intelligence #Beamforming #Class (philosophy) #Computer science #Context (archaeology) #Generative grammar #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Multi-objective optimization #Optimization problem #Range (aeronautics) #Saddle point #Sparse and Compressive Sensing Techniques #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.1109/msp.2020.3003851

published in IEEE Signal Processing Magazine 37(5), 55-66 (Institute of Electrical and Electronics Engineers)

openalex created_date 2020/06/19 · arxiv created 2020/08/18 · openalex publication_date 2020/09/01 · arxiv updated 2021/08/11 · openalex updated_date 2026/08/05

Abstract

The min-max optimization problem, also known as thesaddle point problem, is a classical optimization problem that 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 that 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 (ML), to just name a few.

Citations

• Explaining and Harnessing Adversarial Examples
• An Iteratively Weighted MMSE Approach to Distributed Sum-Utility Maximization for a MIMO Interfering Broadcast Channel
• Some NP-complete problems in quadratic and nonlinear programming
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Theoretically Principled Trade-off between Robustness and Accuracy
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Efficient Algorithms for Smooth Minimax Optimization
• Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
• On Assessing ML Model Robustness: A Methodological Framework (Academic Track)
• Generative Adversarial Nets

Cited by

• Heterogeneously-Distributed Joint Radar Communications: Bayesian Resource Allocation
• Generative Minimization Networks: Training GANs Without Competition