Convex Optimization 2026, 29 - Chebyshev and Chernoff Bounds

Chebyshev bounds give an upper bound on the probability of a set, from known expected values. Examples include Markov's inequality, and Chebyshev's bound. They make it possible to compute a bound on the probability through convex optimization. For a random variable X and set on which the bound is to be placed C, note 1_C as the 0-1 indicator function on C. In such cases, prior knowledge should consist of known expected values of some functions acting on X. If f(z) ≥ 1_C(z) ∀ z ∈ S, then E f(X) = prob(X ∈ C). These bounds can be found by minimizing the x₀ + a₁x₁ + ... with such f(z) as conditions. The problem is always convex, due to construction of the constraints (Eq. 7.17). In simple cases, such problems can be solved analytically.

Given the first and second moments of a variable X: E X = a ∈ ℝ^m; E X X^T = Σ ∈ 𝕊^m, express f as a general quadratic function z^TPz + 2q^Tz + r with P ∈ 𝕊^m, q ∈ ℝ^m, r ∈ ℝ. Its constraint can be written as a linear matrix inequality, and for a complement C of an open polyhedron, the Chebyshev bound problem emerges as minization of tr(ΣP) + 2q^Ta + r, with semidefinite constraints in P, q, r and further parameters τ_i appearing in the constraint matrices (Eq. 7.19). The optimal value is an upper bound on prob(X ∈ C). (7.4.1)

A random variable X on ℝ has Chernoff bound states as log prob(X ≥ u) ≤ inf{-λu + log E e^λX} (Eq. 7.20). The log-term on the right side is the cumulant generating function of the distribution, which is always convex. As a consequence, the function to be minimized is convex. The Chernoff bound can be extended to a more general setting in ℝ^m. Given a subset C and the 0-1 indicator function of C 1_C, an upper bound on prob(X ∈ C) can be derived as E 1_C(X) ≤ E f(X) (p. 379).