How to Make the Gradients Small in Convex and Min-Max Optimization

One of the most fundamental facts in unconstrained convex optimization is that every point with zero gradient is also a global function minimum. However, the problem of efficiently computing points with small gradients is significantly different from the problem of efficiently computing points with small objective functions values, and methods that exhibit optimal convergence rates under one of these two criteria do not in general exhibit optimal convergence rates under both. In particular, the accelerated gradient method of Nesterov is iteration-complexity-optimal in terms of minimizing smooth (gradient-Lipschitz) convex functions, but suboptimal in terms of finding their near-stationary points.

While the complexity of minimizing convex functions is well-understood for various broad classes of problems, much less is known about the complexity of minimizing the functions' gradients in the appropriate norms. Our understanding is even more limited for the more general setting of min-max optimization. In this talk, I will discuss why finding points with small gradients is an intriguing problem, what we know so far, and what kinds of questions we can hope to answer looking forward.