论文标题
紧密绑定到异质随机变量的总和：应用于机会约束编程
Tight Bound for Sum of Heterogeneous Random Variables: Application to Chance Constrained Programming
论文作者
论文摘要
我们研究了贝内特型浓度不平等，用于异质和自变量的总和，定义为一维最小化。我们表明，这种优于标准已知边界的改进仍然可以计算：我们开发了一种多项式时间算法来计算置信度界限，该算法被证明可以随epsilon-solution终止。从拟议的不平等中，我们将紧密的分配范围推断为偶然受限的编程问题。为了说明我们方法的效率，我们考虑了两种用例。首先，我们研究了偶然受限的二进制背包问题，并通过获得比古典不平等（例如Chebyshev-Cantelli或Hoeffding）更强大的解决方案来突出我们的切面方法的效率。其次，我们处理支持向量机问题，其中凸的保守近似提高了分离超平面的鲁棒性，同时保持计算可牵持。
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.
