揭示非可分消息传递算法的普适性条件，拓展了其在非高斯数据下的适用范围。
On Universality of Non-Separable Approximate Message Passing Algorithms
- 提出张量有界复合性质（BCP），界定非可分AMP算法普适性的关键条件。
- 证明多项式非线性与利普希茨连续非线性均满足BCP近似性，实现状态演化普适。
- 适用于通用信号去噪、谱去噪及组合函数等场景，适合研究算法泛化性者参考。
一阶迭代算法（如近似消息传递、随机与近端梯度下降、朗之万扩散）的平均场表征已为众多统计应用中的学习动态提供了精确理解。对于具有坐标可分形式非线性的算法，其平均场表征对底层数据分布具有一定程度的普适性。然而，非可分算法动态的平均场分析长期局限于独立同分布高斯或旋转不变数据。本文首次系统研究非可分AMP算法的普适性。我们识别出多项式非线性AMP的普遍性条件：其对应张量需满足有界复合性质（BCP）。进一步，我们形式化了利普希茨连续AMP算法的BCP可近似性条件，以获得类似的普适保证。实验表明，多种常见非可分非线性（如局部去噪器、通用信号的谱去噪器、可分函数与一般线性映射的复合）均满足BCP可近似性，意味着采用这些非线性的AMP算法的状态演化具有普适性。
原文摘要 · Abstract (English)
Mean-field characterizations of first-order iterative algorithms -- including Approximate Message Passing (AMP), stochastic and proximal gradient descent, and Langevin diffusions -- have enabled a precise understanding of learning dynamics in many statistical applications. For algorithms whose non-linearities have a coordinate-separable form, it is known that such characterizations enjoy a degree of universality with respect to the underlying data distribution. However, mean-field characterizations of non-separable algorithm dynamics have largely remained restricted to i.i.d. Gaussian or rotationally-invariant data. In this work, we initiate a study of universality for non-separable AMP algorithms. We identify a general condition for AMP with polynomial non-linearities, in terms of a Bounded Composition Property (BCP) for their representing tensors, to admit a state evolution that holds universally for matrices with non-Gaussian entries. We then formalize a condition of BCP-approximability for Lipschitz AMP algorithms to enjoy a similar universal guarantee. We demonstrate that many common classes of non-separable non-linearities are BCP-approximable, including local denoisers, spectral denoisers for generic signals, and compositions of separable functions with generic linear maps, implying the universality of state evolution for AMP algorithms employing these non-linearities.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。