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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 29 references that are in the map.
- First posted on arXiv 22 Jun 2026.

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

- [Rank-normalization, folding, and localization: An improved widehatR for assessing convergence of MCMC](https://mlsanity.com/paper/1903.08008/) (2019)
- [Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling](https://mlsanity.com/paper/2212.00570/) (2022)
- [Geometric ergodicity of the Random Walk Metropolis with position-dependent proposal covariance](https://mlsanity.com/paper/1507.05780/) (2015)
- [Foundation of Calculating Normalized Maximum Likelihood for Continuous Probability Models](https://mlsanity.com/paper/2409.08387/) (2024)
- [A Probabilistic Basis for Low-Rank Matrix Learning](https://mlsanity.com/paper/2510.05447/) (2025)
- [Breaking textitWinner-Takes-All: Cooperative Policy Optimization Improves Diverse LLM Reasoning](https://mlsanity.com/paper/2605.11461/) (2026)
- [The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling](https://mlsanity.com/paper/2605.24477/) (2026)
- [Implicit Null-space Manifold Generation for Redundant Robotic Systems](https://mlsanity.com/paper/2605.25770/) (2026)

## Abstract (arXiv)

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) × (N+k) generalized KKT matrix, while calculating the volume factor requires the determinant of an (N-k) × (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 O(N3) to O(k3 + N2 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× while maintaining double-precision numerical equivalence, rendering exact non-smooth NML estimation highly tractable for large-scale statistical inference.