Convergence Analysis: Gradient Descent

정승우·2024년 3월 11일

수렴률 분석

목록 보기

2/2

본 시리즈는 연합학습의 수렴률 분석을 단계별로 정리한 글입니다. 인공지능 학습과 수학에 대한 최소한의 배경지식만으로 연합학습 알고리즘의 수렴률 분석을 차근차근 학습할 수 있도록 구성되었습니다. 글의 내용에 대한 추가적인 배경지식이 필요한 경우, 보완 설명 섹션을 통해 관련한 내용을 제공하고 있습니다.

1. Introduction

이전 글에서는 머신러닝의 수학적 정의와 머신러닝의 예제들, 그리고 수렴률 분석에 필요한 손실함수에 대한 가정 (i.e., 매끄러움; 볼록성) 들을 알아보았다. 이번 글에서는 이전 글에서 알아본 배경지식들을 바탕으로, L-매끄러움과 볼록성이 가정된 상황에서 경사하강법의 수렴률을 증명하는 방법을 알아본다.

2. Quadratic upper bound on L-smooth function

$f$ 가 L-매끄러움을 만족하면, 함수 $f$ 는 이차 상한(quadratic upper bound)을 가진다. 여기서 이차 상한이란, 어떤 함수가 주어진 점 주변에서 다른 이차 함수에 의해 제한될 수 있다는 것을 의미하는데, L-매끄러움 함수에 대한 이차 상한은 다음과 같다.

f(y) - f(x) - \nabla f(y)^T(x-y) \leq \frac{L}{2}||x-y||^2 \quad (1)

2.1 증명

증명을 위해 먼저, 함수 $g(t)$ 를 정의하자.

g(t) = f(y + t(x-y)),\ t \in [0,1]

이 함수는 $t$ 를 매개변수로 해서, $x$ 와 $y$ 를 잇는 직선을 나타내며, 다음 함수 값을 가진다.

f(x) = g(1), \ f(y) = g(0)

따라서, $f(x)$ 와 $f(y)$ 의 함수 값은 미적분의 기본정리에 따라 다음 적분식으로 나타낼 수 있다.

f(x) - f(y) = g(1) - g(0) = \int_0^1 g'(t)dt \quad (2)

여기에서 $g'(t)$ 는 함성합수의 미분에 따라 다음과 같이 계산된다.

g'(t) = \nabla f(y+t(x-y))^T(x-y) \quad (3)

이제, 공식 (2), (3)을 공식 (1)의 좌변에 대입하자.

f(y)- f(x) - \nabla f(y)^T(x-y) = \int_0^1 g'(t)dt - \nabla f(y)^T(x-y)

f(y)- f(x) - \nabla f(y)^T(x-y) \\= \int_0^1 \nabla f(y+t(x-y))^T(x-y)dt - \nabla f(y)^T(x-y)

이 공식에서, $\nabla f(y)^T(x-y)$ 는 $t$ 에 대해서 독립적인 상수이다. 또한, $t$ 의 범위가 0부터 1까지 이기 때문에 이 상수를 적분하면 원래의 값을 얻는다. 따라서 해당 항을 적분기호 내부로 가져올 수 있다.

f(y)- f(x) - \nabla f(y)^T(x-y) \\= \int_0^1 \nabla f(y+t(x-y))^T(x-y) - \nabla f(y)^T(x-y)dt

이제, 이식을 정리하면 다음과 같다.

f(y)- f(x) - \nabla f(y)^T(x-y) \\= \int_0^1 (\nabla f(y+t(x-y)) - \nabla f(y))^T(x-y)dt

정리된 적분 기호 내부의 식에 코시-슈바르츠 부등식을 적용하면 다음과 같다.

\nabla f(y+t(x-y) - \nabla f(y))^T(x-y) \\\leq ||((\nabla f(y+t(x-y)) - \nabla f(y))|| \cdot ||x-y||

따라서, 다음과 같이 부등식을 생성할 수 있다.

f(y)- f(x) - \nabla f(y)^T(x-y) \\\leq \int_0^1 ||(\nabla f(y+t(x-y)) - \nabla f(y))|| \cdot ||(x-y)||dt \quad (4)

이제 L-매끄러움 조건식을 $||(\nabla f(y+t(x-y)) - \nabla f(y))||$ 에 적용한다.

∣∣(\nabla f(y+t(x-y)) - \nabla f(y)))∣∣≤L∣∣y+t(x-y)−y∣∣

정리하면, 다음과 같다.

∣∣(\nabla f(y+t(x-y)) - \nabla f(y)))∣| \leq L∣∣t(x-y)∣∣

부등호의 기호 ( $\leq$ ) 가 동일하므로, 식 (4)에 L-매끄러움 조건식을 대입할 수 있다. 이를 대입하면, 다음과 같다.

f(y)- f(x) - \nabla f(y)^T(x-y) \leq \int_0^1 L∣∣t(x-y)∣∣ \cdot ||(x-y)||dt

이 식을 한번 더 정리한다.

f(y)- f(x) - \nabla f(y)^T(x-y) \leq \int_0^1 Lt||(x-y)||^2dt \quad (5)

이제, 식 (5)의 적분 기호 이하의 항에서 상수항을 적분 기호 앞으로 뺀다.

f(y)- f(x) - \nabla f(y)^T(x-y) \leq L||(x-y)||^2 \int_0^1 tdt

마지막으로 적분을 계산하면, 증명이 완료된다.

f(y)- f(x) - \nabla f(y)^T(x-y) \leq \frac{L}{2}||(x-y)||^2

보완 설명 1: 코시-슈바르츠 부등식
두 벡터 사이의 내적 값은 두 벡터의 노름의 곱보다 커질 수 없음을 나타내는 부등식이다.

\vec{a} \cdot \vec{b} \leq ||\vec{a}||\cdot||\vec{b}||

3. Convergence analysis: L-smooth and convex

이제 실제로 간단한 L-매끄러움과 볼록성이 가정된 함수 $f$ 에 대한 경사 하강법의 수렴률을 증명해보자. 먼저 결론부터 살펴보면, 경사 하강법은 고정된 스텝 사이즈 ( $t$ ) 가 $t \leq \frac{1}{L}$ 일 때 다음을 만족한다.

f(x^{(k)}) - f(x^*) \leq \frac{||x^{(0)} - x^*||^2}{2tk}

$f(x^{(k)})$ : k번째 반복에서의 목적 함수의 값
$f^*$ : 목적 함수의 최솟값
$x^{(0)}$ : 최적화를 시작하는 초기 점
$x^*$ : 최적화 문제의 해

즉, 고정된 스텝 사이즈에서 수렴률은 $O(\frac{1}{k})$ 가 된다.

3.1 증명

먼저 섹션 2.1에서 살펴보았던, 이차 상한 식을 함수 $f$ 에 적용하는 것으로 시작한다.

f(y) \leq f(x) + \nabla f(x)^T(y-x) + \frac{L}{2}||y-x||^2

이제 이 식에 경사 하강법을 적용하기 위해, 경사 하강법의 이동을 생각해보자. 경사 하강법에는 어떤 위치 ( $x$ ) 에서 이동한 다음 위치를 $x^+ = x - t\nabla f(x)$ 라고 표현할 수 있다. 따라서, 위의 식에서 $y = x^+$ 를 대입할 수 있다. 이를 대입해서 전개하면 다음과 같다.

f(x^+) \leq f(x) + \nabla f(x)^T(x^+-x) + \frac{L}{2}||x^+-x||^2

f(x^+) \leq f(x) + \nabla f(x)^T(x - t\nabla f(x)-x) + \frac{L}{2}||x - t\nabla f(x)-x||^2

f(x^+) \leq f(x) - t\nabla f(x)^T(\nabla f(x)) + \frac{L}{2}||t\nabla f(x)||^2

f(x^+) \leq f(x) - t||\nabla f(x)||^2 + \frac{Lt^2}{2}||\nabla f(x)||^2

f(x^+) \leq f(x) - t(1 - \frac{Lt}{2})||\nabla f(x)||^2

여기에서 고정된 스텝 사이즈는 $t \leq \frac{1}{L}$ 이기 때문에, $\frac{Lt}{2} \leq \frac{1}{2}$ 가 된다. 따라서 다음과 같이 정리가 가능하다.

f(x^+) \leq f(x) - \frac{t}{2}||\nabla f(x)||^2 \quad (6)

다음으로, 함수 $f$ 의 볼록성에 의한 제약조건을 사용해야 한다. 함수 $f$ 는 볼록함수이기 때문에 다음과 같은 1차 미분의 특성을 만족한다.

f(y) \leq f(x) + \nabla f(x)^T(y-x)

이 식에서 $y = x^*$ 라고 하면, 다음과 같이 정리된다.

f(x^*) \leq f(x) + \nabla f(x)^T(x^* - x)

f(x^*) - \nabla f(x)^T(x^* - x) \leq f(x)

f(x) \geq f(x^*) + \nabla f(x)^T(x-x^*)

이 볼록성을 식 (6)에 대입애서 정리해보면 다음과 같다.

f(x^+) \leq f(x) - \frac{t}{2}||\nabla f(x)||^2

f(x^+) \leq f(x^*) + \nabla f(x)^T(x-x^*) - \frac{t}{2}||\nabla f(x)||^2

식 변형을 위해, 좌변을 $\frac{1}{2t}$ 로 묶고, 묶인 식 내부에서 $||x - x^*||^2$ 를 더하고 뺸다.

f(x^+) \leq f(x^*) + \\\frac{1}{2t}(||x - x^*||^2 - ||x - x^*||^2 - t^2 || \nabla f(x)||^2 + 2t \nabla f(x)^T(x - x^*))

이 식을 정리하면 다음과 같다.

f(x^+) \leq f(x^*) + \\\frac{1}{2t}(||x - x^*||^2 - (x-x^*)^T(x-x^*) - t^2 \nabla f(x)^T\nabla f(x) + 2t \nabla f(x)^T(x - x^*))

f(x^+) \leq f(x^*) + \\\frac{1}{2t}(||x - x^*||^2 - [(x-x^*)^T(x-x^*) - 2t \nabla f(x)^T(x - x^*) + t^2 \nabla f(x)^T\nabla f(x) ])

아래 식을 자세히 보면, 중괄호 ( $[]$ ) 내부의 식이, 2차 식의 꼴로 나타내져 있는 것을 볼 수 있다. 따라서, 이차 식의 인수분해를 사용해서 어떤 두 식의 곱으로 변형할 수 있다.

f(x^+) \leq f(x^*) + \\\frac{1}{2t}(||x - x^*||^2 - [(x - t\nabla f(x)^T-x^*)^T(x - t\nabla f(x)^T - x^*)])

f(x^+) \leq f(x^*) + \frac{1}{2t}(||x - x^*||^2 - ||(x - t\nabla f(x)^T-x^*)||^2)

이 식에서 $x - t\nabla f(x)^T$ 부분은 경사 하강법의 한 번의 반복을 정의하는 공식인 $x^+ = x - t\nabla f(x)$ 에 따라서 $x^+$ 로 치환할 수 있다.

f(x^+) - f(x^*) \leq \frac{1}{2t}(||x - x^*||^2 - ||(x^+-x^*)||^2)

이 식은 특정 반복 시점 (e.g., $1, 2, \dots, k$ ) 의 위치 ( $x^+$ ) 와 최적 해 ( $x^*$ ) 의 차이를 모델링하고 있다. 이제 첫 번째 반복 시점 부터 $k$ 번째 반복 시점까지의 모든 시점에서의 차이를 더해서, 경사 하강법의 반복을 모델링하자.

\sum_{i=1}^k f(x^{(i)}) - f(x^*) \leq \sum_{i=1}^k \frac{1}{2t}(||x^{(i - 1)} - x^*||^2 - ||(x^{(i)}-x^*)||^2)

이 식의 좌변을 전개해보면, $(x^{(i)}-x^*)$ 가 다음 반복의 $(x^{(i-1)}-x^*)$ 에 의해서 소거되는 것을 볼 수 있다. 따라서 최종적으로 다음과 같은 식이 남게된다.

\sum_{i=1}^k f(x^{(i)}) - f(x^*) \leq \frac{1}{2t}(||x^{(0)} - x^*||^2 - ||(x^{k}-x^*)||^2)

이 식에서, $||(x^{k}-x^*)||^2$ 부분은 노름의 정의에 따라 항상 양수이고, 빼기 연산이 수행되고 있기 떄문에, 제거되어도 부등식은 유효하다. 따라서 다음과 같이 식을 표현할 수 있다.

\sum_{i=1}^k f(x^{(i)}) - f(x^*) \leq \frac{1}{2t}(||x^{(0)} - x^*||^2)

마지막으로, 양 변을 $\frac{1}{k}$ 로 나누어, 좌변을 정리하자.

\frac{1}{k}\sum_{i=1}^k f(x^{(i)}) - f(x^*) \leq \frac{1}{k}\times\frac{1}{2t}(||x^{(0)} - x^*||^2)

또한, $f(x^{(i)})$ 는 한 방향으로 이동하는 동안 $i$ 값이 커져도 절대로 증가하지 않는 함수이기 때문에, 다음 부등식이 성립한다.

\frac{1}{k}\sum_{i=1}^k f(x^{(i)}) - f(x^*) \ge \frac{1}{k}\sum_{i=1}^k f(x^{(k)}) - f(x^*)

\frac{1}{k}\sum_{i=1}^k f(x^{(k)}) - f(x^*) = f(x^{(k)}) - f(x^*)

따라서, 식을 정리하면 증명이 완료된다.

f(x^{(k)}) - f(x^*) \le \frac{1}{2tk}(||x^{(0)} - x^*||^2)

4. Inequality of L-smooth and $\mu$ -strongly convex

다음으로, $\mu$ -강한 볼록이 추가적으로 가정된 손실 함수에 대한 경사 하강법의 수렴률을 살펴보기 이전에, 수렴률 증명을 위한 하나의 부등식을 먼저 살펴보자. 함수 $f$ 가 L-매끄러우면서 $\mu$ -강한 볼록하다면, 다음 부등식을 만족한다.

\frac{1}{2\mu}||\nabla f(x)||^2 \ge f(x) - f^* \ge \frac{\mu}{2}||x - x^*||^2

4.1 증명

이를 증명하기 위해서 먼저 $\mu$ -강한 볼록의 정의에서 시작하자. 아래의 식은 우리가 이전 글에서 살펴본 $\mu$ -강한 볼록의 정의와는 다르지만, 동일한 의미를 가지는 부등식이다.

f(y) \ge f(x) + \nabla f(x)^T(y-x) + \frac{\mu}{2}||x - y||^2

이 식의 $y$ 를 $x$ 로, $x$ 를 $x^*$ 로 치환해보자.

f(x) \ge f(x^*) + \nabla f(x^*)^T(x-x^*) + \frac{\mu}{2}||x^* - x||^2

이 식에서 $\nabla f(x^*)$ 은 $0$ 이 되는데, 그 이유는 함수 $f$ 는 강한 볼록이기 떄문에 하나의 최소 값을 가진다. 변수의 정의에 따라 $x^*$ 는 최소 값의 $x$ 값을 나타내므로, $0$ 이 된다. 따라서, 다음과 같이 부등식을 간소화할 수 있다.

f(x) \ge f(x^*) + \frac{\mu}{2}||x^* - x||^2

위의 부등식에 따라서 우변이 증명되었다. 다음으로 좌변을 증명해보자. 좌변의 증명도 마찬가지로 $\mu$ -강한 볼록의 정의에서 출발한다.

f(y) \ge f(x) + \nabla f(x)^T(y-x) + \frac{\mu}{2}||x - y||^2

이 부등식에서 좌변을 최소화 하는 $y$ 값은 $x^*$ 이 된다. 마찬가지로, 우변을 최소화 하는 $y$ 는 우변이 이차식이므로 다음과 같이 계산된다.

\frac{\mu}{2}(||x - y||^2 - \frac{2}{\mu}\nabla f(x)^T(x-y) + \frac{2}{\mu}f(x))

완전 제곱식을 만들기 위해, $\frac{1}{\mu^2}||\nabla f(x)||^2$ 를 더하고 뺀다.

\frac{\mu}{2}(||x - y||^2 - \frac{2}{\mu}\nabla f(x)^T(x-y) + \frac{1}{\mu^2}||\nabla f(x)||^2 + \frac{2}{\mu}f(x) - \frac{1}{\mu^2}||\nabla f(x)||^2)

\frac{\mu}{2}(||x - y - \frac{1}{\mu} \nabla f(x)||^2 + \frac{2}{\mu}f(x) - \frac{1}{\mu^2}||\nabla f(x)||^2)

제곱 항 이하의 항은 $y$ 에 대해서 독립이므로, $y$ 는 $x - \frac{1}{\mu}||\nabla f(x)||$ 일 때 최소가 된다. 따라서 우변의 $y$ 에 $x - \frac{1}{\mu}||\nabla f(x)||$ 를 대입하면 최종적으로 식이 다음과 같이 구성된다.

f(x^*) \ge f(x) - \frac{1}{2\mu}||\nabla f(x)||^2

따라서 부등식이 모두 증명되었다.

5. Convergence analysis: L-smooth and $\mu$ -strongly convex

이제 실제로 간단한 L-매끄러움과 $\mu$ -강한 볼록이 가정된 함수 $f$ 에 대한 경사 하강법의 수렴률을 증명해보자. 먼저 결론부터 살펴보면, 경사 하강법은 고정된 스텝 사이즈 ( $t$ ) 가 $t \leq \frac{2}{\mu + L}$ 일 때 다음을 만족한다.

f(x^{(k)}) - f(x^*) \leq c^k\frac{L}{2}||x^{(0)} - x^*||^2

따라서, $O(c^k)$ 의 수렴률을 가진다.

5.1 증명

증명은 먼저, L-매끄러움의 정의에서 시작한다.

f(y) \le f(x) + \nabla f(x)^T(y-x) + \frac{L}{2}||y - x||^2

경사 하강법의 정의에 따라 현재 위치 $x$ 에서 다음 위치 $x^+ = x - t\nabla f(x)$ 로 진행한다고 가정하고 $y$ 에 $x^+$ 를 대입하자.

f(x^+) \leq f(x) + \nabla f(x)^T(x^+-x) + \frac{L}{2}||x^+-x||^2

f(x^+) \leq f(x) + \nabla f(x)^T(x - t\nabla f(x)-x) + \frac{L}{2}||x - t\nabla f(x)-x||^2

f(x^+) \leq f(x) - t\nabla f(x)^T(\nabla f(x)) + \frac{L}{2}||t\nabla f(x)||^2

f(x^+) \leq f(x) - t||\nabla f(x)||^2 + \frac{Lt^2}{2}||\nabla f(x)||^2

이 식을 $t$ 에 대해서 미분해보면, $t$ 가 $\frac{1}{L}$ 일 때 $0$ 이 되어서 최소가 된다. 따라서, $t$ 에 $\frac{1}{L}$ 를 대입한다.

f(x^+) \leq f(x) - \frac{1}{2L}||\nabla f(x)||^2

이 식에서 양 변에 $f(x^*)$ 를 뺀다.

f(x^+) - f(x^*) \leq f(x) - f(x^*) - \frac{1}{2L}||\nabla f(x)||^2

이제 섹션 4에서 살펴보았던 부등식을 적용할 수 있다.

f(x) - f^* \ge \frac{1}{2\mu}||\nabla f(x)||^2

2\mu(f(x) - f(x^*)) \ge || \nabla f(x)||^2

적용하면 다음과 같은 식이 유도된다.

f(x^+) - f(x^*) \leq f(x) - f(x^*) - \frac{\mu}{L}(f(x) - f(x^*))

f(x^+) - f(x^*) \leq (1 - \frac{\mu}{L})(f(x) - f(x^*))

$1 - \frac{\mu}{L}$ 를 $c$ 라고 정의하면 다음과 같다.

f(x^+) - f(x^*) \leq c(f(x) - f(x^*))

섹션 3에서와 마찬가지로 이 식은 특정 시점에 대한 함수 값 차이를 모델링하고 있기 때문에, 여러 반복을 모델링하는 식으로 변형해보다. 위의 부등식을 보면, 하나의 반복 이후에는 이전 반복의 오차보다 $c$ 에 비례해서 줄어드는 규칙성이 있음을 알 수 있다. 즉, $k$ 번의 반복 이후에는 다음과 같은 부등식이 된다.

f(x^+) - f(x^*) \leq c^k(f(x^{(0)})) - f(x^*))

이제, 마지막으로 $f(x) - f(x^*)$ 를 정리하면 된다. 이 정리는 다음과 같다. 먼저 함수 $f$ 가 L-매끄러우므로, 섹션 2의 이차 상한 식을 사용할 수 있다. 아래 식은 섹션 2의 식을 약간 수정하여 반대 방향으로 나타내고 있다. 하지만, 여전히 식은 성립한다. 반대 방향으로 서술된 이유는 단순히 계산의 편의성 떄문임에 주의하자.

f(y) \leq f(x) +\nabla f(x)^T(y-x) + \frac{L}{2}||y-x||^2

여기에 $x$ 는 $x^*$ , $y$ 는 $x^{(0)}$ 를 대입한다.

f(x^{(0)}) \leq f(x^*) +\nabla f(x^*)^T(x^{(0)}-x^*) + \frac{L}{2}||x^{(0)}-x^*||^2

$f$ 가 강한 볼록이므로, $f(x^*)$ 는 $0$ 이 된다. 따라서, 다음과 같이 간소화된다.

f(x^{(0)}) \leq f(x^*) +\frac{L}{2}||x^{(0)}-x^*||^2

이를 정리하면,

f(x^{(0)}) - f(x^*) \leq \frac{L}{2}||x^{(0)}-x^*||^2

이 되고, 이를 $f(x^+) - f(x^*) \leq c^k(f(x^{(0)})) - f(x^*))$ 에 적용하면 증명이 완료된다.

f(x^{(k)}) - f(x^*) \leq c^k\frac{L}{2}||x^{(0)} - x^*||^2

6. Conclusion

본 글에서는 L-매끄러움과 볼록성이 가정된 손실 함수를 가진 경사 하강법의 수렴률을 분석하였다. 다음 글에서는 확률적 경사 하강법의 수렴률 증명에 대해 알아보자.

정승우

이전 포스트

Convergence Analysis: Gradient Descent

수렴률 분석

1. Introduction

2. Quadratic upper bound on L-smooth function

2.1 증명

3. Convergence analysis: L-smooth and convex

3.1 증명

4. Inequality of L-smooth and $\mu$ -strongly convex

4.1 증명

5. Convergence analysis: L-smooth and $\mu$ -strongly convex

5.1 증명

6. Conclusion

Convergence Analysis: Background

0개의 댓글

Convergence Analysis: Gradient Descent

수렴률 분석

1. Introduction

2. Quadratic upper bound on L-smooth function

2.1 증명

3. Convergence analysis: L-smooth and convex

3.1 증명

4. Inequality of L-smooth and μ\muμ-strongly convex

4.1 증명

5. Convergence analysis: L-smooth and μ\muμ-strongly convex

5.1 증명

6. Conclusion

Convergence Analysis: Background

0개의 댓글

4. Inequality of L-smooth and $\mu$ -strongly convex

5. Convergence analysis: L-smooth and $\mu$ -strongly convex