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/\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?
Yes. See for example the stronger concentration for the occupancy problem in the following note:
Theorems 10.3.1 and 10.3.2. (This is also covered in the Randomized Algorithm book by Motwani and Raghavan).
The version stated here is the martingale version, but it is the same thing...
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.$$