# The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling

arXiv: https://arxiv.org/abs/2605.24477 · HTML: https://mlsanity.com/paper/2605.24477/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 23 May 2026.

## Builds on (most cited first, 15 of 15)

- [Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning](https://mlsanity.com/paper/1909.10300/) (2019)
- [Deep Learning is Singular, and That's Good](https://mlsanity.com/paper/2010.11560/) (2020)
- [A mathematical model for automatic differentiation in machine learning](https://mlsanity.com/paper/2006.02080/) (2020)
- [Minimum Description Length Revisited](https://mlsanity.com/paper/1908.08484/) (2019)
- [Symmetry in Neural Network Parameter Spaces](https://mlsanity.com/paper/2506.13018/) (2025)
- [Gradient Sampling Methods for Nonsmooth Optimization](https://mlsanity.com/paper/1804.11003/) (2018)
- [A survey of Monte Carlo methods for noisy and costly densities with application to reinforcement learning and ABC](https://mlsanity.com/paper/2108.00490/) (2021)
- [On the complexity of nonsmooth automatic differentiation](https://mlsanity.com/paper/2206.01730/) (2022)
- [Learning Capacity: A Measure of the Effective Dimensionality of a Model](https://mlsanity.com/paper/2305.17332/) (2023)
- [Foundation of Calculating Normalized Maximum Likelihood for Continuous Probability Models](https://mlsanity.com/paper/2409.08387/) (2024)
- [On randomized step sizes in Metropolis-Hastings algorithms](https://mlsanity.com/paper/2601.19710/) (2026)
- [A projected semismooth Newton method for a class of nonconvex composite programs with strong prox-regularity](https://mlsanity.com/paper/2303.05410/) (2023)
- [Gradient sampling algorithm for subsmooth functions](https://mlsanity.com/paper/2503.16638/) (2025)
- [Normalized Maximum Likelihood Code-Length on Riemannian Data Spaces](https://mlsanity.com/paper/2508.21466/) (2025)
- [Evidence Slopes and Effective Dimension in Singular Linear Models](https://mlsanity.com/paper/2601.01238/) (2026)

## Built on by (most cited first, 1 of 1)

- [Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling](https://mlsanity.com/paper/2606.23867/) (2026)

## Abstract (arXiv)

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.