1

I am reading this paper:

ai.stanford.edu/~ang/papers/icml04-apprentice.pdf

Step 2 of section 3 is to compute an expression of the form max(min(expr)). What does this mean?

I made a simple example of such an expression and am equally puzzled as to how to evaluate it:

$\max_{x \in (-3,5)} \min_{y \in \{-1,1\}} \frac{x-2}{y}$

EDIT: I changed the example problem (-1,1) -> {-1,1}.

capybaralet
  • 1,265

2 Answers2

3

Fix $x \in (-3,5)$. Then, solve the problem $f(x) = \min_{y \in (-1,1)} \frac{x-2}{y}$. Then, you have $f(x)$ defined on $(-3,5)$. Now solve $\max_{x \in (-3,5)} f(x)$.

There are various theorems on problems of the sort, known as minimax theorems (such as sion's minimax theorem, von neumann's minimax theorem, etc.)

Batman
  • 19,390
  • So the answer will depend on the x that you initially chose. I think they are just using poor notation in the paper I reference. I noticed after posting that they specify what the expression actually means in equations (10-12). – capybaralet Feb 20 '15 at 22:11
  • 1
    No, it doesn't. You first solve the inner minimization assuming $x$ is fixed (giving $f(x)$, then you solve the outer maximization over $x$. – Batman Feb 21 '15 at 16:43
  • I changed the example from y in (-1,1) to y in {-1,1}.

    In that case, if x > 2, then y = -1 minimizes the expression, but if x < 2, then y = 1 minimizes the expression.

     – capybaralet Feb 21 '15 at 21:25
  • 3
    So f(x) = x-2/ -1 for x>2 and f(x)=x-2/ 1 for x<2. – mathematician Feb 21 '15 at 23:07
1

First take the minimum of $\frac{x-2}{y}$ for $y\in (-1,1)$. Then that 'minimum' is in terms of $x$. Now take the maximum of that 'minimum' for $x\in (-3,5)$. But your example is little bit inappropriate because for instance $\frac{x-2}{y}$ is not defined at $y=0$. However, this is the procedure you have to use.

Extremal
  • 5,785