Stochastic gradient pursuit methods and their ties to random matrix theory

Deanna Needell, UCLA Mathematics of Information and Applications Seminar
November 13, 2014 3:00 pm ESB 4133

In this talk we will give a brief overview of stochastic gradient pursuit and the closely related Kaczmarz method for solving linear systems, or more generally convex optimization problems. We will present some new results which tie these methods together and prove the best known convergence rates for these methods under mild Lipschitz conditions. The methods empirically and theoretically rely on probability distributions to dictate the order of sampling in the algorithms. It turns out that the choice of distribution may drastically change the performance of the algorithm, and the theory has only begun to explain this phenomenon.