Logical Scribbles
[논문 리뷰] Revisiting The Polyak Step Size 본문
오늘은 2022년 8월 arXiv에 공개된 논문 'Revisiting The Polyak Step Size' (https://arxiv.org/abs/1905.00313)에 대해서 살펴보자. 직접 만든 PPT Slide로 설명하도록 하겠다. 만드느라 힘들었다..
1. 개요
이 논문의 의의는 크게 두가지로 나눌 수 있다.
첫번째로, 기존의 Polyak step size scheduling이 GD 방식 (gradient discent method)을 통하여 다양한 함수에서 best known convergence rate를 이룰 수 있음 보임에 있다.
저자는 Polyak step size가 gradient bound G를 갖는 non-smooth한 general convex function, beta smooth function, alpha strongly convex function, smooth and strongly convex function에서 모두 best known error bound를 달성함을 보인다. 증명과정은 뒤에서 다루기로 하자.
두번째로, 첫번째에서 보인 error bound와 optimal value의 lower bound를 이용하여 저자가 제시한 Adaptive polyak step size 방식의 알고리즘은 또한 best known error bound를 얻을 수 있음을 보인다. 또한 이 알고리즘은 Polyak step size를 이용한 GD 방식의 시간 복잡도와 비교했을 때 로그 팩터가 곱해지는 수준이라고 주장한다.
이 논문이 제안한 것은 간단한 Polyak step size의 변형 알고리즘이다. 저자는 논문에서 'All we need is a lower bound' 라는 문장을 사용하였는데, 이를 통해 기존 Polyak step size 방식에서 필요했던 optimal function value를 모르는 상황에서도 optimization이 잘 된다는 점을 알 수 있다.
2. 연구 배경
다음으로 연구 배경에 대해서 살펴보자.
저자는 논문의 Introduction에서 optimization의 이론과 실전의 차이에 대해 언급하며 논리를 전개한다.
저자에 따르면, 대부분의 optimization theory에는 parameter들로부터 자유로운 알고리즘들이 거의 없다. 즉, 많은 최적화 이론들이 parameter에 의존한다는 것이다.
따라서 실전적인 측면에서 많은 parameter를 위한 휴리스틱 방법들이 사용되고 있다. 즉 기존 이론들에는 사전 정보들이 필요하다는 것이다. 이 때 사전정보란 GD 방식의 best known rate를 위한 parameter들일 수 있고, Polyak step size 관점에서는 optimal fuction value 일 수 있다.
기존방법의 또 다른 한계로는 best known rate을 위한 step size setting이 다양한 함수 영역에서 다르다는 것이다. 위 slide의 Table1을 보면 다양한 함수 영역에서 best known convergence rate과 이를 얻기 위한 서로 다른 step size setting을 알 수 있다. 즉, 함수마다 best known convergence rate을 얻기 위한 step size 설정이 달라야 한다는 것이다.
마지막으로, 기존 Polyak step size setting은 non-smooth convex function에서 optimal을 달성한다고 알려져 왔다. 즉 Table1과 같은 다양한 함수 영역에서는 Polyak step size setting이 optimal을 달성하는지 여부는 알려져 있지 않았었다.
추가적으로 이 논문에서 사용하고 있는 Notation들을 첨부한다. 많은 증명과 수식들이 여기서 정의한 notation들을 사용하며 전개되기 때문에, 한번 읽고 이렇게 약속했구나 이해하면 되겠다.
앞서 의의에서도 언급했지만 이 논문의 핵심 주장은 1. Polyak step size로 Non-smooth, convex funtion의 optimal을 달성할 수 있다는 사실을 여러 함수로 확장하고, 2. Polyak step size에서 필요했던 Optimal value 값 대신 optimal value의 lower bound를 활용한 알고리즘을 제시한다는 것이다.
이제부터는 이 두가지 핵심 주장에 대해 살펴보도록 하자.
3. 핵심 주장 ①
논문 저자는 우선 GD 방식을 이용한 Polyak step size scheduling이 여러 함수에서 동시에 optimal을 달성한다고 주장한다. 처음 이 논문을 읽을 때는 약간 의아한 부분이 있었다. 내가 알기로는 Polyak step size scheduling이 Subgradient method 방식에 속해있는 것으로 알고 있었는데, GD 방식을 이용하여 논리를 전개하기 때문이다. 하지만 Subgradient의 정의를 곱씹어보고 이 논문에서 선택한 step size를 보고난 뒤 어느정도 납득이 되었다.
첫번째 핵심주장에서는 Theorem 1을 주장하는데, Theorem 1의 내용은 'Algorithm1'이 T스텝 이후 위와 같은 Regret bound를 갖는다는 것이다. Regret Bound는 찾아보니 강화학습에서 많이 사용되고 있는 용어라고 한다. Regret의 정확한 정의는 선택한 model / policy를 이용하여 얻은 reward가 최선의 선택에 비해 얼마나 손해가 있는지를 수치화 한 것이라고 한다.
더 자세히 살펴보면, Algorithm1(기존의 Polyak Step Size scheduling을 사용한 일반적인 GD 방식의 알고리즘)이 return한 값에 대한 sub-optimality gap이 regret bound B_t(중괄호 안에 있는 T에 대한 function value 들중 minimum 값)을 갖는다는 것이다. (이후 이 Theorem1에 대한 증명이 나온다)
이 theorem으로 첫번째 결과를 얻는다.
'Algorithm1' 에서 return 된 값에 대한 sub-optimality gap이 B_t 값을 upper bound로 갖는다고 했을 때, 이러한 Polyak step size scheduling을 통한 알고리즘의 결과가 best known rate의 minimum값을 Regret bound로 갖는다고 볼 수 있다는 것이다.
사실 convergence rate에 대한 개념이 어려웠다. 하지만 많은 자료와 글을 읽다보니 결국 convergence rate은 알고리즘이 얼마나 잘 수렴하는지에 대한 척도이고, 시간복잡도 개념으로 이해할 수 있다는 것을 알게 되었다.
따라서 위의 표와 B_T의 정의를 보면 시간복잡도 측면에서 B_T가 best known rate의 minimum 값을 갖는다는 것을 쉽게 납득 할 수 있다.
이제 이 Theorem1의 증명과정을 살펴보자.
첫번째 핵심 주장의 증명 과정은 위와 같다. 앞서 소개했던 regret bound를 0에서 1사이의 값을 갖는 감마를 이용하여 general하게 정의한 뒤, lemma2를 이용해 증명한다. 세부적인 증명과정은 함수의 Case를 나누어 함수의 Basic Property를 이용하고, finite-sum problem 꼴의 식을 이용하여 각각의 함수가 general regret bound를 가짐을 보인다. 더 자세한 설명은 논문을 읽어보면 이해가 될 것이다.
4. 핵심 주장 ②
두번째 핵심 주장의 내용이 사실 이 논문의 진짜 핵심이다.
바로 저자가 제시한 Adaptive Polyak step size 알고리즘이다. 저자는 함수의 Optimal value 대신 optimal value의 lower bound를 활용한 알고리즘을 제시한다. (따라서 사전정보 : optimal funtion value를 알고 있지 않아도 된다!) 이 알고리즘은 optimal value 이외에도 또 다른 parameter에 대한 사전 정보 없이 앞의 Algorithm1의 Gradient Descent with polyak step size method에 근접한 결과를 보여준다. 보통 초기값 lower bound는 리스크 최소화를 위해 0으로 설정하고 시작하기로 하자.
이 알고리즘은 에포크 K만큼의 gradient update를 T번 진행하는 알고리즘으로, 앞서 소개했던 B_t의 error bound를 얻기 위해서는 T*K만큼의 gradient update가 진행된다. 따라서 gradient 업데이트 시간복잡도 측면에서 로그팩터만큼의 차이가 존재하지만, optimal known bound를 얻을 수 있다고 한다.
지금부터는 저자가 제시한 Adaptive Polyak Step Size Algorithm을 한줄 한줄 살펴보기로 하자. 첨부한 slide에 자세히 설명이 되어있으니 slide를 보는 것이 더 이해가 빠를 수 있다.
이 Adaptive polyak step size algorithm은 Algorithm2와 Algorithm3으로 구성된다. Algorithm3에 Input data를 넣으면 for문을 통해 Epoch 횟수만큼 라인 3~4가 실행되는데, 한 에포크가 실행될 때마다 Algorithm2를 호출한다. 이 sub-routine Algorithm2는 T번 만큼 반복하며 learning rate를 계산하고, gradient descent 한 후 objective function을 최소화하는 t*에 대하여 x̄를 return 한다. 다시 Algorithm3로 돌아와서 return 받은 x̄와 k번째 lower bound를 이용하여 lower bound를 업데이트 한다. 결과적으로, Algorithm3의 line6에서 objective function을 minimize하는 k*번째 x̄를 리턴한다.
이러한 알고리즘으로 저자는 Theorem3을 주장한다. Theorem3은 Algorithm3 에서 return된 x̄ 를 이용하여 구한 objective function value와 optimal과의 gap(sub-optimality gap)의 upper bound는 기존의 Polyak Step Size method의 regret bound *2 가 된다는 것이다. 앞서 Algorithm3에서 인풋데이터는 T,K,x_0,lowerbound 4가지 였기 때문에, 기존 polyak step size와 다르게, optimal value의 정보가 필요 없음을 다시 한번 알 수 있다.
이번에는 이 Theorem2의 증명과정을 살펴보자.
두번째 핵심주장의 증명과정을 간략히 slide로 만들어 보았다. Lemma3를 이용하여 증명하는데, objective function f의 gradient 가 G-Lipschitz countinuous 하다고 가정하고 시작한다. 처음에는 이 부분에서 왜 이런 가정을 하는지 헷갈렸었는데 이는 gradient descent의 수렴성 분석에서 자주 쓰이는 가정이니 그려러니 했다.
결론적으로 General regret bound의 감마에 1/2을 넣은 값이 B_t보다 작음을 이용하고, 두가지 case를 나누어 증명한다.
첫번째 case는 Algorithm3에서 return 된 값에 대한 optimal value와의 차이가 general regret bound 보다 작을 때이다. 이때 h(x̄_k) 는 자동적으로 B_t보다 작아지게 되어 증명이 끝난다.
두번째 case는 Algorithm3에서 return 된 값에 대한 optimal value와의 차이가 general regret bound 보다 클 때이다. 이 때의 증명은 lemma3.2를 이용하여 저자가 제시한 에포크 횟수에서 optimal value와 gap이 B_t로 bounded됨을 보이며 끝난다.
5. 느낀점
사실 아직 많은 Optimization 논문을 읽어보지 않아서, 이 논문이 주장하는 최대 장점(사전 정보의 불필요성)이 얼마나 powerful한지는 와닿지 않는다. 처음 읽을 때는 뭔말인가 싶었지만 증명도 직접 해보고 글도 여러번 읽어보니 수식 천국인 논문을 그래도 절반(?)은 이해할 수 있게 된 것 같다.
