기술 요약: 최소 제곱 회귀를 위한 조기 종료 기반 정규화

문제 정의

본 논문은 머신러닝 모델, 특히 선형 회귀의 맥락에서 조기 종료(early stopping)가 파라미터와 일반화 능력에 미치는 영향을 이해하는 근본적인 과제를 다룹니다. 조기 종료는 널리 사용되는 정규화 기법임에도 불구하고, 임의의 학습률 스케줄과 데이터 분포를 가진 이산적 풀-배치 경사 하강법(full-batch gradient descent) 환경에서의 이론적 특성은 여전히 불완전하게 이해되어 있습니다.

기존 문헌은 종종 연속 시간 경사 흐름(gradient flow) 역학이나 특징 행렬(feature matrix)에 대한 가우시안 가정을 기반으로 중단 규칙을 도출합니다. 이러한 접근 방식은 실질적인 비정적 학습률 스케줄 하에서의 최적 중단 시간을 정량화하거나, 이산적 설정에서 발생하는 현상인 "그로킹(grokking)"(모델이 초기에는 과적합되었다가 나중에 일반화되는 현상)을 설명하는 데 한계가 있습니다. 또한, 조기 종료와 명시적 $L_2$ (릿지) 정규화 사이의 정확한 관계, 그리고 조기 종료가 유익한 경우와 해로운 경우에 대한 조건은 제한적인 분포 가정 없이 더욱 엄밀하게 규명될 필요가 있습니다.

방법론

저자들은 연속 시간 경사 흐름 근사를 피하고, 풀-배치 경사 하강법의 이산 역학을 분석합니다. 핵심적인 방법론적 기여는 $k$ 단계 이후의 파라미터 궤적 $\beta_k$에 대한 **정확하고 폐쇄적인 형태의 표현식(closed-form expressions)**을 도출하는 것입니다.

주요 방법론적 구성 요소는 다음과 같습니다:

1. 스펙트럼 분해(Spectral Decomposition): 분석은 샘플 공분산 행렬 $X^T X$의 고유 기저(eigenbasis)에서 수행됩니다. 저자들은 특정 고유값 $\zeta$에 대한 학습률 스케줄 $\{\eta_i\}$의 누적 효과를 포착하는 함수 $\phi(k; \zeta, \{\eta_i\})$를 정의합니다.
2. 정확한 궤적 공식화: 이 함수를 사용하여, 어떤 데이터 행렬 $X$, 어떤 학습률 스케줄, 어떤 초기화에 대해서도 성립하는 $\beta_k$의 명시적 공식을 도출합니다. 이 공식은 오차를 초기화 및 실제 파라미터에 의존하는 신호 성분과 잔차에 의존하는 노이즈 성분으로 분해합니다.
3. 리스크 분석: 기대 초과 리스크(expected excess risk)는 노이중에 대한 기댓값을 취하고, 구형 사전 확률(spherical prior) 가정하에 신호에 대한 기댓값을 취함으로써 분석됩니다. 저자들은 임계점을 식별하기 위해 (가정 2를 통해 $k$를 연속 변수로 취급하여) 반복 횟수에 대해 리스크를 미분합니다.
4. 동등성 증명: 조기 종료된 솔루션과 일반화된 릿지 회귀 문제의 솔루션 사이의 수학적 동등성을 확립하여, 정규화 효과를 직접 비교할 수 있게 합니다.

주요 기여

1. 이산 역학을 위한 정확한 궤적

본 논문은 커널 릿지 회귀 문제에 대한 $\beta_k$의 이산 역학에 대한 정확한 공식을 제공하는 **명제 1(Proposition 1)**을 제시합니다. 기존 연구들과 달리, 이 공식은 데이터 분포, 학습률 스케줄 또는 노이즈 분포에 대해 어떠한 가정도 하지 않습니다. 저자들은 상수, 다항식 감소, 상수 가산 감소, 지수 감소를 포함한 다양한 일반적 스케줄에 대한 $\phi$의 폐쇄형 표현식을 제공합니다 (감마 함수 및 $q$-포호카머 심볼 사용).

2. 일반화된 릿지 회귀와의 동등성

저자들은 **정리 5(Theorem 5)**를 통해, 일반적인 데이터와 임의의 학습률 스케줄에 대해 $T$번의 반복 후 얻은 조기 종료 솔루션($\mu=0$일 때)이 일반화된 릿지 회귀 문제의 최소 노름(minimum norm) 솔루션과 동일함을 증명합니다. 이 일반화된 문제에서의 정규화 행렬 $D$는 학습률 스케줄과 중단 시간에 의해 명시적으로 결정됩니다.
반대로, **정리 6(Theorem 6)**은 샘플 공분산 행렬의 각 고유 공간에 서로 다른 학습률을 할당할 수 있다면, 표준 릿지 회귀 문제의 모든 최소 노름 솔루션을 조기 종료를 통해 얻을 수 있음을 보여줍니다.

3. 유익함과 해로움의 조건

조기 종료가 일반화 성능을 향상시키는 조건에 대한 충분 조건을 설정합니다:

• 정리 8 (유익함): 조기 종료가 유익하려면 학습률 스케줄이 "수축 계수(shrinkage factor)" $\phi(k)$를 충분히 빠르게 감소시켜서, $\phi(k)/\phi(0)$의 극한값이 신호 대 잡음비(SNR)에 의해 결정되는 임계값보다 작아야 합니다. 이는 상수, 선형 감소 및 누적 스텝 사이즈가 발산하는 기타 스케줄에서 성립합니다.
• 정리 9 (유익하지 않음): 조기 종료가 유익하지 않은 경우는 학습률이 너무 빠르게 감소하여(예: 빠른 다항식 또는 지수 감소) 수축 계수가 필요한 임계치에 도달하지 못하는 경우입니다. 이 경우 훈련을 계속할수록 리스크가 계속 감소합니다.
• 정리 10 (릿지 정규화): 이러한 조건들은 명시적 릿지 정규화($\mu > 0$)가 존재하는 경우로 확장됩니다. 핵심 발견은 만약 명시적 정규화 파라미터 $\mu$가 임계값($\mu \ge \tau^2 / (n\sigma^2)$)을 초과하면, 조기 종료가 추가적인 이득을 제공하지 않는다는 것입니다.

4. 최적 중단 시간 추정치

저자들은 누적 학습률 예산 $\sum \eta_i$를 기반으로 한 최적 중단 시간 추정치(식 31)를 제안합니다. 이 추정치는 대표적인 고유값에 대한 신호와 노이즈의 최적 균형을 수축 계수에 대응시킴으로써 도출되었습니다. 이 추정치는 임의의 스펙트럼과 비정적 학습률을 가진 이산 역학에서도 작동하도록 하여, 그래디언트 플로 regime에서의 기존 결과들을 일반화합니다.

결과 및 경험적 검증

이론적 결과는 합성 데이터와 실제 데이터셋(MNIST 및 CIFAR10)에 대한 실험을 통해 검증되었습니다.

• 추정치의 정확도: 제안된 중단 시간 추정치(식 31)는 다양한 학습률 스케줄(상수, 다항식, 선형, 지수, 코사인 어닐링, 랜덤)에 대해 경험적으로 관찰된 최적 중단 시간과 밀접하게 일치합니다.
• 레짐 의존성: 실험은 명시적 릿지 파라미터 $\mu$가 최적의 릿지 파라미터 $\mu^*$보다 낮을 때 조기 종료가 유익하지만, $\mu \ge \mu^*$일 때는 해롭거나 불필요해진다는 이론적 예측을 확인해 줍니다.
• 스케줄 민감도: 결과는 최적점이 발생하는 반복 횟수가 학습률 스케줄에 따라 크게 달라지지만, 학습률의 누적 예산이 최적 중단 지점을 예측하는 강력한 지표 역할을 한다는 것을 보여줍니다.
• 그로킹(Grokking): 분석에 따르면 많은 일반적인 학습률 스케줄(누적 스텝 사이즈가 발산하는 경우)에 대해 선형 모델은 "그로킹"(과적합 후 늦은 일반화)을 보이지 않습니다. 대신, 조기 종료가 최적인 전형적인 편향-분산 트레이드오프를 보여줍니다.

의의 및 주장

본 논문은 선형 회귀에서 조기 종료에 대한 비점근적이고 분포에 무관한(distribution-free) 특성을 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

1. 이론과 실제의 연결: 연속 시간 그래디언트 플로와 가우시안 가정에서 벗어남으로써, 결과가 임의의 학습률 스케줄을 가진 실질적인 이산 훈련 시나리오에 적용될 수 있게 합니다.
2. 통합적 관점: 조기 종료를 일반화된 릿지 정규화와 수학적으로 통합하여, 조기 종료의 "암묵적" 정규화가 명시적이고 데이터 의존적인 $L_2$ 페널티와 수학적으로 동일함을 보여줍니다.
3. 실용적 가이드: 실제 신호에 대한 지식을 요구하는 대신, 관찰 가능한 양들(신호 대 잡음비, 고유값 스펙트럼, 학습률 스케줄)에만 의존하는 이론적으로 근거 있는 최적 중단 시간 추정치를 제공합니다.
4. 한계 명시: 조기 종료가 언제 유익하고 언제 그렇지 않은지를 명확히 구분하며, 특히 명시적 릿지 정규화와 조기 종료 사이의 상호작 작용을 강조하고, 조기 종료를 효과 없게 만드는 특정 학습률 스케줄을 식별합니다.

저자들은 현재의 분석이 선형 모델에 국한되어 있지만, 이 프레임워크가 두 층 신경망(two-layer neural networks)과 같은 더 복잡한 모델을 이해하기 위한 토대를 제공하며, 확률적 경사 하강법(SGD) 및 적응형 최적화 방법론으로 확장할 수 있는 미래 방향을 제시한다고 결론짓습니다.