하프스페이스 절단(halfspace truncation) 하에서의 가우시안 학습을 위한 최적 샘플 복잡도를 가진 빠른 알고리즘

우리는 알려지지 않은 하프스페이스(halfspace)로 절단된 고차원 가우시안(Gaussian)을 학습하는 근본적인 문제를 연구합니다. Lee, Mehrotra 및 Zampetakis (FOCS'24)는 최근 이 문제에 대해 최초의 다항 시간(polynomial time) 알고리즘을 얻었으나, 그 결과로 도출된 샘플 및 시간 복잡도 경계는 최적(optimal)이 아닙니다. 유의미한 절단(non-trivial truncation) 하에서, 임의의 목표 정확도 $\varepsilon > 0$ 및 차원 $d$에 대해 우리는 $n = \tilde{O}(d^2/\varepsilon^2)$개의 샘플을 사용하고 총 변동 거리(total variation distance)에서 오차 $\varepsilon$ 내로 기저 가우시안을 학습하는 효율적인 알고리즘을 제시합니다. 우리의 알고리즘은 또한 빠릅니다. 실행 시간은 경험적 공분산 행렬(empirical covariance matrix)을 계산하는 비용에 의해 지배됩니다. 우리의 샘플 및 시간 복잡도는 절단이 없는 경우에도 $d$와 $\varepsilon$ 측면에서 최적입니다. 이 점에 있어서, 우리는 하프스페이스 절단 하에서의 가우시안을 비용 없이(for free) 학습할 수 있습니다. 우리 결과의 핵심 요소는 상대적 절단 파라미터(relative truncation parameter)의 관점에서 절단된 가우시안의 저차 모멘트(low-degree moments)를 새롭게 재해석한 것입니다. 이 상대적 절단 파라미터는 절단되지 않은 가우시안의 파라미터를 고유하게 결정하며 직접적인 파라미터 복구(parameter recovery)를 가능하게 합니다. 이러한 재해석을 통해 우리는 절단 하에서의 학습에 널리 사용되는 시간 집약적인 투영 확률적 경사 하강법(projected stochastic gradient descent) 절차를 우회할 수 있습니다.