3
$\begingroup$

McDiarmid's inequality says if a function $f: \mathcal{X}^n\to\mathbb{R}$ has the property that $$ \sup_{x_1,\dotsc,x_n,x'_i\in\mathcal{X}} |f(x_1,\dotsc,x_n)-f(x_1,\dotsc,x_{i-1},x'_i,x_{i+1},\dotsc,x_n)| \leq c_i, 1\leq i \leq n $$ then $$ P(f(x_1,\dotsc,x_n) - \mathbb{E}f(x_1,\dotsc,x_n) > t) \leq \exp\left(-\frac{2t^2}{\sum_{i=1}^nc_i}\right). $$

Is it possible to use an $f: \mathcal{X}^n\to\mathbb{M}$ to some normed space $(\mathbb{M},||\cdot||)$ and $$ \sup_{x_1,\dotsc,x_n,x'_i\in\mathcal{X}} ||f(x_1,\dotsc,x_n)-f(x_1,\dotsc,x_{i-1},x'_i,x_{i+1},\dotsc,x_n) ||\leq c_i, 1\leq i \leq n $$ such that the inequality holds?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It may be helpful to point out that in the second display, the $x_i$ have changed from arbitrary elements of $\mathcal{X}$ into independent $\mathcal{X}$-valued random variables. Perhaps it would be better to call the random variables $X_i$ instead? $\endgroup$
    – Nate Eldredge
    Commented Nov 10, 2014 at 15:00
  • $\begingroup$ What exactly does $f(x)-Ef(x)>t$ mean when M is a normed space? Can you specify which inequality are you after? $\endgroup$
    – ofer zeitouni
    Commented Nov 16, 2014 at 18:34
  • $\begingroup$ Also, this is only true for product measures in general. $\endgroup$
    – Aryeh Kontorovich
    Commented Nov 17, 2014 at 12:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .