COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > An Approximate Shapley-Folkman Theorem.

## An Approximate Shapley-Folkman Theorem.Add to your list(s) Download to your calendar using vCal - Alex d'Aspremont (CNRS - Ecole Normale Superieure Paris)
- Tuesday 26 June 2018, 16:00-16:45
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact INI IT. STSW04 - Future challenges in statistical scalability with Thomas Kerdreux and Igor Colin. The Shapley-Folkman theorem shows that Minkowski averages of uniformly bounded sets tend to be convex when the number of terms in the sum becomes much larger than the ambient dimension. In optimization, \citet{Aubi76} show that this produces an a priori bound on the duality gap of separable nonconvex optimization problems involving finite sums. This bound is highly conservative and depends on unstable quantities, and we relax it in several directions to show that 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's classical approximate Carath\'eodory lemma where we sample a significant fraction of the coefficients, without replacement. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsCambridge Network Sales & Marketing SIG Joint Machine Learning Seminars LMS Invited Lectures 2011## Other talksAutumn Cactus & Succulent Show Development of SAW-driven photon detectors and sources in an undoped GaAs/AlGaAs quantum well structure Differential responses to cognitive training: insights from a machine learning approach Self-Other Processes in ASD - the Case of Empathy Competitive Online Algorithms for Budgeted Allocation with Application to Online Experiment Design |