CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Độ tập trung quanh kì vọng (concentration inequalities) (2) – McDiarmid inequality

Posted by Trần Quốc Long 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 \displaystyle f: \mathbb{R}^n \rightarrow R sao cho

\displaystyle f(x_1,\ldots,x_i,\ldots, x_n) - f(x_1,\ldots,x_i',\ldots, x_n) \leq c_i,\forall x_1,\ldots, x_n, x_i', \forall i

và các biến \displaystyle X_1,\ldots,X_n độc lập xác suất thì

\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 \displaystyle f(X_1,\ldots,X_n) = \frac{1}{n}\sum_{i=1}^n X_i.

Chứng minh: Đặt \displaystyle Z_i = E[f(X_1,\ldots,X_n)|X_1,\ldots, X_i] là kì vọng của hàm \displaystyle f nếu biết trước giá trị của \displaystyle i biến đầu tiên. Như vậy

\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}

Theo bất đẳng thức Chernoff, với mọi \displaystyle s ta có

\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]

\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] bằng bổ đề Hoeffding.

Đặt \displaystyle Y = Z_n - Z_{n-1}|X_1,\ldots,X_{n-1}. Ta có

\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}]

\displaystyle L_n = \inf_u E[f|X_1,\ldots,X_{n-1},u]-E[f|X_1,\ldots,X_{n-1}]

Ta có \displaystyle L_i\leq Y\leq U_i\displaystyle U_n-L_n\leq c_n

Vậy \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}

\displaystyle \leq \exp\left\{-s\epsilon+\frac{1}{8}s^2\sum_{i=1}^nc_i^2\right\}

Chọn \displaystyle s để cực tiểu hóa hàm \displaystyle -s\epsilon+\frac{1}{8}s^2\sum_{i=1}^nc_i^2 ta được điều phải chứng minh.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: