기술 요약: 온라인 실현 가능한 회귀와 ReLU 네트워크에 대한 응용

문제 정의

본 논문은 표적 가설 $h^* \in \mathcal{H}$가 레이블을 완벽하게 생성하는 실현 가능성(realizability) 조건이 주어지는 상황에서, 확률적 가정이나 마진 조건이 부과되지 않는 적대적 설정에서의 **실현 가능한 온라인 회귀(realizable online regression)**를 조사한다. 핵심 문제는 실현 가능성(실제 타겟 가설의 존재)이 호라이즌 프리(horizon-free, 유한한) 누적 손실 상한을 함의하는 조건이 무엇인지, 그리고 이 상한을 결정하는 복잡도 파라미터가 무엇인지 결정하는 것이다.

저자들은 이는 단순한 클래스인 퍼셉트론조차 마진 가정이 없으면 무한한 실수(mistake) 상한을 가질 수 있는 온라인 분류 문제와 대조된다고 설명한다. 그러나 회귀의 경우, 유사한 분류 문제가 학습 불가능하더라도, 메트릭 형태의 손실 함수 하에서는 실현 가능성이 유한한 총 손실을 강제할 수 있다. 본 연구는 학습자가 가설 공간의 큰 간격에도 불구하고 미미한 손실로 중간 레이블을 예측할 수 있는 퇴화적인 시나리오를 방지하기 위해 필요한 조건인 **근사 삼각 부등식(approximate triangle inequality, 근사 의사 메트릭)**을 만족하는 손실 함수 $\ell$에 초점을 맞춘다.

방법론

본 논문은 minimax 실현 가능 누적 손실을 특징짓는 추상적 차원인 **스케일드 리틀스톤 차원(scaled Littlestone dimension, $D_{\text{onl}}$)**을 상한으로 구하기 위해 **일반적 포텐셜 방법(generic potential method)**을 도입한다.

엔트로피 포텐셜 프레임워크

$D_{\text{onl}}$을 직접 계산하는 것은 어려울 수 있으므로, 저자들은 유도된 sup 의사 메트릭 $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$에 대한 가설 클래스 $\mathcal{H}$의 커버링 수(covering numbers)를 기반으로 한 Dudley 유형의 엔트로피 적분을 사용하여 이를 상한으로 묶는다.

1. 엔트로피 포텐셜 정의: 유한한 지름을 가진 가설 클래스 $\mathcal{H}$에 대해, 엔트로피 포텐셜은 다음과 같이 정의된다:
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   여기서 $N(\mathcal{H}, \varepsilon)$은 $d_\ell$에 대한 $\mathcal{H}$의 $\varepsilon$-커버링 수이다.

2. 주요 정리: 저자들은 임의의 $c$-근사 의사 메트릭 손실에 대해, 스케일드 리틀스톤 차원이 엔트로피 포텐셜에 의해 상한이 됨을 증명한다:
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   증명은 실현 가능한 스케일드 리틀스톤 트리 상에서의 브랜치 바운드(branch bound) 논증을 활용한다. 각 노드에서의 버전 공간(version spaces)을 분석함으로써, 근사 삼각 부등식이 $\varepsilon < \gamma/(2c)$일 때 노드의 자식들 사이에서 간격 $\gamma$를 가지며 커버를 분할하도록 강제함을 보여준다. 다양한 스케일에 걸쳐 이 "커버 분할(cover splitting)"을 적분함으로써, 임의의 브랜치를 따르는 총 간격을 $\Phi(\mathcal{H})$에 비례하도록 제한하여 $\Phi(\mathcal{H})$에 의해 전체 간격을 제한한다.

3. 시사점: 만약 $\mathcal{H}$가 다항식 커버링 수(즉, $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$)를 가진다면, $\Phi(\mathcal{H}) < \infty$이며, 이는 호라이즌 프리 실현 가능한 누적 손실 상한을 의미한다.

주요 기여 및 결과

1. $\ell_q$ 손실 하의 리프시츠(Lipschitz) 회귀

저자들은 $[-1, 1]^d$ 상의 $L$-리프시츠 함수 클래스 $\mathcal{H}_L$을 손실 함수 $\ell_q(y, y') = |y - y'|^q$에 적용한다. 이들은 $q$와 차원 $d$ 사이의 관계에 기초한 **날카로운 상전이(sharp phase transition)**를 확립한다:

• 학습 가능한 영역 ($q > d$): 엔트로피 포텐셜이 유한하다. minimax 실현 가능한 누적 손실은 $\Theta_{d,q}(L^d)$이다. 저자들은 리프시츠 엔벨로프(하한 및 상한)를 기반으로 하여 이 상한을 달성하는 **효율적인 결정론적 프로퍼 알고리즘(efficient deterministic proper algorithm)**을 제공한다.
• 학습 불가능한 영역 ($q \leq d$): 엔트로피 포텐셜이 발산한다.
  • $q < d$인 경우, minimax 누적 손실은 호라이즌 $T$에 따라 다항식적으로 증가한다.
  • $q = d$인 경우, 손실은 $T$에 따라 로그 함수적으로 증가한다.
  • 두 경우 모두 $D_{\text{onl}}(\mathcal{H}_L) = \infty$이다.
• 결국의 학습 가능성: $\ell(y,y)=0$을 만족하는 임의의 연속 함수 $\ell$에 대해, 저자들은 $L$-리프시츠 함수의 경우 총 누적 손실의 유한 여부와 관계없이 순시 손실 $\ell(\hat{y}_t, y_t)$가 $t \to \infty$로서 0으로 수렴함을 보여준다.

2. 유계 $k$-ReLU 네트워크

본 논문은 제곱 손실 하의 유계 $k$-ReLU 네트워크 클래스 $\mathcal{H}_{k,d}$($[-1, 1]^d$ 상의 유계 가중치를 가진 $k$개의 ReLU 합)를 연구한다.

• 회귀 vs 분류의 분리:
  • 분류: 0/1 손실 하에서, $\mathcal{H}_{2,1}$(두 개의 은닉 뉴런, 1차원 입력)에 대해 실현 가능한 온라인 분류는 불가능하다. 유계 가중치를 사용하더라도 리틀스톤 차원이 무한하기 때문이다.
  • 회귀: 제곱 손실 하에서, 실현 가능한 온라인 회귀는 유한한 총 손실을 허용한다.
• 상한:
  • 누적 손실이 $O(k^2 \log^4 d) = \tilde{O}(k^2)$인 (정보 이론적) 온라인 알고리즘이 존재한다.
  • 단일 ReLU ($k=1$)의 경우, 차원 $d$와 독립적으로 $O(1)$의 누적 손실을 갖는 효율적인 알고리즘이 존재한다.
• 하한:
  • $\Omega(k^2 \log(d/k^2))$의 하한이 증명되어, $k$와 $\log d$에 대한 의존성이 필요함을 보여준다.
• 계산 복잡도:
  • Gap-ETH 가설을 가정할 때, 저자들은 $k \geq 2$인 경우 누적 손실 $e^{o(d)}$를 달성하면서 시간 복잡도가 $d$에 대한 다항식인 효율적인 프로퍼(proper) 온라인 학습자의 존재를 부정한다. 이는 유한한 손실이 정보 이론적으로는 가능할지라도, 프로퍼 학습자를 통해 이를 효율적으로 계산하는 것은 어려울 가능성이 높음을 시사한다.

3. 심층 네트워크로의 일반화

결과는 깊이 $L$, 너비 $k$인 네트워크로 확장된다. minimax 실현 가능한 누적 제곱 손실은 $\tilde{O}(k^L)$로 나타나며, $d/k^L \to \infty$일 때 $\Omega(k^L \log(d/k^L))$의 일치하는 하한을 갖는다.

의의 및 주장

본 논문은 **실현 가능성(realizability)**이 에이전틱(agnostic) 설정과 비교했을 때 온라인 학습의 지형을 근본적으로 변화시킨다고 주장한다. 구체적으로:

1. 복잡도 척도로서의 메트릭 엔트로피: 저자들은 근사 의사 메트릭 하의 실현 가능한 회귀에 대해, 메트릭 엔트로피(엔트로피 포텐셜 $\Phi$를 통한)가 $D_{\text{onl}}$의 충분하고 종종 타이트한 대리 지표임을 확립한다. 이는 추상적인 차원이 다루기 힘든 상황에서 학습 가능성을 분석할 수 있는 구체적이고 계산 가능한 도구를 제공한다.
2. 비매개변수 회귀의 상전이: 본 연구는 비매개변수 리프시츠 회귀가 호라이즌 프리(horizon-free)가 되는 정확한 조건($q > d$)을 식별하며, 이는 분류 또는 $q \leq d$인 회귀의 학습 불가능성과 극명하게 대조된다.
3. 신경망 학습 가능성: 본 논문은 ReLU 네트워크에 대한 분류와 회귀 사이의 극명한 분리를 강조한다. 유계 ReLU 네트워크는 분류 설정에서는 학습이 불가능(무한한 리틀스톤 차원)하지만, 회귀 설정에서는 유한한 누적 손실을 허용한다. 그러나 이러한 학습 가능성에는 주의 사항이 따른다: $k \geq 2$인 경우, 프로퍼 학습자를 통해 이를 효율적으로 달성하는 것은 계산적으로 난해할 가능성이 높다.
4. 한계: 저자들은 엔트로피 포텐셜 상한이 항상 타이트하지는 않다는 점을 언급한다. 즉, $\Phi(\mathcal{H}) = \infty$이지만 $D_{\text{onl}}(\mathcal{H}) < \infty$인 클래스가 존재한다. 따라서 $\Phi$는 완전한 특징화보다는 명시적인 상한 대리물(upper bound surrogate) 역할을 한다.

본 연구는 최근의 온라인 차원 이론[2]의 진보에 의존하며, 순차적 체이닝(sequential chaining) 대신 실현 가능성 가정을 활용하여 표준 커버를 사용하여 확률 과정(stochastic processes)의 기법(Dudley 적분)을 적대적 온라인 설정에 적응시켰다.