Tight Bound for Sum of Heterogeneous Random Variables: Application to Chance Constrained Programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2022

Tight Bound for Sum of Heterogeneous Random Variables: Application to Chance Constrained Programming

Résumé

We study a tight Bennett-type concentration inequality for sums of heterogeneous and independent variables, defined as a one-dimensional minimization. We show that this refinement, which outperforms the standard known bounds, remains computationally tractable: we develop a polynomial-time algorithm to compute confidence bounds, proved to terminate with an epsilon-solution. From the proposed inequality, we deduce tight distributionally robust bounds to Chance-Constrained Programming problems. To illustrate the efficiency of our approach, we consider two use cases. First, we study the chance-constrained binary knapsack problem and highlight the efficiency of our cutting-plane approach by obtaining stronger solution than classical inequalities (such as Chebyshev-Cantelli or Hoeffding). Second, we deal with the Support Vector Machine problem, where the convex conservative approximation we obtain improves the robustness of the separation hyperplane, while staying computationally tractable.
Fichier principal
Vignette du fichier
main.pdf (694.57 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03865441 , version 1 (22-11-2022)

Identifiants

Citer

Quentin Jacquet, Riadh Zorgati. Tight Bound for Sum of Heterogeneous Random Variables: Application to Chance Constrained Programming. 2022. ⟨hal-03865441⟩
34 Consultations
26 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More