확률적 서브그래디언트법 마지막 반복점의 비최적성, 1차원에서도 남는 로그 격차 입증

기계학습 모델을 훈련하는 거의 모든 절차의 밑바닥에는 확률적 경사 하강법, 더 넓게는 확률적 서브그래디언트법이 자리한다. 매 단계에서 손실 함수의 기울기를 잡음 섞인 추정값으로 대체하고 그 방향으로 조금씩 움직이는 단순한 반복이, 거대한 신경망부터 고전적인 볼록 최적화까지 동일하게 작동한다. 그런데 이 방법을 둘러싼 이론과 실무 사이에는 좀처럼 좁혀지지 않는 간극이 하나 있다. 수렴 속도를 증명하는 정리들은 대부분 반복 과정에서 거쳐 온 모든 점의 평균을 분석 대상으로 삼는다. 정작 현장에서 학습을 멈춘 뒤 저장하고 배포하는 것은 평균이 아니라 가장 마지막에 나온 점인데도 그렇다.

평균은 알지만 마지막 점은 모른다

볼록 립시츠 목적 함수에서 평균 반복점이 1/√n 규모의 오차로 최적해에 다가간다는 사실은 오래전부터 잘 알려져 있었고, 이 속도는 이론적으로 더 줄일 수 없는 최적값이다. 문제는 마지막 점이다. Shamir와 Zhang을 비롯한 일련의 연구는 1/√n 규모의 고정 스텝을 쓸 때 마지막 점의 오차가 (log n)/√n 규모임을 보였다. 평균보다 로그 인자만큼 나쁜 셈이다. 그렇다면 이 여분의 로그는 분석이 느슨해서 생긴 군더더기인가, 아니면 마지막 점이라는 대상 자체에 내재한 본질적 한계인가. Koren과 Segal은 2020년 COLT에서 바로 이 질문을 공개 문제로 제기했고, 그 뒤로 답은 비어 있었다.

독립 잡음은 로그를 지우지만, 그것만으로는 부족하다

이 논문은 가장 단순한 무대인 1차원 볼록 립시츠 함수로 내려가 문제를 양면에서 매듭짓는다. 한쪽 면은 희소식이다. 서브그래디언트에 더해지는 잡음이 매 단계 서로 독립이고 동일한 분포를 따르며 분산이 균등하게 유계라는 가정 아래에서는, 고정 스텝을 쓴 마지막 점의 오차가 정확히 1/√n 규모로 줄어든다. 기존의 일반적 한계에 붙어 있던 로그 인자가 깨끗이 사라지는 것이다. 다른 쪽 면이 이 논문의 진짜 핵심이다. 독립·동일분포라는 가정을 빼고 분산이 균등하게 유계라는 조건만 남기면, 마지막 점의 오차는 다시 (log n)/√n 규모까지 커질 수 있음을 구체적인 구성으로 보인다. 결국 균등 유계 분산이라는 표준 가정 하나만으로는, 마지막 점이 차원이 1인 가장 단순한 경우에서조차 최적이 될 수 없다. Koren과 Segal의 공개 문제에 대한 또렷한 부정의 답이다.

단순함이 드러내는 본질

이 결과가 인상적인 까닭은 반례를 1차원에서 만들어 냈다는 데 있다. 고차원의 복잡한 기하 구조가 아니라, 잡음이 시간에 따라 어떻게 상관되어 있는가라는 구조적 조건이 마지막 점의 운명을 가른다는 사실이 군더더기 없이 드러나기 때문이다. 실무적으로 이는 마지막 점과 평균 사이의 간극이 막연한 이론적 우려가 아니라, 잡음 모델에 따라 실제로 존재하거나 사라지는 현상임을 말해 준다. 미니배치 추출이 매 단계 독립적으로 이루어진다면 마지막 점은 평균만큼 좋지만, 데이터 순서나 잡음에 시간적 상관이 끼어드는 순간 로그만큼의 손해를 각오해야 한다. 꼬리 평균이나 가중 평균 같은 보정 기법이 왜 여전히 안전한 선택으로 남는지도 같은 맥락에서 설명된다. 우리가 매일 돌리는 알고리즘의 마지막 한 걸음에 대해, 학계가 생각보다 적게 알고 있었음을 이 깔끔한 분리가 일깨운다.