๐Ÿ“–
Tight Bound for Sum of Heterogeneous Random Variables: Application to Chance Constrained Programming
Quentin Jacquet, Riadh Zorgati

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

Author / Organization:
Science & Mathematics Published 2022 Verification Pending

Overview & Synopsis

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Tight Bound for Sum of Heterogeneous Random Variables: Application to Chance Constrained Programming
Author / Organization Quentin Jacquet, Riadh Zorgati
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2022
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-159800
Original Source Link Visit Source Page on hal.science »