終点枕崎

にゃーんo(^・x・^)o

McDiarmidの不等式(メモ)

$$
\newcommand{\Ex}{{\rm E}}
\newcommand{\Pr}{{\rm Pr}}
\newcommand{\expo}{{\rm e}}
$$

汎化誤差の一様上限について調べていたら必要になりました。絶対に忘れるので、確率論の勉強も兼ねてメモしておきます。(ほぼ
https://cs.nyu.edu/~rostami/ml/2007/ashish-mcdiarmid.pdfの日本語訳+行間です。)

定理1(McDiarmidの不等式)

\(c_1, \ldots, c_m\) : 正の実定数
\( f : \mathcal{X}^m \rightarrow \mathbb{R} \) : 各 \(i\) に対しつぎを満たす関数
$$
\sup_{x_1, \ldots, x_m, x_i' \in \mathcal{X}} | f(x_1, \ldots, x_m) - f(x_1, \ldots, x_i', \ldots, x_m) | \leq c_i
$$
\( X_1, \ldots, X_m \in \mathcal{X} \) : 互いに独立な確率変数
このとき、任意の \(\epsilon > 0\) に対し以下の不等式が成り立つ。
$$
\Pr[f(X_1, \ldots, X_m) - \Ex[f(X_1, \ldots, X_m)] \geq \epsilon] \leq \exp \left(\frac{-2\epsilon^2}{\sum_{i = 1}^{m} c_i^2} \right)
$$
ただし \(\Pr[A], \Ex[X] \) はそれぞれ事象Aの起こる確率、確率変数Xの期待値。

この定理の証明には以下の道具を使います。

命題1(総期待値和の法則, Law of total expectation)

$$
\Ex[X] = \Ex_Y[\Ex_X[X | Y]]
$$
条件付き期待値 \(\Ex_X[X | Y] = \Ex_X[X | Y = y] \) は \(y\) に関する関数であることに注意する必要があります。
証明→Law of total expectation - Wikipedia

命題2(マルコフの不等式, Markov's inequality)

$$
\Pr[X \geq t] \leq \frac{\Ex[X]}{t}
$$

証明

\begin{align}
\Ex[X] = &\sum_x x \Pr[X = x] \nonumber \\
\geq & \sum_{x \geq t} x \Pr[X = x] \nonumber \\
\geq & \sum_{x \geq t} t \Pr[X = x] \nonumber \\
= & t \Pr[X \geq t] \nonumber
\end{align}

補題1(Hoeffdingの補題, Hoeffding's lemma)

\(x\) : \(a \leq x \leq b, \Ex[x] = 0 \) を満たす確率変数
任意の\(t > 0\)に対し、
$$
\Ex[\expo^{tx}] \leq \exp(t^2 (b - a)^2 / 8)
$$

証明

\( \exp(x)\)の凸性から
\begin{align}
\expo^{tx} \leq & \frac{\expo^{tb} - \expo^{ta}}{b - a} (x - a) + \expo^{ta} \nonumber \\
= & \frac{b - x}{b - a} \expo^{ta} - \frac{a - x}{b - a}\expo^{tb} \nonumber
\end{align}
両辺に期待値をとると、期待値の線形性と\(\Ex[x] = 0 \)から
\begin{align}
\Ex[\expo^{tx}] \leq & \frac{b}{b - a}\expo^{ta} - \frac{a}{b - a}\expo^{tb} - \frac{\Ex[x]}{b - a}\expo^{ta} + \frac{\Ex[x]}{b - a}\expo^{tb} \nonumber \\
= & \frac{b}{b - a}\expo^{ta} - \frac{a}{b - a}\expo^{tb} \nonumber
\end{align}
\(h = t(b - a), p = -a / (b - a), L(h) = -hp + \log(1 - p + p\expo^h) \) とすると、
$$
\frac{b}{b - a}\expo^{ta} - \frac{a}{b - a}\expo^{tb} = \exp(L(h))
$$
となっている。
\begin{align}
L(0) = & 0 \nonumber \\
L'(0) = & -p + \frac{p\expo^h}{1 - p + p\expo^h} \Bigg|_{h = 0} = 0 \nonumber \\
L''(h) = & \frac{p\expo^h}{1 - p + p\expo^h} \bigg( 1 - \frac{p\expo^h}{1 - p + p\expo^h} \bigg) \nonumber \\
\leq & \frac{1}{2} \bigg( 1 - \frac{1}{2}\bigg) = \frac{1}{4} \nonumber
\end{align}
よりテイラーの定理(中心を0とした場合)が使えて、
$$
L(h) \leq \frac{1}{8} h^2 = \frac{t^2(b - a)^2}{8 }
$$
よって
$$
\Ex[\expo^{tx}] \leq \exp(t^2 (b - a)^2 / 8)
$$
が成り立つ。

定理1(McDiarmidの不等式)(再掲)

\(c_1, \ldots, c_m\) : 正の実定数
\( f : \mathcal{X}^m \rightarrow \mathbb{R} \) : 各 \(i\) に対しつぎを満たす関数
$$
\sup_{x_1, \ldots, x_m, x_i' \in \mathcal{X}} | f(x_1, \ldots, x_m) - f(x_1, \ldots, x_i', \ldots, x_m) | \leq c_i
$$
\( X_1, \ldots, X_m \in \mathcal{X} \) : 互いに独立な確率変数
このとき、任意の \(\epsilon > 0\) に対し以下の不等式が成り立つ。
$$
\Pr[f(X_1, \ldots, X_m) - \Ex[f(X_1, \ldots, X_m)] \geq \epsilon] \leq \exp \bigg(\frac{-2\epsilon^2}{\sum_{i = 1}^{m} c_i^2} \bigg)
$$

証明

\(Z_i = \Ex[f | X_1, ..., X_i]\) とする。
\begin{align}
\Ex[Z_i - Z_{i - 1} | X_1, ..., X_{i - 1}] =& \Ex[Z_i | X_1, ..., X_{i - 1}] - Z_{i - 1} \nonumber \\
= & \Ex_{X_i} \big[\Ex_{X_{i+1}, \ldots, X_m}[f | X_1, ..., X_{i}] \big| X_1, ..., X_{i - 1}\big] - Z_{i - 1} \nonumber \\
= & \Ex[f | X_1, ..., X_{i - 1}] - Z_{i - 1} = 0 \nonumber
\end{align}
が成り立つ。
\begin{align}
U_i =& \sup_{x'} \{ \Ex[f | X_1, \ldots, X_{i - 1} , X_i = x'] - \Ex[f | X_1, \ldots, X_{i - 1} ] \} \nonumber \\
L_i =& \inf_{x'} \{ \Ex[f | X_1, \ldots, X_{i - 1} , X_i = x'] - \Ex[f | X_1, \ldots, X_{i - 1} ] \} \nonumber
\end{align}
と置くと、
$$
L_i \leq (Z_i - Z_{i - 1} | X_1, \ldots, X_{i - 1} ) \leq U_i \\
U_i - L_i \leq c_i
$$
が成り立つから、補題1が使えて、
\begin{equation}
\Ex[\expo^{t(Z_i - Z_{i - 1})} | X_1, \ldots, X_{i - 1}] \leq \expo^{t^2 c_i^2 / 8}
\end{equation}
この結果を使うと、次のように評価できる。
1行目→2行目 : 命題2
3行目→4行目 : 命題1
4行目→5行目 : \(Z_i - Z_{i - 1} (i = 1, \ldots, m - 1)\) は \(X_1, \ldots, X_{m - 1}\) の関数だから2つ目のEの中では定数となる。
5行目→6行目 : 式(1)を使う
6行目→7行目 : 再帰的に繰り返す
\begin{align}
\Pr[f - \Ex[f] \geq \epsilon] =& \Pr\left[\expo^{\large t(f - \Ex[f])} \geq \expo^{t\epsilon}\right] \nonumber \\
\leq & \expo^{-t\epsilon} \Ex\left[\expo^{\large t(f - \Ex[f])}\right] \nonumber \\
=& \expo^{-t\epsilon} \Ex\left[\expo^{\large t \sum_{i = 1}^{m} (Z_i - Z_{i - 1}) }\right] \nonumber \\
=& \expo^{-t\epsilon} \Ex \left[ \Ex\left[\expo^{\large t \sum_{i = 1}^{m} (Z_i - Z_{i - 1}) } \middle| X_1, \ldots, X_{m - 1}\right] \right] \nonumber \\
= & \expo^{-t\epsilon} \Ex\left[ \expo^{\large \sum_{i = 1}^{m - 1} (Z_i - Z_{i - 1})} \Ex\left[\expo^{\large t(Z_m - Z_{m - 1})} \middle| X_1, \ldots, X_{m - 1}\right]\right] \nonumber \\
\leq & \expo^{-t\epsilon} \expo^{\frac{t^2 c_m^2}{8}} \Ex\left[ \expo^{\large \sum_{i = 1}^{m - 1} (Z_i - Z_{i - 1})}\right] \nonumber \\
\leq & \ldots \leq \exp\left(\frac{t^2}{8} \sum_{i = 1}^{m} c_i^2 - t\epsilon\right)
\end{align}
ここで、
\begin{align}
\frac{t^2}{8} \sum_{i = 1}^{m} c_i^2 - t\epsilon = \frac{1}{8} \sum_{i = 1}^{m} c_i^2 \left(t - \frac{4\epsilon}{\sum_{i = 1}^{m} c_i^2} \right)^2 - \frac{2\epsilon^2}{\sum_{i = 1}^{m} c_i^2} \nonumber
\end{align}
であり、任意の\(t > 0\)に対し式(2)が成り立つから、
$$
\Pr[f(x_1, \ldots, x_m) - \Ex[f(x_1, \ldots, x_m)] \geq \epsilon] \leq \exp \left(\frac{-2\epsilon^2}{\sum_{i = 1}^{m} c_i^2} \right)
$$

(証明終)