¿Una prueba simple de McDiarmid ' desigualdad s?

Question

$\newcommand{\Ex}{\mathrm{E}} \newcommand{\Pr}{\mathrm{Pr}} \newcommand{\Ind}{\mathbf{1}} \newcommand{\implies}{\Rightarrow}$ Deje $f(x_1, \ldots, x_n)$ ser una verdadera función con valores de $n$ variables, con cada una de las $x_i \in \mathcal{X}$, tal que: \begin{equation} \forall (x_1,\ldots,x_{n-1}) \in \mathcal{X}^{n-1}, | f(x_1, \ldots, x_{n-1}, x) - f(x_1, \ldots, x_{n-1}, x') | \leq 1 , \end{equation} donde $x, x' \in \mathcal{X}$. Tenga en cuenta que McDiarmid s se supone que $f$ 1-Lipschitz, es decir, la condición anterior se sostiene si cambiamos cualquiera de coordenadas (y no sólo de la n-ésima coordenada). La constante 1 no es importante, puede ser cualquier constante arbitraria.

En primer lugar, yo uso el Hoeffding la desigualdad para mostrar que para cualquier arbitrario $(x_1,\ldots,x_{n-1})$: \begin{equation*} \Pr_{X_n}\{ \hat{\Ex}[f(x_1, \ldots, x_{n-1}, X_n)] - \Ex[f(x_1, \ldots, x_{n-1}, X_n)] \geq t \mid (x_1, \ldots, x_{n-1}) \} \leq e^{-2mt^2}, \end{ecuación*} donde $\hat{\Ex}$ es el promedio de $f(\cdot)$ $m$ muestras de la $X_n$ mientras que la fijación de la primera $n-1$ variables $x_1, \ldots, x_{n-1}$.

A continuación, me tome la expectativa con respecto a $X_1, \ldots, X_{n-1}$, de ambos lados de la ecuación para obtener: \begin{gather*} \Pr_{X_n}\{ \hat{\Ex}[f(x_1, \ldots, x_{n-1}, X_n)] - \Ex[f(x_1, \ldots, x_{n-1}, X_n)] \geq t \mid (x_1, \ldots, x_{n-1}) \} \leq e^{-2mt^2} \\ \implies \Ex_{X_n}[ \Ind[\hat{\Ex}[f(x_1, \ldots, x_{n-1}, X_n)] - \Ex[f(x_1, \ldots, x_{n-1}, X_n)] \geq t] \mid (x_1, \ldots, x_{n-1}) ] \leq e^{-2mt^2} \\ \implies \Ex_{X_1, \ldots X_{n-1}}[\Ex_{X_n}\{ \Ind[\hat{\Ex}[f(x_1, \ldots, x_{n-1}, X_n)] - \Ex[f(x_1, \ldots, x_{n-1}, X_n)] \geq t]] \mid (x_1, \ldots, x_{n-1}) ] \leq e^{-2mt^2} \\ \implies \Pr_{X_1, \ldots, X_n}\{ \hat{\Ex}[f(X_1, \ldots, X_n)] - \Ex[f(X_1, \ldots, X_n)] \geq t \} \leq e^{-2mt^2}. \end{reunir*} Esencialmente, me han demostrado que la concentración de $f(.)$ con respecto a todas las variables, mostrando a la concentración sólo con respecto a una variable y sin la construcción de un Doob Martingala como el estándar de McDiarmid de la prueba. El de arriba es definitivamente malo, pero no soy capaz de ver donde.

Además, es el que por encima de prueba correcta si $\mathcal{X}$ es finito o countably infinito?

Answer 1

He encontrado el error en mi prueba. Seguir adelante y responder a mi pregunta. El problema con esto es que si fijar el primer $n-1$$(x1, \ldots, x{n-1})$ variables y luego tomar muestras independientes de la $m$ $X_n$: $X_n^1, \ldots, X_n^m$. Indicar $f_i = f(x1, \ldots, x{n-1}, X_n^i)$. Entonces el %#% de #% no son necesariamente independientes. Hoeffding se aplica sólo a la suma de variables aleatorias independientes. La prueba de las faldas de la desigualdad de McDiarmid sobre esta cuestión mediante la construcción de una secuencia de la diferencia de martingala.