BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:An Approximate Shapley-Folkman Theorem. - Alex d'Aspremont (CNRS -
  Ecole Normale Superieure Paris)
DTSTART:20180626T150000Z
DTEND:20180626T154500Z
UID:TALK107410@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:with Thomas Kerdreux and Igor Colin.  The Shapley-Folkman theo
 rem shows that Minkowski averages of uniformly bounded sets tend to be con
 vex when the number of terms in the sum becomes much larger than the ambie
 nt dimension. In optimization\, \\citet{Aubi76} show that this produces an
  a priori bound on the duality gap of separable nonconvex optimization pro
 blems involving finite sums. This bound is highly conservative and depends
  on unstable quantities\, and we relax it in several directions to show th
 at non convexity can have a much milder impact on finite sum minimization 
 problems such as empirical risk minimization and multi-task classification
 . As a byproduct\, we show a new version of Maurey&#39\;s classical approx
 imate Carath\\&#39\;eodory lemma where we sample a significant fraction of
  the coefficients\, without replacement.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR