arXiv:2606.23867cs.LGcs.IT2026-06

突破非光滑模型的计算瓶颈,实现精确贝叶斯推断的高速采样。

Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling

  • 利用分块舒尔补和西尔维斯特恒等式,重构计算流程
  • 单步复杂度从O(N³)降至O(k³ + N²k),提速超1.4万倍
  • 适用于Lasso、SVM等模型,适合大规模统计推断研究者

对正则非光滑估计器(如Lasso)的归一化最大似然(NML)码长进行精确计算,长期受限于流形约束投影与体积积分的三次方复杂度。在几何提议-投影马尔可夫链蒙特卡洛(PPMH)采样每一步中,投影算子需逆一个(N+k)×(N+k)广义KKT矩阵,体积因子需计算一个(N−k)×(N−k)格拉姆矩阵的行列式。本文提出数学等价的新公式,通过块舒尔补和西尔维斯特行列式恒等式,彻底绕过这两个瓶颈。我们证明两项操作的计算复杂度均从O(N³)降为O(k³ + N²k)每步。该方法推广至稀疏支持向量机(SVM)、弹性网和组Lasso。最后,提供严格的数值稳定性分析,并以每秒有效样本数(ESS)评估采样效率。高维数据集上的实证基准显示,保持双精度数值等价的同时,实现了超过14,100倍的恒定加速,使大规模统计推断中的精确非光滑NML估计变得可行。

原文摘要 · Abstract (English)

The exact computation of the Normalized Maximum Likelihood (NML) codelength for regular non-smooth estimators (e.g., Lasso) has been historically limited by the cubic scaling walls of manifold-constrained projection and volume integration. At each step of the geometric Propose-and-Project Metropolis--Hastings (PPMH) sampler, evaluating the projection operator requires inverting an $(N+k) \times (N+k)$ generalized KKT matrix, while calculating the volume factor requires the determinant of an $(N-k) \times (N-k)$ Gram matrix. This paper presents an exact, mathematically equivalent formulation that bypasses both bottlenecks by utilizing the block Schur complement and Sylvester's determinant identity. We prove that the computational complexity of both operations collapses from $\mathcal{O}(N^3)$ to $\mathcal{O}(k^3 + N^2 k)$ per step. We generalize this reduction to Sparse Support Vector Machines (SVMs), Elastic Net, and Group Lasso. Finally, we provide a rigorous numerical stability analysis and evaluate the sampler's efficiency using the Effective Sample Size (ESS) per second. Our empirical benchmarks on high-dimensional datasets confirm a constant speedup exceeding $14{,}100\times$ while maintaining double-precision numerical equivalence, rendering exact non-smooth NML estimation highly tractable for large-scale statistical inference.

贝叶斯推断优化算法高维统计

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