BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Statistics
SUMMARY:Harder\, Better\, Faster\, Stronger Convergence Ra
tes for Least-Squares Regression - Francis Bach (I
NRIA)
DTSTART;TZID=Europe/London:20161007T160000
DTEND;TZID=Europe/London:20161007T170000
UID:TALK67485AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/67485
DESCRIPTION:We consider the optimization of a quadratic object
ive function whose gradients are only accessible t
hrough a stochastic oracle that returns the gradie
nt at any given point plus a zero-mean finite vari
ance random error. We present the first algorithm
that achieves jointly the optimal prediction error
rates for least-squares regression\, both in term
s of forgetting of initial conditions in O(1/n^2)\
, and in terms of dependence on the noise and dime
nsion d of the problem\, as O(d/n). Our new algori
thm is based on averaged accelerated regularized g
radient descent\, and may also be analyzed through
finer assumptions on initial conditions and the H
essian matrix\, leading to dimension-free quantiti
es that may still be small while the "optimal" ter
ms above are large. In order to characterize the t
ightness of these new bounds\, we consider an appl
ication to non-parametric regression and use the k
nown lower bounds on the statistical performance (
without computational limits)\, which happen to ma
tch our bounds obtained from a single pass on the
data and thus show optimality of our algorithm in
a wide variety of particular trade-offs between bi
as and variance. (joint work with Aymeric Dieuleve
ut and N. Flammarion)
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge.
CONTACT:Quentin Berthet
END:VEVENT
END:VCALENDAR