Is Minimax equals to Maximin?

Consider a loss funcation $\ell(x,y)$ with a penalty $g(x,y)$

If I want to consider the worst case robust scenario, that is

\begin{equation} \min_x \max_y \ell(x,y) + g(x,y) \end{equation}

Is it equivalent to consider the maximin version

\begin{equation} \max_y \min_x \ell(x,y) + g(x,y) \end{equation}

If yes, does it mean that I can consider the problem as an ordinary optimization problem once

\begin{equation} \min_x \ell(x,y) + g(x,y) \end{equation}

or

\begin{equation} \max_y \ell(x,y) + g(x,y) \end{equation}

has close form solution ?

Solution 1:

In general, if $X$ and $Y$ are non-empty sets and $f:X\times Y\to\mathbb R$, then $$\sup_{x\in X}\inf_{y\in Y}f(x,y)\leq\inf_{y\in Y}\sup_{x\in X}f(x,y)\quad(*)$$ and strict inequality is possible.

For example, let $X=Y=\mathbb R$ and $$f(x,y)=\begin{cases}0&\text{if $x=y$,}\\1&\text{otherwise.}\end{cases}$$ In this case, for any given $x^*\in X$, $f(x^*,x^*)=0$, so $\inf_{y\in Y}f(x^*,y)=0$. Since this is true for all $x^*\in X$, it follows that $\sup_{x\in X}\inf_{y\in Y}f(x,y)=0$, so the left-hand side of $(*)$ vanishes. On the other hand, for any given $y^*\in Y$, $f(y^*+1,y^*)=1$, so $\sup_{x\in X}f(x,y^*)=1$ and this is true for all $y^*\in Y$, so $\inf_{y\in Y}\sup_{x\in X}f(x,y)=1$. In this case, $(*)$ holds strictly.

At any rate, there do exist so-called minimax theorems establishing sufficient conditions on $X$, $Y$, and $f$ for $(*)$ to hold with equality.

To see why $(*)$ holds, suppose that it does not, so that $$\sup_{x\in X}\inf_{y\in Y}f(x,y)>\inf_{y\in Y}\sup_{x\in X}f(x,y).$$ We can derive a contradiction: By the definition of supremum (the least upper bound), there must exist some $x^*\in X$ such that $$\inf_{y\in Y}f(x^*,y)>\inf_{y\in Y}\sup_{x\in X}f(x,y).$$ Similarly, by the definition of infimum (the greatest lower bound), there exists some $y^*\in Y$ such that $$\inf_{y\in Y}f(x^*,y)>\sup_{x\in X}f(x,y^*).\quad(\spadesuit)$$ Also, $$f(x^*,y^*)\geq\inf_{y\in Y}f(x^*,y)\quad(\heartsuit)$$ and $$\sup_{x\in X}f(x,y^*)\geq f(x^*,y^*).\quad(\clubsuit)$$ Putting $(\heartsuit)$, $(\spadesuit)$, and $(\clubsuit)$ together yields $$f(x^*,y^*)\geq\inf_{y\in Y}f(x^*,y)>\sup_{x\in X}f(x,y^*)\geq f(x^*,y^*),$$ which is a contradiction.