Motivation

Machine Learning에서 가장 중요한 부분 중 하나는 어떤 알고리즘 (혹은 어떤 losss)가 어떤 Complexity를 가지는지, 그리고 Loss가 Uniform convergence하는지 입니다.
그렇기 때문에 일반적으로 data distribution $p$에서 단순히 하나만 sampling하기 보다는 Independent and identically distributed(이하 $i.i.d$) 가정을 가지고 sampling하는 경우가 많습니다.
이렇게 여러 개의 R.V. $X_1$, $X_2$, $\cdots$, $X_n$을 sampling하였을 경우엔 확률의 개념에 따라 $X_1+\cdots +X_n$와 $\mathbb{E}[X_1+\cdots+X_n]$이 완전히 일치하지는 않겠죠.
(물론, Weak Law of Large number에 의해, $n\rightarrow \infty$에 대해 두 값을 n으로 나눈 값은 high probability로 임의의 $\varepsilon$의 차이가 나게하는, 즉 converge to probability하게 됩니다.)
특히, 우리는 sampling한 Data들에 대해 Hypothesis $h\in\mathcal{H}$를 따로 취한 후 Loss를 계산해야하기 때문에, 함수를 취했을 때에도 동일하게 기댓값 주변에 어느 정도의 확률로 모이는지에 대해 관심을 가질 필요가 있습니다.
이번 글에서는 여러개의 Concentration Inequality와 기초가 되는 Big-O notation에 대해 알아볼 예정입니다.

Support Material

이 글은 STATS214/CS229M를 참고하여 작성합니다.
유튜브에서도 강의 영상이 있으니, 참고하시면 좋습니다.

Big-O notation

해당 CS229M 수업을 듣다보면, Complexity를 표시할 때 굉장히 자주 쓰는 표현이 Big-O notation입니다.
Computer Science에서 사용하는 Big-O notation과 동일하고, 간략하게 알아봅시다.

어떤 함수 $f(x)$가 있을 때, 이가 어떤 Constant $C$에 의해 값이 Bounded되는 경우가 발생합니다.
예를 들어, $x>1$에서 정의된 함수 $f(x)=\ln x$를 생각해봅시다.
$x>1$에서 $\ln x>0$이고, $\forall x>0\::\:\ln x < x$임은 자명한 사실이죠.
그렇기 때문에, $|f(x)| \leq x$라고 적어도 문제가 없습니다. 이때는, 위에서 의미한 Universial constant $C$의 값은 $1$이 됩니다.
이렇듯 어떤 Universial constant $C$가 존재하며 $|f(x)|\leq Cx$를 만족시킬 때, 우리는 Big-O notation을 사용하여 $f(x) = O(f(x))$ 또는 $f(x) = O(x)$로 표기를 합니다.
이때 $O(x)$에 들어간 $x$는 $f$에 들어가는 $x$와 동일합니다. 예를 들어, $O(\sigma \sqrt{\log n})$이라는 표기가 있으면 이는 $\exists C\in\R~s.t.~|f(\sigma \sqrt{\log n})|\leq C\sigma\sqrt{\log n}$를 의미합니다.
또한, $O(\log n)$같은 경우 굉장히 자주 나오는 표기입니다. 따라서 가끔씩 $\log n$ Factor를 숨기기 위하여 $\tilde{O}(n)$을 사용합니다. 즉, $f(n)=O(\log n)$이면 $f(n)=\tilde{O}(1)$입니다.

Concentration Inequality (R.V.)

Markov's Inequality

추후 소개할 Chebyshev's inequality에 사용되는 Markov inequality에 대해 알아봅시다.

Theorem

먼저 $X$는 음수를 가지지 않고 finite expectation이 있는 Random varaible라고 합시다.
그러면, 임의의 실수 $a$에 대해 다음 부등식이 성립합니다.

또한, $|X|\geq 0$이므로 이를 이용하여 Momentum 관점에서 하나의 따름정리를 만들 수 있습니다.

Proof는 생략합니다.

Chebyshev's Inequality

가장 Weak하지만 범용성이 뛰어난 Chebyshev's inequality에 대해 알아봅시다.

Theorem 1

$E(Z)<\infty$, $\rm{Var}(Z)<\infty$인 Random Variable $Z$가 있다고 할 때, 임의의 양수 $t$에 대해

이때, 임의의 $\delta\in(0,\:1]$에 대해 $t=sd(Z)/\sqrt{\delta}$를 대입하게 되면

Analysis

의미를 하나하나 분석해봅시다.
1. $Z-\mathbb{E}(Z)$는 Random variable $Z$의 값이 얼마나 평균으로부터 떨어져있는지를 의미합니다.
2. 이 값이 $t$보다 크다는 것은, 꼬리쪽에 해당이 됩니다. 즉, $t$가 크면 클 수록 엄청 멀리 있는 값들만이 후보가 됩니다.
3. 이때 평균으로부터의 거리를 $t$라고 하면 그 확률은 $t^{-2}$에 비례합니다. 즉, 이는 polynomial한 Complexity를 가지고, 이 감소율은 Exponential에 비해 굉장히 Slow합니다.
즉, Chebyshev에서는 $O(n^{c/2})$밖에 보장을 안해준다는 것을 의미합니다. (w.h.p)
4. 만약, Random Variable $Z$가 Gaussian이라 하면 Gaussian tail bound를 이용하여 다음 식을 유도해낼 수 있습니다.

즉, $\delta=1/n^c$라 하면 $|Z-\mathbb{E}[Z]|\leq \sigma \tilde{O}(1)$을 유도할 수 있습니다. (w.h.p)
유도 과정은 아래 Appendix에서 확인할 수 있습니다.

Appendix: Derive Gaussian Tail bound

먼저, Markov inequality를 체른오프식 Bound로 표현을 하면

이때 $\inf$는 하한을 의미합니다.
$X\sim \mathcal N(\mu,\:\sigma^2)$에서 $y=X-\mu$라 하면, $y \sim \mathcal N(0,\:\sigma^2)$을 따름은 자명합니다.
Moment generating function에서

이를 위의 체른오프 bound에 대입하면

이고 이차함수의 성질을 사용하면 우측은 $-\dfrac{t^2}{2\sigma^2}$와 동일합니다.
즉, $\Pr[X -\mathbb{E}[X]\geq t]\leq e^{-t^2/2\sigma^2}$가 성립하게 됩니다.
이때 $X-\mathbb{E}[X]$, 즉 $y$는 Gaussian distribution이므로 대칭성을 활용 하면

이고 $2e^{-t^2/2\sigma^2}=\delta$라 하면 $\delta = \sigma\sqrt{2\log(2/\delta)}$이므로 위의 식이 성립합니다.

Hoeffding's inequality

다음은 위와 약간 동떨어져서, 범위를 가지는 즉 Bounded 되어 있는 Random Variable"들"에 대해서 성립하는 아주 강력한 inequality에 대해 알아봅시다.

Theorem 2 (Hoeffding's inequality)

$X_1$, $X_2$, $\cdots$, $X_n$이 독립적인 실수의 R.V라 하고, $\forall i\leq n\::\:a_i\leq X_i\leq b_i$라 합시다.
즉, Random variable들이 모두 bounded 되어 있습니다.
이때, $\overline{X}=\dfrac{1}{n}\displaystyle\sum_{i=1}^n X_i$라 하고 $\mu=\mathbb{E}[\overline{X}]$라 정의합니다. 즉, $\mu$는 평균의 기댓값입니다.
이때, 임의의 양수 $\varepsilon$에 대해

가 성립합니다.

Analysis

$\sigma^2=\frac{1}{n^2}\sum_{i=1}^n (b_i-a_i)^2$라 할 때, $\varepsilon = O(\sigma\sqrt{\log n})$이라 하면

즉, with high probability로 $|\overline{X}-\mu|\leq \tilde{O}(\sigma)$임을 알 수 있습니다.
또한, $a_i$와 $b_i$ 모두 상수이므로 $\sigma^2=O\left(\dfrac{1}{n}\right)$이고 이를 대입하면 $|\overline{X}-\mu|=\tilde{O}\left(\dfrac{1}{\sqrt{n}}\right)$입니다.
이는 추후 sub-gaussian와 연계되어 활용됩니다.

Sub-Gaussian Random variables

Definition (Sub-Gaussian Random Variable), Version I

먼저, Sub-gaussian이라는 것이 무엇인지부터 정의를 해 봅시다.
R.V. $X$에 대해 $\mu:=\mathbb{E}[X]<\infty$라 합시다. 이때,

가 성립하면 $X$를 $\sigma$를 parameter로 가지는 sub-Gaussian R.V.라고 합니다.
Formally하게, $X$를 $\sigma$-sub-Gaussian 혹은 $X$가 $variance~proxy$를 $\sigma^2$로 가진다고 표현합니다.

Analysis

일반적으로 Moment Generating function을 $\mathbb{E}[e^{tX}]$로 정의합니다. 이러한 관점에서 보면, 위는 무한히 많은 moment들이 존재하고, 이것들이 지수적으로 감소함을 의미하는 바입니다. 조금 더 strictly하게, Momentum Generating function에 대한 Maclaurin's series을 생각하면

로 적을 수 있고, 이가 Bounded 되기 때문에 모든 값이 존재함을 알 수 있습니다.
또한, Series가 수렴하므로 극한을 취했을 때 $0$이 되어야 하고, 더하고 있는 항들은 모두 실수열이므로 Cauchy Sequence로 간주할 때 굉장히 Slowly하게 증가함을 알 수 있습니다.

Definition (Sub-Gaussian Random Variable), Version II

위는 Momentun function에 대해 초점을 맞추었다면, 이제는 Tail에 대해 직관적으로 정의를 해봅시다.
동일하게, $X$는 유한한 기댓값을 가지는 R.V.라고 할 때,

일 때 $X$를 $\sigma$-sub-Gaussain이라 합니다.

참고로 두 정의는 동치인 증명이며, Version I => II는 위의 Appendix 과정과 동일하고 II에서 I을 증명하는 과정은 굉장히 복잡합니다.

Sum of sub-gaussian

독립적이고 Gaussian Random variable $X_1$, $X_2$, $\cdots$, $X_n$에 대해 이들의 합 $X_1+X_2+\cdots+X_n$도 동일하게 Gaussian을 따름은 자명합니다.
그럼, 과연 Sub-gaussian도 동일할까요?
정답은 Yes입니다. 이에 대해 알아봅시다.

Theorem

$X_1$, $X_2$, $\cdots$, $X_n$을 각각 variance proxy가 $\sigma_1^2$, $\sigma_2^2$, $\cdots$, $\sigma_n^2$인 sub-gaussian R.V. 라고 합시다.
이때, $Z=\sum_{i=1}^n X_i$라 하면 $Z$는 variance proxy가 $\sum_{i=1}^n \sigma_i^2$인 sub-gaussian이 됩니다.
결론적으로, 임의의 실수 $t$에 대해

가 성립합니다.

Proof

Defintion II을 활용하는 것은 굉장히 어려워보입니다. 각각의 확률을 모두 구하여 Union Bound를 사용하기엔 $n$개의 범위를 알맞게 나누기가 힘들죠.
그렇기 때문에, Version I을 사용합시다.
운이 좋게 각각의 R.V.들이 독립이기 때문에, 각각을 분리할 수 있으므로 더 유용하겠네요!

즉, $Z$는 variance proxy $\sum_{i=1}^n \sigma_i^2$인 sub-gaussian이고, Definition II에 의해 위의 확률식이 유도됩니다.

Next Posting

• Examples of sub-gaussian random variables
• Usefulness of sub-gaussian random variables
• Functions of random variables
  • McDiarmid's inequality
  • Poincar´e inequality