Un théorème approximatif de Shapley-Folkman.

Résumé Le théorème de Shapley-Folkman montre que les moyennes de Minkowski d'ensembles uniformément bornés ont tendance à être convexes lorsque le nombre de termes dans la somme devient beaucoup plus grand que la dimension ambiante. En optimisation, Aubin et Ekeland [1976] montrent que cela produit une limite a priori sur l'écart de dualité des problèmes d'optimisation non convexes séparables impliquant des sommes finies. Cette limite est très conservatrice et dépend de quantités instables, et nous la relaxons dans plusieurs directions pour montrer que la non-convexité peut avoir un impact beaucoup plus faible sur les problèmes de minimisation de sommes finies tels que la minimisation du risque empirique et la classification multi-tâches. Comme sous-produit, nous montrons une nouvelle version du lemme classique approximatif de Carath'eodory de Maurey où nous échantillonnons une fraction significative des coefficients, sans remplacement, ainsi qu'un résultat sur les contraintes d'échantillonnage utilisant un théorème de Helly approximatif, tous deux d'intérêt indépendant.