Stable Bounds on the Duality Gap of Separable Nonconvex Optimization Problems

Autor: Thomas Kerdreux, Igor Colin, Alexandre d’Aspremont
Přispěvatelé: Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Huawei Technologies France [Boulogne-Billancourt], Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Centre National de la Recherche Scientifique (CNRS), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019)
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Mathematics of Operations Research
Mathematics of Operations Research, 2022, ⟨10.1287/moor.2022.1291⟩
ISSN: 0364-765X
1526-5471
DOI: 10.1287/moor.2022.1291⟩
Popis: 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, Aubin and Ekeland 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; we relax it in several directions to show that nonconvexity can have a much milder impact on finite sum minimization problems, such as empirical risk minimization and multitask classification. As a byproduct, we show a new version of Maurey’s classical approximate Carathéodory lemma where we sample a significant fraction of the coefficients, without replacement, as well as a result on sampling constraints using an approximate Helly theorem, both of independent interest. Funding: A. d’Aspremont acknowledges support from the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program [Grant ANR-19-P3IA-0001] (PRAIRIE 3IA Institute), the Machine Learning and Optimisation Joint Research Initiative with the Fonds AXA pour la Recherche and Kamet Ventures, as well as a Google focused award.
Databáze: OpenAIRE
Externí odkaz: