提出最优学习布尔变量组分布的算法，与难题LPN等价
New Statistical and Computational Results for Learning Junta Distributions
- 将变量组分布学习转化为噪声奇偶性学习问题
- 统计复杂度达理论最优，计算效率匹配已有算法
- 适用于关注计算下界与学习效率的研究者
研究定义在{0,1}^n上的k-变量组分布学习问题，即其概率质量函数仅依赖于最多k个变量。本文主要贡献有二：一是证明学习k-变量组分布与带噪声的k-奇偶性学习（LPN）在计算上等价，这是计算学习理论中的经典难题；二是设计出一种统计复杂度最优（仅差polylog因子）的算法，计算复杂度与先前非样本最优算法相当。二者结合表明，除非对LPN取得突破，否则该算法在统计或计算层面均无法显著改进。
原文摘要 · Abstract (English)
We study the problem of learning junta distributions on $\{0, 1\}^n$, where a distribution is a $k$-junta if its probability mass function depends on a subset of at most $k$ variables. We make two main contributions: - We show that learning $k$-junta distributions is \emph{computationally} equivalent to learning $k$-parity functions with noise (LPN), a landmark problem in computational learning theory. - We design an algorithm for learning junta distributions whose statistical complexity is optimal, up to polylogarithmic factors. Computationally, our algorithm matches the complexity of previous (non-sample-optimal) algorithms. Combined, our two contributions imply that our algorithm cannot be significantly improved, statistically or computationally, barring a breakthrough for LPN.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。