BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian
  Sketching - Peter Richtarik (University of Edinburgh\; King Abdullah Univ
 ersity of Science and Technology (KAUST)\; Moscow Institute of Physics and
  Technology)
DTSTART:20190620T085000Z
DTEND:20190620T094000Z
UID:TALK126265@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:We develop a new family of variance reduced stochastic gradien
 t descent methods for minimizing the average of a very large number of smo
 oth functions. Our method&mdash\;JacSketch&mdash\;is motivated by novel de
 - velopments in randomized numerical linear algebra\, and operates by main
 taining a stochastic estimate of a Jacobian matrix composed of the gradien
 ts of individual functions. In each iteration\, JacSketch efficiently upda
 tes the Jacobian matrix by first obtaining a random linear measurement of 
 the true Jacobian through (cheap) sketching\, and then projecting the prev
 ious estimate onto the solution space of a linear matrix equa- tion whose 
 solutions are consistent with the measurement. The Jacobian estimate is th
 en used to compute a variance-reduced unbiased estimator of the gradient\,
  followed by a stochastic gradient descent step. Our strategy is analogous
  to the way quasi-Newton methods maintain an estimate of the Hessian\, and
  hence our method can be seen as a stochastic q uasi-gradient method. Inde
 ed\, quasi-Newton methods project the current Hessian estimate onto a solu
 tion space of a linear equation consistent with a certain linear (but non-
 random) measurement of the true Hessian. Our method can also be seen as st
 ochastic gradient descent applied to a controlled stochastic optimization 
 reformulation of the original problem\, where the control comes from the J
 acobian estimates. We prove that for smooth and strongly convex functions\
 , JacSketch converges linearly with a meaningful rate dictated by a single
  convergence theorem which applies to general sketches. We also provide a 
 refined convergence theorem which applies to a smaller class of sketches\,
  featuring a novel proof technique based on a stochastic Lyapunov function
 . This enables us to obtain sharper complexity results for variants of Jac
 Sketch with importance sampling. By specializing our general approach to s
 pecific sketching strategies\, JacSketch reduces to the celebrated stochas
 tic average gradient (SAGA) method\, and<br><br>Co-authors: Robert Mansel 
 Gower (Telecom ParisTech)\, Francis Bach (INRIA - ENS - PSL Research Unive
 rsity)<br>
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR