LSH for Stochastic Gradient Descent

SGD와 같은 optimization 알고리즘에 대해서 굉장히 이해도가 낮다고 생각해서 이번에 겸사겸사 세미나 주제를 이걸¹로 정해버렸는데, 후회중ㅠㅠ 그냥 모르겠다. 뭘 모르고 왜 모르는지 정리해본다.

SGD

LGD

• 왜 필요한가?

  • 기본의 방법론들은 Variance를 낮추기 위해서 $$

    \nabla f_i

    ^2\(를 모두 계산하거나, 업데이트 되는\)\theta$$에 dependent한 distribution이 필요했다.

    • max $$

      \nabla f_i

      ^2$$ 가 왜 variance를 낮추는 방향인가? (1)

    • distribution 이 부분은 추가적으로 공부해야함!! (2)
  • 그래서 결과적으론 SGD에서 얻은 O(1)이라는 계산의 효융성에서 발견된 Variance를 해결하기 위해 다시금 O(n)이 되어버리는 문제가 발생했다. 그래서 저자는 이를 두고 “Chicken and egg loop”라고 표현하였다.
  • 따라서 필요한 것은 O(1)에 가깝게 유지하면서도 Variance를 감소시킬 수 있는 방향이다.
  • 저자는 (1)을 수행하면서도 (2)가 계속 업데이트 될 필요가 없는 방법론을 위해서 LSH를 사용하였다.
  • 근데 지금 문제는 LSH를 대충 공부해봤는데 알고리즘을 봐도 어떤 식으로 샘플링을 하는지 모르겠다는 점이다ㅠㅠ

Reference

1. Lsh-sampling Breaks the Computation Chicken-and-egg Loop in Adaptive Stochastic Gradient Estimation ↩