# Heterogeneous Hoeffding/McDiarmid

Hoeffding's inequality for independent random variables $$a_i\le X_i\le b_i$$ states that their sum has sub-Gaussian tails, decaying as $$\exp(-2t^2/\sum_i (b_i-a_i)^2)$$. Question: Are there any interesting applications exploiting the heterogeneous ranges? In all of the applications I'm aware of, either the $$X_i$$ all have the same range, or else Hoeffding/McDiarmid (and for that matter, Bernstein/Bennett) are simply too crude, and a sharper tool such as Kearns-Saul is called for (see, e.g., Theorem 1(i) in http://jmlr.org/papers/v16/berend15a.html, or Theorem 2.1 in https://projecteuclid.org/euclid.ecp/1465315542; Talagrand's inequality also comes to mind of course). So again: is heterogenous Hoeffding actually ever used?

Well what do you know -- in a recent paper of ours, https://arxiv.org/abs/1910.05270, the inequalities leading to (12) invoke Hoeffding where the $$(b_i-a_i)^2=p_i^2$$, and further the $$0\le p_i\le c$$ satisfy $$\sum_i p_i\le 1$$, which implies $$\sum_i p_i^2\le c$$ -- precisely the sort of heterogeneous Hoeffding bound I had in mind. BTW, the argument we use in (11) is actually unnecessary, as Hölder's inequality yields $$\sum_i p_i^2 \le ||p||_1 \cdot ||p||_\infty \le c.$$