arXiv:2410.07685

Breaking the curse of dimensionality in structured density estimation

Robert A. Vandermeulen, Wai Ming Tai, Bryon Aragam

제출 2024-10-10

원문 초록

We consider the problem of estimating a structured multivariate density, subject to Markov conditions implied by an undirected graph. In the worst case, without Markovian assumptions, this problem suffers from the curse of dimensionality. Our main result shows how the curse of dimensionality can be avoided or greatly alleviated under the Markov property, and applies to arbitrary graphs. While existing results along these lines focus on sparsity or manifold assumptions, we introduce a new graphical quantity called "graph resilience" and show how it controls the sample complexity. Surprisingly, although one might expect the sample complexity of this problem to scale with local graph parameters such as the degree, this turns out not to be the case. Through explicit examples, we compute uniform deviation bounds and illustrate how the curse of dimensionality in density estimation can thus be circumvented. Notable examples where the rate improves substantially include sequential, hierarchical, and spatial data.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2505.23527v4cs.LG공통 태그 Density Estimation공식 코드 · Papers with Code

정규화 흐름은 연속 제어에 유능한 모델이다

Normalizing Flows are Capable Models for Continuous Control

현대 강화학습(RL) 알고리즘은 트랜스포머, 에너지 기반 모델, diffusion/flow 기반 모델과 같은 강력한 확률 모델을 활용함으로써 성공을 거두었다. 이를 위해 RL 연구자들은 이러한 모델을 알고리즘에 맞추는 대가를 자주 감수한다. diffusion 모델은 표현력이 뛰어나지만 미분 방정식을 풀어야 한다는 점 때문에 계산 비용이 크고, autoregressive 트랜스포머 모델은 확장성은 있지만 일반적으로 이산 표현을 학습해야 한다. 반면 정규화 흐름(NF)은 미분 방정식을 풀거나 autoregressive 아키텍처 없이도 우도와 샘플링을 가능하게 하므로 매력적인 대안으로 보인다. 그러나 RL에서의 잠재력은 정규화 흐름이 충분한 표현력을 갖추지 못한다는 지배적인 믿음 때문인지 제한적인 주목만 받아왔다. 우리는 그렇지 않음을 보인다. NF의 최근 연구를 기반으로, 우리는 RL 알고리즘에 원활하게 통합되어 정책(policy), Q-함수(Q-function), 점유도(occupancy measure) 역할을 하는 단일 NF 아키텍처를 제안한다. 우리의 접근은 훨씬 더 단순한 알고리즘으로 이어지며, 모방 학습(imitation learning), 오프라인 RL, 목표 조건 RL(goal-conditioned RL), 비지도 RL에서 더 높은 성능을 달성한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.