Optimization 심화: SGD (2)

 

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

 

오늘은 stochastic gradient의 noise에 대한 개념에 대해 살펴보고자 한다.

 

먼저 $f(x)$가 L-smooth하고 convex할 때 가지는 성질에 대해 알고 넘어가자.

 

$\frac{1}{2L} \lVert \nabla f(y) - \nabla f(x) \rVert^2 \le f(y) - f(x) - \langle \nabla f(x), y - x \rangle$

$\frac{1}{L} \lVert \nabla f(x) - \nabla f(y) \rVert^2 \le \langle \nabla f(y) - \nabla f(x), y - x \rangle$

 

이 중 아래의 식을 Co-coercivity라고 한다.

이에 대한 증명은 다음과 같이 이뤄진다.

 

$f(x) - f(y) = f(x) - f(z) + f(z) - f(y)$

$\le \langle \nabla f(x), x - z \rangle + \langle \nabla f(y) , z - y \rangle + \frac{L}{2} \lVert z - y \rVert$

 

두 번째 부등식은 convex의 정의와 L-smooth의 성질을 적용해준 것이다.

모든 $x, y, z$에 대해서 성립하므로 가장 tight한 upper bound를 얻기 위해서 RHS를 최소화하는 $z$를 구한다. 

이를 위해 우리는 RHS를 $z$에 대해 미분해서 $=0$을 푼다.

그러면 $z$는 다음과 같이 나온다.

 

$z = y - \frac{1}{L} (\nabla f(y) - \nabla f(x))$

 

이를 대입하고 식을 정리하면 다음의 결과를 얻을 수 있다.

 

$\frac{1}{2L} \lVert \nabla f(y) - \nabla f(x) \rVert^2 \le f(y) - f(x) - \langle \nabla f(x), y - x \rangle$

 

이제 위 식에서 $x$와 $y$를 서로 바꿔서 부등식 2개를 만든 다음에, 두 부등식을 연립해주면 Co-coercivity를 얻을 수 있다.

 

다음은 (stochastic) gradient의 noise에 대한 개념이다.

이를 위해서는 먼저 interpolation이란 것에 대해 알아야 한다.

먼저 다음과 같은 Finite-sum optimization problem 문제를 가정하자.

 

$\min f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x)$

 

여기서 $i$는 data sample (또는 mini-batch) index이다.

그렇다면 이런 의문점이 들 수 있다. 모든 $f_i(x)$는 동일한 최소점을 무조건 가진다고 할 수 있을까?

즉, $x^{\star} \in \arg \min f(x)$일 때 모든 $i$에 대해 $x^{\star} \in \arg \min f_i(x)$라고 할 수 있을까?

이것이 보장되기 위해서는 interpolation이 성립해야 된다.

즉, 모든 함수 $f_i(x)$가 적어도 하나 공통의 $x^{\star}$를 공유할 때 우리는 $f$가 데이터를 interpolation한다고 이야기한다. 일반적으로 overparameterized neural network는 interpolation이 성립한다.

 

가정으로 $f_i$가 bounded from below이고 $L_i$-smooth하다고 하자.

참고로 $f_i$가  $L_i$-smooth하다면 $f$는 $L_{avg}$-smooth하다. 여기서 $L_{avg}$는 $\frac{1}{n} \sum_{i=1}^n L_i$이다.

 

$\sigma_f^{\star} := \inf \mathbb{V}[\nabla f_i(x^{\star})$

 

만약 interpolation이 성립하면 위 값은 0이다. 하지만 그렇지 않으면 0보다 큰 값을 가질 수 있고 이 말은 각각의 $\nabla f(x^{\star}) = 0$이지만 $\nabla f_i(x^{\star})$는 0이 아니라는 의미이다.

또한, 분산은 제곱의 평균에서 평균의 제곱을 뺀 것이고 Finite-sum optimization problem에서 평균은 True graident $\nabla f(x)$이기 때문에 제곱의 평균과 같아진다. (True gradient는 $x^{\star}$에서 값이 0이므로)

 

즉 위와 같은 finite-sum optimization problem에서 모든 $f_i$가 공통의 $x^{\star}$를 공유하는, 즉 interpolation이 성립하는 경우도 많지만 그렇지 않은 경우도 있고 이 경우에는 우리가 stochastic graident로 파라미터를 업데이트할 때 정확히 딱 stationary point로 수렴하는 것이 불가능할 수도 있다.

왜일까?

 

stationary point란 $\nabla f(x) = 0$인 점들의 집합이다.

우리는 $\nabla f(x)$가 아니라 이것의 (unbiased) estimator, 즉 추정치값인 $\nabla f_i(x)$를 사용해서 파라미터를 업데이트한다.

충분히 오랫동안 학습을 돌려서 $\nabla f_i(x) = 0$이 되었을 때 학습을 멈춘다고 하자.

하지만 interpolation이 성립하지 않으면, $\nabla f_i(x)  = 0$인 지점이라고 하여 $\nabla f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x) = 0$이 성립한다는 보장은 없다. 다른 stochastic gradient에 대해서는 0보다 큰 값을 가지고 있을 수도 있기 때문이다. 그렇다면 우리는 진정한 stationary point에 도달했다고는 할 수 없다.

(추가적으로 interpolation이 성립한다고 하더라도 진정한 stationary point에 도달했다고 보장하는 것은 non-convex에서는 불가능에 가깝다.)

 

하지만 그렇다고 해서 학습이 실패한 것이라고 할 수는 없다.

오히려 요즈음 딥러닝에서는 stationary point에 도달할 때까지 학습을 계속 돌리지도 않고, 충분히 loss 값이 낮아졌으면 학습을 멈추는 경우가 대다수이다. 즉, gradient norm이 충분히 작아졌으면 학습이 충분히 되었다고 판단한다.

또한, 딥러닝은 (high-dimension) non-convex loss landscape을 가지기 때문에 무수히 많은 local minima, gloabal minima, saddle point 등이 존재하고 loss 값이 제일 낮은 global minima에 도착했다는 것을 보장하는 것은 불가능하다. 

그런 상황에서 gradient norm이 정확히 0이 될 때까지 학습을 돌리는 것은 이득보다 손해/비용이 훨씬 더 크기 때문에 비 실용적이고 비현실적이다.

그래서 우리는 gradient norm이 충분히 작아졌는지로 학습 완료 여부를 판단한다.

그리고 이러한 지점들을 우리는 $\epsilon$-stationary points라고 부른다. 즉, 어떤 작은 양수 $\epsilon$에 대하여 다음을 만족하는 지점들이다.

 

$\mathbb{E}]\lVert \nabla f(x) \rVert]_2^2 \le \epsilon$

 

 

다음 글에서는 L-smooth의 descent lemma에서 왜 우리는 stochastic gradient의 second moment upper bound를 잡아야 하는지, 그리고 이와 관련하여 어떤 가정들이 있어왔는지에 대해 알아보고자 한다.