Search papers, labs, and topics across Lattice.
This paper addresses the computational challenges in calculating the Normalized Maximum Likelihood (NML) codelength for non-smooth estimators by introducing an exact formulation that leverages block Schur complements and Sylvester's determinant identity. By reducing the complexity of projection and volume integration from \(\mathcal{O}(N^3)\) to \(\mathcal{O}(k^3 + N^2 k)\) per step, the authors demonstrate significant efficiency improvements in the Propose-and-Project Metropolis-Hastings (PPMH) sampler. Empirical results show a remarkable speedup of over 14,100 times on high-dimensional datasets, making non-smooth NML estimation feasible for large-scale applications.
Bypassing cubic scaling walls, this method achieves over 14,100 times speedup in non-smooth NML estimation, revolutionizing large-scale statistical inference.
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.
