선형 쿼리(Linear Queries)를 통한 최적 재구성

요약

본 연구는 근사적인 선형 쿼리를 사용하여 $\mathbb{R}^d$ 공간 내의 미지의 점을 재구성하는 문제의 최적 오차를 규명합니다. 쿼리 횟수, 차원, 노이즈 파라미터에 따른 재구성 오차의 수렴성을 분석하며, 특히 차원이 고정된 경우 초과 오차가 이중 지수적으로 빠르게 감소함을 증명합니다. 또한 Jung의 정리를 일반화하여 근사적 극한체를 규명하는 기하학적 방법론을 제시합니다.

핵심 포인트

• 쿼리 횟수가 무한할 때 최적 재구성 오차가 $\sqrt{2d/(d+1)} \delta$로 수렴함을 입증
• 차원이 고정된 환경에서 초과 오차가 일반적인 학습 곡선보다 훨씬 빠른 이중 지수적 속도로 감소
• 차원 증가 시 초과 오차 제거를 위해 $\exp(d)$ 차수의 쿼리 횟수가 필요함을 증명
• Jung의 정리를 일반화하여 근사적 극한체를 규명하는 강건한 변형 제공