Massart 노이즈가 존재하는 상황에서 표류하는 하프스페이스(Halfspaces)의 효율적인 학습

우리는 Massart 노이즈 (Massart noise)가 존재하는 상황에서 표류하는 개념 (drifting concept)을 학습하는 문제를 연구합니다. 이 프레임워크에서 온라인 학습자 (online learner)는 매 라운드마다 변할 수 있는 타겟 개념 (target concept)의 노이즈가 섞인 레이블을 가진 독립적인 샘플들의 이력을 사용할 수 있습니다. 목표는 각 라운드에서 예측 오차 (prediction error)가 작은 가설 (hypothesis)을 출력하는 것입니다. 우리는 가장 기본적인 클래스인 마진 분리 가능 선형 분류기 (margin-separable linear classifiers, 하프스페이스 (halfspaces))에 대해 이 학습 문제의 복잡도를 연구합니다. 긍정적인 측면에서, 우리는 $η+ ilde O(Δ^{1/3}/γ)$의 오차를 달성하는 계산적으로 효율적인 학습자를 제시합니다. 여기서 $η$는 Massart 노이즈율의 상한이며, $Δ$는 표류율 (drift rate), $γ$는 마진 (margin)입니다. 흥미롭게도, 실현 가능한 설정 (realizable setting)에서는 우리의 기술을 응용하여 이전 연구보다 개선된 오차율을 가진 효율적인 학습자를 도출할 수 있습니다. 하한 (lower-bound) 측면에서는 정보-계산 트레이드오프 (information-computation tradeoff)에 대한 공식적인 증거를 제공하며, 이는 우리 알고리즘의 성능이 본질적으로 최적임을 강력하게 시사합니다. 구체적으로, 정보 이론적으로 최적인 오차는 $Δ^{1/2}$에 비례하지만, 우리는 무작위 분류 노이즈 (random classification noise)의 특수한 경우에서도 저차 다항식 테스트 (low-degree polynomial tests)에 대해서는 $Δ^{1/3}$ 스케일링이 불가피함을 증명합니다.