BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On computational barriers in data science and the paradoxes of dee
 p learning - Anders Hansen (University of Cambridge)
DTSTART:20171102T111000Z
DTEND:20171102T120000Z
UID:TALK94354@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:The use of regularisation techniques such as l^1 and Total Var
 iation in Basis Pursuit and Lasso\, as well as linear and semidefinite pro
 gramming and neural networks (deep learning) has seen great success in dat
 a science. Yet\, we will discuss the following paradox: it is impossible t
 o design algorithms to find minimisers accurately for these problems when 
 given inaccurate input data\, even when the inaccuracies can be made arbit
 rarily small. The paradox implies that any algorithm designed to solve the
 se problems will fail in the following way: For fixed dimensions and any s
 mall accuracy parameter epsilon > 0\, one can choose an arbitrary large ti
 me T and find an input such that the algorithm will run for longer than T 
 and still not have reached epsilon accuracy. Moreover\, it is impossible t
 o determine when the algorithm should halt to achieve an epsilon accurate 
 solution. The largest epsilon for which this failure happens is called the
  Breakdown-epsilon. Typically\, the Breakdown-epsilon > 1/2 even when the 
 the input is bounded by one\, is well-conditioned\, and the objective func
 tion can be computed with arbitrary accuracy. <br><br>Despite the paradox 
 we explain why empirically many modern algorithms perform very well in rea
 l-world scenarios. In particular\, when restricting to subclasses of probl
 ems the Breakdown epsilon may shrink. Moreover\, typically one can find po
 lynomial time algorithms in L and n\, where L < log(1/Breakdown-epsilon) i
 s the number of correct digits in the computed solution and n is the size 
 of the input data. However\, the Breakdown-epsilon is the breaking point\,
  and for L >&nbsp\; log(1/Breakdown-epsilon)\, any algorithm\, even random
 ised\, becomes arbitrarily slow and will not be able to halt and guarantee
  L correct digits in the output. <br><br>The above result leads to the par
 adoxes of deep learning: (1) One cannot guarantee the existence of algorit
 hms for accurately training the neural network\, even if there is one mini
 mum and no local minima. Moreover\, (2) one can have 100% success rate on 
 arbitrarily many test cases\, yet uncountably many misclassifications on e
 lements that are arbitrarily close to the training set.<br><br>This is joi
 nt work with Alex Bastounis (Cambridge) and Verner Vlacic (ETH)<br>
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR