I have an optimization problem of the following form: $$\min_y\left[\max_x f(x,y)\right].$$ It is fairly straightforward to minimize $f(x,y)$ over $y$ with $x$ fixed, and similarly to maximize $f(x,y)$ over $x$ with $y$ fixed. If it helps, my $x$ problem is concave---but while I can solve the $y$ problem in closed-form it is not convex.
An obvious candidate for an optimization algorithm for the minimax problem might look something like the following: $$ \begin{array}{rl} x_{k+1}&\gets\arg\max_x f(x,y_k)\\ y_{k+1}&\gets\arg\min_y f(x_{k+1},y) \end{array} $$ But, this algorithm doesn't have to converge.
Given oracles for optimizing in one variable at a time, can we construct an optimization algorithm for the minimax problem?
The gradient descent-ascent (GDA) algorithm has a similar flavor, but for our problem finding the global optima for $x,y$ independently is possible so it doesn't seem necessary to just take small gradient steps. If it helps, I'm happy to add a quadratic term to $f$ and assume I can optimize the objective $f(x,y)+\alpha\|y-y_0\|_2^2-\beta\|x-x_0\|_2^2$.
