Desigualdad de McDiarmid
Concepto de probabilidad y ciencia informática

En teoría de probabilidad y ciencia informática teórica , la desigualdad de McDiarmid (nombrada en honor a Colin McDiarmid [1] ) es una desigualdad de concentración que limita la desviación entre el valor muestreado y el valor esperado de ciertas funciones cuando se evalúan en variables aleatorias independientes . La desigualdad de McDiarmid se aplica a funciones que satisfacen una propiedad de diferencias acotadas , lo que significa que reemplazar un solo argumento de la función mientras se dejan todos los demás argumentos sin cambios no puede causar un cambio demasiado grande en el valor de la función.

Declaración

Una función satisface la propiedad de diferencias acotadas si al sustituir el valor de la coordenada n cambia el valor de en como máximo . Más formalmente, si hay constantes tales que para todos , y todos , F : incógnita 1 × incógnita 2 × ⋯ × incógnita norte → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } i {\estilo de visualización i} incógnita i Estilo de visualización x_{i}} F {\estilo de visualización f} do i Estilo de visualización c_{i} do 1 , do 2 , … , do norte {\displaystyle c_{1},c_{2},\puntos ,c_{n}} i ∈ [ norte ] {\displaystyle i\in [n]} incógnita 1 ∈ incógnita 1 , incógnita 2 ∈ incógnita 2 , … , incógnita norte ∈ incógnita norte {\displaystyle x_{1}\in {\mathcal {X}}_{1},\,x_{2}\in {\mathcal {X}}_{2},\,\ldots ,\,x_{n}\in {\mathcal {X}}_{n}}

sorber incógnita i " ∈ incógnita i | F ( incógnita 1 , … , incógnita i − 1 , incógnita i , incógnita i + 1 , … , incógnita norte ) − F ( incógnita 1 , … , incógnita i − 1 , incógnita i " , incógnita i + 1 , … , incógnita norte ) | ≤ do i . {\displaystyle \sup _{x_{i}'\in {\mathcal {X}}_{i}}\left|f(x_{1},\puntos ,x_{i-1},x_{i},x_{i+1},\ldots ,x_{n})-f(x_{1},\puntos ,x_{i-1},x_{i}',x_{i+1},\ldots ,x_{n})\right|\leq c_{i}.}

Desigualdad de McDiarmid [2]  —  Sea satisfecha la propiedad de diferencias acotadas con límites . F : incógnita 1 × incógnita 2 × ⋯ × incógnita norte → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } do 1 , do 2 , … , do norte {\displaystyle c_{1},c_{2},\puntos ,c_{n}}

Consideremos variables aleatorias independientes donde para todos . Entonces, para cualquier , incógnita 1 , incógnita 2 , … , incógnita norte {\displaystyle X_{1},X_{2},\puntos ,X_{n}} incógnita i ∈ incógnita i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} i {\estilo de visualización i} mi > 0 {\displaystyle \varepsilon >0}

PAG ( F ( incógnita 1 , incógnita 2 , … , incógnita norte ) − mi [ F ( incógnita 1 , incógnita 2 , … , incógnita norte ) ] ≥ mi ) ≤ exp ⁡ ( − 2 mi 2 ∑ i = 1 norte do i 2 ) , {\displaystyle {\text{P}}\left(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\geq \varepsilon \right)\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}
PAG ( F ( incógnita 1 , incógnita 2 , … , incógnita norte ) − mi [ F ( incógnita 1 , incógnita 2 , … , incógnita norte ) ] ≤ − mi ) ≤ exp ⁡ ( − 2 mi 2 ∑ i = 1 norte do i 2 ) , {\displaystyle {\text{P}}(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\leq -\varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}

y como consecuencia inmediata,

P ( | f ( X 1 , X 2 , … , X n ) − E [ f ( X 1 , X 2 , … , X n ) ] | ≥ ε ) ≤ 2 exp ⁡ ( − 2 ε 2 ∑ i = 1 n c i 2 ) . {\displaystyle {\text{P}}(|f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}

Extensiones

Distribuciones desequilibradas

Se puede dar un límite más fuerte cuando los argumentos de la función se toman de distribuciones no balanceadas, de modo que remuestrear un solo argumento rara vez causa un cambio grande en el valor de la función.

Desigualdad de McDiarmid (no balanceada) [3] [4]  —  Sea satisfecha la propiedad de diferencias acotadas con límites . f : X n → R {\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} } c 1 , c 2 , … , c n {\displaystyle c_{1},c_{2},\dots ,c_{n}}

Consideremos variables aleatorias independientes extraídas de una distribución donde hay un valor particular que ocurre con probabilidad . Entonces, para cualquier , X 1 , X 2 , … , X n ∈ X {\displaystyle X_{1},X_{2},\ldots ,X_{n}\in {\mathcal {X}}} χ 0 ∈ X {\displaystyle \chi _{0}\in {\mathcal {X}}} 1 − p {\displaystyle 1-p} ε > 0 {\displaystyle \varepsilon >0}

P ( | f ( X 1 , … , X n ) − E [ f ( X 1 , … , X n ) ] | ≥ ε ) ≤ 2 exp ⁡ ( − ε 2 2 p ( 2 − p ) ∑ i = 1 n c i 2 + 2 3 ε max i c i ) . {\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left({\frac {-\varepsilon ^{2}}{2p(2-p)\sum _{i=1}^{n}c_{i}^{2}+{\frac {2}{3}}\varepsilon \max _{i}c_{i}}}\right).}

Esto se puede usar para caracterizar, por ejemplo, el valor de una función en gráficos cuando se evalúa en gráficos aleatorios dispersos e hipergráficos , ya que en un gráfico aleatorio disperso es mucho más probable que falte algún borde en particular que esté presente.

Diferencias acotadas con alta probabilidad

La desigualdad de McDiarmid puede extenderse al caso en que la función analizada no satisface estrictamente la propiedad de diferencias acotadas, pero las diferencias grandes siguen siendo muy raras.

Desigualdad de McDiarmid (Diferencias acotadas con alta probabilidad) [5]  —  Sea una función y un subconjunto de su dominio y sean constantes tales que para todos los pares y , f : X 1 × X 2 × ⋯ × X n → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } Y ⊆ X 1 × X 2 × ⋯ × X n {\displaystyle {\mathcal {Y}}\subseteq {\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}} c 1 , c 2 , … , c n ≥ 0 {\displaystyle c_{1},c_{2},\dots ,c_{n}\geq 0} ( x 1 , … , x n ) ∈ Y {\displaystyle (x_{1},\ldots ,x_{n})\in {\mathcal {Y}}} ( x 1 ′ , … , x n ′ ) ∈ Y {\displaystyle (x'_{1},\ldots ,x'_{n})\in {\mathcal {Y}}}

| f ( x 1 , … , x n ) − f ( x 1 ′ , … , x n ′ ) | ≤ ∑ i : x i ≠ x i ′ c i . {\displaystyle \left|f(x_{1},\ldots ,x_{n})-f(x'_{1},\ldots ,x'_{n})\right|\leq \sum _{i:x_{i}\neq x'_{i}}c_{i}.}

Consideremos variables aleatorias independientes donde para todos . Sea y sea . Entonces, para cualquier , X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} X i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} i {\displaystyle i} p = 1 − P ( ( X 1 , … , X n ) ∈ Y ) {\displaystyle p=1-\mathrm {P} ((X_{1},\ldots ,X_{n})\in {\mathcal {Y}})} m = E [ f ( X 1 , … , X n ) ∣ ( X 1 , … , X n ) ∈ Y ] {\displaystyle m=\mathbb {E} [f(X_{1},\ldots ,X_{n})\mid (X_{1},\ldots ,X_{n})\in {\mathcal {Y}}]} ε > 0 {\displaystyle \varepsilon >0}

P ( f ( X 1 , … , X n ) − m ≥ ε ) ≤ p + exp ⁡ ( − 2 max ( 0 , ε − p ∑ i = 1 n c i ) 2 ∑ i = 1 n c i 2 ) , {\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq p+\exp \left(-{\frac {2\max \left(0,\varepsilon -p\sum _{i=1}^{n}c_{i}\right)^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}

y como consecuencia inmediata,

P ( | f ( X 1 , … , X n ) − m | ≥ ε ) ≤ 2 p + 2 exp ⁡ ( − 2 max ( 0 , ε − p ∑ i = 1 n c i ) 2 ∑ i = 1 n c i 2 ) . {\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-m|\geq \varepsilon )\leq 2p+2\exp \left(-{\frac {2\max \left(0,\varepsilon -p\sum _{i=1}^{n}c_{i}\right)^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}

Existen refinamientos más fuertes de este análisis en algunos escenarios dependientes de la distribución, [6] como aquellos que surgen en la teoría del aprendizaje .

Normas subgaussianas y subexponenciales

Sea la versión condicional centrada de una función k {\displaystyle k} f {\displaystyle f}

f k ( X ) ( x ) := f ( x 1 , … , x k − 1 , X k , x k + 1 , … , x n ) − E X k ′ f ( x 1 , … , x k − 1 , X k ′ , x k + 1 , … , x n ) , {\displaystyle f_{k}(X)(x):=f(x_{1},\ldots ,x_{k-1},X_{k},x_{k+1},\ldots ,x_{n})-\mathbb {E} _{X'_{k}}f(x_{1},\ldots ,x_{k-1},X'_{k},x_{k+1},\ldots ,x_{n}),}

Por lo tanto, es una variable aleatoria que depende de valores aleatorios de . f k ( X ) {\displaystyle f_{k}(X)} x 1 , … , x k − 1 , x k + 1 , … , x n {\displaystyle x_{1},\ldots ,x_{k-1},x_{k+1},\ldots ,x_{n}}

Desigualdad de McDiarmid (norma subgaussiana) [7] [8]  —  Sea una función. Consideremos variables aleatorias independientes donde para todo . f : X 1 × X 2 × ⋯ × X n → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } X = ( X 1 , X 2 , … , X n ) {\displaystyle X=(X_{1},X_{2},\dots ,X_{n})} X i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} i {\displaystyle i}

Hagamos referencia a la versión condicional centrada de . Denotemos la norma subgaussiana de una variable aleatoria. f k ( X ) {\displaystyle f_{k}(X)} k {\displaystyle k} f {\displaystyle f} ‖ ⋅ ‖ ψ 2 {\displaystyle \|\cdot \|_{\psi _{2}}}

Entonces, para cualquier , ε > 0 {\displaystyle \varepsilon >0}

P ( f ( X 1 , … , X n ) − m ≥ ε ) ≤ exp ⁡ ( − ε 2 32 e ‖ ∑ k ∈ [ n ] ‖ f k ( X ) ‖ ψ 2 2 ‖ ∞ ) . {\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\varepsilon ^{2}}{32e\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{2}}^{2}\right\|_{\infty }}}\right).}

Desigualdad de McDiarmid (norma subexponencial) [8]  —  Sea una función. Consideremos variables aleatorias independientes donde para todo . f : X 1 × X 2 × ⋯ × X n → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } X = ( X 1 , X 2 , … , X n ) {\displaystyle X=(X_{1},X_{2},\dots ,X_{n})} X i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} i {\displaystyle i}

Sea la versión condicional centrada de . Sea la norma subexponencial de una variable aleatoria. f k ( X ) {\displaystyle f_{k}(X)} k {\displaystyle k} f {\displaystyle f} ‖ ⋅ ‖ ψ 1 {\displaystyle \|\cdot \|_{\psi _{1}}}

Entonces, para cualquier , ε > 0 {\displaystyle \varepsilon >0}

P ( f ( X 1 , … , X n ) − m ≥ ε ) ≤ exp ⁡ ( − ε 2 4 e 2 ‖ ∑ k ∈ [ n ] ‖ f k ( X ) ‖ ψ 1 2 ‖ ∞ + 2 ε e max k ∈ [ n ] ‖ ‖ f k ( X ) ‖ ψ 1 ‖ ∞ ) . {\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\varepsilon ^{2}}{4e^{2}\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{1}}^{2}\right\|_{\infty }+2\varepsilon e\max _{k\in [n]}\left\|\|f_{k}(X)\|_{\psi _{1}}\right\|_{\infty }}}\right).}

Formas Bennett y Bernstein

Los refinamientos de la desigualdad de McDiarmid en el estilo de la desigualdad de Bennett y las desigualdades de Bernstein son posibles al definir un término de varianza para cada argumento de la función. Sea

B := max k ∈ [ n ] sup x 1 , … , x k − 1 , x k + 1 , … , x n | f ( x 1 , … , x k − 1 , X k , x k + 1 , … , x n ) − E X k f ( x 1 , … , x k − 1 , X k , x k + 1 , … , x n ) | , V k := sup x 1 , … , x k − 1 , x k + 1 , … , x n E X k ( f ( x 1 , … , x k − 1 , X k , x k + 1 , … , x n ) − E X k f ( x 1 , … , x k − 1 , X k , x k + 1 , … , x n ) ) 2 , σ ~ 2 := ∑ k = 1 n V k . {\displaystyle {\begin{aligned}B&:=\max _{k\in [n]}\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\left|f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right|,\\V_{k}&:=\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\mathbb {E} _{X_{k}}\left(f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right)^{2},\\{\tilde {\sigma }}^{2}&:=\sum _{k=1}^{n}V_{k}.\end{aligned}}}

Desigualdad de McDiarmid (forma Bennett) [4]  —  Sea que se satisface la propiedad de diferencias acotadas con límites . Consideremos variables aleatorias independientes donde para todo . Sea y se definan como al comienzo de esta sección. f : X n → R {\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} } c 1 , c 2 , … , c n {\displaystyle c_{1},c_{2},\dots ,c_{n}} X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} X i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} i {\displaystyle i} B {\displaystyle B} σ ~ 2 {\displaystyle {\tilde {\sigma }}^{2}}

Entonces, para cualquier , ε > 0 {\displaystyle \varepsilon >0}

P ( f ( X 1 , … , X n ) − E [ f ( X 1 , … , X n ) ] ≥ ε ) ≤ exp ⁡ ( − ε 2 B log ⁡ ( 1 + B ε σ ~ 2 ) ) . {\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon }{2B}}\log \left(1+{\frac {B\varepsilon }{{\tilde {\sigma }}^{2}}}\right)\right).}

Desigualdad de McDiarmid (forma de Bernstein) [4]  —  Sea que se satisface la propiedad de diferencias acotadas con límites . Sea y definida como al comienzo de esta sección. f : X n → R {\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} } c 1 , c 2 , … , c n {\displaystyle c_{1},c_{2},\dots ,c_{n}} B {\displaystyle B} σ ~ 2 {\displaystyle {\tilde {\sigma }}^{2}}

Entonces, para cualquier , ε > 0 {\displaystyle \varepsilon >0}

P ( f ( X 1 , … , X n ) − E [ f ( X 1 , … , X n ) ] ≥ ε ) ≤ exp ⁡ ( − ε 2 2 ( σ ~ 2 + B ε 3 ) ) . {\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon ^{2}}{2\left({\tilde {\sigma }}^{2}+{\frac {B\varepsilon }{3}}\right)}}\right).}

Prueba

La siguiente prueba de la desigualdad de McDiarmid [2] construye la martingala de Doob siguiendo el valor esperado condicional de la función a medida que se muestrean y condicionaran más y más de sus argumentos, y luego aplica una desigualdad de concentración de martingala ( desigualdad de Azuma ). También existe un argumento alternativo que evita el uso de martingalas, aprovechando la independencia de los argumentos de la función para proporcionar un argumento similar al límite de Chernoff . [4]

Para una mejor legibilidad, introduciremos una abreviatura de notación: denotará para cualquier y enteros , de modo que, por ejemplo, z i ⇁ j {\displaystyle z_{i\rightharpoondown j}} z i , … , z j {\displaystyle z_{i},\dots ,z_{j}} z ∈ X n {\displaystyle z\in {\mathcal {X}}^{n}} 1 ≤ i ≤ j ≤ n {\displaystyle 1\leq i\leq j\leq n}

f ( X 1 ⇁ ( i − 1 ) , y , x ( i + 1 ) ⇁ n ) := f ( X 1 , … , X i − 1 , y , x i + 1 , … , x n ) . {\displaystyle f(X_{1\rightharpoondown (i-1)},y,x_{(i+1)\rightharpoondown n}):=f(X_{1},\ldots ,X_{i-1},y,x_{i+1},\ldots ,x_{n}).}

Elija cualquier . Entonces, para cualquier , por desigualdad triangular , x 1 ′ , x 2 ′ , … , x n ′ {\displaystyle x_{1}',x_{2}',\ldots ,x_{n}'} x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\ldots ,x_{n}}

| f ( x 1 ⇁ n ) − f ( x 1 ⇁ n ′ ) | ≤ | f ( x 1 ⇁ n ) − f ( x 1 ⇁ ( n − 1 ) ′ , x n ) | + c n ≤ | f ( x 1 ⇁ n ) − f ( x 1 ⇁ ( n − 2 ) ′ , x ( n − 1 ) ⇁ n ) | + c n − 1 + c n ≤ … ≤ ∑ i = 1 n c i , {\displaystyle {\begin{aligned}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown n})|\\[6pt]\leq {}&|f(x_{1\rightharpoondown \,n})-f(x'_{1\rightharpoondown (n-1)},x_{n})|+c_{n}\\\leq {}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown (n-2)},x_{(n-1)\rightharpoondown n})|+c_{n-1}+c_{n}\\\leq {}&\ldots \\\leq {}&\sum _{i=1}^{n}c_{i},\end{aligned}}}

y por lo tanto está limitado. f {\displaystyle f}

Dado que está acotado, defina la martingala de Doob ( siendo cada una una variable aleatoria que depende de los valores aleatorios de ) como f {\displaystyle f} { Z i } {\displaystyle \{Z_{i}\}} Z i {\displaystyle Z_{i}} X 1 , … , X i {\displaystyle X_{1},\ldots ,X_{i}}

Z i := E [ f ( X 1 ⇁ n ) ∣ X 1 ⇁ i ] {\displaystyle Z_{i}:=\mathbb {E} [f(X_{1\rightharpoondown n})\mid X_{1\rightharpoondown i}]}

para todos y , para que . i ≥ 1 {\displaystyle i\geq 1} Z 0 := E [ f ( X 1 ⇁ n ) ] {\displaystyle Z_{0}:=\mathbb {E} [f(X_{1\rightharpoondown n})]} Z n = f ( X 1 ⇁ n ) {\displaystyle Z_{n}=f(X_{1\rightharpoondown n})}

Ahora defina las variables aleatorias para cada i {\displaystyle i}

U i := sup x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) , X i = x ] − [ f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] , L i := inf x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) , X i = x ] − [ f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] . {\displaystyle {\begin{aligned}U_{i}&:=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&:=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\\end{aligned}}}

Como son independientes entre sí, el condicionamiento no afecta las probabilidades de las otras variables, por lo que estas son iguales a las expresiones X i , … , X n {\displaystyle X_{i},\ldots ,X_{n}} X i = x {\displaystyle X_{i}=x}

U i = sup x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) − f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] , L i = inf x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) − f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] . {\displaystyle {\begin{aligned}U_{i}&=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\\end{aligned}}}

Tenga en cuenta que . Además, L i ≤ Z i − Z i − 1 ≤ U i {\displaystyle L_{i}\leq Z_{i}-Z_{i-1}\leq U_{i}}

U i − L i = sup u ∈ X i , ℓ ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , u , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] − E [ f ( X 1 ⇁ ( i − 1 ) , ℓ , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] = sup u ∈ X i , ℓ ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , u , X ( i + 1 ) ⇁ n ) − f ( X 1 ⇁ ( i − 1 ) , l , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] ≤ sup x u ∈ X i , x l ∈ X i E [ c i ∣ X 1 ⇁ ( i − 1 ) ] ≤ c i {\displaystyle {\begin{aligned}U_{i}-L_{i}&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]-\mathbb {E} [f(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},l,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\&\leq \sup _{x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}\mathbb {E} [c_{i}\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&\leq c_{i}\end{aligned}}}

Luego, aplicando la forma general de la desigualdad de Azuma a , tenemos { Z i } {\displaystyle \left\{Z_{i}\right\}}

P ( f ( X 1 , … , X n ) − E [ f ( X 1 , … , X n ) ] ≥ ε ) = P ⁡ ( Z n − Z 0 ≥ ε ) ≤ exp ⁡ ( − 2 ε 2 ∑ i = 1 n c i 2 ) . {\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )=\operatorname {P} (Z_{n}-Z_{0}\geq \varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}

El límite unilateral en la otra dirección se obtiene aplicando la desigualdad de Azuma a y el límite bilateral se deduce de un límite de unión . { − Z i } {\displaystyle \left\{-Z_{i}\right\}} ◻ {\displaystyle \square }

Véase también

Referencias

  1. ^ McDiarmid, Colin (1989). "Sobre el método de diferencias acotadas". Surveys in Combinatorics, 1989: Artículos invitados a la Duodécima Conferencia Combinatoria Británica : 148–188. doi :10.1017/CBO9781107359949.008. ISBN 978-0-521-37823-9.
  2. ^ ab Doob, JL (1940). "Propiedades de regularidad de ciertas familias de variables aleatorias" (PDF) . Transactions of the American Mathematical Society . 47 (3): 455–486. doi : 10.2307/1989964 . JSTOR  1989964.
  3. ^ Chou, Chi-Ning; Love, Peter J.; Sandhu, Juspreet Singh; Shi, Jonathan (2022). "Limitaciones de los algoritmos cuánticos locales en Max-k-XOR aleatorio y más allá". 49.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2022) . 229 :41:13. arXiv : 2108.06049 . doi : 10.4230/LIPIcs.ICALP.2022.41 . Consultado el 8 de julio de 2022 .
  4. ^ abcd Ying, Yiming (2004). «Desigualdades de McDiarmid de las formas de Bernstein y Bennett» (PDF) . City University of Hong Kong . Consultado el 10 de julio de 2022 .
  5. ^ Combes, Richard (2015). "Una extensión de la desigualdad de McDiarmid". arXiv : 1511.05240 [cs.LG].
  6. ^ Wu, Xinxing; Zhang, Junping (abril de 2018). "Desigualdades de concentración dependientes de la distribución para límites de generalización más estrictos". Science China Information Sciences . 61 (4): 048105:1–048105:3. arXiv : 1607.05506 . doi :10.1007/s11432-017-9225-2. S2CID  255199895 . Consultado el 10 de julio de 2022 .
  7. ^ Kontorovich, Aryeh (22 de junio de 2014). «Concentración en espacios métricos no acotados y estabilidad algorítmica». Actas de la 31.ª Conferencia Internacional sobre Aprendizaje Automático . 32 (2): 28–36. arXiv : 1309.1007 . Consultado el 10 de julio de 2022 .
  8. ^ ab Maurer, Andreas; Pontil, Pontil (2021). «Desigualdades de concentración en condiciones subgaussianas y subexponenciales» (PDF) . Avances en sistemas de procesamiento de información neuronal . 34 : 7588–7597 . Consultado el 10 de julio de 2022 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=McDiarmid%27s_inequality&oldid=1237349424"