Distribution regression predicts a number from a whole probability distribution: the aerosol level over a patch of satellite pixels, or a county's vote share from the demographics of its residents. The standard method represents each distribution by its kernel mean embedding, the average of a feature map over the points drawn from it, and then runs kernel ridge regression on those averages. In practice, each distribution is seen only through a finite "bag" of $N$ samples. Theory therefore has to track two sample sizes, the number of bags $m$ and the points per bag $N$. This note argues that the finite bag does more than add noise. It adds a specific, computable ridge penalty to the regression. That penalty grows as the kernel bandwidth shrinks, which is exactly the regime where a characteristic kernel is most sensitive to fine differences between distributions. It also differs from bag to bag whenever bag sizes differ.
This observation changes how the regularization parameter should be set. In the usual schedule, the ridge penalty $\lambda$ shrinks as a function of $m$ alone. Instead, $\lambda$ should be the one-bag-count optimal value minus the penalty the bags already supply. When the bags already supply too much, which happens at small $N$ or narrow bandwidth, the right fix is to remove the bag-induced diagonal rather than tune $\lambda$. We propose to derive this joint schedule $\lambda(m, N, \sigma)$, build a debiased estimator that follows it, and test whether it recovers accuracy in the small-bag and uneven-bag regimes common in real data.
Core Claim
Let $k$ be a characteristic kernel with bandwidth $\sigma$. A characteristic kernel is one whose mean embedding $\mu_P = \mathbb{E}_{X\sim P}[k(X,\cdot)]$ is one-to-one, so distinct distributions map to distinct points (Injective Hilbert Space Embeddings of Probability Measures). The regression uses the linear "set kernel" between embeddings. For bags drawn independently, the empirical Gram matrix of estimated embeddings $\hat\mu_i$ satisfies
$$\mathbb{E}\,\langle \hat\mu_i, \hat\mu_j\rangle = \langle \mu_i, \mu_j\rangle + \delta_{ij}\,\frac{v_i}{N_i}, \qquad v_i = \mathbb{E}_{X\sim P_i} k(X,X) - \|\mu_{P_i}\|^2 .$$
Here $N_i$ is the size of bag $i$, $\delta_{ij}$ is one when $i=j$ and zero otherwise, and $v_i$ is the "embedding variance" of distribution $i$. The off-diagonal entries are unbiased, which is the cancellation exploited by Improved learning theory for kernel distribution regression with two-stage sampling. The diagonal is biased upward by $v_i/N_i$.
Kernel ridge regression solves $(\hat K + m\lambda I)\alpha = y$. Here $\hat K$ is the empirical Gram matrix, $\alpha$ is the vector of per-bag coefficients, and $y$ is the vector of targets. The bias therefore acts as an extra per-bag ridge of size $v_i/(mN_i)$ on top of the explicit $\lambda$.
For a Gaussian kernel, $k(x,x)=1$ and $\|\mu_P\|^2 \to 0$ as $\sigma \to 0$, so $v_i \to 1$. Narrow bandwidths, which are needed to see high-frequency differences, therefore produce the largest hidden ridge. Suppose $\lambda^\star(m)$ is the optimal one-stage schedule, meaning the rate one would use if the true embeddings were known. The effective penalty should match it, which gives explicit $\lambda \approx (\lambda^\star(m) - \bar v/(mN))_+$, where $\bar v$ is the average embedding variance. Once $\bar v/(mN) > \lambda^\star(m)$, no nonnegative $\lambda$ is correct and the estimator is over-regularized by construction.
This gives a transparent, testable version of the $N$-versus-$m$ requirement: bags must satisfy $N \gtrsim \bar v/(m\lambda^\star(m))$. The requirement is explicitly dependent on bandwidth. That dependence is absent from the $N \gtrsim n^{5/4}$ and $N \gtrsim n^{7/8}$ conditions in prior work.
Relation to Prior Work
Three papers motivate and supply method for this work. Consistent, Two-Stage Sampled Distribution Regression via Mean Embedding introduced Mean Embedding Ridge Regression (MERR) and proved a $1/t^{2/7}$ rate with pessimistic bag-size requirements. It treats bag noise as a generic perturbation, not as a structured diagonal. Improved learning theory for kernel distribution regression with two-stage sampling showed that sampling errors largely cancel across distributions under a "near-unbiased condition," improving the bag requirement. We build on that cancellation but isolate the one term that does not cancel, and we make it an explicit control variable for $\lambda$. Coefficient-based regularized distribution regression supplies a needed tool: it penalizes $\lambda m\|\alpha\|_2^2$ directly and tolerates indefinite kernels. This matters because subtracting the diagonal bias can make the debiased Gram matrix indefinite.
On the theory side, the one-stage schedules we try to match come from classical Tikhonov analyses of kernel learning (Learning, Regularization and Ill-Posed Inverse Problems). The bandwidth sensitivity we exploit echoes the finding that bandwidth mistuning distorts kernel distances (Kernel Hyperparameter Sensitivity in Distributional Metrics).
Our work differs from the spectral-regularized testing line (Spectral Regularized Kernel Two-Sample Tests). That line schedules $\lambda$ for a fixed kernel and splits samples to estimate covariances. We study regression, and the quantity we schedule against is the per-bag variance, not a covariance spectrum.
Research Program
The first component is analytical. We will prove a risk bound for MERR in which the explicit $\lambda$ and the bag-induced diagonal enter jointly. The bound should show that risk is governed by an effective per-bag penalty $\lambda + v_i/(mN_i)$. We will derive from it the joint schedule $\lambda(m,N,\sigma)$ under the capacity and source conditions used by the coefficient-based analysis. We will also state the bandwidth-dependent bag-size threshold, and check whether the zero-bias regime recovers the one-stage minimax rate.
The second component is an estimator we call variance-aware MERR. It estimates each $v_i$ without bias from within-bag pairs; this is a U-statistic, an average over distinct pairs of points. It then subtracts $v_i/N_i$ from the diagonal of $\hat K$, which yields an unbiased Gram matrix. Finally it applies coefficient-based regularization, so that any indefiniteness is harmless. With the hidden penalty removed, $\lambda$ can be set by the one-stage rate or chosen by cross-validation.
A reweighted variant keeps the diagonal but equalizes it across bags. This addresses the case where bag sizes vary by orders of magnitude, as with census regions.
The third component is empirical and is described below. Its central prediction is a phase transition. Plotted against $N$, the loss from using standard MERR instead of the variance-aware version should appear where $\bar v/(mN)$ crosses $\lambda^\star(m)$. That crossing point should move to larger $N$ as $\sigma$ shrinks.
Baselines
The naive reference point is standard MERR (Consistent, Two-Stage Sampled Distribution Regression via Mean Embedding). We will run it with the median-heuristic bandwidth and $\lambda$ chosen by five-fold cross-validation on a log grid. This is what most practitioners run. On supervised entropy learning, the source paper reports an RMSE of 0.11 for MERR against 0.285 for the density-estimation method DFDR, and an RMSE of 7.86–7.91 on MISR1 aerosol prediction.
The strongest existing competitor is mean-embedding regression with random Fourier features, a random low-dimensional approximation of the kernel. On the US Census/Election task, Improved learning theory for kernel distribution regression with two-stage sampling reports that it explains over 82% of variance. It is strongest here because its theory already accounts for two-stage sampling and it scales to 2.4 million individuals. We will also include coefficient-based regularized regression (Coefficient-based regularized distribution regression), for which no reported number was found on Lacuna. It is the closest method to ours in form.
Every method will see identical bags, splits, and random-feature budgets. Each will get the same cross-validation budget over a joint grid of bandwidth and $\lambda$. This matters because a fair baseline must be allowed to tune bandwidth too.
Two ablations isolate the key ingredient. The first applies diagonal debiasing without coefficient regularization, which tests whether indefiniteness matters. The second uses per-bag reweighting without debiasing, which tests whether heterogeneity or bias drives any gain.
Beating the baselines means two things. The first is a statistically significant RMSE reduction, or $R^2$ gain, in the small-$N$ and heterogeneous-$N$ regimes. The second is no loss in the large-$N$ regime, where all methods should converge.
Why not just…?
Why not just cross-validate $\lambda$ and let it absorb the hidden penalty? For homogeneous bags at moderate $N$, cross-validation will largely do this. We expect little gain there and will report that honestly. Cross-validation fails in two places. First, a single scalar $\lambda$ cannot cancel a diagonal that differs across bags. Second, once $\bar v/(mN) > \lambda^\star(m)$, cross-validation hits $\lambda = 0$ and remains over-regularized. The phase-transition experiment decides whether these regimes are wide enough to matter. If the transition sits at bag sizes nobody uses, the practical claim fails and only the theory remains.
Why not just use an unbiased U-statistic Gram matrix and stop? This is the most plausible simpler competitor, and it is our first ablation. Taken alone, it can produce an indefinite matrix, so ridge regression becomes unstable. The coefficient-based penalty fixes that problem. If plain debiasing with a small positive $\lambda$ matches the full method, we will report that it does. The contribution would then be the schedule and the bandwidth-dependent bag-size threshold, not the estimator.
Why not just widen the bandwidth so the embedding variance is small? A wider bandwidth shrinks $v_i$ but also shrinks the kernel's sensitivity to high-frequency structure. The cost of that trade is documented for kernel distances (Kernel Hyperparameter Sensitivity in Distributional Metrics). Our joint-grid baselines already allow any bandwidth. If the best standard MERR simply selects a wide bandwidth and matches our method, this alternative wins. We will check this directly on targets that depend on fine structure, such as mode counts.
Why not just subsample every bag to equal size? Equal bags remove heterogeneity but discard data from the largest bags. We include equal-size subsampling as an extra baseline on the census data, where the imbalance is most extreme.
Proposed Experiments
The synthetic core uses two tasks. The first is the rotated-Gaussian entropy task from Consistent, Two-Stage Sampled Distribution Regression via Mean Embedding. The second is Gaussian-mixture mode counting from Improved learning theory for kernel distribution regression with two-stage sampling, for which no reported result was found on Lacuna. On both we sweep $m$, $N$, and $\sigma$ on a grid, which lets us measure the location of the phase transition directly. The decisive check is whether the crossover $N$ scales like $\bar v(\sigma)/(m\lambda^\star(m))$ as predicted, including its movement with $\sigma$. We will also draw bag sizes from a heavy-tailed law so the heterogeneous regime is tested separately.
On real data, we will subsample MISR1 bags to small $N$ and compare against the reported RMSE of 7.86–7.91 at full size. We will run the US Census/Election task using its natural population imbalance, against the reported figure of more than 82% explained variance.
Two results would falsify the proposal. The first is standard MERR with a jointly tuned bandwidth and $\lambda$ matching variance-aware MERR across the whole grid. The second is an observed crossover that does not track the predicted dependence on $\sigma$.
References
- Injective Hilbert Space Embeddings of Probability Measures
- Improved learning theory for kernel distribution regression with two-stage sampling
- Consistent, Two-Stage Sampled Distribution Regression via Mean Embedding
- Coefficient-based regularized distribution regression
- Learning, Regularization and Ill-Posed Inverse Problems
- Spectral Regularized Kernel Two-Sample Tests