7.136 선형 수렴과 초선형 수렴

1. 선형 수렴의 특성

선형 수렴(linear convergence)에서 오차는 매 반복마다 일정한 비율로 감소한다.

$e_{k+1} \leq \rho \, e_k, \quad 0 < \rho < 1$

이로부터 $e_k \leq \rho^k e_0$ 이 성립하며, 오차가 기하급수적으로(exponentially) 감소한다. $\epsilon$ -정확도( $e_k < \epsilon$ )를 달성하기 위한 반복 횟수는 다음과 같다.

$k \geq \frac{\log(\epsilon / e_0)}{\log \rho} = O\left(\frac{1}{\log(1/\rho)} \log\frac{1}{\epsilon}\right)$

$\rho$ 가 1에 가까우면( $1 - \rho \ll 1$ ) $\log(1/\rho) \approx 1 - \rho$ 이므로, 필요 반복 횟수는 $O\left(\frac{1}{1-\rho}\log\frac{1}{\epsilon}\right)$ 로 증가한다.

1.1 경사 하강법의 선형 수렴

강볼록 매개변수 $\mu$ , 리프시츠 상수 $L$ 인 함수에서 고정 학습률 $\alpha = 1/L$ 의 경사 하강법은 다음의 수렴비를 갖는다.

$\rho = 1 - \frac{\mu}{L} = 1 - \frac{1}{\kappa}$

조건수 $\kappa = 100$ 이면 $\rho = 0.99$ 로, $\epsilon = 10^{-6}$ 을 달성하기 위해 약 1382회의 반복이 필요하다. $\kappa = 10$ 이면 $\rho = 0.9$ 로 약 132회이다.

1.2 모멘텀에 의한 개선

네스테로프 가속법은 강볼록 함수에서 다음의 수렴비를 달성한다.

$\rho = \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}$

$\kappa = 100$ 이면 $\rho = 0.818$ 로, 필요 반복 횟수가 약 76회로 크게 감소한다. 이 개선은 $\kappa$ 의 역수가 아닌 $\sqrt{\kappa}$ 의 역수에 비례하는 수렴비에 기인한다.

2. 초선형 수렴의 특성

초선형 수렴(superlinear convergence)에서 연속 오차의 비율이 영에 수렴한다.

$\lim_{k \to \infty} \frac{e_{k+1}}{e_k} = 0$

이는 유효 수렴비가 반복에 따라 개선됨을 의미한다. 초기에는 선형 수렴과 유사하지만, 최적해에 접근할수록 수렴이 급격히 가속된다.

2.1 차수 $p$ 의 초선형 수렴

수렴 차수 $p > 1$ 에서 $e_{k+1} \leq C e_k^p$ 이면, $p < 2$ 인 경우를 초선형 수렴이라 하기도 한다. 그러나 통상적으로 초선형 수렴은 특정 차수 $p$ 로 특성화되지 않는 경우를 포함한다. 예를 들어 $e_{k+1} \leq C_k e_k$ 에서 $C_k \to 0$ 인 경우이다.

2.2 준뉴턴법의 초선형 수렴

BFGS 방법의 초선형 수렴은 데니스-모레 조건에 의해 보장된다.

$\frac{\lVert (\mathbf{B}_k - \nabla^2 f(\mathbf{x}^*))\mathbf{d}_k \rVert}{\lVert \mathbf{d}_k \rVert} \to 0$

이 조건은 근사 헤시안이 탐색 방향에서 실제 헤시안에 수렴함을 의미하며, BFGS 갱신이 이를 자연스럽게 달성한다.

3. 선형 수렴과 초선형 수렴의 비교

반복 횟수 $k$ 에 따른 오차의 대수 도(logarithmic plot)에서, 선형 수렴은 직선(기울기 $\log\rho$ )으로, 초선형 수렴은 기울기가 점차 급해지는 곡선으로 나타난다.

$\text{선형}: \log e_k \approx k\log\rho + \log e_0 \quad (\text{직선})$

$\text{이차}: \log e_k \approx 2^k\log e_0 + \text{const.} \quad (\text{급격 감소})$

실용적 관점에서 초선형 수렴의 이점은 최적해 근방에서 현저하게 나타난다. 원거리에서는 선형 수렴과 유사한 거동을 보이다가, 최적해에 충분히 가까워지면 급속한 수렴이 발동한다. 이러한 특성은 “어떻게 시작하느냐보다 어떻게 끝나느냐“가 중요한 정밀 계산 문제에서 초선형/이차 수렴 알고리즘의 가치를 드높인다.

4. 로봇 공학에서의 실용적 의미

실시간 제어: 제한된 반복 횟수(1~5회)에서의 성능이 중요하다. 이 경우 수렴 차수보다는 초기 감소의 속도가 결정적이며, 좋은 초기 추정(웜 스타트)이 수렴 차수의 차이를 상쇄할 수 있다.

정밀 오프라인 최적화: 캘리브레이션, 번들 조정 등에서 기계 정밀도 수준의 수렴이 요구되는 경우, 초선형/이차 수렴 알고리즘이 선형 수렴에 비해 현저히 적은 반복으로 목표를 달성한다.

5. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Dennis, J. E., & Moré, J. J. (1977). “Quasi-Newton Methods, Motivation and Theory.” SIAM Review, 19(1), 46–89.
Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Springer.
Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative Solution of Nonlinear Equations in Several Variables. Academic Press.

version: 1.0