Despite the development of many new optimization techniques, constant step-size stochastic gradient descent (SGD) remains the tool of choice in modern machine learning. It performs unreasonably well in practice, both in convex settings where there are poor guarantees, and also in non-convex settings, where there are often no guarantees. In this talk, we will give an argument as to why it works for low-rank models, illustrating the argument for the particular case of phase retrieval.

Phase retrieval is the problem of solving systems of rank-1 quadratic equations, and can be solved by optimizing a non-convex, non-smooth objective. In order to obtain guarantees, however, a spectral initialization method is first used in order to get a constant error estimate. We will show how SGD works even from arbitrary initialization. The key insight is that the low-rank nature of the signal allows us to study the dynamics as a Markov process with a two-dimensional phase space, and in this phase space, the effective step size decreases as the dimension increases. Our analysis also introduces and makes use of several new ideas from stochastic process theory, which we believe will be of use much more broadly.