Taking Band-Limited Maximum Likelihood to High Dimensions: Linear Memory, the Parametric Rate, and a Self-Tuning Cut-off
Band-limited maximum likelihood (BLML) estimates a density as the square of a band-limited function. The estimate is non-negative, and when the square root of the true density is band-limited its error falls at the parametric rate $n^{-1}$. Its algorithm bins the data, which is fast only in one or two dimensions: from three on every point has its own bin, the kernel system is dense, and memory grows as $n^2$, 40 GB at $10^5$ points. Whether the rate survives in higher dimension, where kernel estimators slow down, had not been tested. We study dense data, densities that fill their space, not data near a low-dimensional manifold. We show that the binned equations are the stationarity condition of a strictly convex objective and minimise it by block coordinate descent without forming the kernel matrix: memory is linear in $n$, a sweep costs $O(n^2 d)$ and a fit takes about ten, and one A100 GPU fits $10^6$ points in eight dimensions in about ten minutes. On band-limited truths the error then decays as $n^{-1}$ in every dimension we tested, up to eight, while the slopes of kernel estimators flatten from -0.67 to -0.28, and it is 2 to 18 times lower than a neural spline flow's. A…
- arXiv
- 2611.19011
- Authors
- Rahul Agarwal, Ankit Agarwal
- Categories
- stat.ML · cs.LG