Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

 

논문제목: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

 

Loss function의 optimization을 위해서 기존에는 gradient descent 방식을 사용해 왔다. 하지만 gradient descent 방식은 각 step마다 n차 미분을 필요로 하고, 이는 expensive하다. 이에, stochastic gradient descent 방식이 생겨났다. 각 step마다 it를 랜덤하게 뽑아 진행한다. Stochastic gradient 방식은 각 step에서 한번의 미분만 하면 되서 computational cost가 1/n로 줄어든다. 하 지만 randomness가 variance를 유발한다. 이로 인해 작은 learning rate를 선택해야 하며, 느리게 수렴된다. 이에, 더 큰 learning rate을 사용하기 위해 variance를 줄이는 방법들이 제안되었다. 하지만 해당 방법들은 모든 gradient들을 다 저장해야 하는 문제점이 있었다고 한다. SGD는 수렴하기 위해 learning rate가 0에 가까워져야 하는데, 이것이 수렴 속도를 늦춘다고 한다. 제안된 stochastic variance reduced gradient(SVRG)는 다음과 같다. Contribution은 다음과 같다. 기존의 방식과 달리 모든 gradient들을 저장하지 않아도 된다. 논문 에서 더 간단한 방법으로 convex loss에서의 linear convergence를 증명했다. 또한 variance reduction 개념을 수렴과 연관시키면서 직관적인 설명을 하였고, 이는 추가적인 알고리즘의 발전 에 도움이 된다. Non-convex optimization 문제에서도 variance reduction이 가능하다. 따라서 딥러 닝에서의 응용이 가능하다.