쿼리를 이용한 일반 ReLU의 강건한 회귀 (Robust Regression of General ReLUs with Queries)

우리는 가우시안 분포 (Gaussian distribution) 하에서 제곱 손실 (squared loss)에 대해 일반적인 (homogeneous가 아닌) ReLU를 불가지론적으로 학습하는 태스크를 연구합니다. 수동적 학습 (passive learning) 설정에서, 최근 연구는 $poly(d,1/ε)$개의 레이블이 지정된 예시를 사용하고 $O(opt)+ε$의 오차를 가진 가설을 출력하는 계산 효율적인 알고리즘을 제시했습니다. 여기서 $opt$는 최적 적합 ReLU의 제곱 손실입니다. 본 연구에서는 학습자가 레이블이 없는 예시의 레이블에 대해 일종의 쿼리 접근 권한 (query access)을 갖는 상호작용 설정 (interactive setting)에 집중합니다. 우리의 주요 결과는 $d polylog(1/ε)+\tilde{O}(\min{1/p, 1/ε})$개의 블랙박스 레이블 쿼리 (black-box label queries)를 사용하는 최초의 계산 효율적인 학습기이며, 여기서 $p$는 타겟 함수의 편향 (bias)이고, $O(opt)+ε$의 오차를 달성합니다. 우리는 계산적 제약을 무시하더라도 쿼리 복잡도 (query complexity) 경계가 질적으로 최적에 가깝다는 것을 보여줌으로써 알고리즘 결과를 보완합니다. 마지막으로, 우리는 수동적 학습의 레이블 복잡도 (label complexity)를 개선하기 위해서는 쿼리 접근이 본질적으로 필요함을 입증합니다. 구체적으로, 풀 기반 능동 학습 (pool-based active learning)의 경우, 초다항식 (super-polynomial) 개수의 레이블이 없는 예시를 추출하지 않는 한, 모든 능동 학습자는 $\tilde{Ω}(d/ε)$개의 레이블을 필요로 합니다.