Stochastic gradient pursuit methods and their ties to random matrix theory

02/04/2014 - 12:15pm
02/04/2014 - 1:10pm
Deanna Needell (Claremont McKenna College)

In this blackboard 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. We conclude with an interesting open problem about convergence which links the results to an important open question in random matrix theory.

Mudd Science Library 126, Pomona College