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:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Optimising star-convex functions - Jasper Lee\, Br
own University
DTSTART;TZID=Europe/London:20160610T140000
DTEND;TZID=Europe/London:20160610T150000
UID:TALK66421AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/66421
DESCRIPTION:We introduce a polynomial time algorithm for optim
izing the class of star-convex functions\, under n
o restrictions except boundedness on a region abou
t the origin\, and Lebesgue measurability. The alg
orithm's performance is polynomial in the requeste
d number of digits of accuracy\, contrasting with
the previous best known algorithm of Nesterov and
Polyak that has exponential dependence\, and that
further requires Lipschitz second differentiabilit
y of the function\, but has milder dependence on t
he dimension of the domain. Star-convex functions
constitute a rich class of functions generalizing
convex functions to new parameter regimes\, and wh
ich confound standard variants of gradient descent
\; more generally\, we construct a family of star-
convex functions where gradient-based algorithms p
rovably give no information about the location of
the global optimum. \nWe introduce a new randomize
d algorithm for finding cutting planes based only
on function evaluations\, where\, counterintuitive
ly\, the algorithm must look outside the feasible
region to discover the structure of the star-conve
x function that lets it compute the next cut of th
e feasible region. We emphasize that the class of
star-convex functions we consider is as unrestrict
ed as possible: the class of Lebesgue measurable s
tar-convex functions has theoretical appeal\, intr
oducing to the domain of polynomial-time algorithm
s a huge class with many interesting pathologies.
We view our results as a step forward in understan
ding the scope of optimization techniques beyond t
he garden of convex optimization and local gradien
t-based methods.\n\nThis is joint work with Paul V
aliant.
LOCATION:FW26
CONTACT:Dominic Mulligan
END:VEVENT
END:VCALENDAR