Littlestone 클래스에 대한 사적 온라인 학습 및 예측

우리는 무지한 실현 가능한 적대자(oblivious realisable adversaries) 하에서의 차분 프라이버시를 갖는 온라인 학습과 온라인 예측의 실수 경계(mistake bounds)를 연구합니다. 온라인 학습은 학습자가 각 시간 단계에서 가설을 공개하도록 요구하는 반면, 온라인 예측에서는 학습자가 가설을 공개할 필요 없이 예측만 하면 됩니다. 사적 온라인 학습에 대한 새로운 하한(lower bound)과 사적 예측에 대한 상한(upper bound)을 사용하여, 우리는 유한 Littlestone 차원 $d$를 갖는 모든 클래스에 대해 이 두 문제의 표본 복잡도(sample complexity)가 시간 지평($T$)에 따라 증가하는 인자만큼 분리됨을 보여줍니다. 먼저, 우리는 모든 $(\epsilon,\delta)$-사적 온라인 학습자가 실수 경계가 $Es{M_T}=\Omega(\frac d\epsilon\log\br{ T}^{2/3})$ 이상인 결정론적 실현 가능한 스트림(deterministic realisable stream)을 길이 $T$로 가지고 있음을 증명합니다. 특히, 이는 이전 연구[SR22,DSS24,LWY24]에서 열려 있던 범위 $1/T < \delta < 1/\log T)$ 내의 첫 번째 비자명한 하한입니다. 둘째, 우리는 Littlestone 차원 $d$를 갖는 모든 클래스에 대해, 임의의 상수 $c>0$에 대해 $T$과 독립적으로 최대 $2^{2^{cd^2}}\epsilon^{-2}\log^2(\frac{2}{\epsilon\delta})$의 기대 실수(expected mistakes)를 가지는 $(\epsilon,\delta)$-공동 사적 예측자가 존재함을 증명합니다. 따라서, 유한 Littlestone 차원을 갖는 모든 고정된 클래스의 경우 $\delta=\Theta(\frac{1}{\log T})$일 때, 사적 학습은 $\Omega(\log T)^{2/3}$의 기대 실수를 요구하는 반면, 사적 예측은 $igO(\log\log T)^2$를 허용합니다.