Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
원문 초록
Diffusion models over discrete spaces have recently shown striking empirical success, yet their theoretical foundations remain incomplete. In this paper, we study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation, with a focus on $τ$-leaping-based samplers. We establish sharp convergence guarantees for attaining $\varepsilon$ accuracy in Kullback-Leibler (KL) divergence for both uniform and masking noising processes. For uniform discrete diffusion, we show that the $τ$-leaping algorithm achieves an iteration complexity of order $\tilde O(d/\varepsilon)$, with $d$ the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size $S$ and improving existing bounds by a factor of $d$; moreover, we establish a matching algorithmic lower bound showing that linear dependence on the ambient dimension is unavoidable in general. For masking discrete diffusion, we introduce a modified $τ$-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity, termed the effective total correlation, which is bounded by $d \log S$ but can be sublinear or even constant for structured data. As a consequence, the sampler provably adapts to low-dimensional structure without prior knowledge or algorithmic modification, yielding sublinear convergence rates for various practical examples (such as hidden Markov models, image data, and random graphs). Our analysis requires no boundedness or smoothness assumptions on the score estimator beyond control of the score entropy loss.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2602.15008v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
진화 변분 오토회귀 네트워크를 통한 이산 확산 모델
Discrete Diffusion Models via Evolving Variational Autoregressive Networks
기존 score 기반 확산 모델은 정규화된 밀도를 표현하지 않은 채 score만 학습하는 반면, 다루기 쉬운(tracable) 정규화 모델은 샘플링과 직접적인 가능도 평가를 모두 지원한다. 최근 텐서 네트워크 접근법은 이러한 표현을 제공하지만, 대체로 저차원 격자에 제한된다. 본 연구에서는 변분 오토회귀 네트워크로 정규화된 확률 분포를 매개변수화하는 이산 확산 모델을 제안한다. 명시적인 Markov jump 연산자가 순방향 노이징과 역방향 디노이징 역학을 지배하며, 정규화된 분포를 갖는 이산 확산 모델을 고차원 격자上的 스핀 시스템으로 확장한다. 이 프레임워크를 질서, 임계, 무질서 영역에 걸친 2차원·3차원 Ising 모델에 적용하여 자유 에너지, 에너지, 자화를 포함한 열역학량을 정확히 계산한다. 또한 Monte Carlo 샘플링과 통합하고, 적응형 확산 단계로 낮은 온도에서도 높은 수락률을 유지하면서 샘플 다양성을 높인다. 이 결과는 정규화된 확률 분포를 갖는 이산 확산 모델을 위한 신경망 프레임워크를 확립한다.
완전 이산 조건부 확산 모델에 대한 유한 표본 보장
Finite-Sample Guarantees for Fully Discrete Conditional Diffusion Models
본 연구에서는 데이터로부터 학습(training)되고 유한한 수의 노이즈 제거 단계를 통해 구현되는 조건부 확산 모델(conditional diffusion models)에 대한 유한 표본 보장(finite-sample guarantees)을 정립합니다. 제안하는 접근법은 스코어 학습 목적식을 샘플링 그리드와 일치시켜 통계적 추정 오차와 수치적 이산화 오차를 함께 분석할 수 있도록 합니다. 매끄러운 조건부 밀도 모델 하에서 생성된 분포의 오차에 대한 높은 확률의 한계(high-probability bounds)를 도출하고 필요한 스코어 평가 횟수를 정량화합니다. 모든 매끄러움 지수 $β>0$에 대해, 적절한 그리드는 조기 종료(early stopping) 여부와 관계없이 원래 타깃 대비 $\widetilde O_p(n^{-2β/(d_x+d_y+2β)})$의 평균 조건부 쿨백-라이블러(KL) 발산을 산출합니다. 전체 샘플러와 조기 종료 샘플러 모두 $\widetilde O_p(n^{-β/(d_x+d_y+2β)})$의 평균 타깃 총변동(TV) 오차를 달성합니다. 여기서 $n$은 표본 크기이고, $d_x, d_y$는 데이터 및 조건부 변수의 차원이며, 오차는 조건부 변수에 대해 평균화됩니다. 이 총변동 한계는 로그 인자를 제외하면 기존 조건부 분포 추정 이론에서 확립된 수렴율과 일치합니다.
마스크 이산 확산 모델에서 타우 리핑을 위한 스케줄 최적화
Schedule optimization for tau-leaping in masked discrete diffusion
마스크 확산(masked diffusion) 모델은 이산 분포를 위한 대표적인 생성 모델이다. 표준적인 자기회귀(autoregressive) 샘플링과 달리, 이 모델은 여러 좌표를 병렬로 드러내며 각 블록의 결합 조건부 법칙을 1차원 좌표 조건부들의 곱으로 근사한다. 통상적으로 타우 리핑(tau-leaping)이라 불리는 이러한 절차는 계산 비용을 줄이지만, 완벽하게 학습된 예측기가 주어지더라도 인수분해 오차($\varepsilon_\text{fact}$)를 유발한다. 본 연구에서는 고정된 샘플링 예산 내에서 $\varepsilon_\text{fact}$를 최소화하기 위해 노이즈 제거 스케줄을 선택하는 방법에 초점을 맞추어, 생성 정확도와 계산 비용 사이의 상충관계를 분석한다. 이를 위해 스케줄과 타깃의 의존성 구조를 분리하는 $\varepsilon_\text{fact}$의 정확한 적분 표현을 확립하고 이를 의존성 밀도 $ρ$로 요약한다. 이 표현식은 최적 스케줄에 대한 재귀적 정상성 방정식을 도출하며, $ρ$의 추정 오차가 스케줄 선택에 미치는 영향을 정량화할 수 있게 한다. 차원 $N$과 샘플링 예산이 증가함에 따라 최적 스케줄의 특성을 규명하고, 결정론적 플래너 대비 무작위 블록 크기의 비용을 정량화한다. 또한 본 연구는 근본적인 이분법을 제시한다. 즉, $N\to\infty$일 때 $ρ$가 엄격하게 양인 연속 프로파일로 균등 수렴하면 스케줄 최적화는 $\varepsilon_\text{fact}$의 최고차 계수만 개선할 수 있는 반면, $ρ$가 퇴화하면 스케줄 최적화가 점근적 차수 자체를 개선할 수 있음을 보인다. 정상 과정(stationary process) 및 교환 가능 혼합 모델에 기반한 예시들을 통해 이러한 영역들을 실증한다.
분포 변화 하에서 확산 모델의 강건성
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 발산에서 일치하는 미니맥스 보장을 도출합니다. 종합적으로, 이러한 결과들은 유한한 데이터, 본질적 차원, 그리고 분포 변화가 스코어 기반 확산 모델의 강건성에 미치는 영향을 규명합니다.
일반화된 랑주뱅 역학을 위한 메모리 조건부 확산 모델
Memory-Conditioned Diffusion Model for Generalized Langevin Dynamics
일반화된 랑주뱅 방정식(Generalized Langevin equation)은 분해된 변수(resolved variable)의 진화가 과거에 의존하는 비마르코프 역학(non-Markovian dynamics)을 설명합니다. 본 연구에서는 메모리 커널(memory kernel)을 식별하거나 미분해 변수(unresolved variable)를 재구성하지 않고도, 관측된 궤적으로부터 이러한 역학의 확률적 흐름 맵(stochastic flow map)을 학습하기 위한 메모리 조건부 확산 기법을 제안합니다. 컴팩트하고 재귀적으로 업데이트되는 지수 필터 뱅크(bank of exponential filters)를 통해 흐름 맵은 긴 관측 윈도우에 조건을 부여하지 않고도 여러 시간 척도에 걸쳐 예측 이력을 유지할 수 있습니다. 다음 단계 분포는 현재 관측값과 이 메모리 상태를 조건으로 하며, 고정된 뱅크 크기에서 메모리 상태의 저장 및 업데이트 비용은 이력 길이와 무관합니다. 예측 기준을 통해 메모리 예산을 결정하고 벡터 벤치마크에서는 참조 지원 선택을 활용하며, 선택적 선형 투영을 통해 조건부 차원을 더욱 축소합니다. 커널 기반 스코어 추정기는 스코어 네트워크를 학습(training)시키지 않고도 조건부 샘플을 생성하며, 이 샘플들은 자기회귀 시뮬레이션을 위한 신경 흐름 맵을 학습하는 데 사용됩니다. 세 가지 수치 예제를 통해 작은 조건부 차원에서의 긴 메모리 유지력, 결합된 벡터 역학에서의 예측 압축, 비가우스 조건부 분포 및 간헐적 이벤트를 평가(evaluation)합니다. 비가우스 예제는 플라스마 스크레이프-오프 층(plasma scrape-off layer)의 확률적 모델에서 조건부 비대칭성과 버스트 통계를 재현합니다.
확산 모델과 개념 형성
Diffusion Models and Concept Formation
인간은 중첩된 추상화 수준과 사람들이 최소한의 인지적 노력으로 사물을 인식하고 이름을 붙이는 \emph{기본 수준}(basic level)을 가진 개념 분류 체계로 지식을 구조화합니다. Cobweb은 범주 효용(category utility)을 극대화하여 확률적 개념 계층을 구축하는 점진적 학습자로서 이러한 능력에 대한 고전적인 인지적 설명을 제공합니다. 본 논문에서는 확산 모델(diffusion model)이 이미지 합성을 위해 설계되었음에도 불구하고 암묵적으로 동일한 계산을 수행한다고 주장합니다. 확산 모델의 노이즈 주변 확률 분포(noisy marginals)는 데이터 분포의 가우시안 평활화(Gaussian smoothing)이며, 이러한 주변 확률 분포의 모드(mode)들은 네 가지 측면에서 확률적 프로토타입의 Cobweb 트리와 일치하는 계층을 형성합니다. 두 모델 모두 계층적 밀도 모델이고, 가우시안 프로토타입을 갖는 계층적 베이지안(hierarchical-Bayesian) 모델이며, 범주화를 불확실성을 줄이는 점수 추적(score-following)으로 취급하고, 두 모델 모두에서 기본 수준이 창발적(emergent)으로 나타납니다. 우리는 확산 모델의 이러한 기본 수준을 중간 노이즈 수준에 위치시키며, 최근 분석에 따르면 역과정(reverse process)이 샘플의 클래스 정체성을 확정하는 지점임을 보여줍니다. 두 모델은 주로 분류 체계를 표현하고 학습(training)하는 방식에서 차이를 보입니다. Cobweb은 이산 트리를 점진적으로 학습하는 반면, 확산 모델은 데이터 분포에 적합화된 단일 학습 스코어 필드(score field) 내에 연속적이고 보간 가능한 계층을 인코딩합니다. 우리는 모드 탐색(mode-finding)을 통해 확산 계층을 복원하고 두 모델의 기본 수준을 비교함으로써 MNIST와 Fashion-MNIST에서 이러한 대응 관계를 검증합니다. 이는 확산 모델을 개념 형성의 인지 모델로 재구성하고 Cobweb에 연속적이고 확장 가능한(scalable) 구현체를 제공합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.