일반적인 거리 손실 (Metric Losses) 에 대한 실현 가능한 Bayes-Consistency 강건성 연구

우리는 일반적 거리 손실 (general metric losses) 을 가진 실현 가능한 설정 (realizable setting) 에서 강한 보편적 Bayes-consistency 를 연구하며, $0$-$1$ 분류 (classification) 와 실수값 회귀 (real-valued regression) 를 넘어선 고전적인 특징화 (classical characterizations) 를 확장합니다 \

주어진 인스턴스 공간 $(\mathcal X,ρ)$, possibly unbounded loss 를 가진 라벨 공간 $(\mathcal Y,\ell)$ 과 가설 클래스 $\mathcal H \subseteq \mathcal Y^{\mathcal X}$를 가정할 때, 우리는 \citet{pmlr-v178-cohen22a}에서 제시된 열린 문제 (open problem) 의 실현 가능한 경우를 해결합니다. 구체적으로, 모든 실현 가능한 데이터 생성 분포 (realizable data-generating distribution) 에 대해 위험 (risk) 이 가장 좋은 클래스 내 위험 (best-in-class risk, 즉 0) 으로 거의 확실하게 수렴하는 (almost surely converges to the best-in-class risk (which is zero)) 분포 독립적 학습 규칙 (distribution-free learning rule) 이 존재하는 가설 클래스 $\mathcal H$에 대한 필요 및 충분 조건을 찾습니다.

우리의 주요 기여는 조합적 장애물 (combinatorial obstruction) 을 기반으로 한 날카로운 특징화입니다: \citet{attias2024optimallearnersrealizableregression}와 유사하게, 우리는 $\gamma_k \to \infty$인 무한 증가 $(\gamma_k)$-Littlestone 트리를 소개합니다. 이는 \citet{bousquet_theory_2021}에서 사용된 Littlestone 트리 구조를 거리 손실 (metric loss) 설정으로 확장합니다.