Taking Band-Limited Maximum Likelihood to High Dimensions: Linear Memory, the Parametric Rate, and a Self-Tuning Cut-off

Rahul Agarwal, Ankit AgarwalarXiv 2026 · arXiv

TL;DR

Researchers have scaled Band-Limited Maximum Likelihood (BLML) to high dimensions by reducing its memory requirements from quadratic to linear. This allows the estimator to maintain a "parametric" error rate ($n^{-1}$) even as dimensions grow—drastically outperforming standard kernel methods and rivaling modern normalizing flows on dense datasets.

What Problem Does This Paper Address?

Density estimation—the art of figuring out the underlying probability distribution of a dataset—usually hits a wall called the "curse of dimensionality." Most nonparametric methods, like Kernel Density Estimation (KDE), see their error rates plummet as you add more dimensions. While a 1D model might converge quickly, an 8D model requires an astronomical amount of data to reach the same accuracy.

Band-Limited Maximum Likelihood (BLML) was proposed as a solution because it assumes the "square root" of the density is band-limited (smooth and frequency-constrained). Theoretically, this allows it to hit the "parametric rate" of $n^{-1}$, a speed of learning usually reserved for simple models like Gaussians. However, until now, BLML was computationally "heavy": in more than two dimensions, it required storing a massive kernel matrix, leading to $O(n^2)$ memory usage. Storing the matrix for just 100,000 points would require 40 GB of RAM, making high-dimensional, large-scale applications impossible.

Methods

The authors introduce three major innovations to make BLML practical:

  1. Linear Memory Solver: They prove that the BLML equations are the stationarity conditions of a strictly convex objective function. By using Block Coordinate Descent (BCD) and clever 1D kernel tables, they can solve the system without ever forming the full $n \times n$ kernel matrix. This drops memory usage to $O(n)$, allowing a single A100 GPU to process a million points in 8D.
  2. Self-Tuning Cut-off: Traditionally, choosing the "bandwidth" or frequency cut-off required refitting the model dozens of times. The authors developed a streaming algorithm that learns the optimal cut-off on the fly using analytic gradients of the held-out likelihood.
  3. Periodic Support: They extended the framework to handle periodic data (like "hour of day") using Dirichlet kernels, which is essential for real-world time-series data.

Datasets

The paper evaluates the model on a mix of synthetic and real-world benchmarks:

  • Synthetic Truths: T1 (separable sinc bumps), T2 (non-separable bumps), and T3 (correlated Normal).
  • CAISO Electricity Prices: Real-world hourly price data from California, which is heavy-tailed and multimodal.
  • Standard Benchmarks: The POWER (household consumption) and GAS (chemical sensors) datasets, which are standard for testing normalizing flows.

Key Insights and Ideas

  • The Rate vs. The Constant: The most striking finding is that the $n^{-1}$ error rate actually survives in high dimensions. While KDE's performance degrades to $n^{-4/(4+d)}$, BLML keeps its "slope." The "curse of dimensionality" doesn't disappear, but it shifts: it shows up in the constant (the error at a fixed $n$ grows geometrically) rather than the rate of improvement.
  • Effective Dimension: The authors argue that band-limited functions live in a linear space of finite "effective dimension." Because BLML essentially acts as a maximum likelihood estimator within this finite-dimensional space, it inherits parametric-like convergence properties.
  • Smoothness is a Double-Edged Sword: BLML wins big on smooth densities but loses on "kinks." If a density has a sharp point (like a Laplace distribution), the band-limited assumption fails, and ripples (Gibbs-like phenomena) appear in the estimate.

Key Results

  • Speed: The new solver is 12–185x faster than a CPU implementation. It can fit 10^6 points in 8 dimensions in about ten minutes on an A100 GPU.
  • Accuracy: On band-limited synthetic data, BLML's error was 2 to 18 times lower than a Neural Spline Flow.
  • Real-World Performance: On the POWER and GAS benchmarks, BLML outperformed tuned KDEs by 0.39 and 1.58 "nats" (a measure of likelihood) per point. It placed comfortably between early normalizing flows (like Real NVP) and the most recent state-of-the-art architectures.
  • Variable Selection: The streaming cut-off learner automatically "dropped" uninformative variables by driving their frequency cut-offs toward zero.

Limitations and Future Work

  • The "Kink" Problem: As noted, BLML struggles with non-smooth densities. Future work could involve using a union of separate bands to fit densities with sparse or non-low-pass spectra.
  • Axis-Aligned Kernels: The current implementation uses a product of 1D kernels (an axis-aligned box in frequency space). This might be less efficient for data with strong diagonal correlations compared to flows that can "bend" coordinates.
  • Stationarity: The streaming algorithm assumes the data stream is stationary. Adapting this for non-stationary data (where the distribution changes over time) would require a "forgetting rule" for the sufficient statistics.

Summary updated

Abstract

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 streaming fit learns the cut-off, BLML's only tuning parameter, from analytic gradients of the held-out likelihood, for about the cost of one more fit. On real data BLML is the strongest nonparametric estimator we tested: it leads kernel and nearest-neighbour estimators on electricity prices by 0.27 to 0.47 nats per hour, and a tuned kernel estimator on the full POWER and GAS benchmarks by 0.39 and 1.58 nats per point, placing it between early and recent normalizing flows. It loses on densities with a kink.
BibTeX
@misc{agarwal2026taking,
  author = {Rahul Agarwal and Ankit Agarwal},
  title = {{Taking Band-Limited Maximum Likelihood to High Dimensions: Linear Memory, the Parametric Rate, and a Self-Tuning Cut-off}},
  year = {2026},
  eprint = {2611.19011},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19011},
}
Figure