BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On momentum methods and acceleration in stochastic optimization - 
 Praneeth Netrapalli (Microsoft Research India)
DTSTART:20180521T150000Z
DTEND:20180521T160000Z
UID:TALK102841@talks.cam.ac.uk
CONTACT:Quentin Berthet
DESCRIPTION:It is well known that momentum gradient methods (e.g.\, Polyak
 's heavy ball\, Nesterov's acceleration) yield significant improvements ov
 er vanilla gradient descent in deterministic optimization (i.e.\, where we
  have access to exact gradient of the function to be minimized). However\,
  there is widespread sentiment that these momentum methods are not effecti
 ve for the purposes of stochastic optimization due to their instability an
 d error accumulation. Numerous works have attempted to quantify these inst
 abilities in the face of either statistical or non-statistical errors (Pai
 ge\, 1971\; Proakis\, 1974\; Polyak\, 1987\; Greenbaum\, 1989\; Roy and Sh
 ynk\, 1990\; Sharma et al.\, 1998\; d’Aspremont\, 2008\; Devolder et al.
 \, 2013\, 2014\; Yuan et al.\, 2016) but a precise understanding is lackin
 g. This work considers these issues for the special case of stochastic app
 roximation for the linear least squares regression problem\, and shows tha
 t:\n\n1. classical momentum methods (heavy ball and Nesterov's acceleratio
 n) indeed do not offer any improvement over stochastic gradient descent\, 
 and\n\n2. introduces an accelerated stochatic gradient method that provabl
 y achieves the minimax optimal statistical risk faster than stochastic gra
 dient descent (and classical momentum methods).\n\nCritical to the analysi
 s is a sharp characterization of accelerated stochastic gradient descent a
 s a stochastic process. While the results are rigorously established for t
 he special case of linear least squares regression\, experiments suggest t
 hat the conclusions hold for the training of deep neural networks.\n\nJoin
 t work with Prateek Jain\, Sham M. Kakade\, Rahul Kidambi and Aaron Sidfor
 d
LOCATION:MR14
END:VEVENT
END:VCALENDAR