Timeline for McDiarmid's Inequality bounding deviation with multiplicative error?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Sep 14, 2017 at 2:37 | comment | added | Neal Young | Looks likely that the answer to the current question is yes, from Theorem 10 of this paper and Proposition 5 of this one. | |
| Sep 14, 2017 at 0:36 | history | edited | Neal Young | CC BY-SA 3.0 |
typo
|
| Sep 13, 2017 at 22:48 | history | edited | Neal Young | CC BY-SA 3.0 |
added one word
|
| Sep 13, 2017 at 22:36 | history | edited | Neal Young | CC BY-SA 3.0 |
typo
|
| Sep 13, 2017 at 22:14 | comment | added | Neal Young | I realized that the answer to the first general question I asked is NO. I've edited the post to reflect this. | |
| Sep 13, 2017 at 22:03 | history | edited | Neal Young | CC BY-SA 3.0 |
typo
|
| Sep 13, 2017 at 21:51 | history | edited | Neal Young | CC BY-SA 3.0 |
added minor clarification
|
| Sep 13, 2017 at 21:46 | history | edited | Neal Young | CC BY-SA 3.0 |
added minor clarification
|
| Sep 13, 2017 at 21:44 | comment | added | Synia | Yes, I was suspecting something like that, namely that $c $ be independent of $n $ (no need to edit, I guess). Stated like this, the question becomes of course much more interesting. There may be some inequalities available in the literature in the case of a sum that "beat" the classical MacDiarmid inequality (I am thinking of Chatterjee's method with exchangeable pairs). I will try to look it up. | |
| Sep 13, 2017 at 21:07 | comment | added | Neal Young | @Synia, In the form stated on Wikipedia, the bound is $$\Pr[X \ge \mu + A] \le \exp(-A^2/n),$$ where $n$ is the number of random variables. So, (in the general case) if you substitute $A=\epsilon\mu$, the bound is $\exp(-\epsilon^2 \mu^2/n)$, not $\exp(-\epsilon^2 \mu)$. (And note that, likewise, in the application above we want $c$ to be a constant independent of $k$ and $\mu$, e.g. $c=3$.) Also, if you look at the proof of McDiarmid, the Doob martingale that it uses can either increase or decrease in each step, which forces the use of an additive error bound. | |
| Sep 13, 2017 at 18:53 | comment | added | Synia | It seems to me that multiplicative or additive are the same, of the form $\mathbb{P}(X \geqslant \mu + A)$ with $ A = \varepsilon n $ in one case and $ A = \varepsilon \mu $ in the other case (the wikipedia link states that this is for all $ A > 0$). If you want to state the MacDiarmid inequality in a multiplicative form, replace the $A$ accordingly in the second case, i.e. take $ \mu t = \varepsilon k $ and the bound in $ \exp(-\varepsilon^2 k/3) $ becomes $ \exp( - ( \mu t / k )^2 k/3) = \exp( - t^2 \mu^2/(3 k) ) $ (hence $c = 3k/\mu $). Of course, $c$ depends of $ \mu $ here... | |
| Sep 12, 2017 at 22:34 | history | asked | Neal Young | CC BY-SA 3.0 |