Min-max optimization

A min-max optimization (MMO) problem is a mathematical optimization problem of the following form:

$\min _{\mathbf {x} \in \mathbb {R} ^{d_{x}}}\max _{\mathbf {y} \in \mathbb {R} ^{d_{y}}}f(\mathbf {x} ,\mathbf {y} )~~~{\text{ such that }}~~~g(\mathbf {x} ,\mathbf {y} )\leq 0$,

where f is a bounded function and g is a convex function. MMO problems play a central role in game theory, convex optimization and online machine learning. The solution of an MMO problem involves finding a feasible pair of vectors (x*,y*) that is a saddle point, that is, it satisfies the following two conditions simultaneously:

• f(x*,y*) ≤ f(x,y*) for all x with g(x,y*) ≤ 0;
• f(x*,y*) ≥ f(x*,y) for all y with g(x*,y) ≤ 0.

Note that the optimization is not done sequentially (maximize f(x,y) over y for every fixed x, then maximize the resulting function over x). It is done simultaneously: the solution should both be minimum over x for the given y*, and maximum over y for the given x*.

The solution to an MMO problem is a Nash equilibrium in a two-player zero-sum game, where the payoff of the y player is f(x,y) (and the payoff of the x player is -f(x,y)). Thus, solving an MMO problem is a special case of Nash equilibrium computation.

Convex-concave objective

The function f is called convex-concave if it is a convex function of x for any fixed y, and a concave function of y for any fixed x. When f is continuous and convex-concave, and the constraint set is a convex compact space, MMO always has a solution, which can be computed efficiently using convex programming. This was proved by Rosen in 1965 and was used to prove the existence of Nash equilibria in concave games.

Sion's minimax theorem (1958) proves an even more general statement: if f is a quasiconvex function of x for any fixed y, and a quasiconcave function of y for any fixed x, and the constraint set is a convex compact space, MMO always has a solution, which can be computed by sequentially computing the maximum and then the minimum, or the minimum and then the maximum (the two sequential computations lead to identical outcomes in this case).

If f is L-smooth, the problem can be solved using first-order methods, achieving an approximation error polynomial in L and 1/T in T iterations.

If f is also strongly convex-concave, linear convergence rate is possible.

Non convex-concave objective

In deep learning, it is often required to solve MMO with objectives that are not convex-concave. This is particularly useful for testing the robustness of deep learning systems against adversaries, as we want to compute the minimum (over all attack strategies) of the maximum (over all defense strategies) of our payoff.

In non convex-concave MMO, a solution might not exist even when the feasible set is compact (this is in contrast to standard minimization or maximization problems, where a solution always exists even when the objective is neither convex nor concave). An example is when f(x,y) = (x-y)² and the feasible set is the unit cube [0,1]x[0,1]. Here, for every fixed x, the maximum over y is attained at either y=0 (if x>0.5) or y=1 (if x<0.5). However, for every fixed y, the minimum over x is attained at x=y. Hence, no point is simultaneously maximum over y and minimum over x.

Checking whether a given MMO problem has a solution is NP-hard. It remains NP-hard even in the special case in which the feasible region is a box [0,1]^d, the function f is G-Lipschitz and L-smooth, and only an epsilon-approximate solution is allowed (where 1/epsilon, G and L are polynomial in the dimension d). First order methods to not work well for such problems.

Daskalakis, Skoutakis and Zampetakis study such MMO with linear constraints (the feasible set is a polytope). They analyze the run-time complexity of computing approximatre local min-max equilibria as a function of the approximation parameters, the smoothness and the Lipschitz constant of the objective function.

See also

• Lexicographic max-min optimization - a different kind of optimization problem (multi-objective rather than single objective).
• Folk theorem (game theory) - a theorem in which minmax payments are important. They are known as "punishment points" or "threat points", since a player cannot be punished beyond that.
• Cooperative bargaining - another field in which minmax payments are important. Here, they are better known as "disagreement points" or "status quo points".
• Minimax theorem - gives conditions on games, guaranteeing that the minimax value equals the maximin value.