BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Optimising star-convex functions - Jasper Lee\, Brown University
DTSTART:20160610T130000Z
DTEND:20160610T140000Z
UID:TALK66421@talks.cam.ac.uk
CONTACT:Dominic Mulligan
DESCRIPTION:We introduce a polynomial time algorithm for optimizing the cl
 ass of star-convex functions\, under no restrictions except boundedness on
  a region about the origin\, and Lebesgue measurability. The algorithm's p
 erformance is polynomial in the requested number of digits of accuracy\, c
 ontrasting with the previous best known algorithm of Nesterov and Polyak t
 hat has exponential dependence\, and that further requires Lipschitz secon
 d differentiability of the function\, but has milder dependence on the dim
 ension of the domain. Star-convex functions constitute a rich class of fun
 ctions generalizing convex functions to new parameter regimes\, and which 
 confound standard variants of gradient descent\; more generally\, we const
 ruct a family of star-convex functions where gradient-based algorithms pro
 vably give no information about the location of the global optimum. \nWe i
 ntroduce a new randomized algorithm for finding cutting planes based only 
 on function evaluations\, where\, counterintuitively\, the algorithm must 
 look outside the feasible region to discover the structure of the star-con
 vex function that lets it compute the next cut of the feasible region. We 
 emphasize that the class of star-convex functions we consider is as unrest
 ricted as possible: the class of Lebesgue measurable star-convex functions
  has theoretical appeal\, introducing to the domain of polynomial-time alg
 orithms a huge class with many interesting pathologies. We view our result
 s as a step forward in understanding the scope of optimization techniques 
 beyond the garden of convex optimization and local gradient-based methods.
 \n\nThis is joint work with Paul Valiant.
LOCATION:FW26
END:VEVENT
END:VCALENDAR