arXiv:2610.13924v1 cs.LG

혼합 전후의 KL: 병렬 샘플링에서의 라운드 복잡도 분리

KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling

Tianyi Wu

제출 2026-10-09

저자 비고

arXiv Comments

15 pages of main text; 169 pages total including references and appendices; 7 figures. Formal proof materials included as ancillary files

한국어 초록

병렬 샘플러(parallel sampler)는 함께 생성할 좌표들을 무작위로 선택할 수 있다. 목표 분포 $p$와, 각 출력마다 새로 추출되는 스케줄 $U$의 출력 법칙 $q_U$에 대해, 우리는 스케줄 평균 발산(schedule-averaged divergence) $\mathbb{E}_U D_{\mathrm{KL}}(p\|q_U)$와 출력 법칙 발산(output-law divergence) $D_{\mathrm{KL}}(p\|\mathbb{E}_U q_U)$를 (단위: 나츠) 비교한다. 라운드는 해당 라운드 시작 시점에 고정된 정확한 조건부 마진(conditional marginals)으로부터의 독립적인 추출을 확정하며, 각 출력의 스케줄은 유한한 스케줄 혼합(mixture)으로부터 샘플링 이전에 추출되고, 스케줄링된 모든 라운드에 대해 비용이 부과된다. 짝수 길이 $n$이고 1의 개수가 $n/2$인 이진 문자열에 대한 균등 분포(uniform distribution)의 경우, 고정된 허용오차(tolerance) $\varepsilon>0$에서 기대 라운드 수의 최솟값은 첫 번째 기준 하에서는 $Θ_\varepsilon((\log n)^2)$이지만 두 번째 기준 하에서는 $(e^{-\varepsilon}+o(1))\log_2\ln n$이며, 이 이중 로그(double-logarithmic) 차수는 모든 실행에서 동일한 라운드 수로 달성 가능하다. 이 목표 분포에 대해, 카운트 상태 재귀(count-state recursion)는 모든 인과적 무작위 정책(causal randomized policy)에 대한 모든 라운드 상한에서의 정확한 최소 출력 발산을 제공한다. 이 분리(separation)는 가중치(weight) 비율이 유계이고 쿼터 비율(quota fraction)이 0과 1로부터 떨어져 있는, 순열 대칭성(permutation symmetry)이 없는 가중 고정-개수 목표(weighted fixed-count target)로 확장되며, 완전 지지(full-support) Beta$(1,1)$--베르누이(Bernoulli) 목표로도 확장된다. 이 경우 출력 법칙 기준 하에서의 정확한(sharp) 기대 비용은 $(e^{-\varepsilon}/2+o(1))\log_2\log_2n$이며, 드문 $n$-라운드 실행에서 달성된다. 선행 연구는 균형잡힌(balanced) 목표에 대한 스케줄 평균 비용의 차수와, 두 확장 모두에 대한 $O_\varepsilon((\log n)^2)$ 상한을 암시한다.

원문 초록

A parallel sampler can choose at random which coordinates to generate together. For a target $p$ and the output law $q_U$ of a schedule $U$ drawn afresh for each output, we compare the schedule-averaged divergence $\mathbb{E}_U D_{\mathrm{KL}}(p\|q_U)$ with the output-law divergence $D_{\mathrm{KL}}(p\|\mathbb{E}_U q_U)$, in nats. Rounds commit independent draws from exact conditional marginals frozen at the round's start, each output's schedule is drawn before sampling from a finite mixture of schedules, and every scheduled round is charged. For the uniform distribution on binary strings of even length $n$ with $n/2$ ones, the least expected number of rounds at a fixed tolerance $\varepsilon>0$ is $Θ_\varepsilon((\log n)^2)$ under the first criterion but $(e^{-\varepsilon}+o(1))\log_2\ln n$ under the second, and the double-logarithmic order is attainable with the same round count on every run. For this target, a count-state recursion gives the exact least output divergence at every round cap over all causal randomized policies. The separation extends to weighted fixed-count targets with bounded weight ratios and quota fractions bounded away from zero and one, without permutation symmetry, and to the full-support Beta$(1,1)$--Bernoulli target, where the sharp expected cost under the output-law criterion is $(e^{-\varepsilon}/2+o(1))\log_2\log_2n$, attained with rare $n$-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its $O_\varepsilon((\log n)^2)$ upper bounds on both extensions.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.13924v1

함께 살펴볼 논문

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

arXiv:2606.22976v2cs.LG공통 태그 parallel sampling

빠르게 걷되 주의하라: 마스크 확산 모델에서의 병렬 샘플링 이해

Walk fast but be careful: Understanding Parallel Sampling in Masked Diffusion

본 논문에서는 마스크 확산 모델(MDM, masked diffusion model)의 병렬 샘플링 전략을 연구하기 위한 검증 가능한 샌드박스로 그래프 상의 무작위 보행(random walk)을 활용한다. 고정된 그래프에서 생성된 무작위 보행 표본을 바탕으로 MDM을 학습(training)시킨다. 모델(model)에는 그래프와 전이 커널(kernel)이 전혀 주어지지 않으며, 이는 제어 가능하면서도 평가를 가능하게 하는 잠재 구조 역할을 한다. 본 프레임워크는 생성된 보행의 유효성 검증과 추정된 전이 커널을 통한 분포 충실도 측정 방식을 제공한다. 단순한 그래프를 통해, 최저 엔트로피와 같이 널리 쓰이는 점수를 기반으로 한 병렬 언마스킹(unmasking)이 무작위 병렬 샘플링보다 일관되게 우수한 것은 아님을 이론적으로 증명한다. 즉, 정확한 조건부 확률이 주어지더라도 성능은 그래프가 유도하는 조건부 의존성 구조에 결정적으로 좌우되며, 이는 스도쿠와 같은 벤치마크에서는 분리하여 파악하기 어려운 현상이다. 또한 시퀀스 길이에 대해 로그 수준의 스텝만을 소요하며, 학습된 주변 분포가 정확할 경우 무작위 보행에 대해 정확성이 증명되는 MDM용 훈련 불필요(training-free) 이분(bisection) 샘플러를 개발한다. 그래프 보행 태스크에 대한 실험을 통해 그래프 구조에 따라 서로 다른 병렬 샘플러의 성능이 더 우수함을 확인한다. 사전학습된 MDM에 대한 실험 결과, 이분 형태의 샘플러가 OpenWebText 생성 및 GSM8K, MBPP, HumanEval을 포함한 추론 벤치마크에서 뛰어난 속도-품질 트레이드오프를 제공함을 보여준다. 종합하면, 이러한 결과들은 그래프 보행을 통해 조건부 의존성이 병렬 MDM 샘플링의 핵심 원리임을 밝혀내고, 이 통찰을 언어 생성 및 추론으로 전이 가능한 효율적인 샘플러로 전환한다.

arXiv:2607.22201v2eess.SY공통 태그 kl divergence

KL 발산을 통한 궤적 정규화 확률적 최적 제어

Trajectory-Regularized Stochastic Optimal Control via KL Divergence

우리는 표준 확률적 최적 제어(SOC)에 제어된 궤적 분포와 기준 궤적 분포 사이의 쿨백-라이블러(KL) 발산을 증강한 궤적 정규화 확률적 최적 제어(TRSOC)를 소개한다. 기르사노프 정리를 활용하면 궤적 KL은 2차 드리프트 불일치 페널티로 단순화되어 동적 계획법(DP) 구조를 보존하는 수정된 실행 비용을 산출한다. 우리는 이에 대응하는 해밀턴-야코비-벨만(HJB) 방정식을 유도하고 최적 정책을 특성화한다. 선형-2차(LQ) 설정에서 이 정식화는 증강된 제어 비용을 갖는 닫힌 형태의 해를 허용한다. 실험을 통해 정규화 매개변수가 성능 중심 행동과 기준 보존 행동 간의 절충(trade-off)을 유도함을 보이며, 여기에는 오프라인 데이터로부터 학습된 기준 동역학을 사용하는 경우가 포함된다.

arXiv:2506.11378v3cs.LG공통 태그 kl divergence

스코어 기반 확산 샘플링에서 확률성의 효과: KL 발산 분석

The Effect of Stochasticity in Score-Based Diffusion Sampling: a KL Divergence Analysis

스코어 기반 확산 모델에서의 샘플링은, 임의의 확률성 함수로 매개변수화된 역시간 확률적 미분방정식(SDE)을 풀거나, 이 확률성 함수를 0으로 설정하는 것에 해당하는 확률 흐름 ODE(probability flow ODE)를 풀어 수행할 수 있다. 본 연구에서는 Kullback-Leibler(KL) 발산의 시간적 진화를 통해 이러한 확률성이 생성 과정에 미치는 효과를 조사하고, 일반적인 KL 발산 상한을 도출하며, 스코어 오류의 시간 프로파일(time-profile)이 모델 성능에 미치는 영향에 대한 새로운 분석을 제시한다. 정확한 스코어 함수의 경우, 확률성은 수축(contractive) 효과를 가져 샘플링 궤적을 따라 KL 발산이 감소한다. 그러나 근사 스코어의 경우, 누적 오류를 보정하는 것과 현재 스코어 오류를 증폭시키는 것 사이에 트레이드오프가 발생하여, 확률성이 생성 성능을 향상시킬 수도 있고 저하시킬 수도 있다. 이론적 고찰에 따르면, 확률성으로 얻는 이득은 학습된 모델 오류의 시간적 국소화(time-localization)에 따라 달라진다. 이를 toy 데이터셋과 벤치마크 데이터셋 모두에 대한 실험으로 검증하며, KL 발산의 진화를 도출된 상한과 비교한다. 또한 관련된 모든 양을 계산할 수 있고, 최적 확률성 함수가 최적 제어(optimal control) 분석을 통해 특성화될 수 있는 완전 해석적 예시도 제시한다.

arXiv:2411.00214v2stat.ML공통 태그 kl divergence

포괄적 KL 그래디언트 플로우: Otto-Wasserstein, Fisher-Rao-Gaussian, 그리고 로컬 추정기 동역학

Inclusive KL Gradient Flows: Otto-Wasserstein, Fisher-Rao-Gaussian, and Local-Estimator Dynamics

포괄적(순방향) Kullback–Leibler(KL) 발산의 Otto Wasserstein 그래디언트 플로우는 통계적 추론 알고리즘을 분석하는 원칙적 프레임워크를 제공하지만, 배타적(역방향) KL 발산을 목표로 하는 알고리즘은 이러한 도구로 거의 연구되지 않았다. 우리는 포괄적 KL 추론을 위한 통합 그래디언트 플로우 및 확률밀도함수(PDF) 프레임워크를 확립한다. 최대 평균 불일치(MMD) 최소화가 근사 그래디언트 추정기를 사용하는 포괄적 KL 추론으로 볼 수 있음을 보이고, 포괄적 KL 발산을 직접 목표로 하는 Fisher–Rao 및 Wasserstein–Fisher–Rao 그래디언트 플로우를 개발한다. 이 플로우를 가우시안 분포의 다양체로 제한하면 명시적인 그래디언트 플로우 상미분방정식(ODE)이 도출되며, 이는 가우시안 변분 추론의 토대를 제공한다. 이러한 관점을 바탕으로, 우리는 밀도비 평가나 커널 그래디언트 없이 로컬 비모수 회귀로 속도 필드를 구하는 로컬 추정기 Wasserstein 그래디언트 플로우를 추가로 도입하여, MMD 기반 파티클 방법 대비 알고리즘 성능을 향상시킨다.

arXiv:2503.08038v2cs.LG공통 태그 kl divergence

일반화된 쿨백-라이블러(KL) 발산 손실

Generalized Kullback-Leibler Divergence Loss

본 논문에서는 쿨백-라이블러(KL) 발산 손실을 심층 분석하여, 이것이 (1) 가중 평균 제곱 오차(wMSE) 손실과 (2) 소프트 라벨을 포함하는 교차 엔트로피 손실로 구성된 분리된 쿨백-라이블러(DKL) 발산 손실과 수학적으로 동등함을 증명합니다. DKL 손실의 분리된 구조 덕분에 개선이 필요한 두 가지 영역을 식별했습니다. 첫째, 더 부드러운 가중치 함수를 사용하여 비대칭 최적화 속성을 해소함으로써 지식 증류(knowledge distillation)와 같은 시나리오에서 KL 손실의 한계를 해결합니다. 이러한 수정은 최적화 과정에서의 수렴(convergence) 문제, 특히 소프트 라벨에서 높은 예측 점수를 가진 클래스에 대한 수렴 문제를 효과적으로 완화합니다. 둘째, 개별 샘플에서 발생하는 바이어스(bias)를 줄이기 위해 KL/DKL에 클래스별 전역 정보를 도입합니다. 이 두 가지 향상을 통해 일반화된 쿨백-라이블러(GKL) 발산 손실을 도출하였으며, 적대적 학습(adversarial training) 및 지식 증류 작업에 중점을 두고 CIFAR-10/100, ImageNet 및 비전-언어(vision-language) 데이터셋에서 실험을 수행하여 그 효과를 평가했습니다. 구체적으로, 공개 리더보드인 RobustBench에서 새로운 최첨단(state-of-the-art) 적대적 강건성을 달성했으며, CIFAR/ImageNet 모델 및 CLIP 모델 전반에서 경쟁력 있는 지식 증류 성능을 보여주어 상당한 실용적 이점을 입증했습니다. 본 연구의 코드는 https://github.com/jiequancui/DKL 에서 확인할 수 있습니다.

토론

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