Algorithms for finding min-max equilibrium points in a zero sum game often exhibit cyclic behavior and non-convergence. The authors define a new solution concept for the zero sum game played through stochastic gradient descent (and similar such methods) and propose an algorithm which converges with very high probability. The equilibrium point is reached in time polynomial in dimension and smoothness parameters of the function. Importantly no convexity or concavity in either players control is assumed and the convergence is independent of the initialization point.
