NeurIPS 2025 Oral, Best Paper Runner-up
문제 순서를 미리 알면 실수는 얼마나 줄까
온라인 학습에서 문제 순서를 미리 보면 최적 실수가 리틀스톤 차원 d에서 √d 수준까지 줄 수 있고, 그보다 더 줄지는 않음을 보인 NeurIPS 2025 최우수 논문 차점작
온라인 학습 이론
3줄 요약
- 온라인 학습(online learning)에서 적대자가 문제를 하나씩 골라 내면, 학습자가 피할 수 없는 최적 실수 횟수는 가설 클래스의 리틀스톤 차원(Littlestone dimension) \(d\)와 정확히 같다. 레이블 없는 문제 순서를 처음에 모두 알려 주는 트랜스덕티브 온라인 학습(transductive online learning)에서 이 값이 얼마나 작아질 수 있는지는 1995년부터 열린 문제였고, 답은 \(\Omega(\log d)\)와 \(\tfrac23 d\) 사이라고만 알려져 있었다.
- 이 논문은 리틀스톤 차원이 \(d\)인 어떤 클래스에서도 학습자가 \(\Omega(\sqrt d)\)번은 틀리고(정리 6.1), \(O(\sqrt d)\)번 안에 배울 수 있는 클래스가 \(d\)마다 있음을 보인다(정리 8.1). 미리 보는 이득은 많아야 제곱근만큼이고, 그만큼은 실제로 얻을 수 있다.
- 하한은 실수를 아껴 쓰며 후보 함수를 천천히 줄이는 적대자로, 상한은 경로 밖 레이블에 맞히기 쉬운 희소 부호를 심은 무작위 클래스와 둘로 나뉘는 전문가 알고리즘으로 얻었다. 상수와 계산 효율, 정의역 크기는 아직 열려 있다.
선정 이유
NeurIPS 2025 최우수 논문상 차점작(Best Paper Runner-up)이다. 심사위원회는 30년 된 열린 문제를 우아하고 빈틈없이, 결정적으로 풀었다고 평했다. 로그 수준이던 이전 하한을 지수적으로 뛰어넘었고, PAC 학습에서는 역할이 제한적인 레이블 없는 데이터가 이 설정에서는 큰 가치를 갖는다는 점을 보였다는 이유다.
블로그의 연구 여지 지도에서 ’온라인 학습 이론’은 LLM 중심 주제를 뺀 109개 주제 중 2위다.
- 전후로 아는 것이 달라졌나. 달라졌다. 답이 놓일 수 있는 범위가 \(\log d\)에서 \(\tfrac23 d\)까지 지수적으로 넓었는데, 상수 배 안으로 좁혀졌다.
- 새 질문을 여는가, 닫는가. 닫는다. 남은 질문은 정확한 상수, 계산 효율, 정의역 크기처럼 결과를 다듬는 쪽으로 옮겨 갔다(3장).
- 일반화될 근거가 있나. 제한적이다. 이진 레이블, 실현 가능(realizable), 결정론적 학습자의 결과이고, 무작위 학습자로 넓혀도 두 배 안에서 성립한다(1.1절 각주). 잡음이 있는 불가지(agnostic) 설정은 다루지 않는다.
- 증거가 주장만큼 강한가. 증명이므로 강하다. 네 리뷰어 모두 수락(6점 만점에 6, 5, 5, 6)했지만, 두 리뷰어는 분야에 익숙하지 않다며 확신도를 5점 만점에 1과 2로 적었다.
왜 중요한가
PAC 모형에서 레이블 없는 데이터는 최악의 경우 도움이 되지 않는다. VC 하한의 어려운 분포는 학습자가 주변 분포를 아는 경우로도 만들 수 있어서, 레이블 없는 표본을 마음껏 뽑아도 빨라지지 않는다(1장). 이 논문은 같은 질문을 온라인 학습에서 던진다.
온라인 학습에는 분포가 없다. 적대자와 학습자가 \(n\)라운드 동안 게임을 한다(게임 1). 매 라운드 적대자가 점 \(x_t\)를 내면 학습자가 레이블 \(\hat y_t\)를 예측하고, 적대자가 정답 \(y_t\)를 알려 준다. 적대자는 마음대로 답하되, 지금까지 준 정답과 모두 맞는 함수가 클래스 \(\mathcal H\)에 하나는 남아야 한다. 최악의 적대자를 상대로 최선의 학습자가 내는 실수 수를 최적 실수 한계(optimal mistake bound)라 하고, Littlestone(1987)이 이 값이 리틀스톤 차원과 같음을 보였다(정리 5.7).
리틀스톤 차원은 트리로 정의된다. 노드마다 점이 붙은 완전 이진 트리에서, 함수는 뿌리부터 자기 레이블이 가리키는 쪽 자식으로 내려가며 경로 하나를 그린다(논문 그림 1). 깊이 \(d-1\)인 트리의 모든 경로를 클래스의 함수들이 빠짐없이 그리면 리틀스톤 차원이 \(d\) 이상이다(정의 5.6). 표준 게임의 적대자는 이 트리를 따라 내려가며 깊이마다 학습자가 고르지 않은 쪽을 정답으로 주면 되므로, 학습자를 \(d\)번 틀리게 한다.
트랜스덕티브 온라인 학습(게임 2)은 한 가지만 다르다. 적대자가 게임 전에 문제 수열 \(x_1,\dots,x_n\)을 정해 학습자에게 모두 보여 준다. 레이블은 여전히 예측을 본 뒤에 적대자가 고른다. 시험지는 미리 받았지만 채점은 한 문제씩 받는 셈이고, 레이블 없는 데이터에 미리 접근하는 상황을 옮긴 설정이다.
(가) 표준 온라인 게임
(나) 트랜스덕티브 게임
이득은 어디서 올까. 적대자가 수열을 처음에 정해 두되 학습자에게는 하나씩만 보여 주는 중간 설정은 표준 게임보다 쉽지 않다. 결정론적 학습자가 상대라면 적대자가 표준 게임을 미리 돌려 보고 그때 나온 수열을 그대로 내면 되기 때문이다(1.2절 각주). 트랜스덕티브 게임의 이득은 적대자가 묶여서가 아니라 학습자가 순서를 미리 알아서 생긴다.
미리 알아도 소용없는 클래스도 있다. \(d\)개 점 위의 모든 함수를 모은 클래스라면 적대자는 점을 하나씩 내며 매번 반대로 답해 \(d\)번 틀리게 한다. 그래서 질문은 미리 보기가 가장 잘 통하는 클래스에서 실수가 얼마나 줄어드느냐다. 하한은 \(\Omega(\log\log d)\)(1995), \(\Omega(\sqrt{\log d})\)(1997), \(\Omega(\log d)\)(Hanneke, Moran, Shafer 2023)로 조금씩 올라왔지만, 상한은 Ben-David 외(1997)의 \(\tfrac23 d\)에서 멈춰 있었다(1.2절). 두 값 사이가 지수적으로 벌어져 있었다.
핵심 아이디어
직관: 실수와 정보의 줄다리기
적대자가 실수를 강요할 때마다 학습자는 정답 함수에 대해 무언가를 배운다. 적대자는 실수 한 번에 새는 정보를 아껴야 하고, 학습자는 틀리지 않으면서 정보를 모아야 한다. 2.4절은 이 줄다리기를 짧은 셈으로 보여 준다. 트리의 경로 밖 레이블을 확률 \(2^{-k}\)로만 1로 두는 클래스를 생각하자. 적대자가 잎 \(d/2k\)개를 내면 어떤 레이블을 붙여도 그 잎들이 모두 경로 밖에 있으면서 레이블과 맞는 함수가 남으므로, 잎마다 실수를 강요할 수 있다. 위쪽 \(k/2\)층을 너비 우선으로 내면 경로 위 노드마다 실수를 강요할 수 있다. 그래서 적대자는 대략 \(d/k + k\)번 틀리게 하고, 이 값은 \(k=\sqrt d\)일 때 가장 작다. 논문은 이 클래스를 \(O(\sqrt d)\)번 안에 배우는 학습자가 있음을 증명한다.
(가) 리틀스톤 트리와 경로
(나) 희소 부호를 심은 클래스
방법 1: 실수를 아껴 쓰는 적대자
적대자는 매 라운드 남은 후보, 곧 버전 공간(version space) 가운데 다음 문제에 1이라고 답하는 비율 \(r_t\)를 본다. 비율이 \([\varepsilon, 1-\varepsilon]\) 안에 있을 때만 예측의 반대를 정답으로 줘서 실수를 강요하고, 그렇지 않으면 다수 쪽 레이블을 준다(알고리즘 1). 무조건 강요하지 않는 것은, 1이라고 답하는 후보가 하나뿐인 문제에서 1을 정답으로 주면 후보가 그 하나만 남아 더는 실수를 강요할 수 없기 때문이다(2.2절). 이 규칙이면 실수 없는 라운드에서 후보가 \(1-\varepsilon\) 이상, 실수한 라운드에서도 \(\varepsilon\) 이상 남는다.
(가) 하한: 실수를 아껴 쓰는 적대자
(나) 상한: 맞히기 쉬운 부호
수열은 강요할 실수를 \(M=\sqrt d/10\)번으로 정해 두고, 실수가 갈라 놓는 경우를 모두 따라가며 경우마다 남은 후보가 함께 지나는 경로 위 노드를 넣어 짠다(알고리즘 2). 길이는 \((d+1)2^{M+1}\)보다 짧고(주장 6.3), 어느 경우든 마지막 함수의 경로를 모두 담으니 게임이 끝나면 후보는 하나 남는다. 처음 후보는 \(2^{d}\)개 남짓이다. 후보는 실수 \(m\)번에 많아야 \(\varepsilon^m\)배로, 실수 없는 라운드 전체에서 많아야 \((1-\varepsilon)^n\)배로 준다. \(\varepsilon = 2^{-\sqrt d/2}\)로 잡으면 수열이 짧아서 \((1-\varepsilon)^n \ge 1/2\)이고(\(d\ge 800\)), 정리하면 \(1 \ge 2^{d - m\sqrt d/2}\), 곧 \(m \ge 2\sqrt d\)가 나온다(6.3절). 실수가 \(\sqrt d/10\)번 이하라는 가정과 모순이므로 어떤 학습자도 \(\sqrt d/10\)번보다 많이 틀린다.
블로그의 해석으로 정리하면, 실수를 \(M\)번 계획한 수열은 \(2^M\)에 비례해 길어지므로 \(\varepsilon\)을 \(2^{-M}\) 정도로 작게 잡아야 하고, 그러면 실수 한 번이 알려 주는 정보가 \(M\)비트 정도다. \(d\)비트를 채우려면 \(M \cdot M\)이 \(d\) 정도여야 하니 \(M\)은 \(\sqrt d\) 수준이다.
이전 증명과 갈리는 곳도 여기다. Hanneke, Moran, Shafer(2023)의 적대자는 트리 노드를 전부 너비 우선으로 보여 줬는데, 저자들의 심사 답변에 따르면 그런 적대자에게는 \(O(\log d)\)번만 틀리는 학습자가 있다. 맞히기 쉬운 노드도 정보를 조금씩 흘리기 때문이다. 새 적대자는 맞히기 어려운 노드만 골라 보이고, 문턱 \(\varepsilon\)도 하나로 고정해 증명이 단순해졌다.
방법 2: 맞히기 쉬운 희소 부호
상한은 2.3.1절의 관찰에서 시작한다. 0부터 63 사이의 수를 한 자리씩 맞힐 때, 이진 부호 6자리는 적대자가 6번 다 틀리게 할 수 있지만 64자리 원-핫(one-hot) 부호는 늘 0을 찍으면 많아야 한 번 틀린다. 얻는 정보는 같은 6비트다.
저자들은 이 원리를 리틀스톤 트리에 심는다(보조정리 8.2). 함수의 경로 위 레이블은 리틀스톤 차원을 지키려고 경로대로 두고, 경로 밖 레이블은 함수와 노드마다 독립으로 확률 \(2^{-\sqrt d}\)로만 1로 둔다. 경로 밖이 모두 0인 ‘최소’ 클래스는 경로 밖 레이블이 아무 정보도 주지 않아서, 적대자가 트리를 너비 우선으로 보이며 층마다 실수를 강요할 수 있다(2.3.2절 각주). 무작위 클래스에서는 경로 밖에서 0을 볼 때마다 후보가 조금씩, 드문 1을 볼 때마다 크게 준다. 정보가 트리 전체에 퍼져 있는 셈이다.
장애물은 셋이다(2.3.3절). 적대자가 경로 위 노드를 앞쪽에 몰아 둘 수 있고, 조상보다 먼저 나온 노드는 경로 위인지 알 수 없고, 경로 밖의 드문 1도 함수마다 평균 \(2^{\Omega(d)}\)개라 다 틀릴 수는 없다. 학습자는 세 기법으로 맞선다.
- 위험 구역 줄이기(danger zone minimization). 수열의 앞 \(t_{\max}=2^{4\sqrt d}\)개 가운데 아직 경로 위일 수 있는 노드를 위험 구역으로 둔다. 한쪽 자손이 위험 구역의 3분의 1을 넘으면 그쪽 레이블을 찍고, 틀리면 그 자손들이 모두 경로 밖으로 드러나 위험 구역이 3분의 2 이하로 준다. 이런 실수는 \(O(\sqrt d)\)번이다(2.3.4절).
- 전문가 나누기(splitting experts). 경로 위인지 모르는 노드에서 전문가를 둘로 나눠 한쪽은 경로 위, 다른 쪽은 밖이라고 가정한다. 가정이 모두 맞는 전문가가 늘 하나 있다. 곱셈 가중치(multiplicative weights)로 틀린 전문가의 가중치를 반으로 줄이고, 나뉠 때는 반씩 나눈다(알고리즘 5).
- Halving으로 넘어가기. 앞 \(t_{\max}\)개의 정답을 다 보거나 경로 밖의 1을 \(3\sqrt d\)개 보면 남은 후보가 \(2^{2\sqrt d}\)개 이하가 된다(주장 8.6, 보조정리 8.2). 그다음은 남은 후보의 다수결을 따르는 Halving으로 많아야 \(2\sqrt d\)번 더 틀린다(사실 A.1).
모두 더하면 가정이 모두 맞는 전문가는 \(24\sqrt d\)번 이하로 틀리고(주장 8.7), 실수 한 번에 가중치가 많아야 4분의 1로 주므로 그 전문가의 가중치는 \(2^{-48\sqrt d}\) 이상 남는다. 학습자가 틀릴 때마다 전체 가중치가 일정 비율 이상 줄어드니 학습자의 실수도 \(O(\sqrt d)\)번에 묶인다(주장 8.8).
수식: 정리의 정확한 형태
\(M_{\mathrm{std}}(\mathcal H, n)\)과 \(M_{\mathrm{tr}}(\mathcal H, n)\)을 길이 \(n\)인 두 게임의 미니맥스 실수, \(n\)에 대한 상한을 \(M_{\mathrm{std}}(\mathcal H)\), \(M_{\mathrm{tr}}(\mathcal H)\)라 하자(5.4절). 언제나 \(M_{\mathrm{tr}}(\mathcal H) \le M_{\mathrm{std}}(\mathcal H) = d\)이다.
정리 6.1 (하한). 어떤 상수 \(d_0\)가 있어서, 리틀스톤 차원이 \(d \ge d_0\)인 모든 클래스에 대해 길이 \(n = O(d\cdot 2^{\sqrt d})\)인 수열과 그 수열을 쓰는 적대자가 있고, 어떤 학습자도 \(\sqrt d/10\)번 이상 틀린다. 수열 길이 \(n\)이 정해져 있으면 다음이 성립한다.
\[ M_{\mathrm{tr}}(\mathcal H, n) \;\ge\; \min\Big\{\frac{\sqrt d}{10},\; \big\lfloor \log_2 (n+1) \big\rfloor\Big\} \]
정리 8.1 (상한). \(d \ge 43\)인 모든 정수 \(d\)에 대해, 정의역 크기가 \(2^d-1\)이고 리틀스톤 차원이 \(d\)인 클래스가 있어서 모든 \(n\)에서 다음이 성립한다.
\[ M_{\mathrm{tr}}(\mathcal H, n) \le 48\sqrt d, \qquad M_{\mathrm{std}}(\mathcal H, n) = \min\{n, d\} \]
둘을 합친 것이 주 정리(정리 1.1)다. 따로 정리 7.2는 실수 \(M\)번을 강요하는 수열이 있으면 길이 \(2^M-1\)로 충분하고, 이 길이가 꼭 필요한 클래스도 있음을 보인다. 하한의 수열이 \(2^{\sqrt d}\) 규모로 긴 데는 이유가 있다.
결과 해설
간격이 상수 배 안으로 닫혔다. 아래 그림 (가)는 상수를 떼고 그린 증가 속도다. 2023년까지는 답이 보라 띠 어디쯤인지 몰랐고, \(d\)가 백만이면 띠는 20에서 약 67만까지 걸쳤다. 이 논문은 답을 \(\sqrt d\), 곧 천 근처로 정했다(정리 1.1). PAC 학습에서는 두 설정의 표본 복잡도가 비슷한데, 온라인 학습에서는 제곱만큼 벌어진다(초록).
작은 클래스에서 풀어 보면. (나)는 보조정리 8.2처럼 만든 작은 무작위 클래스에서 두 게임의 값을 미니맥스 재귀로 정확히 푼 것이다. 표준 게임은 늘 \(d\)다(정리 5.7). 트랜스덕티브 게임은 가장 나쁜 수열의 값으로, \(d=5\)와 6에서 모두 \(d-1\)이었다. 적대자가 노드를 전부 너비 우선으로 보이면 \(d=6\)에서 40개 중 37개가 4로 더 작아졌다. 노드를 다 보여 주면 적대자가 손해를 본다는 저자들의 설명과 맞는다. 블로그의 해석으로는, \(d\)가 작으면 \(\sqrt d\)와 \(d\)가 별로 다르지 않으니 이득이 한 번에 그치는 것도 이상하지 않다.
(가) 그동안의 간격과 새 답
(나) 작은 클래스에서 직접 푼 값
의심해볼 점
- 상수가 크다. 상한 \(48\sqrt d\)는 \(d>2304\)에서야 \(d\)보다 작아지고, 하한의 증명은 \(d \ge 800\)을 쓴다(6.3절). 정리의 숫자로 이득이 드러나는 것은 리틀스톤 차원이 수천을 넘는 클래스에서다. 답이 \((\alpha + o(1))\sqrt d\) 꼴인지, 그렇다면 \(\alpha\)가 얼마인지는 저자들도 열린 문제로 남겼다(3장).
- 존재 증명이다. 상한의 클래스는 확률적 방법(probabilistic method)으로 있다는 것만 보였다. 임계값이나 반공간 같은 자연스러운 클래스가 미리 보기로 얼마나 득을 보는지는 알 수 없다.
- 정의역이 크다. 상한의 클래스는 점이 \(2^d-1\)개다. 점이 \(\mathrm{poly}(d)\)개일 때도 \(O(\sqrt d)\)가 가능한지는 모른다(3장).
리뷰어들이 짚은 점
영역 의장은 리뷰어 모두가 기여와 서술을 높이 샀다고 적었다.
- 정의역 크기. 희소 부호에는 큰 정의역이 필요해 보인다는 리뷰어의 질문에, 저자들은 날카로운 지적이라며 답을 모른다고 했고 최종본의 열린 질문에 넣었다.
- 계산 효율. 논문은 학습자를 임의의 함수로 두고 계산을 따지지 않는다(5.4절). 전문가 수가 지수적 이상으로 불어나지 않느냐는 질문에, 저자들은 전문가 수가 클래스 크기를 넘지 않아 실행 시간이 \(\mathrm{poly}(2^d, n)\)이라고 답하고, \(\mathrm{poly}(d, n)\) 시간 학습자는 열린 문제로 남겼다.
- 무엇이 막혀 있었나. 결정적 통찰을 묻자 저자들은 구체적인 예를 만지작거린 결과라고 답했다. \(\Omega(d)\)도 \(O(\log d)\)도 그럴듯해 보였고, 지금도 \(\sqrt d\)에 대한 간결한 직관은 없다고 했다.
- 곱셈 가중치 단계의 셈. 주장 8.8의 증명은 학습자가 틀릴 때마다 가중치 합이 절반 이하로 준다고 적지만 근거가 없다. 블로그의 해석으로는 표준 가중 다수결의 셈으로 4분의 3까지만 보장되어 상수 48이 115 남짓으로 커지지만, \(O(\sqrt d)\)라는 결론은 그대로다. OpenReview 최종본(주장 D.8)도 같은 문장이다.
계보
- 출발점. Littlestone(1987)이 온라인 학습의 최적 실수를 리틀스톤 차원으로 특징지었다. Ben-David, Kushilevitz, Mansour(EuroCOLT 1995, Machine Learning 1997)가 트랜스덕티브 설정을 ’최악 수열 오프라인 모형’이라는 이름으로 처음 정의하고 앞의 하한과 상한, 트리 계수(rank)를 쓴 특징화를 냈다(7장).
- 효율 쪽 갈래. Kakade, Kalai(NIPS 2005)의 오라클 기반 효율적 학습자를 Cesa-Bianchi, Shamir(2013)가 개선했다.
- 직전 연구. Hanneke, Moran, Shafer(NeurIPS 2023)는 수열 길이 \(n\)에 따른 최적 실수가 \(n\), \(\Theta(\log n)\), \(\Theta(1)\) 셋 중 하나라는 삼분법을 보이고 하한을 \(\Omega(\log d)\)로 올렸다. 이 논문의 하한은 그 아이디어 일부를 이어받았다. Hanneke, Raman, Shaeiri, Subedi(NeurIPS 2024)는 레이블 수가 무한한 다중 클래스로 넓혔다.
- 이어진 연구. 2026년 10월 기준 Semantic Scholar에 잡힌 인용은 3편이다. Attias, Hanneke, Ramaswami(NeurIPS 2025)는 클래스를 ERM 오라클로만 볼 수 있을 때 실수와 오라클 호출 수의 교환 관계를 다뤘다. Hanneke, Wang(arXiv 2605.30479)은 보편 학습(universal learning) 관점의 다중 클래스 설정을, Livni, Singla(arXiv 2608.29503)는 레이블 붙은 수열의 무작위 일부를 미리 보여 주는 모형을 다뤘다.
열린 질문
- 정의역 크기와 실수의 교환. 점이 \(\mathrm{poly}(d)\)개뿐인 정의역에서도 \(O(\sqrt d)\)번 안에 배울 수 있는 클래스가 있을까. 정의역이 작아질수록 최적 실수는 어떻게 커질까.
- 효율적인 학습자. \(\mathrm{poly}(d, n)\) 시간이나 적은 수의 ERM 오라클 호출만으로 \(O(\sqrt d)\) 실수에 이르는 학습자가 있을까.
- 상수와 자연스러운 클래스. 최적 실수의 정확한 상수는 얼마일까. 그리고 리틀스톤 차원이 크지 않은 클래스나 자연스러운 클래스에서는 미리 보기의 이득이 언제부터 의미 있게 커질까.
이해 확인
1. 적대자가 문제 수열을 게임 전에 정해 두기만 하고, 학습자에게는 표준 게임처럼 한 번에 하나씩만 보여 준다고 하자. 리틀스톤 차원이 d인 클래스에서 결정론적 학습자의 최적 실수는?
- 표준 게임과 같은 d다
- 트랜스덕티브 게임과 같은 Θ(√d) 수준이다
- 적대자가 순서를 바꿀 수 없으니 log d 수준으로 준다
- 한 번뿐이다. 수열이 고정되면 학습자가 정답 함수를 곧바로 좁힐 수 있다
적대자는 그 학습자와 표준 게임을 미리 돌려 보고 그때 나온 수열과 정답을 그대로 쓰면 된다. 학습자가 보는 것이 두 게임에서 같으니 d번 틀린다(1.2절 각주).
2. 하한 증명의 적대자는 실수를 강요할 수 있어도 1이라고 답하는 후보의 비율이 ε보다 작거나 1-ε보다 크면 강요하지 않는다. 왜인가?
- 그런 문제에서 실수를 강요하면 지금까지의 정답과 모두 맞는 함수가 남지 않을 수 있어서
- 실수를 강요할 때마다 수열을 늘려야 하므로, 수열 길이를 d 안으로 묶으려고
- 소수 쪽 정답을 주면 후보가 한꺼번에 크게 줄어, 남은 게임에서 강요할 실수가 거의 사라져서
- 비율이 쏠린 문제에서는 학습자가 늘 소수 쪽을 찍으니 다수 쪽 정답만 줘도 실수가 나서
비율이 극단적인 문제에서 실수를 강요하면 정답이 소수 쪽이 되어 후보가 그 소수만 남고, 후보가 하나뿐이면 더는 실수를 강요할 수 없다(2.2절). 문턱 규칙 덕분에 실수 한 번이 주는 정보가 많아야 log(1/ε)비트로 묶인다.
3. 상한의 클래스는 경로 밖 레이블을 작은 확률 2^(-√d)로만 1로 둔다. 모두 0으로 두면 안 되는 까닭은?
- 함수들이 경로 밖에서 모두 같아져 리틀스톤 차원이 d보다 작아지므로
- 경로 밖 레이블이 정보를 주지 않아, 적대자가 트리를 너비 우선으로 보이며 d번 틀리게 할 수 있으므로
- 경로 밖 노드가 쓸모없어져 정의역이 사실상 d개 점으로 줄어들므로
- Halving으로 넘어갈 때 남는 후보가 2^(2√d)개보다 많아지므로
경로 위 레이블은 그대로이니 모두 0이어도 리틀스톤 차원은 d다. 하지만 경로 밖 0은 모든 함수가 공유해 배울 것이 없고, 적대자는 층마다 경로 위 노드에서 실수를 강요한다(2.3.2절). 드문 1이 섞여야 0을 맞히며 조금씩, 1을 틀리며 크게 배운다.
논문 정보
- 제목: Optimal Mistake Bounds for Transductive Online Learning
- 저자: Zachary Chase (Kent State University), Steve Hanneke (Purdue University), Shay Moran (Technion, Google Research), Jonathan Shafer (MIT)
- 학회: NeurIPS 2025 Oral, Best Paper Runner-up
- 링크: arXiv 2512.12567, OpenReview, NeurIPS 2025 수상작 발표