Taking Band-Limited Maximum Likelihood to High Dimensions: Linear Memory, the Parametric Rate, and a Self-Tuning Cut-off
Authors: Rahul Agarwal, Ankit Agarwal
Organizations: Independent researcher (Ph.D., Biomedical Engineering, Johns Hopkins University) Sammamish, WA, USA · Independent researcher (M.B.A., University of Southern California) San Jose, CA, USA
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 n2, 40 GB at 105 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(n2d) and a fit takes about ten, and one A100 GPU fits 106 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.
Figures & tables
Figure 1: What makes high-dimensional BLML feasible. (a) Binning compresses the data only for d≤2 ; from d=3 on every point has its own bin, so a solver must handle B=n . (b) Peak GPU memory of our solver grows as O(n) (dotted: linear fit), where a dense float32 Gram matrix grows as 4n2 bytes and exceeds an A100 beyond n≈105 . (c) Fit time against n ; dashed: the O(n2d) cost per sweep, anchored at the largest fit.
Figure 2: The truths in two dimensions, on a linear scale (top) and as log10f/maxf (bottom). T1: a product of sinc4 bumps; T2: four bumps along the diagonal whose ripples do not factor; T3: a correlated normal, not band-limited.
Figure 3: Relative integrated squared error against n for the separable truth T1 (mean ± s.e. over replicates).
Figure 4: Left, centre: asymptotic slope of log relative ISE against logn , fitted over the two largest n ( 3×104 and 105 ; for BLML on T1 in d=4,6,8 , the large- n runs at 3×105 and 106 ), with 95% bootstrap intervals. Dashed: −1 ; dotted: the KDE rate −4/(4+d) . Slopes over all n are in Table 9 . Right: the cost of a cutoff twice too high, as the ratio of BLML’s error at 2fctrue to that at fctrue ; dashed: 2d .
Figure 5: n⋅ relative ISE divided by the exact constant fcd/∫f2−1 of the unbiased sinc KDE (dashed line at 1), T1. A flat line is an n−1 rate; its height is the constant. BLML at fctrue sits near 2−d ; at 2fctrue it approaches the sinc KDE’s constant from below. BLML points beyond n=105 are from the large- n runs.
Figure 6: Relative ISE against the cutoff, at n=104 (top) and n=105 (bottom); circles mark each curve’s minimum. Left: T1, with the cutoff relative to the true one (dashed). The minimum stays at fctrue as n grows, and the slope of the right branch (in the legend) grows with d . Right: T3, which has no true cutoff; the minimum moves to higher cutoffs as n grows. Left of each minimum the error is dominated by truncation bias, right of it by variance.
d
n
BLML, one-shot
BLML, streaming
best data-driven KDE
Laplace (kink)
2
103
0.0486
0.0776
0.0213 (adaptive)
2
104
0.0216
0.0215
0.00599 (adaptive)
4
103
0.279
0.266
0.0972 (adaptive)
4
104
0.141
0.147
0.0405 (adaptive)
8
103
0.66
0.74
0.545 (LSCV)
Table 2: Truths that are not smooth: relative ISE (median of four replicates) with every estimator’s smoothing chosen from the data. Best per row in bold; the best KDE’s bandwidth rule in parentheses.
d
n
BLML
neural spline flow
best KDE
band-limited, separable (T1)
2
103
0.0049
0.034
0.013
2
104
0.00055
0.0072
0.0029
4
103
0.029
0.065
0.064
4
104
0.00089
0.016
0.018
8
103
0.15
0.14
0.33
Table 3: Relative ISE of BLML (cut-off by validation search) and the best data-driven KDE, both nonparametric, and a neural spline flow, a flexible parametric reference (medians over replicates; best per row in bold).
Figure 7: Fixed cut-off, d=4 , both to tolerance 10−4 (CPU, float64). Left: fit time; right: relative ISE. Medians over three replicates, bars min–max. Dashed: BCD; solid: streaming.
Figure 8: Cut-offs of streaming BLML against points seen (in passes over the data), two-dimensional band-limited truths, n=104 ; geometric mean over four replicates and both columns. Dotted: the true cut-off; dash-dotted: the common cut-off of least integrated squared error on replicate 0.
Figure 9: Error of a competitor divided by the error of streaming BLML (relative ISE, median over replicates); above 1, streaming is better. Dotted: the best of four data-driven Gaussian KDEs in that cell; dashed: BLML at the true cut-off (oracle; T1, T2), which sits near 1.
fc error
relative ISE
truth
d
n
(rel. rms)
streaming
oracle
best KDE
T1
2
103
12%
4.08e-3
2.75e-3
1.34e-2 (Scott)
T1
2
104
9%
5.24e-4
2.07e-4
2.91e-3 (Scott)
T1
4
103
16%
1.19e-2
1.05e-2
6.38e-2 (Scott)
T1
4
104
7%
1.12e-3
1.17e-3
1.83e-2 (adaptive)
T1
8
103
26%
1.42e-1
8.70e-2
3.32e-1 (Scott)
Table 4: Streaming BLML against the truth. fc error: relative rms error of the learned cut-offs, (d1∑j(fc,j/fctrue−1)2)1/2 (T1, T2; T3 has no true cut-off). Relative ISE of streaming BLML, the oracle and the best data-driven Gaussian KDE (rule in parentheses). Medians over replicates.
model
hour, lag 24 h
hour, lags 24, 168 h
nonparametric (complexity grows with n )
BLML (this paper)
-3.393
-3.383
conditional KDE
-3.787
-3.850
conditional k -NN
-3.703
-3.654
flexible parametric, semiparametric and neural (fixed architecture; reference)
Gaussian mixture
-3.425
-3.427
Table 7: Test log-likelihood of the CAISO price on held-out days (nats per hour, higher is better; best per group in bold). Columns are the covariate sets. ∗ TabPFN is pretrained on synthetic tables and is not fitted to these data.
model
POWER ( d=6 )
GAS ( d=8 )
nonparametric (complexity grows with n )
BLML, streaming cut-off (this paper)
0.06
12.51
Gaussian KDE, bandwidth on validation
−0.33
10.93
neural (fixed architecture; published, reference)
MADE
−3.08
3.56
Real NVP
−0.02
4.78
Table 8: Test log-likelihood on the standard benchmarks (nats per point, higher is better; full training splits, published preprocessing). Best per group in bold.
Appendix figures & tables16 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 10: Relative ISE against n for the non-separable truth T2.
Figure 11: Fitted slopes for the correlated normal T3 (not band-limited).
Figure 12: Kullback–Leibler divergence against n , T1.
Figure 13: Relative ISE against n for the correlated normal T3 ( fc=2 and 4 for BLML and sinc KDE).
Figure 14: Correlated normal T3: relative ISE against n for BLML at six cutoffs (light to dark: low to high) and the oracle-bandwidth kernel estimators. Low cutoffs win at small n and level off at a bias floor; high cutoffs decay as n−1 with a large constant.
Figure 15: Convergence: constraint residual maxb∣ρb∣ (left; dashed: tolerance) and objective gap (right) per sweep.
Figure 16: GPU fit time against n ( d=3 , where B≈n ), float32 and float64.
Workload
B
fit (s)
predict (s)
speedup
CPU
GPU
CPU
GPU
fit / predict
synthetic d=3 n=3000
2,999
1.6
0.13
1.7
0.007
12 × / 237 ×
synthetic d=3 n=10000
9,991
12.1
0.38
5.3
0.021
32 × / 256 ×
synthetic d=3 n=30000
29,963
160.9
0.87
15.9
0.059
185 × / 269 ×
CAISO p(price—hour) n=10001
9,808
19.8
0.29
5.4
0.024
69 × / 221 ×
Appendix
Table 11: CPU (Numba, single thread) versus GPU (A100), same algorithm and tolerance.
Table 23
Figure 17: Fitted slope of log KL divergence against logn (top: all n ; bottom: the two largest n ), with 95% bootstrap intervals, for estimators that return a density. Dashed: −1 .
Figure 18: Fixed architectures against sample size on the band-limited truth T1 at d=4 : neural spline flows of three sizes (weights in parentheses) and BLML at the true cutoff, with n−1 for reference. One replicate at n=106 , where the smallest flow reached its cap of 150 passes; two below.
variant ( n=2⋅104 , CPU, two passes)
time (s)
held-out log-lik.
one-shot selection (reference)
83.5
−2.4214
fixed-e gradient
24.8
−2.4629
+ one-sweep response
24.2
−2.4332
+ smoothing
22.4
−2.4285
+ pooled over 3 batches
21.7
−2.4209
default: smoothing and pooling, no one-sweep response
16.6
−2.4257
Appendix
Table 15: Gradient variants for streaming BLML, each added to the one above.
Figure 19: Learned period against batch, from 22 h (blue) and 26 h (orange), three seeds each; dotted: 24 h.
ISE at n=64,000
slope of log ISE in logn
truth
seed
str. KDE
oracle
valid.
Scott
str. BLML
str. KDE
oracle
valid.
Scott
str. BLML
T1
0
1.2e-3
2.2e-5
2.8e-5
2.4e-5
2.4e-5
+0.41
−0.77
−0.76
−0.80
−1.33
T1
1
6.7e-4
2.3e-5
1.1e-4
2.3e-5
3.5e-6
+0.36
−0.77
−0.78
−0.77
−1.77
T2
0
4.3e-5
1.8e-5
3.6e-5
1.8e-4
9.3e-6
−1.08
−0.85
−0.99
−0.62
−1.19
T2
1
8.7e-5
2.0e-5
4.1e-5
1.9e-4
5.1e-6
−0.79
−0.77
−0.90
−0.55
−1.33
T3
0
6.4e-5
5.8e-5
8.5e-5
5.8e-5
9.9e-6
−0.54
−0.54
−0.53
−0.61
−2.32
Appendix
Table 16: One-dimensional ISE at n=64,000 (best in bold) and the least-squares slope of log ISE in logn over n=2,000 – 64,000 . The KDE theory gives −0.8 .
truth
d
seed
streaming KDE
KDE, oracle h
KDE, validated h
KDE, Scott
streaming BLML
hstr/hor
T1
1
0
0.01590
0.02723
0.15171
0.10722
0.00170
2.01
T1
1
1
0.00509
0.00173
0.00173
0.00533
0.00113
1.66
T2
1
0
0.00553
0.00415
0.00623
0.00468
0.00134
0.76
T2
1
1
0.00015
-0.00011
-0.00011
0.00139
0.00148
1.31
T3
1
0
0.00007
0.00004
0.00013
0.00004
-0.00011
1.22
T3
1
1
-0.00009
-0.00016
-0.00013
-0.00009
-0.00024
2.78
Appendix
Table 17: Excess test loss (nats, lower is better; best in bold) at n=64,000 , and streaming KDE’s bandwidth relative to the oracle’s. Differences below about 10−3 are within the noise of the 5,000 -point test sample, which also makes some entries negative.
tolerance 21/4
tolerance 2
n
sample
no sweeps
two sweeps
(no rebuild)
2⋅104
0
−2.4429 (16.5 s)
−2.4257 (16.9 s)
−2.4265 (15.7 s)
2⋅104
1
−2.4412 (16.9 s)
−2.4327 (17.5 s)
−2.4199 (16.1 s)
2⋅104
2
−2.4150 (17.2 s)
−2.4005 (17.7 s)
−2.4005 (15.8 s)
4⋅104
0
−2.2429 (55.8 s)
−2.2262 (59.8 s)
−2.2321 (49.0 s)
Appendix
Table 18: Held-out log-likelihood (time) of streaming BLML under two re-binning tolerances; one row per sample.
Minimax-optimal rates for multivariate distribution estimation are known to suffer from the curse of dimensionality. We propose a sparse Bayesian network approach in which each conditional probability is estimated using sparsity-aware conditional mean methods. The resulting estimator, BAyesian Network Distribution regression (BAND), handles mixed data types in high-dimensional time series and achieves polynomial total variation convergence rates while allowing the feature dimension to grow polynomially with the sample size. These rates are substantially faster than the classical optimal rates for multivariate histogram density estimators that lack sparsity. Empirical evaluations show that BAND performs competitively for data sampling and confidence region forecasting against a range of state-of-the-art benchmarks.
Shuo-Chieh Huang, Chien-Ming Chi, Jau-er Chen
Department of Statistics, Rutgers University, Piscataway, NJ, U.S.A. · Institute of Statistical Science, Academia Sinica, Taipei, Taiwan · School of Political Science and Economics, National Taiwan University, Taipei, Taiwan
Density estimation in high-dimensional settings is an important and challenging statistical problem.Traditional methods based on kernel smoothing are inefficient in high dimensions due to the difficulties in specifying appropriate location-adaptive kernels. In this work, we introduce pre-training, a key idea behind many cutting-edge AI technologies, to the context of non-parametric density estimation. By establishing a pre-trained neural network that can recommend an appropriate location-adaptive kernel for each sample point, efficient density estimation with adaptive kernels is achieved in high dimensions. A wide range of numerical experiments show that this strategy is highly effective for improving density-estimation accuracy, when the target distribution is close to the distribution family for pre-training. When the target distribution is substantially different from the pre-training distribution family, the benefit from the proposed pre-training strategy may be diluted, but can be reactivated by an additional fine-tuning procedure.
Ruitong Zhang, Ke Deng
Department of Statistics and Data Science Tsinghua University Beijing, China
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+N2k) 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.
Trenton Lau, Gary P. T. Choi
Department of Mathematics, The Chinese University of Hong Kong