BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Harder\, Better\, Faster\, Stronger Convergence Rates for Least-Sq
 uares Regression - Francis Bach (INRIA)
DTSTART:20161007T150000Z
DTEND:20161007T160000Z
UID:TALK67485@talks.cam.ac.uk
CONTACT:Quentin Berthet
DESCRIPTION:We consider the optimization of a quadratic objective function
  whose gradients are only accessible through a stochastic oracle that retu
 rns the gradient at any given point plus a zero-mean finite variance rando
 m error. We present the first algorithm that achieves jointly the optimal 
 prediction error rates for least-squares regression\, both in terms of for
 getting of initial conditions in O(1/n^2)\, and in terms of dependence on 
 the noise and dimension d of the problem\, as O(d/n). Our new algorithm is
  based on averaged accelerated regularized gradient descent\, and may also
  be analyzed through finer assumptions on initial conditions and the Hessi
 an matrix\, leading to dimension-free quantities that may still be small w
 hile the "optimal" terms above are large. In order to characterize the tig
 htness of these new bounds\, we consider an application to non-parametric 
 regression and use the known lower bounds on the statistical performance (
 without computational limits)\, which happen to match our bounds obtained 
 from a single pass on the data and thus show optimality of our algorithm i
 n a wide variety of particular trade-offs between bias and variance. (join
 t work with Aymeric Dieuleveut and N. Flammarion)
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge.
END:VEVENT
END:VCALENDAR