# Minimax optimization with an oracle

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$$.

• Can you speak of some properties of $f(x,y)$? Is it possible to split it for instance such that $f(x,y)=g(x) \cdot h(y)$ or can $f$ take some similar special form? – Tolga Birdal Dec 6 '20 at 23:49
• No special form, I'm afraid! The x problem is concave, and the y problem is on a low-dimensional compact group, if that helps. – Justin Solomon Dec 7 '20 at 4:22