提出高效采样感知机解空间的新方法，突破传统瓶颈。
Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms
- 基于复本理论分析高维非凸感知机问题的可采样性。
- 球形权重下可在多数区域高效采样均匀解分布。
- 针对二元权重设计新势函数，结合退火实现快速采样算法。
在高维极限下研究随机非凸感知机问题，考虑样本数M与权重数N均较大且负载α = M/N有限的情况。基于复本理论，预测使用生成扩散算法高效采样解空间的根本极限，该极限在分数函数由近似消息传递提供时被逼近。对于带负边距κ的球形感知机，其解空间的均匀分布可在α-κ平面上大部分对称区直接高效采样。然而，二元权重情况下均匀采样仍不可行。理论分析揭示此障碍源于解空间几何结构，提出潜在函数U(s) = -log(s)，使对应的倾斜分布可通过扩散算法高效采样。数值实验表明，对这一势函数进行退火处理，可构造出一种快速且鲁棒的马尔可夫链蒙特卡洛算法，用于二元感知机解空间的采样。
原文摘要 · Abstract (English)
We consider random instances of non-convex perceptron problems in the high-dimensional limit of a large number of examples $M$ and weights $N$, with finite load $α= M/N$. We develop a formalism based on replica theory to predict the fundamental limits of efficiently sampling the solution space using generative diffusion algorithms, conjectured to be saturated when the score function is provided by Approximate Message Passing. For the spherical perceptron with negative margin $κ$, we find that the uniform distribution over solutions can be efficiently sampled in most of the Replica Symmetric region of the $α$-$κ$ plane. In contrast, for binary weights, sampling from the uniform distribution remains intractable. A theoretical analysis of this obstruction leads us to identify a potential $U(s) = -\log(s)$, under which the corresponding tilted distribution becomes efficiently samplable via diffusion. Moreover, we show numerically that an annealing procedure over the shape of this potential yields a fast and robust Markov Chain Monte Carlo algorithm for sampling the solution space of the binary perceptron.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。