5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

Yes. See for example the stronger concentration for the occupancy problem in the following note:

http://sarielhp.org/teach/17/b/lec/10_martin_II.pdf

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...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, I think I’ll put this on an exam! $\endgroup$ – Aryeh Jun 1 '18 at 5:22
1
$\begingroup$

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.$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.