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:Isaac Newton Institute Seminar Series
SUMMARY:On computational barriers in data science and the
paradoxes of deep learning - Anders Hansen (Univer
sity of Cambridge)
DTSTART;TZID=Europe/London:20171102T111000
DTEND;TZID=Europe/London:20171102T120000
UID:TALK94354AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/94354
DESCRIPTION:The use of regularisation techniques such as l^1 a
nd Total Variation in Basis Pursuit and Lasso\, as
well as linear and semidefinite programming and n
eural networks (deep learning) has seen great succ
ess in data science. Yet\, we will discuss the fol
lowing paradox: it is impossible to design algorit
hms to find minimisers accurately for these proble
ms when given inaccurate input data\, even when th
e inaccuracies can be made arbitrarily small. The
paradox implies that any algorithm designed to sol
ve these problems will fail in the following way:
For fixed dimensions and any small accuracy parame
ter epsilon > 0\, one can choose an arbitrary larg
e time T and find an input such that the algorithm
will run for longer than T and still not have rea
ched epsilon accuracy. Moreover\, it is impossible
to determine when the algorithm should halt to ac
hieve an epsilon accurate solution. The largest ep
silon for which this failure happens is called the
Breakdown-epsilon. Typically\, the Breakdown-epsi
lon > 1/2 even when the the input is bounded by on
e\, is well-conditioned\, and the objective functi
on can be computed with arbitrary accuracy.

**Despite the paradox we explain why empirically m
any modern algorithms perform very well in real-wo
rld scenarios. In particular\, when restricting to
subclasses of problems the Breakdown epsilon may
shrink. Moreover\, typically one can find polynomi
al time algorithms in L and n\, where L < log(1/Br
eakdown-epsilon) is the number of correct digits i
n the computed solution and n is the size of the i
nput data. However\, the Breakdown-epsilon is the
breaking point\, and for L > \; log(1/Breakdow
n-epsilon)\, any algorithm\, even randomised\, bec
omes arbitrarily slow and will not be able to halt
and guarantee L correct digits in the output. **

The above result leads to the paradoxes of de
ep learning: (1) One cannot guarantee the existenc
e of algorithms for accurately training the neural
network\, even if there is one minimum and no loc
al minima. Moreover\, (2) one can have 100% succes
s rate on arbitrarily many test cases\, yet uncoun
tably many misclassifications on elements that are
arbitrarily close to the training set.

Thi
s is joint work with Alex Bastounis (Cambridge) an
d Verner Vlacic (ETH)

LOCATION:Seminar Room 1\, Newton Institute
CONTACT:INI IT
END:VEVENT
END:VCALENDAR