Độ tập trung quanh kì vọng (concentration inequalities) (2) – McDiarmid inequality
Đăng bởi tqlong on Tháng Sáu 23, 2009
Tổng quát hóa bất đẳng thức Hoeffding cho lớp hàm bị chặn ta được bất đẳng thức McDiarmid như sau
Định lý (McDiarmid): Nếu hàm 
và các biến 
![\displaystyle \mathrm{Pr}_{X_1,\ldots,X_n}\{f - E[f]\geq\epsilon\}\leq \exp \left\{-\frac{2\epsilon^2}{\sum_{i=1}^n c_i^2} \right\}](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D_%7BX_1%2C%5Cldots%2CX_n%7D%5C%7Bf+-+E%5Bf%5D%5Cgeq%5Cepsilon%5C%7D%5Cleq+%5Cexp+%5Cleft%5C%7B-%5Cfrac%7B2%5Cepsilon%5E2%7D%7B%5Csum_%7Bi%3D1%7D%5En+c_i%5E2%7D+%5Cright%5C%7D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle \mathrm{Pr}_{X_1,\ldots,X_n}\{f - E[f]\geq\epsilon\}\leq \exp \left\{-\frac{2\epsilon^2}{\sum_{i=1}^n c_i^2} \right\}")
Ta thấy bất đẳng thức Hoeffding là hệ quả của bất đẳng thức McDiarmid với hàm 
Chứng minh: Đặt ![\displaystyle Z_i = E[f(X_1,\ldots,X_n)|X_1,\ldots, X_i]](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+Z_i+%3D+E%5Bf%28X_1%2C%5Cldots%2CX_n%29%7CX_1%2C%5Cldots%2C+X_i%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle Z_i = E[f(X_1,\ldots,X_n)|X_1,\ldots, X_i]")
![\displaystyle Z_0 = E[f], Z_n = f](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+Z_0+%3D+E%5Bf%5D%2C+Z_n+%3D+f&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle Z_0 = E[f], Z_n = f")
![\displaystyle f - E[f] = Z_n - Z_0 = \sum_{i=1}^n Z_i - Z_{i-1}](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+f+-+E%5Bf%5D+%3D+Z_n+-+Z_0+%3D+%5Csum_%7Bi%3D1%7D%5En+Z_i+-+Z_%7Bi-1%7D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle f - E[f] = Z_n - Z_0 = \sum_{i=1}^n Z_i - Z_{i-1}")
Theo bất đẳng thức Chernoff, với mọi 
![\displaystyle \mathrm{Pr}\{f - E[f]\geq \epsilon\} = e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^n Z_i - Z_{i-1}\right\}\right]](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7Bf+-+E%5Bf%5D%5Cgeq+%5Cepsilon%5C%7D+%3D+e%5E%7B-s%5Cepsilon%7DE%5Cleft%5B%5Cexp+%5Cleft%5C%7Bs+%5Csum_%7Bi%3D1%7D%5En+Z_i+-+Z_%7Bi-1%7D%5Cright%5C%7D%5Cright%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle \mathrm{Pr}\{f - E[f]\geq \epsilon\} = e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^n Z_i - Z_{i-1}\right\}\right]")
![\displaystyle = e^{-s\epsilon}E\left[E\left[\left.\exp \left\{s \sum_{i=1}^n Z_i - Z_{i-1}\right\}\right|X_1,\ldots,X_{n-1}\right]\right]](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+%3D+e%5E%7B-s%5Cepsilon%7DE%5Cleft%5BE%5Cleft%5B%5Cleft.%5Cexp+%5Cleft%5C%7Bs+%5Csum_%7Bi%3D1%7D%5En+Z_i+-+Z_%7Bi-1%7D%5Cright%5C%7D%5Cright%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%5Cright%5D%5Cright%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle = e^{-s\epsilon}E\left[E\left[\left.\exp \left\{s \sum_{i=1}^n Z_i - Z_{i-1}\right\}\right|X_1,\ldots,X_{n-1}\right]\right]")
![\displaystyle = e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^{n-1} Z_i - Z_{i-1}\right\}E\left[\left.e^{s(Z_n - Z_{n-1}) }\right|X_1,\ldots,X_{n-1}\right]\right]](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+%3D+e%5E%7B-s%5Cepsilon%7DE%5Cleft%5B%5Cexp+%5Cleft%5C%7Bs+%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D+Z_i+-+Z_%7Bi-1%7D%5Cright%5C%7DE%5Cleft%5B%5Cleft.e%5E%7Bs%28Z_n+-+Z_%7Bn-1%7D%29+%7D%5Cright%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%5Cright%5D%5Cright%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle = e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^{n-1} Z_i - Z_{i-1}\right\}E\left[\left.e^{s(Z_n - Z_{n-1}) }\right|X_1,\ldots,X_{n-1}\right]\right]")
Bây giờ ta đánh giá ![\displaystyle E\left[\left.e^{s(Z_n - Z_{n-1}) }\right|X_1,\ldots,X_{n-1}\right]](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5Cleft%5B%5Cleft.e%5E%7Bs%28Z_n+-+Z_%7Bn-1%7D%29+%7D%5Cright%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%5Cright%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E\left[\left.e^{s(Z_n - Z_{n-1}) }\right|X_1,\ldots,X_{n-1}\right]")
Đặt 
![\displaystyle E[Y] = E[Z_n - Z_{n-1}|X_1,\ldots,X_{n-1}] = 0](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5BY%5D+%3D+E%5BZ_n+-+Z_%7Bn-1%7D%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%5D+%3D+0&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[Y] = E[Z_n - Z_{n-1}|X_1,\ldots,X_{n-1}] = 0")
Đặt
![\displaystyle U_n = \sup_u E[f|X_1,\ldots,X_{n-1},u]-E[f|X_1,\ldots,X_{n-1}]](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+U_n+%3D+%5Csup_u+E%5Bf%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%2Cu%5D-E%5Bf%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle U_n = \sup_u E[f|X_1,\ldots,X_{n-1},u]-E[f|X_1,\ldots,X_{n-1}]")
![\displaystyle L_n = \inf_u E[f|X_1,\ldots,X_{n-1},u]-E[f|X_1,\ldots,X_{n-1}]](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+L_n+%3D+%5Cinf_u+E%5Bf%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%2Cu%5D-E%5Bf%7CX_1%2C%5Cldots%2CX_%7Bn-1%7D%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle L_n = \inf_u E[f|X_1,\ldots,X_{n-1},u]-E[f|X_1,\ldots,X_{n-1}]")
Ta có 
Vậy ![\displaystyle E[e^{sY}]\leq e^{s^2 c_n^2/8}](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5Be%5E%7BsY%7D%5D%5Cleq+e%5E%7Bs%5E2+c_n%5E2%2F8%7D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[e^{sY}]\leq e^{s^2 c_n^2/8}")
Tiếp tục ta được
![\displaystyle \mathrm{Pr}\{f - E[f]\geq \epsilon\}\leq e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^{n-1} Z_i - Z_{i-1}\right\}\right] e^{s^2 c_n^2/8}](http://l.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7Bf+-+E%5Bf%5D%5Cgeq+%5Cepsilon%5C%7D%5Cleq+e%5E%7B-s%5Cepsilon%7DE%5Cleft%5B%5Cexp+%5Cleft%5C%7Bs+%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D+Z_i+-+Z_%7Bi-1%7D%5Cright%5C%7D%5Cright%5D+e%5E%7Bs%5E2+c_n%5E2%2F8%7D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle \mathrm{Pr}\{f - E[f]\geq \epsilon\}\leq e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^{n-1} Z_i - Z_{i-1}\right\}\right] e^{s^2 c_n^2/8}")
Chọn 
