Source-linked AI summary
Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiehed, Maziar Sanjabi, Mingyi Hong
TL;DR
Non-convex min-max optimization is important for robust decision-making and applications including fair machine learning, adversarial learning, and distributed processing, but its theory and algorithms remain limited. The paper surveys these applications, analyzes stationarity and algorithmic challenges, and reviews recent advances while identifying broader solvability and smoothness as future directions.
Problem
Non-convex and/or non-concave min-max problems are widely relevant but have seldom been rigorously analyzed, while global solutions are generally computationally intractable.
Method
The paper provides a selective survey of applications, stationarity concepts, theoretical challenges, and recent algorithms for non-convex min-max optimization.
Results
The survey identifies recent algorithmic advances, including potential-reduction, VI-based, and single-loop methods, while showing that some reformulations achieve theoretical convergence guarantees.
Takeaways & Limitations
Provably solvable non-convex non-concave problems remain limited, motivating extensions to broader problem classes and local-convergence or non-smooth settings.
Takeaways & Limitations
Existing algorithms require restrictive assumptions, and the class of problems provably solvable under current stationarity notions remains very limited.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Non-convex min-max optimization has become important across signal processing, optimization, and machine learning, but remains challenging and comparatively underanalyzed. The paper surveys applications, theoretical and algorithmic challenges, recent advances, and future directions.
- I. INTRODUCTION: The paper selectively surveys applications, theoretical challenges, algorithmic advances, open questions, and future research directions for non-convex min-max optimization.
- I. INTRODUCTION: Non-convex min-max problems model robust decisions against uncertainty or adversaries across signal processing and machine learning applications.Examples include robust transceiver design, fair resource allocation, jammer-aware communication, robust neural-network training, GANs, and fair inference.
- I. INTRODUCTION: Non-convex min-max problems are difficult because global solutions are generally NP-hard, motivating algorithms that seek stationary solutions.
- I. INTRODUCTION: In GANs, the generator minimizes a cost while the discriminator maximizes its negative, forming a min-max game that can measure distributional discrepancy.
2) Fair ML:
Fair machine learning incorporates fairness alongside predictive accuracy, and several fairness formulations naturally produce non-convex min-max optimization problems. These formulations balance model loss against statistical dependence on sensitive attributes or adversarial perturbations.
- 2) Fair ML:: Fair ML seeks accurate models while reducing discrimination against protected groups through preprocessing, in-processing, or postprocessing approaches.
- 2) Fair ML:: Adversarial preprocessing learns representations that minimize classifier loss while protecting sensitive attributes from inference.
- 2) Fair ML:: In-processing fairness adds a statistical-independence penalty to training loss, with λ balancing fairness against accuracy.
- 2) Fair ML:: When λ →∞, the formulation emphasizes independence between model output and sensitive attributes; when λ = 0, it imposes no fairness.
- 2) Fair ML:: Adversarial learning also formulates poisoning attacks and defenses as min-max problems involving bounded data perturbations and neural-network training.
4) Distributed processing:
Distributed optimization can be recast as a min-max saddle-point problem by introducing local variable copies and Lagrange multipliers. The resulting formulation couples primal variables with dual variables through the network incidence matrix.
- 4) Distributed processing:: Distributed nodes replace a shared decision variable with local copies and impose neighbor agreement through a linear constraint.
- 4) Distributed processing:: The incidence-matrix constraint enforces xi = xj for neighboring nodes, while the saddle-point form enables dedicated algorithms for distributed optimization.
- 4) Distributed processing:: The reformulated problem has objective coupling gi(xi) with y^T Ax, where y is the Lagrangian multiplier.
5) Max-Min fair transceiver design:
Max-min fair transceiver design allocates wireless power to maximize the minimum user rate across parallel channels. The discrete worst-user minimization can be transformed into a continuous simplex minimization, yielding a min-max formulation.
- 5) Max-Min fair transceiver design:: The design objective is to maximize the minimum communication rate among N transmitter-receiver pairs over K parallel channels.
- 5) Max-Min fair transceiver design:: User rates depend non-convexly on the transmit-power allocation because of interference and channel gains.
- 5) Max-Min fair transceiver design:: The inner minimization over the discrete user index can be reformulated using continuous variables on the probability simplex.
- 5) Max-Min fair transceiver design:: Because the simplex minimization is linear, an optimum occurs at an extreme point, making the continuous formulation equivalent to the original discrete one.
6) Communication in the presence of jammers:
Communication with jammers can be formulated as a non-convex min-max problem in which users maximize sum rate while jammers transmit noise to reduce it. Such problems are difficult because non-convex min-max optimization lacks broadly reliable tools and even GDA can fail to converge.
- Communication in the presence of jammers:: Jammers transmit noise to reduce system sum rate, while regular users allocate power to maximize information transmission.The formulation uses feasible power-allocation sets for users and jammers and can be converted to min-max form by negating the objective.
- Challenges: Non-convex min-max problems are difficult because non-convexity obstructs global optima and the min-max objective requires more than ordinary non-convex optimization.The paper contrasts these problems with regular smooth non-convex optimization, where projected gradient descent has standard convergence properties.
- Challenges: Projected gradient descent improves objective values and converges to first-order stationary points under mild assumptions in regular non-convex optimization.These properties motivate applying simple iterative methods to ordinary non-convex problems.
- Challenges: Gradient-descent ascent alternates projected descent and ascent steps, but it can fail in practical instances and fail to converge to a meaningful point.The paper illustrates this failure with a simple trajectory in Fig. 1.
IV. RECENT DEVELOPMENTS FOR SOLVING NON-CONVEX MIN-MAX PROBLEMS
The survey examines stationarity and optimality for non-convex min-max problems, where global solutions are generally hard to obtain and different stationarity notions capture different priorities. In particular, game-based stationarity is easier to check but can ignore the prescribed minimization–maximization order.
- IV. RECENT DEVELOPMENTS FOR SOLVING NON-CONVEX MIN-MAX PROBLEMS: Global solution of a non-convex min-max problem is NP-hard in general, so algorithms typically target stationary solutions.The paper frames stationarity through either optimization or zero-sum-game viewpoints.
- A. Optimality Conditions: Game-Stationary points are solutions of the corresponding variational inequality and are attractive because they have a game-theoretic interpretation and are relatively easy to check.Under mild assumptions, fixed-point theorems establish existence of such points.
- A. Optimality Conditions: Game-based stationarity ignores the minimization–maximization order, which matters because non-convex problems generally cannot interchange these operations and may have different solutions.This limitation is especially relevant when the order represents an application-specific priority, such as defense against adversarial attacks.
- A. Optimality Conditions: Optimization-Stationary points instead apply first-order stationarity to g(x)=max_y∈Y f(x,y), preserving the min-max order through the maximized inner objective.This notion exists under mild compactness and continuity assumptions, although checking it can be computationally intractable for general non-convex functions.
- A. Optimality Conditions: For the example f(x,y)=0.2xy−cos(y) on [−1,1]×[−2π,2π], the min-max problem has two global solutions, (0,−π) and (0,π).The surrounding discussion uses this example to contrast optimization and game-based stationarity.
B. Algorithms Based on Potential Reduction
Potential-reduction methods optimize the worst-case objective g(x)=max_y∈Y f(x,y), using Danskin’s theorem when the inner maximization is tractable. Their convergence guarantees depend on accurately solving or approximating that inner problem, which limits applicability to general non-convex non-concave settings.
- B. Algorithms Based on Potential Reduction: Potential-reduction methods minimize g(x)=max_y∈Y f(x,y), whose gradient can be obtained from the inner maximizer under Danskin’s theorem.The theorem assumes differentiability in x, strong concavity in y, and compactness of Y.
- B. Algorithms Based on Potential Reduction: Under Danskin’s theorem, gradient descent on g(x) is implemented by repeatedly solving the inner maximization and updating x using the resulting gradient.The resulting dynamics are equivalent to projected gradient descent on the potential function.
- B. Algorithms Based on Potential Reduction: Inexact inner solutions can still yield an approximate stationary point, with approximation accuracy determined by ϵ.The convergence guarantee can persist even when strong concavity is relaxed, provided the inner step remains computationally affordable.
- B. Algorithms Based on Potential Reduction: For concave-in-y objectives, accelerated and proximal-based procedures improve convergence by constructing locally strongly convex approximations with regularizers.This case also covers finite max problems after rewriting them in an appropriate form.
- B. Algorithms Based on Potential Reduction: Danskin-based algorithms apply only when the inner maximization can be computed efficiently, an assumption that generally fails for non-convex non-concave min-max problems.The paper notes that objective approximation may make the required inner step tractable in particular applications.
C. Algorithms Based on Solving VI
VI-based methods recast min-max optimization as variational inequalities, but non-convexity weakens the monotonicity properties required by classical algorithms. Double-loop procedures and related solution concepts therefore provide only conditional coverage of general non-convex problems.
- Applications: Finite weak-attacker reformulation converts a non-concave inner maximization into a concave problem and achieves comparable results with theoretical convergence guarantees.The reformulation generates a finite set of adversarial instances before applying a concave transformation.
- VI formulation: VI methods derive a mapping from the min-max objective and use it to formulate Stampacchia or Minty variational inequalities.Game-theoretic formulations naturally lead to algorithms targeting the Stampacchia VI, while double-loop dynamics may instead compute a Minty VI solution.
- VI formulation: Classical VI algorithms rely on strong monotonicity, which generally fails when the objective is non-convex and/or non-concave.A common workaround approximates the original mapping with a sequence of strongly monotone mappings.
- Solution concepts: For convex feasible sets, Minty VI solutions also satisfy the Stampacchia VI, and monotonicity gives the converse implication.These equivalences do not extend to generic non-convex or non-concave objectives.
- Solution concepts: Generic non-convex min-max problems may have Stampacchia VI solutions but no Minty VI solution, as illustrated by a cubic example.The example uses f(x, y) = x3 + 2xy − y2 over [−1, 1] × [−1, 1].
D. Algorithms Using Single-Loop Update
Single-loop methods update the minimization and maximization variables in alternating or simultaneous iterations, addressing applications where both sides evolve together. HiBSA adds a diminishing perturbation to the ascent update and is analyzed in power-control experiments.
- Motivation: Single-loop algorithms are preferred in applications where the minimizing and maximizing variables update simultaneously, but they are difficult to design and analyze.This challenge persists even for simple linear problems.
- HiBSA: HiBSA combines descent and ascent steps with a perturbed maximization update, providing a single-loop alternative to alternating gradient methods.The perturbation term γrρyr is intended to keep successive maximization iterates closer and avoid divergent patterns.
- HiBSA: Under strong concavity in y, HiBSA can set γr = 0; under mere concavity, convergence uses βr = O(1/r1/2) and γr = O(1/r1/4).The stated convergence target is a point satisfying the Game-Stationary condition.
- Power-control application: In jammer power control, HiBSA initially oscillates, converges to a lower sum-rate than interference pricing, and enables the jammer to reduce total system sum rate.The comparison uses HiBSA, interference pricing, and WMMSE in a network with regular users and a jammer.
E. Extension to Zeroth-order Based Algorithms
Zeroth-order min-max methods replace unavailable gradients with objective-value-based estimates, enabling adversarial applications where only model outputs are accessible. The survey illustrates this extension through HiBSA applied to data poisoning.
- Motivation: Zeroth-order methods use only objective values at queried points, making them useful when an adversary can access model outputs but not gradients.This setting motivates applying zeroth-order methods to practical adversarial attacks.
- Gradient estimation: A common zeroth-order estimator samples random unit-sphere directions and estimates the gradient of a smoothed objective rather than the original objective.The smoothing parameter is μ, and the estimator is unbiased for the gradient of the smoothing function.
- Poisoning application: The survey compares zeroth-order and first-order HiBSA in data poisoning, measuring testing accuracy across iterations and poisoning ratios.The poisoning experiment uses a logistic-regression training dataset, with the figure’s shaded region representing variance over 10 random trials.
V. CONNECTIONS AMONG ALGORITHMS AND OPTIMALITY CONDITIONS
This section relates Minty, Optimization-Stationary, and Game-Stationary conditions and compares algorithms by their convergence conditions and optimality criteria.
- Table II compares algorithms using convergence conditions and the optimality criteria for which they were originally designed.
- Fig. 4 maps the relationship among the Minty, Optimization-Stationary, and Game-Stationary conditions.
VI. CONCLUSION AND FUTURE RESEARCH DIRECTIONS
The conclusion identifies restrictive assumptions behind current non-convex min-max algorithms and outlines research directions toward broader solvability, robustness guarantees, convergence theory, and practical adaptation.
- Current algorithms require either one player's objective to be easy to optimize or Minty solutions to solve the Stampacchia VI.
- Many non-convex min-max instances satisfy neither assumption, motivating approximation by problems satisfying one of them.
- Future work should develop algorithms under more relaxed assumptions, including local convergence and broader nonconvex non-concave functions.
- Robust applications require methods that can provide or measure robustness certificates after optimization.
- The optimal gradient-based convergence rate remains unknown even when the objective is concave in y and possibly non-convex in x.