arXiv:2506.23456math.STcs.DS2025-06被引 1

无需熵的近似张量化,也能高效采样与身份检验混合分布。

Sampling and Identity-Testing Without Approximate Tensorization of Entropy

  • 基于数据初始化的吉布斯动态快速混合,样本复杂度最优。
  • 首次实现混合分布的身份检验,仅需少量坐标条件采样。
  • 解决开放问题,算法更简洁高效,适用于复杂分布建模。

在高维统计中,当分布满足近似熵张量化(ATE)时,许多任务会变得更容易。例如,满足 ATE 的分布其吉布斯动态马尔可夫链能快速混合,从而在短时间内生成近似样本;且若测试器具备坐标条件访问能力,身份检验所需样本极少。然而,混合分布(由少数满足 ATE 的分布组成)通常不满足 ATE。本文研究此类混合分布的采样与身份检验复杂度。主要成果包括:1. 基于数据初始化的吉布斯动态快速混合,对满足修正对数索博列夫不等式的分布混合,达到最优样本复杂度;此结果推广了黄等人(STOC 2025, COLT 2025)关于满足庞加莱不等式的混合分布的工作。2. 回答了 Blanca 等人提出的开放问题,给出了在坐标条件采样模型下对混合 ATE 分布的高效身份检验算法,并对原算法进行了简化和改进。

原文摘要 · Abstract (English)

Certain tasks in high-dimensional statistics become easier when the underlying distribution satisfies a local-to-global property called approximate tensorization of entropy (ATE). For example, the Glauber dynamics Markov chain of an ATE distribution mixes fast and can produce approximate samples in a small amount of time, since such a distribution satisfies a modified log-Sobolev inequality. Moreover, identity-testing for an ATE distribution requires few samples if the tester is given coordinate conditional access to the unknown distribution, as shown by Blanca, Chen, Štefankovič, and Vigoda (COLT 2023). A natural class of distributions that do not satisfy ATE consists of mixtures of (few) distributions that do satisfy ATE. We study the complexity of identity-testing and sampling for these distributions. Our main results are the following: 1. We show fast mixing of Glauber dynamics from a data-based initialization, with optimal sample complexity, for mixtures of distributions satisfying modified log-Sobolev inequalities. This extends work of Huang, Koehler, Lee, Mohanty, Rajaraman, Vuong, and Wu (STOC 2025, COLT 2025) for mixtures of distributions satisfying Poincaré inequalities. 2. Answering an open question posed by Blanca et al., we give efficient identity-testers for mixtures of ATE distributions in the coordinate-conditional sampling access model. We also give some simplifications and improvements to the original algorithm of Blanca et al.

采样身份检验混合分布马尔可夫链

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。