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

Computing the Normalized Maximum Likelihood (NML) codelength for non-smooth estimators (like Lasso or Sparse SVMs) is essential for model selection but historically computationally prohibitive. The process requires manifold-constrained projection and volume integration, both of which traditionally involve inverting large (N+k) x (N+k) KKT matrices, leading to cubic scaling walls that make large-scale statistical inference intractable.

The authors propose a Schur-Sylvester dimensionality reduction to bypass these bottlenecks. By leveraging the block Schur complement, they reformulate the projection operator to operate solely on the active parameter subspace (k x k). Furthermore, they apply Sylvester’s determinant identity to the volume factor calculation, allowing the determinant of an (N-k) x (N-k) matrix to be computed via a k x k matrix. This approach is generalized to Elastic Net, Sparse SVMs, and Group Lasso, with a dynamic switching mechanism to maintain efficiency even if the active set becomes dense.

The study proves that the computational cost of the projection and volume integration steps collapses from O(N^3) to O(k^3 + N^2k). Empirical benchmarks on high-dimensional datasets demonstrate a constant speedup exceeding 14,100x while maintaining double-precision numerical equivalence. The authors also provide a rigorous error propagation analysis, showing that their method is more numerically stable than direct KKT inversion because it restricts matrix operations to the localized active Gram matrix, preventing the accumulation of floating-point errors over long MCMC trajectories.

This work renders exact non-smooth NML estimation feasible for large-scale statistical applications. By removing the cubic dependency on the ambient data dimension N, researchers can now perform exact model selection and inference for high-dimensional models that were previously limited to asymptotic approximations, which often fail in non-smooth or finite-sample regimes.