완전 다항 시간으로 ReLU의 양의 선형 조합 학습

요약

본 논문은 가우시안 분포 하에서 ReLU 활성화 함수의 양의 선형 조합을 PAC 학습하는 문제를 다룹니다. 기존 알고리즘이 필요했던 초다항 시간 복잡도를 개선하여, $\mathrm{poly}(d, k, 1/\varepsilon)$ 시간에 목표 개념에 근접한 해를 찾는 최초의 완전 다항 시간 알고리즘을 제시합니다.

핵심 포인트

• ReLU 선형 조합 학습에 대한 최초의 완전 다항 시간 알고리즘을 제안했습니다.
• 기존 초다항 시간 복잡도를 $\mathrm{poly}(d, k, 1/\varepsilon)$로 개선했습니다.
• 약한 학습기 부스팅과 암시적 텐서 계산 기법을 활용합니다.
• 가지치기 접근법(pruning approach)으로 관련 벡터만을 유지하는 것이 핵심입니다.