최적 표본 복잡도를 갖는 반공간 절단 하 가우시안 학습을 위한 빠른 알고리즘
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
한국어 초록
우리는 알려지지 않은 반공간으로 절단된 고차원 가우시안을 학습하는 근본적인 문제를 연구한다. Lee, Mehrotra, Zampetakis(FOCS'24)는 최근 이 문제에 대한 최초의 다항 시간 알고리즘을 얻었지만, 그들의 표본 및 시간 복잡도 상한은 최적이 아니다. 비자명한 절단 하에서, 임의의 목표 정확도 $\varepsilon > 0$ 및 차원 $d$에 대해 우리는 $n = \tilde{O}(d^2/\varepsilon^2)$개의 표본을 사용하여 총 변동 거리(total variation distance)에서 오차 $\varepsilon$로 기저 가우시안을 학습하는 효율적인 알고리즘을 제시한다. 우리 알고리즘은 또한 빠르다: 실행 시간은 경험적 공분산 행렬을 계산하는 비용에 의해 지배된다. 표본 및 시간 복잡도 모두 절단이 없는 경우에도 $d$와 $\varepsilon$에 관해 최적이다: 이러한 점에서, 우리는 반공간 절단 하의 가우시안을 추가 비용 없이 학습할 수 있다. 우리 결과의 핵심 요소는 절단된 가우시안의 저차 모멘트를 상대적 절단 매개변수(relative truncation parameter) 관점에서 새롭게 해석한 것이다. 이 상대적 절단 매개변수는 절단되지 않은 가우시안의 매개변수를 유일하게 결정하며 직접적인 매개변수 복원을 가능하게 한다. 이 재해석은 절단 하에서의 학습에 널리 사용되는 시간 집약적인 투영 확률적 경사하강법(projected stochastic gradient descent) 절차를 우회할 수 있게 한다.
원문 초록
We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.
요약
알려지지 않은 반공간으로 절단된 고차원 가우시안을 총 변동 거리에서 학습하는 문제에, 절단된 분포의 저차 모멘트를 상대적 절단 매개변수로 재해석해 직접 매개변수를 복원하는 효율적 알고리즘을 제안한다. n=Õ(d²/ε²) 표본과 경험적 공분산 행렬 계산에 맞는 실행 시간으로, 절단이 없는 경우와 동일하게 d와 ε에 관해 최적인 표본·시간 복잡도를 달성한다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.27298v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
보손 가우시안 상태는 언제 고전적으로 학습할 수 있는가?
When are bosonic Gaussian states classical to learn?
물리학의 근본적인 질문 중 하나는 양자계에서 고전적 거동이 언제 나타나는가이다. 보손 가우시안 상태(bosonic Gaussian state)는 빛의 고전적 장(field) 거동과 본질적인 양자적 성질을 모두 포착하므로, 이러한 양자-고전 경계를 탐구하기에 자연스러운 환경을 제공한다. 본 연구에서는 학습 이론의 관점에서 이 문제를 다루며 다음과 같이 묻는다. 보손 가우시안 상태는 언제 고전적으로 학습할 수 있는가? 즉, n-모드 보손 가우시안 상태를 고전적인 2n변량 가우시안 분포를 학습할 때 필요한 만큼 적은 샘플과 그만큼 단순한 연산으로 학습할 수 있는 조건은 (있다면) 무엇인가? 우리는 상태의 열적 요동(thermal fluctuation)에 의해 결정되는 학습 가능성의 매끄러운 크로스오버를 규명한다. - 차가운 가우시안 상태는 학습 측면에서 비고전적이다. 공분산 행렬이 $\Sigma\le(\frac12+O(\frac1n))I$를 만족하여 진공 공분산에 가까운 경우, 단일 복사본(single-copy, 즉 얽힘이 없는) 측정 하의 토모그래피(tomography)는 근본적으로 $\Omega(n^3)$개의 복사본을 필요로 하며, 이는 고전적 가우시안 분포를 학습하는 샘플 복잡도 $\Theta(n^2)$를 엄밀하게 초과한다. 우리는 소수 복사본에 대한 얽힘 측정이 허용되더라도 이러한 어려움이 지속됨을 보인다. - 따뜻한 가우시안 상태는 학습 측면에서 고전적이다. 열적 요동이 진공 잡음을 초과하여 임의의 매개변수 $\nu>0$에 대해 $\Sigma\ge(\frac12+\nu)I$로 나타내지는 경우, 단일 복사본 토모그래피에는 $N=\Theta\left(n^2\min(n,1+\nu^{-1})\right)$개의 복사본이 필요함을 증명한다. 이 한계는 타이트(tight)하며, 단순하고 비적응적(non-adaptive)이며 얽힘이 없는 헤테로다인(heterodyne) 측정으로 달성된다. 특히 $\nu=\Omega(1)$인 경우 샘플 복잡도는 $\Theta(n^2)$로 줄어들어 고전적인 경우와 일치한다. 우리의 결과는 보손 가우시안 상태의 학습 가능성에서 나타나는 양자-고전 크로스오버를 엄밀하게 규명하고, 근본 물리학과 통계적 학습 이론 사이의 새로운 연결고리를 드러내며, 실제 센싱 실험에도 시사점을 가진다.
절단된 불리언 곱 분포의 효율적 학습: 영향력의 구원
Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue
부분집합 $S \subseteq \{0,1\}^n$으로 제약된 독립 표본으로부터 이산 분포 $μ_z$의 자연 매개변수 $z \in \mathbb{R}^n$를 학습하는 것은 고차원 통계학의 기초적인 난제이다. 절단된(truncated) 불리언 곱 분포를 효율적으로 추정하는 기존 방법, 특히 [Fotakis et al' COLT'20, Algorithmica '22]의 연구는 $S$에 대한 강한 국소 연결성 가정—fatness라 불리는 성질—또는 엄격한 반집중(anti-concentration) 가정을 요구하며, 절단 집합의 총 질량이 $n$에 대해 상수일 것을 필요로 한다. 또한 [Fotakis et al' COLT'20, Algorithmica '22]의 결과는 $S$의 질량이 $n$에 대해 지수적으로 작을 경우 표본 복잡도가 $Ω(2^n)$으로 스케일링되는 한계를 갖는다. 본 연구에서는 측도 $μ_z$ 하에서 $S$의 기하학을 분석함으로써 이러한 한계를 우회한다. fatness 가정 하에서 기존 매개변수 추정 보장을 정교화하여, $\ell_\infty$-복원에 대한 이전 표본 복잡도를 $O( \log n / ε^2)$로 개선하며, 이는 비절단(untruncated) 미니맥스 비율과 일치한다. 나아가 불리언 함수 분석에서 사용되는 영향력(influence) 개념으로 fatness를 일반화하고, 효율적인 추론을 위한 충분 조건을 제시한다. 특히 이전 연구와 달리, 우리의 방법은 모델의 임의의 매개변수화에서 표본을 추출할 것을 요구하지 않는다. 마지막으로, 표본 복잡도가 모델의 폭(width)과 집합 내 원소 간 최소 거리에 본질적으로 지수적 의존성을 갖는다는 것을 보이는 이론적 하한을 확립한다.
연속적 라벨 이동 하에서의 컨포멀 베이즈: 민감도 분석과 정확한 타당성의 한계
Conformal Bayes under Continuous Label Shift: Sensitivity Analysis and the Limits of Exact Validity
볼록 영역에서의 일반화된 점수 매칭
Generalised Score Matching on Convex Domains
점수 매칭(score matching)은 최대가능도 추정(maximum-likelihood estimation)에서 요구하는 정규화 상수 계산을 회피합니다. 제약이 있는 영역(constrained domains)에서는 일반화된 점수 매칭 변형들이 경계 조건 항이 사라지도록 피셔 발산(Fisher divergence)에 가중치를 부여합니다. 본 연구에서는 이웃 영역의 기하학적 구조가 가중치를 결정하는 최소 확률 흐름(minimum probability flow)의 작은 이웃 극한(small-neighbourhood limit)으로서 $\mathbb{R}^{d}$의 열린 볼록 부분집합(open convex subsets)에 대한 일반화된 점수 매칭을 유도합니다. $\mathbb{R}^{d}$에서의 고전적 점수 매칭 및 $\mathbb{R}_{+}^{d}$의 음이 아닌 데이터에 대한 변형들의 가중치를 포함하여, 모든 $C^{2}$ 양의 정부호(positive definite) 가중치가 이러한 방식으로 발생합니다. 지수족(exponential families)에 대해, 우리는 표준적인 볼록성(convexity), 일치성(consistency) 및 점근적 정규성(asymptotic normality) 결과를 이러한 모든 가중치로 확장하고, 특정 경계 조건 하에서 추정량이 참 매개변수로 수렴함을 보여줍니다. 다포체(polytope) 상의 절단 정규분포(truncated Gaussian)와 심플렉스(simplex) 상의 디리클레 분포(Dirichlet distribution)에 대해, 제안된 추정량들은 50개의 실측(ground-truth) 설정 중 최소 42개에서 비교된 모든 방법 중 가장 낮은 중앙값 오차를 달성합니다.
Seer: 학습 속도 곡선을 위한 최대가능도 회귀
Seer: Maximum Likelihood Regression for Learning-Speed Curves
본 연구는 머신러닝 성능 모델링에 초점을 맞춥니다. 본 학위논문에서는 분류 학습 성능에 대한 실증적 관측값을 생성한 뒤, 이를 활용해 통계 모델을 구축하는 시스템인 Seer를 소개합니다. 구축된 모델은 목표 수준을 달성하는 데 필요한 학습 예제 수와 무제한의 학습 예제가 주어졌을 때 달성 가능한 최대 정확도를 예측하는 데 활용할 수 있습니다. Seer는 1) 분류 학습을 위한 최적의 제약 조건과 가장 유용한 파라미터를 구현한 모델, 2) 최대가능도(maximum-likelihood) 모델을 효율적으로 찾는 알고리즘, 3) 세 가지 실제 도메인 데이터를 통해 이러한 모델링의 실용적인 적용 가능성을 입증함으로써 기존 기술을 발전시킵니다. 논문의 전반부에서는 분류 학습 성능에 대한 우수한 최대가능도 모델이 갖추어야 할 요건을 개괄합니다. 이어서 이러한 모델에 적합한 설계 선택지를 탐색합니다. 이러한 모델 간의 선택은 비선형 프로그래밍(nonlinear programming) 문제이지만, 적절한 문제 제약 조건을 활용함으로써 효율적인 반복 알고리즘으로 해결할 수 있는 비선형 회귀(nonlinear regression) 문제로 단순화됩니다. 논문의 후반부에서는 대두 질병, 심장병, 청각 이상 도메인에서 수행된 약 100건의 실험을 설명합니다. 테스트 결과 Seer가 학습 성능을 규명하는 데 매우 뛰어나며, 학습 성능 예측에서도 가능한 최고 수준의 성능을 보이는 것으로 나타났습니다. 마지막으로 특정 상황에 적합한 회귀 모델 선택을 위한 권장 사항을 제시하고 향후 연구 방향을 명시합니다.
분포 변화 하에서 확산 모델의 강건성
Robustness of Diffusion Models under Distribution Shift
스코어 기반 확산 모델(score-based diffusion models)은 기저 데이터 분포가 학습(training) 분포와 다를 수 있는 환경에서 점차 많이 고려되고 있으나, 기존의 이론적 보장은 주로 분포 변화가 없는 환경에 초점을 맞추고 있습니다. 본 연구에서는 기준 분포의 바서슈타인 섭동(Wasserstein perturbations) 하에서 강건한 스코어 추정을 연구합니다. 오룬슈타인-울렌벡(Ornstein-Uhlenbeck) 확산에 대해, 강건한 추정이 두 가지 핵심 요소, 즉 기준 분포를 학습하는 데 따르는 통계적 비용과 분포 변화 자체의 본질적 비용으로 분해됨을 보입니다. 후자는 바서슈타인 반경에 대해 2차(quadratically)로 스케일링되며, 이러한 의존성은 미니맥스 최적(minimax optimal)입니다. 우리는 변화 반경을 알지 못하더라도 도출된 강건한 미니맥스 속도를 달성하는 명시적인 유한 표본 추정기를 구성합니다. 기준 분포가 미지의 저차원 부분공간에 놓여 있을 때, 통계적 항은 본질적 차원에 적응하는 반면 변화 비용은 변하지 않은 채 유지됩니다. 마지막으로, 우리는 동일한 분해가 양의 시간 역방향 샘플링(positive-time reverse sampling)에도 적용됨을 보이고 KL 발산에서 일치하는 미니맥스 보장을 도출합니다. 종합적으로, 이러한 결과들은 유한한 데이터, 본질적 차원, 그리고 분포 변화가 스코어 기반 확산 모델의 강건성에 미치는 영향을 규명합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.