Optimization 심화 : Random Reshuffling (2)

 

 

모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다.

 

 

오늘부터 당분간의 글은 기존처럼 줄글 형식으로 작성된 포스팅이 아닌 필자가 직접 제작한 ppt를 활용하여 포스팅을 올리고자 한다.

본 ppt는 beamer를 활용해 제작되었다.

 

 

 

 

먼저 이전과 동일하게 위와 같은 Finite-sum으로 정의된 optimization problem을 정의하자.

이때 각각의 $f_i$가 smooth한 함수라는 가정을 할 것이다. 

 

 

우리가 현재 관심 있는 주제는 Random reshuffling이므로 이에 대한 간단한 알고리즘을 우선 보이고자 한다.

지난 글에서도 언급하였지만 이는 실제 practical한 상황에서 일반적으로 쓰이는 방법이다.

 

매 epoch을 시작할 때마다 데이터를 random shuffling을 해주고 그 다음 순서대로 데이터를 sampling해나가는 방법이다.

이때 매 iteration마다 접근하는 데이터의 인덱스를 $\pi_i$로 표기하고 있다.

즉, 이 데이터를 활용하여 계산된 $f$의 $x_t^i$의 'stochastic' gradient는 $\nabla f_{\pi_i}(x_t^i)$로 표기될 것이다.

이때 $x_t^i$는 위 (Pseudo)알고리즘을 보면 알 수 있듯이 $t$번째 epoch의 $i$번째 iteration의 파라미터이다.

 

 

지난 글에서도 언급한 것처럼 RR을 사용할 경우 매 iteration마다 계산되는 stochastic gradient는 True gradient의 unbiased estimator가 아니다. 즉, bias가 존재한다.

이는 convergence analysis 증명이 상당히 어려워지게 만드는 문제점이다.

 

 

본 논문에서 사용하고 있는 가정이다.

앞에서 언급한 것처럼 $f_i$가 L-smooth 라고 가정하며 lower-bounded돼 있다고 가정한다.

만약 $f$가 convex (또는 strongly-convex)  함수이면 이때 $f^{\star}$는 global minima에서의 함숫값이다.

 

또한 아래 두 개의 Lemma는 이전 글에서도 언급하였고, 본 논문에서 기본적인 공식으로 증명 과정에서 사용된다.

 

그럼 이 논문의 본론으로 들어가도록 하자.

 

 

먼저 이 논문은 하나의 독특한 개념을 도입한다.

이 개념은 저자들의 convergence rate 유도에 있어서 상당히 핵심적인 기능을 수행한다.

 

사실 위 Shuffling variance의 의미에 대해서 정확히 이해하진 못했다. (깊이 있게)

일단 그냥 저렇게 정의했나보구나.. 받아들이고 나중에 저 의미와 RR setting에서의 위 variance가 갖는 장점을 알게 되면 수정하도록 하겠다

 

자 그러면 어쨌든 위 shuffling variance와 일반적인 variance 사이의 관계식을 Proposition으로 서술하였다.

 

여기서 $\gamma$는 step size, $\mu$는 strongly-convex function의 parameter, $L$은 smoothness의 parameter, $n$은 data sample 수이다.

 

이 Proposition의 증명은 다음과 같다.

 

먼저 증명의 핵심이 되는 아래의 Lemma를 보고 가자

 

결국 어떤 집합에서 without replacement로 (일부 혹은 전체를) 순서대로 sampling을 해나갈 때, 

표본 집단 (확률 변수들의 집합)의 평균과 분산이 어떻게 되는지를 보여주는 식이다.

이에 대한 증명과정은 기초통계학 수준의 내용으로 이뤄져 있기에 본 글에서는 생략한다. 

논문에는 증명과정이 Appendix에 서술되어져 있으므로 이를 참고하자.

 

Proposition에 대한 증명 과정이다.

 

 

Lemme를 제외하고는 나머지 식 전개는 단순 산수이기 때문에 위 슬라이드만으로 충분히 이해가 될 것이다.

 

자, 그러면 이제 Main theorem 1번째를 보자.

 

 

 

위에서부터 차례대로 읽어나가면 크게 어려움은 없으리라 생각된다.

저자들은 이것을 이전 논문의 SGD convergence rate과 비교한다.

여기서 SGD는 'with-replacement' uniform sampling이다.

 

 

결국 SGD와 RR에서 RR에게서 더 빠른 수렴 속도를 기대하기 위해서는 우리는 (매우) 작은 step size를 사용하거나 mini-batch를 사용해야 한다고 주장한다. 

하지만, 매우 작은 step size는 학습하는데 소요되는 시간을 상당히 길게 만들기 때문에 저자들은 mini-batch를 사용하는 것을 권장한다.

 

 

 

그리고 이전 논문과 비교했을 때도 저자들은 더 tight한 결과를 유도하였다고 이야기한다.

실제로 위의 값을 비교해보면 convergence rate의 $\kappa$에 대한 의존도를 상당히 낮췄음을 알 수 있다.

 

다음은 convex case이다.

 

 

역시나 SGD의 이전 논문에서의 convergence rate과 비교한다.

 

충분히 큰 epoch으로 학습을 진행하였을 때 RR이 더 나은 train error를 달성하는 걸 기대할 수 있다고 이야기한다.

 

이 PPT는 첨부파일로 업로드하도록 하겠다.

PPT에는 strongly convex한 경우의 theorem에 대한 증명도 포함되어져 있다.

증명 과정이 크게 어렵지는 않지만, 한 번 읽어보면 좋을 것 같다.

Seminar__09_13_ (2).pdf

0.16MB