提出可计算非光滑模型NML码长的理论与算法,实现数据高效模型选择。
The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling

- 基于几何测度论和保守雅可比,建立非光滑估计器的NML计算框架。
- 设计PDL-PPMH采样器,精确采样高维Lasso后验(维度P=2000)。
- 实证显示其等效交叉验证但无需数据划分,适合小样本场景。
标准化最大似然(NML)码长,即随机复杂度,是一种通用编码的合理准则。尽管最近基于共面积公式的表述为平滑模型提供了计算方法,但该框架在现代机器学习中普遍存在的非光滑估计器(如Lasso、稀疏SVM)上失效。本文为正则路径可微的Lipschitz(PDL)估计器构建了严格的NML计算框架。通过应用经典几何测度论,并将共面积公式与保守雅可比相结合,我们证明了非光滑模型的随机复杂度是良定义的,且在理论上与现代自动微分输出一致。为精确计算该量,我们提出提议-投影梅特罗波利斯-汉金斯(PDL-PPMH)采样器,一种能穿越最大似然估计器不可微水平集的几何马尔可夫链蒙特卡洛算法。我们从理论上验证了其组件,包括随机切空间提议和可证明收敛的非光滑投影求解器。我们在高维Lasso后验(维度P=2000)上展示了方法的鲁棒性,同时量化了决定精确性与混合时间权衡的计算复杂度。关键的是,我们通过实验证明,所提出的精确NML准则提供了一种高度数据高效的替代交叉验证的方法,在无需数据分割的情况下达到统计上无法区分的预测最优性能。综上,本工作为正则非光滑模型的NML码长理论分析铺平了道路。
原文摘要 · Abstract (English)
The Normalized Maximum Likelihood (NML) codelength, or stochastic complexity, represents a principled criterion for universal coding. While recent coarea-based formulations provided a calculation method for smooth models, this framework collapses for the non-smooth estimators ubiquitous in modern machine learning (e.g., Lasso, Sparse SVMs). In this work, we provide a rigorous framework for computing the NML for regular path-differentiable Lipschitz (PDL) estimators. By applying classical geometric measure theory and bridging the coarea formula with conservative Jacobians, we prove that the stochastic complexity for non-smooth models is well-posed and theoretically consistent with the outputs of modern Automatic Differentiation. To compute this quantity exactly, we introduce the Propose-and-Project Metropolis-Hastings (PDL-PPMH) sampler, a geometric MCMC algorithm capable of traversing the non-differentiable level sets of the maximum likelihood estimator. We theoretically justify its components, including a stochastic tangent space proposal and a provably convergent non-smooth projection solver. We demonstrate the method's robustness by sampling from a high-dimensional Lasso posterior ($P=2000$), while simultaneously quantifying the computational scaling that governs the trade-off between exactness and mixing time. Crucially, we empirically demonstrate that our exact NML criterion provides a highly data-efficient alternative to cross-validation, achieving statistically indistinguishable predictive optima without requiring data splitting. Altogether, our work paves the way for the theoretical analysis of the NML codelength for regular non-smooth models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。