Professor Andrea Montanari, Stanford University

How do gradient methods solve non-convex empirical risk minimization problems?

Abstract

Gradient-based (a.k.a. ‘first order’) optimization algorithms are routinely used to solve large scale non-convex problems arising from applications. Yet, it is generally hard to predict when these algorithms converge to a near-global optimum. In order to gain insight into this general question, we study the classical problem of solving n random equations in d real variables. We assume that the equations are independent realizations of a common rotationally-invariant Gaussian process in d dimensions. A special case is the one of random polynomial equations, which has been studied since the seminal contributions of Littlewood-Oﬀord and Kac in the 1940s (who initiated the study of existence of solutions of random polynomials) of and of Shub and Smale in the 1980s. We formulate this as a nonconvex optimization problem, and characterize precisely the behavior of local algorithms based on gradient or Hessian information. We compare these predictions with the empirical behavior of stochastic gradient descent and observe that the latter is close to the optimal algorithm. [Based on joint work with Eliran Subag.]