7.138 수렴 속도와 계산 복잡도의 상충 관계

1. 상충 관계의 본질

최적화 알고리즘의 설계에서 수렴 속도(convergence rate)와 반복당 계산 복잡도(per-iteration computational complexity)는 근본적인 상충 관계를 갖는다. 고차 도함수 정보를 활용하면 수렴 차수가 높아지지만, 해당 정보의 계산과 처리 비용이 증가한다. 총 계산 비용은 반복 횟수와 반복당 비용의 곱으로 결정되므로, 최적의 알고리즘 선택은 두 요소의 균형에 의존한다.

2. 차 방법과 2차 방법의 비교

2.1 차 방법 (그래디언트 기반)

반복당 비용: $O(n)$ (그래디언트 계산 및 벡터 연산)
저장량: $O(n)$
수렴 차수: 선형 (경사 하강법), 가속 선형 (모멘텀, 네스테로프)
$\epsilon$ -정확도까지 반복 횟수: $O(\kappa \log(1/\epsilon))$ 또는 $O(\sqrt{\kappa}\log(1/\epsilon))$

2.2 차 방법 (뉴턴법)

반복당 비용: $O(n^3)$ (헤시안 계산 및 선형 시스템 해법)
저장량: $O(n^2)$
수렴 차수: 이차
$\epsilon$ -정확도까지 반복 횟수: $O(\log\log(1/\epsilon))$

2.3 준뉴턴법 (중간)

반복당 비용: $O(n^2)$ (BFGS), $O(mn)$ (L-BFGS, $m \ll n$ )
저장량: $O(n^2)$ (BFGS), $O(mn)$ (L-BFGS)
수렴 차수: 초선형
$\epsilon$ -정확도까지 반복 횟수: $O(\log\log(1/\epsilon))$ 근방

3. 총 계산 비용의 분석

$\epsilon$ -정확도를 달성하기 위한 총 부동 소수점 연산(FLOP) 수를 비교한다.

방법	반복 횟수	반복당 비용	총 비용
경사 하강법	$O(\kappa\log\frac{1}{\epsilon})$	$O(n)$	$O(\kappa n\log\frac{1}{\epsilon})$
L-BFGS	$O(\log\log\frac{1}{\epsilon}) \sim O(\sqrt{\kappa})$	$O(mn)$	$O(mn\sqrt{\kappa})$ 근방
뉴턴법	$O(\log\log\frac{1}{\epsilon})$	$O(n^3)$	$O(n^3\log\log\frac{1}{\epsilon})$

소규모 문제( $n$ 작음)에서는 뉴턴법의 적은 반복 횟수가 반복당 높은 비용을 보상하여 가장 효율적이다. 대규모 문제( $n$ 큼)에서는 반복당 비용 $O(n^3)$ 이 과도하므로 1차 방법이나 L-BFGS가 선호된다.

4. 문제 규모에 따른 최적 전략

4.1 소규모 ( $n < 100$ )

뉴턴법 또는 BFGS가 가장 효율적이다. 헤시안의 계산과 $O(n^3)$ 선형 시스템 해법의 비용이 관리 가능하며, 이차 또는 초선형 수렴에 의해 5~20회 반복으로 기계 정밀도 수준의 수렴을 달성한다. 로봇 역기구학, 소규모 파라미터 추정이 이에 해당한다.

4.2 중규모 ( $100 < n < 10{,}000$ )

L-BFGS가 최적의 절충을 제공한다. $O(mn)$ 의 반복당 비용과 초선형 수렴의 결합이 효율적이다. 궤적 최적화, 센서 캘리브레이션이 이 범주에 속한다.

4.3 대규모 ( $n > 10{,}000$ )

1차 방법(경사 하강법, SGD, Adam)이 필수적이다. 반복당 $O(n)$ 의 비용만이 허용 가능하며, 선형 수렴의 느린 후기 수렴은 조기 종료(early stopping)나 요구 정밀도의 완화로 대응한다. 심층 신경망의 학습, 대규모 강화 학습이 이에 해당한다.

4.4 대규모 희소 문제

문제 구조에 희소성이 있으면, 2차 방법의 비용이 $O(n^3)$ 에서 현저히 감소한다. SLAM 백엔드의 희소 촐레스키 분해, 궤적 최적화의 밴드 구조 활용 등이 대표적이다. 이 경우 수만 개의 변수를 갖는 문제에서도 2차 방법이 실용적이다.

5. 확률적 최적화에서의 상충 관계

미니 배치 SGD에서 배치 크기 $B$ 의 증가는 그래디언트 추정의 분산을 $1/B$ 로 줄이지만, 반복당 비용은 $B$ 에 비례하여 증가한다. 임계 배치 크기를 넘으면 추가 샘플의 한계 이득이 감소하므로, 배치 크기와 반복 횟수의 최적 균형이 문제에 의존한다.

6. 실시간 로봇 시스템에서의 결정

실시간 제어에서는 제어 주기 $T_{ctrl}$ (통상 1~10ms) 내에 해를 산출해야 하므로, 총 반복 횟수가 $T_{ctrl}$ / (반복당 시간)으로 제한된다. 이 제한 내에서 해의 품질을 최대화하려면 다음의 전략이 적용된다.

반복당 비용이 낮은 알고리즘: 더 많은 반복을 수행하여 수렴에 가까워진다.
반복당 비용이 높지만 수렴이 빠른 알고리즘: 적은 반복으로 양호한 해를 산출한다.
웜 스타트: 이전 해를 초기점으로 활용하여 필요 반복 횟수를 최소화한다.

7. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Bottou, L., Curtis, F. E., & Nocedal, J. (2018). “Optimization Methods for Large-Scale Machine Learning.” SIAM Review, 60(2), 223–311.
Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Springer.

version: 1.0