7.88 확률적 경사 하강법(SGD)

1. 동기와 기본 개념

다수의 기계 학습 및 로봇 학습 문제에서 목적 함수는 개별 데이터 샘플에 대한 손실의 합 또는 기대값으로 구성된다.

$f(\mathbf{x}) = \frac{1}{N}\sum_{i=1}^{N} f_i(\mathbf{x})$

여기서 $N$ 은 데이터 샘플의 수이고, $f_i(\mathbf{x})$ 는 $i$ 번째 샘플에 대한 손실 함수이다. 전체 그래디언트 $\nabla f(\mathbf{x}) = \frac{1}{N}\sum_{i=1}^{N} \nabla f_i(\mathbf{x})$ 를 계산하려면 모든 $N$ 개의 샘플에 대한 그래디언트를 합산해야 하며, $N$ 이 크면 이 계산은 과도한 비용을 요구한다.

확률적 경사 하강법(Stochastic Gradient Descent, SGD)은 전체 그래디언트 대신 무작위로 선택된 단일 샘플의 그래디언트를 사용하여 갱신을 수행한다.

$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f_{i_k}(\mathbf{x}_k)$

여기서 $i_k$ 는 $\{1, 2, \ldots, N\}$ 에서 균일하게 무작위 추출된 인덱스이다. 확률적 그래디언트 $\nabla f_{i_k}(\mathbf{x}_k)$ 는 전체 그래디언트의 비편향 추정량(unbiased estimator)이다.

$\mathbb{E}_{i_k}[\nabla f_{i_k}(\mathbf{x}_k)] = \nabla f(\mathbf{x}_k)$

2. 분산과 잡음의 영향

확률적 그래디언트의 분산은 다음과 같이 정의된다.

$\sigma^2(\mathbf{x}) = \mathbb{E}_i[\lVert \nabla f_i(\mathbf{x}) - \nabla f(\mathbf{x}) \rVert^2]$

이 분산은 확률적 경사 하강법의 수렴 거동에 근본적인 영향을 미친다. 분산이 클수록 갱신의 잡음이 크며, 최적점 주위에서의 진동이 심해진다.

고정 학습률 $\alpha$ 를 사용하는 SGD는 최적점에 정확히 수렴하지 않고, 최적점 주위의 반경 $O(\alpha \sigma^2)$ 근방에서 진동한다. 정확한 수렴을 달성하려면 학습률을 점진적으로 감소시켜야 한다.

3. 수렴 조건과 학습률 스케줄

3.1 로빈스-먼로 조건

확률적 근사 이론에 의하면, SGD가 최적점으로 수렴하기 위한 학습률 $\{\alpha_k\}$ 의 충분 조건은 다음과 같다.

$\sum_{k=0}^{\infty} \alpha_k = \infty, \quad \sum_{k=0}^{\infty} \alpha_k^2 < \infty$

첫 번째 조건은 임의의 초기점에서 최적점까지 도달할 수 있을 만큼 충분한 누적 갱신량을 보장하고, 두 번째 조건은 잡음에 의한 분산이 소멸함을 보장한다. $\alpha_k = \alpha_0/k$ , $\alpha_k = \alpha_0/\sqrt{k}$ 등의 스케줄이 이 조건을 만족한다.

3.2 볼록 함수에서의 수렴률

$f$ 가 볼록이고 $\nabla f$ 가 리프시츠 연속이며 확률적 그래디언트의 분산이 유계( $\sigma^2 < \infty$ )일 때, $\alpha_k = O(1/\sqrt{k})$ 에서 다음의 수렴률이 성립한다.

$\mathbb{E}[f(\bar{\mathbf{x}}_k)] - f(\mathbf{x}^*) = O\left(\frac{1}{\sqrt{k}}\right)$

여기서 $\bar{\mathbf{x}}_k = \frac{1}{k}\sum_{j=1}^{k}\mathbf{x}_j$ 는 반복열의 평균이다. 이 $O(1/\sqrt{k})$ 수렴률은 결정론적 경사 하강법의 $O(1/k)$ 보다 느리지만, 반복당 계산 비용이 $1/N$ 로 축소되므로 총 계산량 관점에서 이득이 있다.

3.3 강볼록 함수에서의 수렴률

$f$ 가 $\mu$ -강볼록이면, $\alpha_k = O(1/k)$ 에서 다음이 성립한다.

$\mathbb{E}[f(\mathbf{x}_k)] - f(\mathbf{x}^*) = O\left(\frac{1}{k}\right)$

4. SGD의 계산 효율성

SGD의 핵심 이점은 반복당 계산 비용이 데이터 수 $N$ 에 무관하게 $O(n)$ 이라는 점이다. $N$ 이 매우 큰 대규모 학습 문제에서, 결정론적 경사 하강법이 한 번의 그래디언트 계산에 $O(Nn)$ 을 소비하는 동안 SGD는 $N$ 회의 갱신을 수행할 수 있다. 초기 수렴 단계에서 SGD는 결정론적 방법보다 현저히 빠른 목적 함수 감소를 보이며, 이는 대규모 데이터셋에서의 핵심적 이점이다.

5. 분산 감소 기법

SGD의 수렴률이 결정론적 경사 하강법보다 느린 근본 원인은 그래디언트 추정의 분산에 있다. 이를 개선하기 위한 분산 감소(variance reduction) 기법이 연구되어 왔다.

5.1 SVRG(Stochastic Variance Reduced Gradient)

주기적으로 전체 그래디언트 $\tilde{\mathbf{g}} = \nabla f(\tilde{\mathbf{x}})$ 를 계산하고, 확률적 그래디언트를 다음과 같이 수정한다.

$\mathbf{g}_k = \nabla f_{i_k}(\mathbf{x}_k) - \nabla f_{i_k}(\tilde{\mathbf{x}}) + \tilde{\mathbf{g}}$

이 수정된 그래디언트는 여전히 비편향이지만, 분산이 $\mathbf{x}_k$ 가 $\tilde{\mathbf{x}}$ 에 가까워질수록 감소하는 특성을 갖는다.

5.2 SAG/SAGA

과거 샘플의 그래디언트를 저장하고 점진적으로 갱신하여 분산을 감소시키는 방법이다. $O(N)$ 의 추가 메모리를 요구하지만, 강볼록 문제에서 선형 수렴률을 달성할 수 있다.

6. 로봇 공학에서의 응용

강화 학습의 정책 그래디언트: 로봇 제어 정책의 학습에서 보상 함수의 그래디언트를 몬테카를로 시뮬레이션으로 추정하며, 이는 본질적으로 확률적 그래디언트이다. 정책 그래디언트 방법(REINFORCE 등)에서 SGD의 이론적 기반이 직접적으로 적용된다.

온라인 적응: 로봇이 센서 데이터를 실시간으로 수신하면서 모델 파라미터를 갱신하는 온라인 학습에서, 각 관측치에 대해 SGD 갱신을 수행한다. 환경의 비정상성(non-stationarity)에 대응하기 위해 고정 학습률 또는 매우 느린 감쇠를 사용하기도 한다.

시뮬레이션 기반 학습: 물리 시뮬레이터를 통해 로봇 궤적을 생성하고, 궤적 샘플에 대한 확률적 그래디언트로 파라미터를 갱신하는 방법이 시뮬레이션-실물 전이(sim-to-real transfer)에 활용된다.

7. 참고 문헌

Robbins, H., & Monro, S. (1951). “A Stochastic Approximation Method.” The Annals of Mathematical Statistics, 22(3), 400–407.
Bottou, L. (2010). “Large-Scale Machine Learning with Stochastic Gradient Descent.” Proceedings of COMPSTAT, 177–186.
Bottou, L., Curtis, F. E., & Nocedal, J. (2018). “Optimization Methods for Large-Scale Machine Learning.” SIAM Review, 60(2), 223–311.
Johnson, R., & Zhang, T. (2013). “Accelerating Stochastic Gradient Descent using Predictive Variance Reduction.” Advances in Neural Information Processing Systems (NeurIPS), 26.
Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. MIT Press.

version: 1.0