Does Order Matter : Connecting The Law of Robustness to Robust Generalization

기술적 요약: "순서가 중요한가: 강건성 법칙과 강건한 일반화의 연결"

문제 정의
본 논문은 Bubek과 Selke [2]가 제기한 근본적인 미해결 문제, 즉 **강건성 법칙(Law of Robustness)**과 강건한 일반화(Robust Generalization) 사이의 명시적인 이론적 연결을 확립하는 문제를 다룹니다.

• 강건성 법칙: 모델이 데이터를 강건하게 보간(즉, 작은 리프시츠 상수(Lipschitz constant)를 가짐)하기 위해서는 과매개변수화(overparameterization)가 필수적임을 상정합니다. 구체적으로, Wu 등 [30]은 임의의 유계 지지 분포(bounded-support distributions)에 대해, 리프시츠 상수 $L$을 달성하려면 $L = \Omega(n^{1/d})$를 만족해야 함을 입증했습니다 (여기서 $n$은 샘플 크기, $d$는 차원).
• 강건한 일반화: 작은 강건한 훈련 손실(robust training loss)이 작은 강건한 테스트 손실(robust test loss)을 보장하는지에 관한 문제입니다.
• 간극: 두 개념 모두 리프시츠 연속성과 과매개변수화에 의존하지만, 기존 문헌에서는 이를 별개로 취급해 왔습니다. 저자들은 이 두 개념을 통일하기 위해 라데마허 복잡도(Rademacher complexity)와 같은 통계적 학습 기법을 사용하여, 전역적 강건성 보장에서 국소적 일반화 경계로 넘어갈 때 요구되는 리프시츠 상수의 "순서(order)"가 변하는지를 결정하고자 합니다.

방법론
저자들은 강건한 손실 클래스의 복잡도에 대한 경계를 도출하기 위해 라데마처 복잡도에 기반한 프레임워크를 채택합니다. 방법론은 전역적(global) 및 국소적(local)이라는 두 가지 뚜렷한 척도로 진행됩니다.

1. 전역적 분석 (분포 불변 - Distribution-Free):

   • 저자들은 먼저 과적합(깨끗한 훈련 오차)과 강건한 일반화 간극 사이의 관계를 확립합니다.
   • 전체 강건한 손실 클래스 $\mathcal{L}_\rho$의 복잡도를 묶기 위해 **전역 라데마처 복잡도(Global Rademacher Complexity)**를 활용합니다.
   • 극단적 포락선(extremal envelopes, $f^+_\rho$ 및 $f^-_\rho$)을 통해 강건한 손실 클래스를 깨끗한 손실 클래스와 연결하고 수축 성질(contraction properties)을 사용하여, 특정 일반화 간극을 유지하는 데 필요한 복잡도의 하한을 도출합니다.

2. 국소적 분석 (저오차 영역 - Low-Error Regime):

   • 전역적 복잡도는 보간 영역(경험적 오차가 0에 가까운 영역)에서 너무 거칠다는 점을 인식하여, 저자들은 **국소 라데마처 복잡도(Local Rademacher Complexity)**로 전환합니다. 이는 작은 경험적 위험을 가진 함수들의 부분 클래스에 대한 복잡도를 측정합니다.
   • 그래프 이론과 맥셰인의 확장 정리(McShane's extension theorem)를 사용하여 유계 리프시츠 함수 클래스의 **메트릭 엔트로피(metric entropy, 피복 수)**를 바운딩합니다.
   • 다항식 메트릭 엔트로피가 라데마처 복잡도의 국소적 하한을 함의함을 증명합니다.
   • 마지막으로, 이 바운드를 역전시켜 작은 강건한 모집단 위험(population risk)과 작은 깨끗한 경험적 위험을 동시에 만족하는 함수들이 가져야 할 리프시츠 상수 $L$의 하한을 도출합니다.

주요 기여 및 결과

1. 전역 척도 일관성:
   전역 설정에서 저자들은 리프시츠 바운드의 순서가 기존의 분포 불변 결과와 일치함을 확인했습니다. 구체적으로, 강건한 손실 클래스의 복잡도는 리프시츠 상수 $L$이 반드시 $\Omega(n^{1/d})$의 척도로 스케일링되어야 함을 의미합니다. 이는 전역적 관점에서 섭동 반경 $\rho$에 관계없이 성립합니다.

2. 국소 척도 발산 ("순서가 중요하다"는 발견):
   국소적 설정(낮은 경험적 오차를 가진 함수들의 부분 집합)에서, 저자들은 리프시츠 바운드의 순서가 변한다는 것을 보여줍니다. $L$에 대한 하한은 다음 요소들에 의존합니다:

   • 섭동 반경 $\rho$.
   • 국소 집중 항(localized concentration term) $\sqrt{r/n}$ (여기서 $r$은 함수 클래스의 $L_2$ 반지름).
   • 비가역적 노이즈 $\sigma^2$와 경험적 오차 사이의 간극.

   국소 영역에서 도출된 $L$의 하한식은 다음과 같습니다:
   $$L = \Omega\left( \frac{\Delta_{n,r,\delta}}{\rho \sqrt{\sigma^2 - \varepsilon} + D n^{-1/d} + \rho \sqrt{\Delta_{n,r,\delta}}} \right)$$
   여기 $\Delta_{n,r,\delta}$는 국소적 초과 마진(localized excess margin)을 나타냅니다. 이 결과는 학습 알고리즘이 선택한 특정 함수들(낮은 오차를 가진 함수들)로 "줌 인(zoom in)"할 때, 섭동 반경 $\rho$와 데이터의 집중도가 필요한 매끄러움(리프시츠 상수)을 결정하는 데 결정적인 역할을 한다는 것을 나타냅니다.

3. 이론적 가교:
   본 논문은 비자명한(non-trivial) 강건한 일반화 간극이 손실 클래스의 복잡도(및 리프시츠 상수)에 대한 하한을 강제한다는 것을 보여줌으로써, 강건성 법칙과 강건한 일반화 사이를 명시적으로 연결합니다.

의의 및 주장
본 논문은 제목의 질문인 "순서가 중요한가?"에 대해 **"얼마나 자세히 들여다보느냐에 따라 다르다!"**라는 미묘한 긍정의 답변을 제시하며 답합니다.

• 전역적 관점: 리프시츠 상수의 순위는 안정적($\Omega(n^{1/d})$)이며, 이는 거대한 "함수의 바다" 속에서 섭동은 차수의 관점에서 볼 때 감지하기 어렵다는 것을 시사합니다.
• 국소적 관점: 최적화 알고리즘에 의해 도달 가능한 특정 함수 부분 집합(낮은 경험적 위험)에 집중할 때, 그 순서가 변합니다. 리프시츠 상수는 섭동 반경과 데이터의 집중도에 의해 직접적인 영향을 받습니다.

저자들은 이 연구를 최악의 경우 강건성(worst-case robustness)과 강건한 일반화를 통합하기 위한 단계로 규정합니다. 저자들은 현재의 결과가 제곱 손실(square-loss) 및 유계 지지 분포에 국한되어 있음을 언급하며, 이러한 발견을 교차 엔트로피 손실(분류) 및 브레그만 발산(Bregman divergences)으로 확장하는 것이 필요한 향후 방향임을 밝힙니다. 이 작업은 새로운 실험적 아키텍처를 제안하는 것이 아니라, 적대적 환경에서 모델 크기, 매끄러움, 그리고 일반화 사이의 트레이드오프를 바라보는 이론적 렌즈를 제공합니다.