Stable Bounds on the Duality Gap of Separable Nonconvex Optimization Problems

Thomas Kerdreux (), Igor Colin () and Alexandre d’Aspremont ()
Additional contact information
Thomas Kerdreux: Département d’Informatique, UMR 8548, École Normale Supérieure, 75005 Paris, France
Igor Colin: Huawei, 92100 Boulogne-Billancourt, France
Alexandre d’Aspremont: Département d’Informatique, UMR 8548, École Normale Supérieure, 75005 Paris, France

Mathematics of Operations Research, 2023, vol. 48, issue 2, 1044-1065

Abstract: 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.

Keywords: 90C26; 90C25; convex relaxation; Shapley-Folkman theorem (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1291 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:2:p:1044-1065

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().