Introduction
Machine learning has long been built upon a simple but powerful abstraction: data as vectors [61 , 21 ] . From classical linear models and support vector machines to modern deep neural networks, the dominant paradigm in machine learning has traditionally assumed that each observation can be represented as a fixed-dimensional point in a Euclidean space. This vector-centric viewpoint has driven decades of progress in computer vision, speech recognition, scientific computing, and predictive modeling. Even as machine learning architectures have grown increasingly sophisticated, much of modern learning theory and algorithm design remains fundamentally rooted in vector-valued representations [29 , 7 ] .
Yet many real-world learning problems are fundamentally not vector-valued. In numerous scientific and engineering domains, each observation is more naturally represented as a collection, set, bag, or probability distribution rather than a single feature vector [16 , 35 ] . A medical diagnosis may rely on an entire collection of pathology images or patient measurements [9 , 23 ] ; a manufacturing process may be characterized by particle size distributions evolving over time [59 ] ; a sensor network may generate streams of stochastic observations [15 ] ; and modern language models themselves process increasingly long contexts that are intrinsically set- or sequence-valued. In such settings, the statistical object of interest is no longer an individual sample, but the underlying distribution generating those samples. This shift has fueled growing interest in learning paradigms capable of operating directly on distributions, where the input to the learning system is itself a probability measure estimated through finite observations [48 , 19 , 40 ] .
Existing approaches to learning from bags, sets, and distributions can be broadly organized into two major paradigms. The first is the multi-instance learning (MIL) paradigm, which treats each input as a finite unordered bag of instances [16 , 35 , 19 ] , is increasingly dominated by deep neural architectures [23 , 66 , 30 ] . The second is distribution regression, which explicitly formulates the problem as supervised learning from probability distributions to responses [41 , 57 , 40 ] . MIL is algorithmically flexible but often statistically opaque and data hungry, whereas distribution regression is principled, stable, and theoretically well understood, but limited by computation.
Distribution regression formulates the set-valued learning problems as supervised learning problems in which each input is an underlying probability distribution observed through a finite bag of samples. Early nonparametric formulations treated the problem directly as regression on probability measures and established consistency under distribution-free assumptions, often through density-based or kernel-kernel constructions [41 ] . A more influential line of work later represented distributions through kernel mean embeddings (KME), which map probability measures into a reproducing kernel Hilbert space (RKHS) [48 , 52 , 53 , 40 , 36 ] . This embedding viewpoint provides a natural way to compare distributions through inner products, distances, and kernels on embedded measures, and has become the dominant foundation for kernel-based distribution regression. Within this framework, support measure machines introduced a discriminative learning formulation over probability measures [38 ] , while subsequent two-stage learning theory established、】【 consistency and convergence guarantees when both the distributions and the samples from each distribution are random [56 , 57 , 6 ] . These developments make kernel mean embedding-based distribution regression especially attractive in scientific and safety-critical settings.
Despite these theoretical guarantee, computation remains a major obstacle in large scale applications. Kernel mean embedding-based distribution regression typically requires constructing and manipulating large kernel matrices over both instances and bags, so the cost grows rapidly with the number of distributions and the number of samples per distribution. As a result, the very framework that is arguably the most principled default for distributional supervised learning becomes difficult to deploy in large-scale settings. Moreover, as in conventional kernel learning, performance remains tightly coupled to the choice of kernel [20 , 13 , 12 ] . A poorly chosen kernel may yield a representation that is statistically ineffective, while adaptive kernel selection or learning procedures can introduce additional optimization overhead.
Previous studies on kernel approximations for distribution regression have primarily emphasized computational efficiency and practical implementation [18 , 37 , 62 , 1 ] , while recent work on adaptive distribution kernels has focused on learning representations suited to downstream tasks [24 ] . These developments have largely pursued efficiency and adaptivity along separate lines, the integration of both scalability and adaptivity into a common framework receives much less attention. Building on these efforts, we develop a finite-sample analysis of random feature distribution regression to theoretically justify its computation and performance trade-off and extend the framework through score-guided feature selection to address scalability and adaptivity together. The paper is organized around three main contributions.
In § 3 , we develop a finite-sample analysis of Random Feature Distribution Regression (RaDR) in the classical two-stage sampling setting. Our perturbation analysis separates the effects of distribution-level sampling, finite within-bag sampling, and random feature approximation. For kernel ridge regression with a linear distribution kernel, we establish sufficient feature-budget conditions under which RaDR preserves the order of the excess-risk upper bound of exact two-stage kernel distribution regression, while reducing the computational cost.
In § 4 , we propose Adaptive Random Feature Distribution Regression (A-RaDR), a unified score-guided framework for achieving adaptive kernels in distribution regression. Our formulation encompasses several important adaptive sampling strategies, including kernel alignment, leverage scores, and distribution variance, within a single framework.
In § 5 , we conduct extensive experiments on synthetic benchmarks and 41 real-world datasets. The results demonstrate that RaDR substantially improves computational efficiency while maintaining competitive predictive performance, and that A-RaDR further improves prediction accuracy in the low-feature regime through adaptive feature selection.
Problem Setup and State-of-the-Art
In this section, we review the mathematical foundations of kernel mean embeddings and two-stage kernel distribution regression. After introducing their definitions and formulations, we highlight the computational bottlenecks that motivate the scalable approach introduced in the following sections.
Notation used throughout the paper
Before proceeding, we summarize the main notation used in the remainder of the paper. Scalars or functions are denoted by non-bold letters such as x x x , y y y , and k k k . Vectors are denoted by bold lower-case letters such as x \mathbf{x} x and y \mathbf{y} y , and matrices by bold upper-case letters such as X \mathbf{X} X and K \mathbf{K} K . Calligraphic letters such as X \mathcal{X} X , Y \mathcal{Y} Y , and H k \mathcal{H}_k H k denote spaces, sets, or function classes. Probability measures on a space X \mathcal{X} X are written as P \mathbb{P} P , Q \mathbb{Q} Q , while empirical bags are written as X i = { x i j } j = 1 N i \mathcal{X}_i = \{\mathbf{x}_{ij}\}_{j=1}^{N_i} X i = { x ij } j = 1 N i . We denote inner product with ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ , norm with ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ , expectation with E [ ⋅ ] \mathbb{E}[\cdot] E [ ⋅ ] , with appropriate subscripts specifying their associated space or measure.
We use n n n for the number of bags or distributions in the training set. The quantity N i N_i N i denotes the size of the i i i th training bag, and N t N_t N t denotes the test bag size. The embedding kernel is written as k k k , with RKHS H k \mathcal{H}_k H k , and the distribution kernel is written as K K K . The population embedding of P \mathbb{P} P is μ P \mu_{\mathbb{P}} μ P , while its empirical embedding from bag X i \mathcal{X}_i X i is μ ^ i \hat{\mu}_i μ ^ i .
Distribution regression as learning over probability measures
Distribution regression considers a supervised learning problem with inputs drawn from a collection of probability measures on an instance space X \mathcal{X} X and outputs taking values in Y ⊆ R \mathcal{Y} \subseteq\mathbb{R} Y ⊆ R for regression, or in a finite label space for classification. Let
( P i , y i ) ∈ M 1 + ( X ) × Y , i = 1 , … , n , (\mathbb{P}_i,y_i) \in\mathcal{M}_1^+(\mathcal{X}) \times\mathcal{Y}, \qquad i=1,\ldots,n, ( P i , y i ) ∈ M 1 + ( X ) × Y , i = 1 , … , n ,
denote the population-level training pairs, where M 1 + ( X ) \mathcal{M}_1^+(\mathcal{X}) M 1 + ( X ) is a suitable class of Borel probability measures on X \mathcal{X} X . The target is to learn a function
f ⋆ : M 1 + ( X ) → Y f^\star:\mathcal{M}_1^+(\mathcal{X}) \to\mathcal{Y} f ⋆ : M 1 + ( X ) → Y
from the observed training data and then predict the response associated with a new input distribution P \mathbb{P} P .
In practice, however, the distributions P i \mathbb{P}_i P i are not directly observed. Instead, for each i i i , one only observes a bag of samples
X i = { x i 1 , … , x i N i } , x i j ∼ i . i . d . P i , \mathcal{X}_i = \{\mathbf{x}_{i1},\ldots,\mathbf{x}_{iN_i}\}, \qquad\mathbf{x}_{ij} \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \mathbb{P}_i, X i = { x i 1 , … , x i N i } , x ij ∼ i.i.d. P i ,
where N i N_i N i is the bag size for the i i i th distribution. The actual training data therefore take the form
D n = { ( X i , y i ) } i = 1 n . \mathcal{D}_n = \{(\mathcal{X}_i,y_i)\}_{i=1}^{n}. D n = {( X i , y i ) } i = 1 n .
As mentioned in the beginning of this Section, we reserve n n n for the number of distributions, and N i N_i N i for the number of instances in bag i i i , since the distinction between these two sampling levels becomes important both computationally and statistically. In particular, later theoretical results will separately track the effect of finite bag sampling and finite random feature approximation.
Distribution regression formulation can therefore be stated as follows: given finitely many bags X 1 , … , X n \mathcal{X}_1,\ldots,\mathcal{X}_n X 1 , … , X n and corresponding responses y 1 , … , y n y_1,\ldots,y_n y 1 , … , y n , estimate a predictor f ^ \hat{f} f ^ such that f ^ ( X ) \hat{f}(\mathcal{X}) f ^ ( X ) approximates the response associated with the underlying distribution that generated the bag X \mathcal{X} X . In a nutshell, the covariates are latent probability measures, and the observed bags are noisy finite-sample surrogates for those measures.
Kernel mean embeddings of distributions
A standard nonparametric way to represent probability distributions is through kernel mean embeddings [48 , 40 ] . Let k : X × X → R k : \mathcal{X} \times\mathcal{X} \to\mathbb{R} k : X × X → R be a positive definite kernel with associated RKHS H k \mathcal{H}_k H k . For a distribution P ∈ M 1 + ( X ) \mathbb{P} \in\mathcal{M}^{+}_{1}(\mathcal{X}) P ∈ M 1 + ( X ) satisfying the usual integrability condition, its kernel mean embedding is defined as
μ P = ∫ X k ( x , ⋅ ) d P ( x ) ∈ H k . \mu_{\mathbb{P}} = \int_{\mathcal{X}} k(\mathbf{x},\cdot)\,\mathrm{d}\mathbb{P}(\mathbf{x}) \in\mathcal{H}_k. μ P = ∫ X k ( x , ⋅ ) d P ( x ) ∈ H k .
The embedding μ P \mu_{\mathbb{P}} μ P is the RKHS element that averages the feature map k ( x , ⋅ ) k(\mathbf{x},\cdot) k ( x , ⋅ ) under P \mathbb{P} P . Equivalently, for any h ∈ H k h \in\mathcal{H}_k h ∈ H k ,
⟨ h , μ P ⟩ H k = ∫ X h ( x ) d P ( x ) , \langle h,\mu_{\mathbb{P}}\rangle_{\mathcal{H}_k} = \int_{\mathcal{X}} h(\mathbf{x})\,\mathrm{d}\mathbb{P}(\mathbf{x}), ⟨ h , μ P ⟩ H k = ∫ X h ( x ) d P ( x ) ,
where ⟨ ⋅ , ⋅ ⟩ H k \langle\cdot,\cdot\rangle_{\mathcal{H}_k} ⟨ ⋅ , ⋅ ⟩ H k denotes the inner product in RKHS H k \mathcal{H}_k H k , so the mean embedding acts as a linear functional encoding expectations of RKHS test functions. When k k k is characteristic [53 , 46 ] , the map P ↦ μ P \mathbb{P} \mapsto\mu_{\mathbb{P}} P ↦ μ P is injective, meaning that the embedding uniquely determines the distribution. In another word, kernel mean embedding is lossless. This lossless embedding property is one of the key reasons behind the popularity of KME in distribution regression.
Since the population distributions are often not directly available in practice, one replaces μ P i \mu_{\mathbb{P}_i} μ P i by its empirical counterpart
μ ^ i = 1 N i ∑ j = 1 N i k ( x i j , ⋅ ) . \hat{\mu}_i = \frac{1}{N_i}\sum_{j=1}^{N_i} k(\mathbf{x}_{ij},\cdot). μ ^ i = N i 1 j = 1 ∑ N i k ( x ij , ⋅ ) .
This is simply the average feature map over the bag X i \mathcal{X}_i X i . The empirical embedding is unbiased for the population embedding and converges in RKHS norm under standard assumptions. Accordingly, the first stage of kernel distribution regression consists of replacing each latent distribution P i \mathbb{P}_i P i by the empirical element μ ^ i ∈ H k \hat{\mu}_i \in\mathcal{H}_k μ ^ i ∈ H k .
Kernels on embedded distributions
It is worth noting that in the distribution regression pipeline, there are usually two kernels involved. In the previous subsection, we have introduced the embedding kernel k k k acting on instances x ∈ X \mathbf{x} \in\mathcal{X} x ∈ X to represent distributions in H k \mathcal{H}_k H k . A second kernel, defined on these embedded objects, is then used for the downstream supervised task, we term the downstream supervised learning kernel as distribution kernel to differentiate it from embedding kernel k k k . Let K : H k × H k → R K : \mathcal{H}_k \times\mathcal{H}_k \to\mathbb{R} K : H k × H k → R be a positive definite kernel on the embedding space. Then the induced distribution kernel is K ( P , Q ) = K ( μ P , μ Q ) K(P, Q) = K(\mu_P, \mu_Q) K ( P , Q ) = K ( μ P , μ Q ) . In practice one uses the empirical approximation K ^ i j = K ( μ ^ i , μ ^ j ) \widehat{K}_{ij} = K(\widehat{\mu}_i, \widehat{\mu}_j) K ij = K ( μ i , μ j ) . A common and important example is the Gaussian kernel on the RKHS:
K ( μ , ν ) = exp ( − ∥ μ − ν ∥ H k 2 2 τ 2 ) , K(\mu, \nu) = \exp\left(-\frac{\lVert\mu-\nu\rVert_{\mathcal{H}_k}^{2}}{2\tau^{2}}\right), K ( μ , ν ) = exp ( − 2 τ 2 ∥ μ − ν ∥ H k 2 ) ,
where τ > 0 \tau> 0 τ > 0 is a bandwidth parameter. Since
∥ μ P − μ Q ∥ H k 2 = E x , x ′ ∼ P k ( x , x ′ ) + E z , z ′ ∼ Q k ( z , z ′ ) − 2 E x ∼ P , z ∼ Q k ( x , z ) , \lVert\mu_P-\mu_Q\rVert_{\mathcal{H}_k}^{2} = \mathbb{E}_{x,x'\sim P}k(x,x') + \mathbb{E}_{z,z'\sim Q}k(z,z') - 2\mathbb{E}_{x\sim P,z\sim Q}k(x,z), ∥ μ P − μ Q ∥ H k 2 = E x , x ′ ∼ P k ( x , x ′ ) + E z , z ′ ∼ Q k ( z , z ′ ) − 2 E x ∼ P , z ∼ Q k ( x , z ) ,
the induced kernel depends on pairwise embedding kernel evaluations across and within bags. Its empirical version is obtained by replacing expectations with bag averages:
∥ μ ^ i − μ ^ j ∥ H k 2 = 1 N i 2 ∑ a = 1 N i ∑ b = 1 N i k ( x i a , x i b ) + 1 N j 2 ∑ a = 1 N j ∑ b = 1 N j k ( x j a , x j b ) \lVert\widehat{\mu}_i-\widehat{\mu}_j\rVert_{\mathcal{H}_k}^{2} = \frac{1}{N_i^{2}}\sum_{a=1}^{N_i}\sum_{b=1}^{N_i}k(x_{ia},x_{ib}) + \frac{1}{N_j^{2}}\sum_{a=1}^{N_j}\sum_{b=1}^{N_j}k(x_{ja},x_{jb}) ∥ μ i − μ j ∥ H k 2 = N i 2 1 a = 1 ∑ N i b = 1 ∑ N i k ( x ia , x ib ) + N j 2 1 a = 1 ∑ N j b = 1 ∑ N j k ( x j a , x j b )
− 2 N i N j ∑ a = 1 N i ∑ b = 1 N j k ( x i a , x j b ) . -\frac{2}{N_iN_j}\sum_{a=1}^{N_i}\sum_{b=1}^{N_j}k(x_{ia},x_{jb}). − N i N j 2 a = 1 ∑ N i b = 1 ∑ N j k ( x ia , x j b ) .
This expression already reveals the main computational difficulty, that even a single distribution kernel evaluation requires summing over all cross-bag instance pairs.
More generally, the second-stage kernel K K K may be chosen according to the downstream task. Linear kernels, radial kernels, and others are all possible. In this paper, we will focus on the linear kernel K ( μ , ν ) = ⟨ μ , ν ⟩ H K K(\mu,\nu) = \langle\mu,\nu\rangle_{\mathcal{H}_K} K ( μ , ν ) = ⟨ μ , ν ⟩ H K , for theoretical analysis, and include Gaussian distribution kernel for numerical studies.
Two-stage distribution regression
The preceding construction leads to a natural two-stage learning paradigm (Szabó et al. [57 ] ). In the first stage, each input distribution is estimated from a finite bag through its empirical embedding, and transformed into an potentially infinite-dimensional RKHS representation via the embedding kernel k k k . In the second stage, a supervised kernel learning method is applied to the resulting embeddings via the distribution kernel K K K . For kernel ridge regression, this yields the predictor
f ^ ( P ) = ∑ i = 1 n α i K ( μ ^ i , μ P ) , \widehat{f}(\mathbb{P}) = \sum_{i=1}^{n}\alpha_iK(\widehat{\mu}_i,\mu_{\mathbb{P}}), f ( P ) = i = 1 ∑ n α i K ( μ i , μ P ) ,
where the coefficient vector α = ( α 1 , … , α n ) ⊤ \alpha= (\alpha_1,\ldots,\alpha_n)^{\top} α = ( α 1 , … , α n ) ⊤ solves
( K N + λ n I n ) α = y , (K_N+\lambda n I_n)\alpha= y, ( K N + λn I n ) α = y ,
with
( K N ) i j = K ( μ ^ i , μ ^ j ) , y = ( y 1 , … , y n ) ⊤ , (K_N)_{ij} = K(\widehat{\mu}_i,\widehat{\mu}_j), \qquad y = (y_1,\ldots,y_n)^{\top}, ( K N ) ij = K ( μ i , μ j ) , y = ( y 1 , … , y n ) ⊤ ,
and λ > 0 \lambda> 0 λ > 0 denotes the regularization parameter. For prediction from a test bag
X t = { x t 1 , … , x t N t } , \mathcal{X}_t = \{x_{t1},\ldots,x_{tN_t}\}, X t = { x t 1 , … , x t N t } ,
one first forms the empirical embedding
μ ^ t = 1 N t ∑ j = 1 N t k ( x t j , ⋅ ) , \hat{\mu}_t = \frac{1}{N_t}\sum_{j=1}^{N_t} k(x_{tj}, \cdot), μ ^ t = N t 1 j = 1 ∑ N t k ( x t j , ⋅ ) ,
and then evaluates
f ^ ( X t ) = ∑ i = 1 n α i K ( μ ^ i , μ ^ t ) . \hat{f}(\mathcal{X}_t) = \sum_{i=1}^{n} \alpha_i K(\hat{\mu}_i, \hat{\mu}_t). f ^ ( X t ) = i = 1 ∑ n α i K ( μ ^ i , μ ^ t ) .
Although we focus on kernel ridge regression for concreteness, the same representation can be coupled with other second-stage learners, including support vector machines [60 ] and other kernel methods.
Computational bottlenecks of exact kernel distribution regression
The exact KME-based formulation is statistically appealing due to its lossless embedding property [53 ] , but its computational cost can be even more prohibitive than instance-level kernel learning. To see this, consider first the construction of the distribution-level Gram matrix K N K_N K N . For each pair ( i , j ) (i,j) ( i , j ) , evaluating K ( μ ^ i , μ ^ j ) K(\hat{\mu}_i,\hat{\mu}_j) K ( μ ^ i , μ ^ j ) generally requires computing quantities of the form
∑ a = 1 N i ∑ b = 1 N j k ( x i a , x j b ) , \sum_{a=1}^{N_i}\sum_{b=1}^{N_j} k(x_{ia},x_{jb}), a = 1 ∑ N i b = 1 ∑ N j k ( x ia , x j b ) ,
together with corresponding within-bag sums. If the average bag size is of order N ˉ \bar{N} N ˉ , then a single entry of K N K_N K N may cost O ( N ˉ 2 ) O(\bar{N}^{2}) O ( N ˉ 2 ) operations, so forming the full n × n n \times n n × n matrix costs roughly O ( n 2 N ˉ 2 ) O(n^{2}\bar{N}^{2}) O ( n 2 N ˉ 2 ) in the balanced case. After this, solving the kernel ridge regression system requires O ( n 3 ) O(n^{3}) O ( n 3 ) time and O ( n 2 ) O(n^{2}) O ( n 2 ) memory in the standard implementation. Thus, unlike ordinary kernel regression on vector-valued inputs, distribution regression incurs a nested computational burden: a kernel method at the bag level built on top of kernel operations at the instance level.
Random Feature Distribution Regression
The computational challenge of kernel distribution regression is shared by kernel methods more broadly and has motivated a substantial literature on scalable kernel approximation [22 ] . Existing approaches include Nyström methods, randomized sketching techniques, and random feature approximations [64 , 67 , 34 , 17 , 69 , 42 ] (Li et al. 2014). Among these, random Fourier features are particularly attractive for shift-invariant kernels because they approximate the kernel function itself through an explicit finite-dimensional feature map rather than a low-rank approximation of the kernel matrix. This explicit representation naturally removes the need to store infinite-dimensional embeddings while preserving the favorable statistical properties of kernel learning [43 , 54 , 3 , 33 ] .
For distribution regression, random feature approximations replace implicit kernel mean embeddings with explicit finite-dimensional vectors. Each bag is represented by the average of its instances’ random features, and a supervised learner is fitted to the resulting bag representations. This construction has been used in earlier work on distribution regression, including ecological inference, approximate Bayesian computation, conformal prediction, and remote sensing [18 , 37 , 62 , 1 ] . We refer to this common construction as Random Feature Distribution Regression (RaDR) and develop its theoretical analysis under two-stage sampling.
We first introduce random feature approximations for the embedding kernel and construct explicit distribution embeddings. We then formulate RaDR for kernel ridge regression, analyze its computational complexity, and establish a perturbation-based excess-risk bound that separates three sources of error: finite distribution-level sampling, finite within-bag sampling, and random feature approximation. Based on this decomposition, we identify sufficient conditions under which RaDR achieves order-wise lossless approximation relative to exact kernel distribution regression. Finally, we extend the same perturbation framework to binary classification with soft-margin support vector machines (SVMs). Proofs are deferred to Appendix § 7 .
Random features for distribution embeddings
Recall from § 2 that exact kernel distribution regression represents a distribution P \mathbb{P} P by its kernel mean embedding μ P \mu_{\mathbb{P}} μ P and then applies a distribution kernel to these embeddings. We focus on the linear outer kernel
K ( P , Q ) = ⟨ μ P , μ Q ⟩ H k , (1) K(\mathbb{P}, \mathbb{Q}) = \langle\mu_{\mathbb{P}}, \mu_{\mathbb{Q}} \rangle_{\mathcal{H}_k}, \tag*{(1)} K ( P , Q ) = ⟨ μ P , μ Q ⟩ H k , (1)
which is already expressive when the base kernel k k k is characteristic, and it isolates the role of random feature approximation, since all approximation error enters through the mean embedding itself.
We focus on shift-invariant kernels of the form
k ( x , z ) = ψ ( x − z ) , x , z ∈ X ⊂ R d , k(\mathbf{x}, \mathbf{z}) = \psi(\mathbf{x} - \mathbf{z}), \qquad\mathbf{x}, \mathbf{z} \in\mathcal{X} \subset\mathbb{R}^{d}, k ( x , z ) = ψ ( x − z ) , x , z ∈ X ⊂ R d ,
normalized so that k ( x , x ) = 1 k(\mathbf{x}, \mathbf{x}) = 1 k ( x , x ) = 1 . By Bochner’s theorem [44 ] , there exists a probability measure Λ \Lambda Λ on R d \mathbb{R}^{d} R d such that
k ( x , z ) = ∫ R d cos { ω T ( x − z ) } d Λ ( ω ) = E ω [ cos { ω T ( x − z ) } ] . (2) k(\mathbf{x}, \mathbf{z}) = \int_{\mathbb{R}^{d}} \cos\{\boldsymbol{\omega}^{\mathsf{T}}(\mathbf{x} - \mathbf{z})\}\,\mathrm{d}\Lambda(\boldsymbol{\omega}) = \mathbb{E}_{\boldsymbol{\omega}}\left[\cos\{\boldsymbol{\omega}^{\mathsf{T}}(\mathbf{x} - \mathbf{z})\}\right]. \tag*{(2)} k ( x , z ) = ∫ R d cos { ω T ( x − z )} d Λ ( ω ) = E ω [ cos { ω T ( x − z )} ] . (2)
In practice, the random feature distribution Λ \Lambda Λ admits analytical forms for popular kernel choices, such as normal distribution for Gaussian kernel, and exponential distribution for Cauchy kernel. We refer the audience to [42 ] for more details. The expression in Eq. (2) reveals that a kernel function k ( x , z ) k(\mathbf{x}, \mathbf{z}) k ( x , z ) can be approximated via sampling random vectors from the probability measure Λ ( ω ) \Lambda(\boldsymbol{\omega}) Λ ( ω ) . Let
ω 1 , … , ω D ∼ i . i . d . Λ , b 1 , … , b D ∼ i . i . d . Unif [ 0 , 2 π ] , \boldsymbol{\omega}_1, \ldots, \boldsymbol{\omega}_D \overset{\mathrm{i.i.d.}}{\sim} \Lambda,\qquad b_1, \ldots, b_D \overset{\mathrm{i.i.d.}}{\sim} \operatorname{Unif}[0, 2\pi], ω 1 , … , ω D ∼ i.i.d. Λ , b 1 , … , b D ∼ i.i.d. Unif [ 0 , 2 π ] ,
independently. Define
ϕ D ( x ) = 2 D ( cos ( ω 1 T x + b 1 ) , … , cos ( ω D T x + b D ) ) T ∈ R D . (3) \phi_D(\mathbf{x}) = \sqrt{\frac{2}{D}}\left(\cos(\boldsymbol{\omega}_1^{\mathsf{T}}\mathbf{x} + b_1), \ldots, \cos(\boldsymbol{\omega}_D^{\mathsf{T}}\mathbf{x} + b_D)\right)^{\mathsf{T}} \in\mathbb{R}^{D}. \tag*{(3)} ϕ D ( x ) = D 2 ( cos ( ω 1 T x + b 1 ) , … , cos ( ω D T x + b D ) ) T ∈ R D . (3)
We then construct the corresponding random feature kernel as
k D ( x , z ) = ⟨ ϕ D ( x ) , ϕ D ( z ) ⟩ 2 = 2 D ∑ r = 1 D cos ( ω r T x + b r ) cos ( ω r T z + b r ) ≈ k ( x , z ) . (4) k_D(\mathbf{x},\mathbf{z})=\langle\boldsymbol{\phi}_D(\mathbf{x}),\boldsymbol{\phi}_D(\mathbf{z})\rangle_2=\frac{2}{D}\sum_{r=1}^{D}\cos(\boldsymbol{\omega}_r^{\mathsf{T}}\mathbf{x}+b_r)\cos(\boldsymbol{\omega}_r^{\mathsf{T}}\mathbf{z}+b_r)\approx k(\mathbf{x},\mathbf{z}). \tag*{(4)} k D ( x , z ) = ⟨ ϕ D ( x ) , ϕ D ( z ) ⟩ 2 = D 2 r = 1 ∑ D cos ( ω r T x + b r ) cos ( ω r T z + b r ) ≈ k ( x , z ) . (4)
The approximation holds by noticing the random-bias construction is unbiased through
E b [ 2 cos ( ω T x + b ) cos ( ω T z + b ) ] = cos { ω T ( x − z ) } , \mathbb{E}_b\left[2\cos(\boldsymbol{\omega}^{\mathsf{T}}\mathbf{x}+b)\cos(\boldsymbol{\omega}^{\mathsf{T}}\mathbf{z}+b)\right]=\cos\{\boldsymbol{\omega}^{\mathsf{T}}(\mathbf{x}-\mathbf{z})\}, E b [ 2 cos ( ω T x + b ) cos ( ω T z + b ) ] = cos { ω T ( x − z )} ,
and hence
E ω , b [ k D ( x , z ) ] = k ( x , z ) . \mathbb{E}_{\boldsymbol{\omega},b}[k_D(\mathbf{x},\mathbf{z})]=k(\mathbf{x},\mathbf{z}). E ω , b [ k D ( x , z )] = k ( x , z ) .
For a distribution P \mathbb{P} P , we can define its random feature distribution embedding by
μ P , D = ∫ X ϕ D ( x ) d P ( x ) ∈ R D . (5) \boldsymbol{\mu}_{\mathbb{P},D}=\int_{\mathcal{X}}\boldsymbol{\phi}_D(\mathbf{x})\,\mathrm{d}\mathbb{P}(\mathbf{x})\in\mathbb{R}^{D}. \tag*{(5)} μ P , D = ∫ X ϕ D ( x ) d P ( x ) ∈ R D . (5)
If P i \mathbb{P}_i P i is observed only through a bag
X i = { x i 1 , … , x i N i } , x i j ∼ i . i . d . P i , \mathcal{X}_i=\{\mathbf{x}_{i1},\ldots,\mathbf{x}_{iN_i}\},\qquad\mathbf{x}_{ij}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mathbb{P}_i, X i = { x i 1 , … , x i N i } , x ij ∼ i.i.d. P i ,
then the empirical RF embedding is
μ ^ i , D = 1 N i ∑ j = 1 N i ϕ D ( x i j ) ∈ R D . (6) \widehat{\boldsymbol{\mu}}_{i,D}=\frac{1}{N_i}\sum_{j=1}^{N_i}\boldsymbol{\phi}_D(\mathbf{x}_{ij})\in\mathbb{R}^{D}. \tag*{(6)} μ i , D = N i 1 j = 1 ∑ N i ϕ D ( x ij ) ∈ R D . (6)
Accordingly, the RF approximation to the linear distribution kernel is
K D ( P , Q ) = ⟨ μ P , D , μ Q , D ⟩ 2 , (7) K_D(\mathbb{P},\mathbb{Q})=\langle\boldsymbol{\mu}_{\mathbb{P},D},\boldsymbol{\mu}_{\mathbb{Q},D}\rangle_2, \tag*{(7)} K D ( P , Q ) = ⟨ μ P , D , μ Q , D ⟩ 2 , (7)
and its empirical version is
K ^ D ( X i , X j ) = ⟨ μ ^ i , D , μ ^ j , D ⟩ 2 . (8) \widehat{K}_D(\mathcal{X}_i,\mathcal{X}_j)=\langle\widehat{\boldsymbol{\mu}}_{i,D},\widehat{\boldsymbol{\mu}}_{j,D}\rangle_2. \tag*{(8)} K D ( X i , X j ) = ⟨ μ i , D , μ j , D ⟩ 2 . (8)
The above construction converts the distribution representation from an RKHS-valued object to a finite-dimensional vector. Next, we construct RaDR under kernel ridge regression.
RaDR for kernel ridge regression
We now formulate RaDR for kernel ridge regression. For simplicity, this subsection assumes a common training bag size N i = N N_i=N N i = N ; the implementation and the empirical studies do not pertain to this restriction.
Let
M ^ D = [ μ ^ 1 , D T ⋮ μ ^ n , D T ] ∈ R n × D , y = ( y 1 , … , y n ) T . (9) \widehat{\mathbf{M}}_D=
\begin{bmatrix}
\widehat{\boldsymbol{\mu}}_{1,D}^{\mathsf{T}}\\
\vdots\\
\widehat{\boldsymbol{\mu}}_{n,D}^{\mathsf{T}}
\end{bmatrix}
\in\mathbb{R}^{n\times D},
\qquad
\mathbf{y}=(y_1,\ldots,y_n)^{\mathsf{T}}. \tag*{(9)} M D = μ 1 , D T ⋮ μ n , D T ∈ R n × D , y = ( y 1 , … , y n ) T . (9)
The RF Gram matrix over distributions is
K ^ D , N = M ^ D M ^ D T ∈ R n × n . (10) \widehat{\mathbf{K}}_{D,N}=\widehat{\mathbf{M}}_D\widehat{\mathbf{M}}_D^{\mathsf{T}}\in\mathbb{R}^{n\times n}. \tag*{(10)} K D , N = M D M D T ∈ R n × n . (10)
For a test distribution P \mathbb{P} P , define
v ^ D , N ( P ) = ( ⟨ μ ^ 1 , D , μ P , D ⟩ 2 , … , ⟨ μ ^ n , D , μ P , D ⟩ 2 ) T . \widehat{\mathbf{v}}_{D,N}(\mathbb{P})=\left(\left\langle\widehat{\boldsymbol{\mu}}_{1,D},\boldsymbol{\mu}_{\mathbb{P},D}\right\rangle_{2},\ldots,\left\langle\widehat{\boldsymbol{\mu}}_{n,D},\boldsymbol{\mu}_{\mathbb{P},D}\right\rangle_{2}\right)^{\mathsf{T}}. v D , N ( P ) = ( ⟨ μ 1 , D , μ P , D ⟩ 2 , … , ⟨ μ n , D , μ P , D ⟩ 2 ) T .
The RaDR kernel ridge predictor is
f ^ λ , N , D ( P ) = v ^ D , N ( P ) T ( K ^ D , N + n λ I n ) − 1 y . (11) \widehat{f}_{\lambda,N,D}(\mathbb{P})=\widehat{\mathbf{v}}_{D,N}(\mathbb{P})^{\mathsf{T}}\left(\widehat{\mathbf{K}}_{D,N}+n\lambda\mathbf{I}_{n}\right)^{-1}\mathbf{y}. \tag*{(11)} f λ , N , D ( P ) = v D , N ( P ) T ( K D , N + nλ I n ) − 1 y . (11)
If the test distribution is observed only through a test bag
X t = { x t 1 , … , x t N t } , x t j ∼ i . i . d . P , \mathcal{X}_{t}=\{\mathbf{x}_{t1},\ldots,\mathbf{x}_{tN_t}\},\qquad\mathbf{x}_{tj}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mathbb{P}, X t = { x t 1 , … , x t N t } , x t j ∼ i.i.d. P ,
then μ P , D \boldsymbol{\mu}_{\mathbb{P},D} μ P , D is replaced by
μ ^ t , D = 1 N t ∑ j = 1 N t ϕ D ( x t j ) . \widehat{\boldsymbol{\mu}}_{t,D}=\frac{1}{N_t}\sum_{j=1}^{N_t}\boldsymbol{\phi}_{D}(\mathbf{x}_{tj}). μ t , D = N t 1 j = 1 ∑ N t ϕ D ( x t j ) .
The finite-dimensional representation also gives a primal form. Since
f ^ λ , N , D ( P ) = ⟨ w ^ λ , N , D , μ P , D ⟩ 2 , \widehat{f}_{\lambda,N,D}(\mathbb{P})=\left\langle\widehat{\mathbf{w}}_{\lambda,N,D},\boldsymbol{\mu}_{\mathbb{P},D}\right\rangle_{2}, f λ , N , D ( P ) = ⟨ w λ , N , D , μ P , D ⟩ 2 ,
where
w ^ λ , N , D = M ^ D T ( M ^ D M ^ D T + n λ I n ) − 1 y , (12) \widehat{\mathbf{w}}_{\lambda,N,D}=\widehat{\mathbf{M}}_{D}^{\mathsf{T}}\left(\widehat{\mathbf{M}}_{D}\widehat{\mathbf{M}}_{D}^{\mathsf{T}}+n\lambda\mathbf{I}_{n}\right)^{-1}\mathbf{y}, \tag*{(12)} w λ , N , D = M D T ( M D M D T + nλ I n ) − 1 y , (12)
we may equivalently compute
w ^ λ , N , D = ( M ^ D T M ^ D + n λ I D ) − 1 M ^ D T y , (13) \widehat{\mathbf{w}}_{\lambda,N,D}=\left(\widehat{\mathbf{M}}_{D}^{\mathsf{T}}\widehat{\mathbf{M}}_{D}+n\lambda\mathbf{I}_{D}\right)^{-1}\widehat{\mathbf{M}}_{D}^{\mathsf{T}}\mathbf{y}, \tag*{(13)} w λ , N , D = ( M D T M D + nλ I D ) − 1 M D T y , (13)
via the Woodbury inversion lemma (push-through identity). This primal representation is one of the key computational advantages of RaDR, as exact kernel distribution regression must work with an n × n n \times n n × n Gram matrix whose entries require pairwise within-bag kernel computations. RaDR instead constructs a D D D -dimensional mean embedding vector for each bag and then performs ordinary finite-dimensional ridge regression. Next, we provide a brief discussion on the computational advantage of RaDR.
Computation and scalability
The computational difference between exact kernel distribution regression and RaDR can be seen directly from the construction of the Gram matrix. In the balanced case N i = N N_i=N N i = N , evaluating one exact linear distribution-kernel entry requires
K N ( X i , X j ) = 1 N 2 ∑ a = 1 N ∑ b = 1 N k ( x i a , x j b ) , K_N(\mathcal{X}_i,\mathcal{X}_j)=\frac{1}{N^2}\sum_{a=1}^{N}\sum_{b=1}^{N}k(\mathbf{x}_{ia},\mathbf{x}_{jb}), K N ( X i , X j ) = N 2 1 a = 1 ∑ N b = 1 ∑ N k ( x ia , x j b ) ,
and therefore costs O ( N 2 ) O(N^2) O ( N 2 ) kernel evaluations. Constructing the full n × n n \times n n × n Gram matrix costs O ( n 2 N 2 ) O(n^2N^2) O ( n 2 N 2 ) embedding kernel evaluations, followed by an O ( n 3 ) O(n^3) O ( n 3 ) inversion computation induced by Eq. (12) .
By contrast, RaDR first constructs the bag embeddings
μ ^ i , D = 1 N ∑ j = 1 N ϕ D ( x i j ) , \widehat{\mu}_{i,D} = \frac{1}{N}\sum_{j=1}^{N}\phi_D(x_{ij}), μ i , D = N 1 j = 1 ∑ N ϕ D ( x ij ) ,
which costs O ( n N D ) O(nND) O ( n N D ) random feature evaluations. Once these embeddings are computed, forming the RF Gram matrix costs O ( n 2 D ) O(n^2D) O ( n 2 D ) if done explicitly, while the primal ridge formulation in Eq. (13) costs O ( n D 2 + D 3 ) O(nD^2 + D^3) O ( n D 2 + D 3 ) when D ≲ n D \lesssim n D ≲ n , and the dual formulation costs O ( n 2 D + n 3 ) O(n^2D + n^3) O ( n 2 D + n 3 ) for D ≳ n D \gtrsim n D ≳ n , where ≲ , ≳ \lesssim, \gtrsim ≲ , ≳ denotes less/greater than or similar to in order.
In a nutshell, in the regime where D ≲ n D \lesssim n D ≲ n and D ≲ N 2 D \lesssim N^2 D ≲ N 2 , RaDR replaces the nested pairwise computation of exact kernel distribution regression by a linear pass through the instances followed by finite-dimensional supervised learning. This un-nesting property reduces computational complexity from O ( n 2 N 2 + n 3 ) O(n^2N^2+n^3) O ( n 2 N 2 + n 3 ) to O ( n N D + n 2 D + D 3 ) O(nND+n^2D+D^3) O ( n N D + n 2 D + D 3 ) , which is even more drastic than the speed up of random features for vector kernel ridge regression.
Moreover, RaDR also supports incremental computation. If a new instance x i , N + 1 x_{i,N+1} x i , N + 1 is added to bag i i i , the empirical RF embedding can be updated as
μ ^ i , D N + 1 = N N + 1 μ ^ i , D N + 1 N + 1 ϕ D ( x i , N + 1 ) . \widehat{\mu}_{i,D}^{N+1} = \frac{N}{N+1}\widehat{\mu}_{i,D}^{N} + \frac{1}{N+1}\phi_D(x_{i,N+1}). μ i , D N + 1 = N + 1 N μ i , D N + N + 1 1 ϕ D ( x i , N + 1 ) .
Thus the distribution representation can be maintained online without recomputing all pairwise kernel values. This property becomes especially relevant when distribution-valued inputs are generated from streaming systems or large collections of instances.
Risk analysis for RaDR
We next state the main risk bound for RaDR. The proof is given in Appendix § 7 . Let R [ f ] \mathcal{R}[f] R [ f ] denote the squared-loss population risk and let
E ( f , f ρ ) = R [ f ] − R [ f ρ ] \mathcal{E}(f,f_{\rho}) = \mathcal{R}[f] - \mathcal{R}[f_{\rho}] E ( f , f ρ ) = R [ f ] − R [ f ρ ]
be the excess risk, where f ρ f_{\rho} f ρ denotes the optimal population predictor. We use f ^ λ \widehat{f}_{\lambda} f λ for the ideal one-stage KRR estimator that observes the true population embeddings, f ^ λ , N \widehat{f}_{\lambda,N} f λ , N for the exact two-stage estimator that uses finite training bags but no random features, and f ^ λ , N , D \widehat{f}_{\lambda,N,D} f λ , N , D for the RaDR estimator. The analysis is built on the following decomposition
f ^ λ , N , D − f ρ = ( f ^ λ − f ρ ) + ( f ^ λ , N − f ^ λ ) + ( f ^ λ , N , D − f ^ λ , N ) . \widehat{f}_{\lambda,N,D} - f_{\rho} = (\widehat{f}_{\lambda} - f_{\rho}) + (\widehat{f}_{\lambda,N} - \widehat{f}_{\lambda}) + (\widehat{f}_{\lambda,N,D} - \widehat{f}_{\lambda,N}). f λ , N , D − f ρ = ( f λ − f ρ ) + ( f λ , N − f λ ) + ( f λ , N , D − f λ , N ) .
The first term is the ordinary one-stage KRR statistical error. The second term is the finite-bag perturbation already present in exact kernel distribution regression. The third term is the new RF approximation perturbation introduced by RaDR.
We first state the one-stage exact-kernel bound abstractly. We assume there exists a function B 1 s ( n , λ , δ ) B_{1\mathrm{s}}(n,\lambda,\delta) B 1 s ( n , λ , δ ) such that, with probability at least 1 − δ 1-\delta 1 − δ ,
E ( f ^ λ , f ρ ) ≤ B 1 s ( n , λ , δ ) , \mathcal{E}(\widehat{f}_{\lambda},f_{\rho}) \le B_{1\mathrm{s}}(n,\lambda,\delta), E ( f λ , f ρ ) ≤ B 1 s ( n , λ , δ ) ,
the assumption is formally stated in the Appendix. The quantity B 1 s ( n , λ , δ ) B_{1\mathrm{s}}(n,\lambda,\delta) B 1 s ( n , λ , δ ) is an abstraction that represents a standard one-stage excess-risk bound for kernel ridge regression (KRR). Such bounds are well studied in the classical source-capacity framework for nonparametric regression; see, for example, Zhang [68 ] and Caponnetto and De Vito [10 ] . This abstraction allows the RaDR perturbation analysis to be combined with any valid one-stage KRR theorem under the desired source and capacity conditions. We provide a concrete example for B 1 s ( n , λ , δ ) B_{1\mathrm{s}}(n,\lambda,\delta) B 1 s ( n , λ , δ ) in the Appendix. With this abstraction, we now state the following theorem.
Theorem 1. Under the boundedness, source, and one-stage baseline conditions stated in Appendix § 7 , there exists a constant C 2 > 0 C_2 > 0 C 2 > 0 , independent of n n n , N N N , λ \lambda λ , δ \delta δ , such that, with probability at least 1 − δ 1-\delta 1 − δ ,
E ( f ^ λ , N , f ρ ) ≤ 2 B 1 s ( n , λ , δ / 2 ) + C 2 [ log ( 2 n / δ ) N λ 2 + log ( 2 n / δ ) N λ 4 ] . (14) \mathcal{E}(\widehat{f}_{\lambda,N},f_\rho) \le2B_{1\mathrm{s}}(n,\lambda,\delta/2)+C_2\left[\frac{\log(2n/\delta)}{N\lambda^2}+\frac{\log(2n/\delta)}{N\lambda^4}\right]. \tag*{(14)} E ( f λ , N , f ρ ) ≤ 2 B 1 s ( n , λ , δ /2 ) + C 2 [ N λ 2 log ( 2 n / δ ) + N λ 4 log ( 2 n / δ ) ] . (14)
Theorem 1 provides a rate bound baseline for the exact kernel distribution regression problem. Our bound is a self-contained alternative to Szabó et al. [57 ] ’s result, where we separate the one-stage learning and the finite sample effect for clarity. Next, we present the excess-risk bound for RaDR.
Theorem 2. Under the boundedness, spectral moment, source, and one-stage baseline conditions stated in Appendix § 7 , let ϵ D ( δ ) \epsilon_D(\delta) ϵ D ( δ ) denote the uniform random feature approximation radius defined in Appendix § 7 . Then there exists a constant C 3 > 0 C_3 > 0 C 3 > 0 , independent of n n n , N N N , D D D , λ \lambda λ , δ \delta δ , such that, with probability at least 1 − δ 1-\delta 1 − δ ,
E ( f ^ λ , N , D , f ρ ) ≤ 4 B 1 s ( n , λ , δ / 3 ) + C 3 [ log ( 3 n / δ ) N λ 2 + log ( 3 n / δ ) N λ 4 + ϵ D ( δ / 3 ) 2 λ 2 + ϵ D ( δ / 3 ) 2 λ 4 ] . (15) \begin{aligned}
\mathcal{E}(\widehat{f}_{\lambda,N,D},f_\rho) &\le4B_{1\mathrm{s}}(n,\lambda,\delta/3) \\
&\quad+ C_3\left[\frac{\log(3n/\delta)}{N\lambda^2}+\frac{\log(3n/\delta)}{N\lambda^4}+\frac{\epsilon_D(\delta/3)^2}{\lambda^2}+\frac{\epsilon_D(\delta/3)^2}{\lambda^4}\right]. \tag*{(15)}
\end{aligned} E ( f λ , N , D , f ρ ) ≤ 4 B 1 s ( n , λ , δ /3 ) + C 3 [ N λ 2 log ( 3 n / δ ) + N λ 4 log ( 3 n / δ ) + λ 2 ϵ D ( δ /3 ) 2 + λ 4 ϵ D ( δ /3 ) 2 ] . (15)
Theorem 2 folds the random feature approximation effect into the exact kernel distribution regression excess-risk bound in Theorem 1. The first term is the one-stage learning error over true distribution embeddings. The second and third terms are the price of observing each distribution through only N N N samples. The last two terms are the price of replacing the exact RKHS embedding by D D D random feature basis. The regularization term λ \lambda λ plays an important role in interpreting the results. A smaller λ \lambda λ improves approximation bias in kernel ridge regression, but it amplifies both the finite-bag perturbation and the random-feature perturbation.
Based on the above two Theorem statements, we further provide an additional result on test distribution finite sample effect in the Appendix.
Remark 1. Theorems 1 and 2 are population excess-risk statements that evaluate predictors on true test distributions. In deployment, a fresh test distribution is typically observed only through a test bag of size N t N_t N t . Appendix § 7 .9 shows that this creates an additional pointwise perturbation of order N t − 1 / 2 N_t^{-1/2} N t − 1/2 with a single factor λ − 1 \lambda^{-1} λ − 1 .
Order-wise No-loss regimes
From Theorems 1 and 2, one can observe that RaDR is able to achieve the same order wise excess-risk upper bound when the finite sample terms are order wise equal to the random feature approximation terms. Specifically, RaDR is in a no-loss regime whenever
ϵ D ( δ / 3 ) 2 ( λ − 2 + λ − 4 ) ≲ log ( 3 n / δ ) N ( λ − 2 + λ − 4 ) . (16) \epsilon_D(\delta/3)^2(\lambda^{-2}+\lambda^{-4}) \lesssim\frac{\log(3n/\delta)}{N}(\lambda^{-2}+\lambda^{-4}). \tag*{(16)} ϵ D ( δ /3 ) 2 ( λ − 2 + λ − 4 ) ≲ N log ( 3 n / δ ) ( λ − 2 + λ − 4 ) . (16)
where ≃ \simeq ≃ denotes asymptotic equivalence. Therefore, one can show that a sufficient condition for Eq. (16) to hold is
ϵ D ( δ / 3 ) 2 ≤ C 0 log ( 3 n / δ ) N . (17) \epsilon_D(\delta/3)^2 \le C_0\frac{\log(3n/\delta)}{N}. \tag*{(17)} ϵ D ( δ /3 ) 2 ≤ C 0 N log ( 3 n / δ ) . (17)
Proposition 2 of Sutherland and Schneider [55 ] gives a uniform kernel-approximation bound on a compact instance domain under a finite second spectral moment. Consequently, for fixed δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and fixed kernel parameters, there exists a constant C δ > 0 C_\delta> 0 C δ > 0 such that
ϵ D ( δ / 3 ) 2 ≤ C δ log ( e D ) D , \epsilon_D(\delta/3)^2 \le C_\delta\frac{\log(eD)}{D}, ϵ D ( δ /3 ) 2 ≤ C δ D log ( eD ) ,
for all sufficiently large D D D . e e e here is the base of natural logarithm. The derivation is included in the Appendix. Hence a convenient sufficient feature-budget condition is
log ( e D ) D ≲ log n N , (18) \frac{\log(eD)}{D} \lesssim\frac{\log n}{N}, \tag*{(18)} D log ( eD ) ≲ N log n , (18)
which is true when D ≃ N D \simeq N D ≃ N . Based on the above observation, we next state the following Corollary.
Corollary 1. Under the assumptions of Theorem 2, fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Suppose that N → ∞ N \to\infty N → ∞ as n → ∞ n \to\infty n → ∞ , N ≤ n p N \le n^p N ≤ n p for some fixed p > 0 p > 0 p > 0 , and D ≃ N D \simeq N D ≃ N . Let λ = λ n > 0 \lambda= \lambda_n > 0 λ = λ n > 0 satisfy the chosen one-stage baseline conditions at confidence level δ / 3 \delta/3 δ /3 . Then RaDR preserves the exact two-stage upper-bound order with probability at least 1 − δ 1-\delta 1 − δ for all sufficiently large n n n .
Moreover, denoting the computational complexity of RaDR with T R a D R T_{\mathrm{RaDR}} T RaDR , and exact kernel distribution regression with T e x a c t T_{\mathrm{exact}} T exact , choosing the less expensive primal or dual formulation gives
T R a D R = O ( n N 2 ) , T e x a c t = Θ ( n 2 N 2 + n 3 ) , T_{\mathrm{RaDR}} = O(nN^2), \qquad T_{\mathrm{exact}} = \Theta(n^2N^2+n^3), T RaDR = O ( n N 2 ) , T exact = Θ ( n 2 N 2 + n 3 ) , therefore,
T R a D R / T e x a c t = O ( n − 1 ) . T_{\mathrm{RaDR}}/T_{\mathrm{exact}} = O(n^{-1}). T RaDR / T exact = O ( n − 1 ) .
The proof of Corollary 1 is given in Appendix § 7 .10. Corollary 1 provides an important insight that RaDR can achieve a significant speed up while provably preserving the exact order-wise excess-risk upper bound of two-stage kernel distribution regression. At the same number of bags and instances per bag, the training cost decreases at the rate of O ( n − 1 ) O(n^{-1}) O ( n − 1 ) . This result is true regardless of whether D ≲ n D \lesssim n D ≲ n is true or not. Moreover, the above Corollary is a conservative characterization of the computational speed up for RaDR. As we will show later on in the empirical results, RaDR training time remains significantly shorter than that of exact kernel distribution regression when D D D is larger than both N N N and n n n , while the performance gap vanishes.
Extension to binary classification
Theoretical properties of kernel distribution regression are predominantly presented in terms of kernel ridge regression, yet one of the most common usages of kernel distribution regression is for classification Kachaiev and Recanatesi [24 ] . Therefore, in this subsection, we briefly discuss how the RaDR construction extends to binary classification with soft-margin SVM. Let y i ∈ { − 1 , + 1 } y_i \in\{-1,+1\} y i ∈ { − 1 , + 1 } and consider the hinge loss
ℓ h ( u ) = ( 1 − u ) + . \ell_h(u) = (1-u)_+. ℓ h ( u ) = ( 1 − u ) + .
We investigate RaDR SVM under a linear SVM on the RF distribution embeddings:
J n , N , D ( β ) = 1 n ∑ i = 1 n ℓ h ( y i β ⊤ μ ^ i , D ) + λ 2 ∥ β ∥ 2 2 . (19) \mathcal{J}_{n,N,D}(\boldsymbol{\beta}) = \frac{1}{n}\sum_{i=1}^{n}\ell_h(y_i\boldsymbol{\beta}^{\top}\widehat{\boldsymbol{\mu}}_{i,D}) + \frac{\lambda}{2}\lVert\boldsymbol{\beta}\rVert_2^2. \tag*{(19)} J n , N , D ( β ) = n 1 i = 1 ∑ n ℓ h ( y i β ⊤ μ i , D ) + 2 λ ∥ β ∥ 2 2 . (19)
In this case, the same finite-dimensional representation used for RaDR regression also provides a scalable distribution classifier. For the RF approximation, it is useful to compare the exact and RF SVM objectives through their duals. Let
Y = diag ( y 1 , … , y n ) , A = { α ∈ R n : 0 ≤ α i ≤ 1 / n } . Y = \operatorname{diag}(y_1,\ldots,y_n), \qquad\mathcal{A} = \{\boldsymbol{\alpha}\in\mathbb{R}^n: 0\leq\alpha_i\leq1/n\}. Y = diag ( y 1 , … , y n ) , A = { α ∈ R n : 0 ≤ α i ≤ 1/ n } .
The exact two-stage SVM dual is
D N ( α ) = ∑ i = 1 n α i − 1 2 λ α ⊤ Y K N Y α , α ∈ A , (20) \mathcal{D}_N(\boldsymbol{\alpha}) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2\lambda}\boldsymbol{\alpha}^{\top}Y\mathbf{K}_N Y\boldsymbol{\alpha}, \qquad\boldsymbol{\alpha}\in\mathcal{A}, \tag*{(20)} D N ( α ) = i = 1 ∑ n α i − 2 λ 1 α ⊤ Y K N Y α , α ∈ A , (20)
where K N \mathbf{K}_N K N is the exact empirical distribution-kernel matrix. The RF dual replaces K N \mathbf{K}_N K N by K ^ D , N \widehat{\mathbf{K}}_{D,N} K D , N :
D N , D ( α ) = ∑ i = 1 n α i − 1 2 λ α ⊤ Y K ^ D , N Y α . (21) \mathcal{D}_{N,D}(\boldsymbol{\alpha}) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2\lambda}\boldsymbol{\alpha}^{\top}Y\widehat{\mathbf{K}}_{D,N}Y\boldsymbol{\alpha}. \tag*{(21)} D N , D ( α ) = i = 1 ∑ n α i − 2 λ 1 α ⊤ Y K D , N Y α . (21)
Proposition 3. Suppose the element wise RF approximation error satisfies
max 1 ≤ i , j ≤ n ∣ [ K ^ D , N ] i j − [ K N ] i j ∣ ≤ ϵ D , \max_{1\leq i,j\leq n}\left\lvert[\widehat{\mathbf{K}}_{D,N}]_{ij}-[\mathbf{K}_N]_{ij}\right\rvert\leq\epsilon_D, 1 ≤ i , j ≤ n max [ K D , N ] ij − [ K N ] ij ≤ ϵ D , the exact and RF SVM dual objectives satisfy
sup α ∈ A ∣ D N , D ( α ) − D N ( α ) ∣ ≤ ϵ D 2 λ . (22) \sup_{\boldsymbol{\alpha}\in\mathcal{A}}\left\lvert\mathcal{D}_{N,D}(\boldsymbol{\alpha})-\mathcal{D}_N(\boldsymbol{\alpha})\right\rvert\leq\frac{\epsilon_D}{2\lambda}. \tag*{(22)} α ∈ A sup ∣ D N , D ( α ) − D N ( α ) ∣ ≤ 2 λ ϵ D . (22) Consequently, the corresponding optimal dual objective values differ by at most ϵ D / ( 2 λ ) \epsilon_D/(2\lambda) ϵ D / ( 2 λ ) .
Proposition 3 establishes that, under uniform kernel approximation, the RF SVM dual objective remains close to the exact two-stage SVM dual objective. As for a complete excess-risk theorem mirroring Theorem 2, we leave it to future extensions.
Enable Adaptivity with Score-based Random Features
In Section 3, we analyze RaDR under two-stage sampling and characterized the relationship between its feature budget, excess-risk upper bound, and computational cost. Beyond their computational advantages, random features possess another important property that distinguishes them from other kernel approximation methods. Unlike Nystrom approximations or randomized sketching methods, whose approximations are largely determined by sampled columns or matrix structure, random features are generated directly from an explicit sampling distribution over the kernel’s spectral measure. This explicit representation naturally permits the feature distribution to be modified, reweighted, or selectively sampled while maintaining a finite-dimensional embedding, making random features particularly well suited for adaptive kernel learning ([42 , 43 , 54 , 3 , 33 , 65 ] ).
The importance of adaptivity stems from a fundamental characteristic of kernel methods: their statistical performance is closely tied to the choice of kernel ([49 , 22 ] ). Consequently, a substantial body of work has studied kernel learning and multiple kernel learning to better align kernel representations with the underlying data geometry or downstream prediction task ([14 , 27 , 5 , 50 , 12 ] ). While effective, these approaches often require repeated kernel construction or additional optimization procedures, potentially diminishing the computational benefits offered by scalable kernel approximations.
A particularly relevant direction is score-based random feature sampling. Instead of drawing random features solely from the original spectral measure, these methods modify the feature distribution according to task-specific information such as prediction objectives, kernel leverage, or alignment criteria ([47 , 3 ] (Shahrampour et al. 2018)). This viewpoint bridges kernel approximation and kernel learning: the same finite-dimensional representation that enables scalability can also be adapted to allocate computational resources toward features that are most informative for prediction.
Motivated by this perspective, we propose Adaptive Random Feature Distribution Regression (A-RaDR), a score-guided extension of RaDR that incorporates adaptive feature selection into distribution regression. The framework expresses established criteria—including kernel alignment Sinha and Duchi [47 ] , leverage scores ([33 ] ), and distribution variance ([24 ] )—through a common score-matrix formulation applied to distribution embeddings. These scores guide the selection of a feature subset from a candidate pool, allowing the representation to adapt to the chosen criterion within the same finite-dimensional RaDR framework.
The two-stage random feature sampling formulation
We continue with the random-bias cosine features introduced in § 3.1 . For simplicity, we denote a frequency–bias pair by η = ( ω , b ) \eta=(\boldsymbol{\omega},b) η = ( ω , b ) and its sampling distribution by π = Λ ⊗ Unif [ 0 , 2 π ] \pi=\Lambda\otimes\operatorname{Unif}[0,2\pi] π = Λ ⊗ Unif [ 0 , 2 π ] . To examine the contribution of an individual feature, we further denote its population and empirical averages by
z P ( η ) = 2 ∫ X cos ( ω T x + b ) d P ( x ) , (23) z_{\mathbb{P}}(\eta)=\sqrt{2}\int_{\mathcal{X}}\cos(\boldsymbol{\omega}^{\mathsf{T}}\mathbf{x}+b)\,\mathrm{d}\mathbb{P}(\mathbf{x}), \tag*{(23)} z P ( η ) = 2 ∫ X cos ( ω T x + b ) d P ( x ) , (23)
z ^ i ( η ) = 2 N i ∑ j = 1 N i cos ( ω T x i j + b ) . (24) \hat{z}_i(\eta)=\frac{\sqrt{2}}{N_i}\sum_{j=1}^{N_i}\cos(\boldsymbol{\omega}^{\mathsf{T}}\mathbf{x}_{ij}+b). \tag*{(24)} z ^ i ( η ) = N i 2 j = 1 ∑ N i cos ( ω T x ij + b ) . (24)
Here P ∈ M 1 + ( X ) \mathbb{P}\in\mathcal{M}_{1}^{+}(\mathcal{X}) P ∈ M 1 + ( X ) , and z ^ i ( η ) \hat{z}_i(\eta) z ^ i ( η ) estimates z P i ( η ) z_{\mathbb{P}_i}(\eta) z P i ( η ) using the observed bag X i \mathcal{X}_i X i . By the random-bias cosine identity, the linear distribution kernel satisfies
K ( P , Q ) = E η ∼ π [ z P ( η ) z Q ( η ) ] . (25) K(\mathbb{P},\mathbb{Q})=\mathbb{E}_{\eta\sim\pi}\left[z_{\mathbb{P}}(\eta)z_{\mathbb{Q}}(\eta)\right]. \tag*{(25)} K ( P , Q ) = E η ∼ π [ z P ( η ) z Q ( η ) ] . (25)
To connect this notation with § 3 , notice that the r r r th coordinate of μ P , D \boldsymbol{\mu}_{\mathbb{P},D} μ P , D is D − 1 / 2 z P ( η r ) D^{-1/2}z_{\mathbb{P}}(\eta_r) D − 1/2 z P ( η r ) .
Collecting the empirical averages of one feature across all bags therefore gives
z ^ ( η ) = ( z ^ 1 ( η ) , … , z ^ n ( η ) ) T ∈ R n , M ^ D = 1 D [ z ^ ( η 1 ) ⋯ z ^ ( η D ) ] . (26) \widehat{\boldsymbol{z}}(\eta)=\left(\widehat{z}_1(\eta),\ldots,\widehat{z}_n(\eta)\right)^{\mathsf{T}}\in\mathbb{R}^n,\qquad\widehat{\mathbf{M}}_D=\frac{1}{\sqrt{D}}\left[\widehat{\boldsymbol{z}}(\eta_1)\ \cdots\ \widehat{\boldsymbol{z}}(\eta_D)\right]. \tag*{(26)} z ( η ) = ( z 1 ( η ) , … , z n ( η ) ) T ∈ R n , M D = D 1 [ z ( η 1 ) ⋯ z ( η D ) ] . (26)
Thus, each vector z ^ ( η r ) \widehat{\boldsymbol{z}}(\eta_r) z ( η r ) represents one column of the existing RF embedding matrix, up to the factor D − 1 / 2 D^{-1/2} D − 1/2 . This arrangement allows us to evaluate and select features individually.
The first stage of A-RaDR starts by drawing a candidate pool η ~ 1 , … , η ~ M 0 ∼ i . i . d . π \widetilde{\eta}_1,\ldots,\widetilde{\eta}_{M_0}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\pi η 1 , … , η M 0 ∼ i.i.d. π , independently of the training data, where M 0 ≥ D M_0\ge D M 0 ≥ D . For convenience, we use z ^ m = z ^ ( η ~ m ) \widehat{\boldsymbol{z}}_m=\widehat{\boldsymbol{z}}(\widetilde{\eta}_m) z m = z ( η m ) and [ M 0 ] = { 1 , … , M 0 } [M_0]=\{1,\ldots,M_0\} [ M 0 ] = { 1 , … , M 0 } . The corresponding pool embedding matrix and Gram matrix are
Z 0 = 1 M 0 [ z ^ 1 ⋯ z ^ M 0 ] ∈ R n × M 0 , K ^ 0 = Z 0 Z 0 T . (27) \mathbf{Z}_0=\frac{1}{\sqrt{M_0}}\left[\widehat{\boldsymbol{z}}_1\ \cdots\ \widehat{\boldsymbol{z}}_{M_0}\right]\in\mathbb{R}^{n\times M_0},\qquad\widehat{\mathbf{K}}_0=\mathbf{Z}_0\mathbf{Z}_0^{\mathsf{T}}. \tag*{(27)} Z 0 = M 0 1 [ z 1 ⋯ z M 0 ] ∈ R n × M 0 , K 0 = Z 0 Z 0 T . (27)
In the second stage, we score the candidates and select a subset S = { m 1 , … , m D } ⊆ [ M 0 ] S=\{m_1,\ldots,m_D\}\subseteq[M_0] S = { m 1 , … , m D } ⊆ [ M 0 ] . The selected embedding of bag i i i becomes
μ ^ i , S = 1 D ( z ^ i ( η ~ m 1 ) , … , z ^ i ( η ~ m D ) ) T . (28) \widehat{\boldsymbol{\mu}}_{i,S}=\frac{1}{\sqrt{D}}\left(\widehat{z}_i(\widetilde{\eta}_{m_1}),\ldots,\widehat{z}_i(\widetilde{\eta}_{m_D})\right)^{\mathsf{T}}. \tag*{(28)} μ i , S = D 1 ( z i ( η m 1 ) , … , z i ( η m D ) ) T . (28)
Accordingly, the selected training matrix is M ^ S = D − 1 / 2 [ z ^ m 1 , … , z ^ m D ] \widehat{\mathbf{M}}_S=D^{-1/2}[\widehat{\boldsymbol{z}}_{m_1},\ldots,\widehat{\boldsymbol{z}}_{m_D}] M S = D − 1/2 [ z m 1 , … , z m D ] , whose i i i th row is μ ^ i , S \widehat{\boldsymbol{\mu}}_{i,S} μ i , S . Its Gram matrix satisfies
K ^ S = M ^ S M ^ S T = 1 D ∑ m ∈ S z ^ m z ^ m T . (29) \widehat{\mathbf{K}}_S=\widehat{\mathbf{M}}_S\widehat{\mathbf{M}}_S^{\mathsf{T}}=\frac{1}{D}\sum_{m\in S}\widehat{\boldsymbol{z}}_m\widehat{\boldsymbol{z}}_m^{\mathsf{T}}. \tag*{(29)} K S = M S M S T = D 1 m ∈ S ∑ z m z m T . (29)
The ( i , j ) (i,j) ( i , j ) th entry is therefore the selected RF distribution kernel K ^ S ( X i , X j ) = ⟨ μ ^ i , S , μ ^ j , S ⟩ 2 \widehat{K}_S(\mathcal{X}_i,\mathcal{X}_j)=\langle\widehat{\boldsymbol{\mu}}_{i,S},\widehat{\boldsymbol{\mu}}_{j,S}\rangle_2 K S ( X i , X j ) = ⟨ μ i , S , μ j , S ⟩ 2 . The same selected features are used for prediction. For a test distribution P \mathbb{P} P , its embedding is
μ P , S = 1 D ( z P ( η ~ m 1 ) , … , z P ( η ~ m D ) ) T . (30) \boldsymbol{\mu}_{\mathbb{P},S}=\frac{1}{\sqrt{D}}\left(z_{\mathbb{P}}(\widetilde{\eta}_{m_1}),\ldots,z_{\mathbb{P}}(\widetilde{\eta}_{m_D})\right)^{\mathsf{T}}. \tag*{(30)} μ P , S = D 1 ( z P ( η m 1 ) , … , z P ( η m D ) ) T . (30)
When P \mathbb{P} P is observed through a test bag X t \mathcal{X}_t X t , we replace the population averages by their empirical counterparts in (24) , using N t N_t N t samples, and denote the resulting embedding by μ ^ t , S \widehat{\boldsymbol{\mu}}_{t,S} μ t , S .
A general trace-based score
Adaptive random feature methods select features according to different objectives, such as response alignment, kernel geometry, or variation across inputs [32 , 63 ] . We next show that these objectives can be expressed through a common trace formulation, which leads to a simple feature selection rule.
Specifically, for a score matrix B ∈ R n × n \mathbf{B}\in\mathbb{R}^{n\times n} B ∈ R n × n and a distribution-level Gram matrix K \mathbf{K} K , consider
J B ( K ) = tr ( K B ) . (31) J_{\mathbf{B}}(\mathbf{K})=\operatorname{tr}(\mathbf{K}\mathbf{B}). \tag*{(31)} J B ( K ) = tr ( KB ) . (31)
Since each candidate contributes a rank-one matrix to (29) , its contribution to the objective is determined by
q B , m = z ^ m T B z ^ m = tr ( z ^ m z ^ m T B ) . (32) q_{\mathbf{B},m}=\widehat{\boldsymbol{z}}_m^{\mathsf{T}}\mathbf{B}\widehat{\boldsymbol{z}}_m=\operatorname{tr}\left(\widehat{\boldsymbol{z}}_m\widehat{\boldsymbol{z}}_m^{\mathsf{T}}\mathbf{B}\right). \tag*{(32)} q B , m = z m T B z m = tr ( z m z m T B ) . (32)
For computation, we form the score vector
( q B , 1 , … , q B , M 0 ) T = M 0 diag ( Z 0 T B Z 0 ) , (33) (q_{B,1},\ldots,q_{B,M_0})^{\mathsf{T}}=M_0\operatorname{diag}(Z_0^{\mathsf{T}}BZ_0), \tag*{(33)} ( q B , 1 , … , q B , M 0 ) T = M 0 diag ( Z 0 T B Z 0 ) , (33)
where diag \operatorname{diag} diag represents the diagonal operator. The following proposition establishes the selection rule and its comparison with vanilla random features.
Proposition 4. Fix the training data and a realized candidate pool. Let B \mathbf{B} B be a score matrix held fixed across all candidate subsets. Then, for every S ⊆ [ M 0 ] S\subseteq[M_0] S ⊆ [ M 0 ] with ∣ S ∣ = D \lvert S\rvert=D ∣ S ∣ = D ,
J B ( K ^ S ) = 1 D ∑ m ∈ S q B , m . (34) \mathcal{J}_{B}(\widehat{\mathbf{K}}_{S})=\frac{1}{D}\sum_{m\in S}q_{B,m}. \tag*{(34)} J B ( K S ) = D 1 m ∈ S ∑ q B , m . (34) Consequently, a maximizing subset
S B ∈ argmax S ⊆ [ M 0 ] ∣ S ∣ = D J B ( K ^ S ) (35) S_{B}\in\underset{S\subseteq[M_0]}{\operatorname{argmax}}_{\lvert S\rvert=D}\mathcal{J}_{B}(\widehat{\mathbf{K}}_{S}) \tag*{(35)} S B ∈ S ⊆ [ M 0 ] argmax ∣ S ∣ = D J B ( K S ) (35) is obtained by selecting the D D D largest scores.
Moreover, let K ^ D , N \widehat{\mathbf{K}}_{D,N} K D , N be the vanilla RaDR Gram matrix constructed from the first D D D candidates, we have the following identity,
J B ( K ^ S B ) ≥ J B ( K ^ D , N ) . \mathcal{J}_{B}(\widehat{\mathbf{K}}_{S_B})\geq\mathcal{J}_{B}(\widehat{\mathbf{K}}_{D,N}). J B ( K S B ) ≥ J B ( K D , N ) . where K S B \mathbf{K}_{S_B} K S B denote the Gram matrix formed with features selected via B \mathbf{B} B . If B \mathbf{B} B is also fixed conditional on the training data and independent of the candidate pool, then
E p o o l [ J B ( K ^ S B ) ] ≥ E p o o l [ J B ( K ^ D , N ) ] = J B ( K N ) , (36) \mathbb{E}_{\mathrm{pool}}\left[\mathcal{J}_{B}(\widehat{\mathbf{K}}_{S_B})\right]\geq\mathbb{E}_{\mathrm{pool}}\left[\mathcal{J}_{B}(\widehat{\mathbf{K}}_{D,N})\right]=\mathcal{J}_{B}(\mathbf{K}_{N}), \tag*{(36)} E pool [ J B ( K S B ) ] ≥ E pool [ J B ( K D , N ) ] = J B ( K N ) , (36) where K N \mathbf{K}_{N} K N is the exact finite-bag Gram matrix. The expectations are conditional on the training data and taken over the i.i.d. candidate pool drawn from π \pi π .
The proof is given in Appendix § 7 .12. Proposition 4 shows that a trace objective reduces feature selection to ranking scalar scores. Once B \mathbf{B} B has been constructed, retaining the top-D D D candidates maximizes that objective over all subsets of the pool. This gives a direct way to incorporate different learning objectives into RaDR through the choice of B \mathbf{B} B .
Adaptive RaDR algorithm
With the selected features, A-RaDR proceeds through the same ridge regression formulation as in § 3.2 . In particular, the predictor has the equivalent dual and primal expressions
f ^ λ , N , S B ( P ) = μ P , S B M ^ S B T ( K ^ S B + n λ I n ) − 1 y = μ P , S B ( M ^ S B T M ^ S B + n λ I D ) − 1 M ^ S B T y . (37) \begin{aligned}
\widehat{f}_{\lambda,N,S_B}(\mathbf{P})=\boldsymbol{\mu}_{\mathbf{P},S_B}\widehat{\mathbf{M}}_{S_B}^{\mathsf{T}}\left(\widehat{\mathbf{K}}_{S_B}+n\lambda\mathbf{I}_n\right)^{-1}\mathbf{y} \\
&=\boldsymbol{\mu}_{\mathbf{P},S_B}\left(\widehat{\mathbf{M}}_{S_B}^{\mathsf{T}}\widehat{\mathbf{M}}_{S_B}+n\lambda\mathbf{I}_D\right)^{-1}\widehat{\mathbf{M}}_{S_B}^{\mathsf{T}}\mathbf{y}. \tag*{(37)}
\end{aligned} f λ , N , S B ( P ) = μ P , S B M S B T ( K S B + nλ I n ) − 1 y = μ P , S B ( M S B T M S B + nλ I D ) − 1 M S B T y . (37)
For prediction from X t \mathcal{X}_t X t , we use μ ^ t , S B \widehat{\boldsymbol{\mu}}_{t,S_B} μ t , S B in place of μ P , S B \boldsymbol{\mu}_{\mathbf{P},S_B} μ P , S B . Algorithm 1 summarizes the procedure. The score matrix determines how the feature budget is allocated. We next describe three choices corresponding to kernel alignment, leverage scores, and distribution variance.
Algorithm 1 Adaptive Random Feature Distribution Regression
Require: Training bags { ( X i , y i ) } i = 1 n \{(X_i,y_i)\}_{i=1}^{n} {( X i , y i ) } i = 1 n ; candidate pool size M 0 ≥ D M_0 \ge D M 0 ≥ D ; random features count D D D ; ridge parameter λ > 0 \lambda> 0 λ > 0 ; score matrix B \mathbf{B} B .
Draw η ~ 1 , … , η ~ M 0 ∼ i . i . d . π \tilde{\boldsymbol{\eta}}_1,\ldots,\tilde{\boldsymbol{\eta}}_{M_0} \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \pi η ~ 1 , … , η ~ M 0 ∼ i.i.d. π .
Compute the candidate vectors z ^ m \widehat{\mathbf{z}}_m z m using (24) and (26).
Evaluate the scores in (32) and retain the top-D D D subset S B S_{\mathbf{B}} S B (bottom if trace objective is minimization).
Assemble the selected embedding matrix M ^ S B \widehat{\mathbf{M}}_{S_{\mathbf{B}}} M S B .
Fit the ridge predictor in (37) using the primal or dual form.
return f ^ λ , N , S B \widehat{f}_{\lambda,N,S_{\mathbf{B}}} f λ , N , S B .
Kernel alignment score
Kernel alignment aims to construct kernels whose similarity structure agrees with the responses of the learning task [14 , 47 ] (Shahrampour et al. 2018). For distribution regression, this suggests selecting features whose bag-level averages align with the observed responses.
For scalar responses, the response similarity matrix is y y T \mathbf{y}\mathbf{y}^{\mathsf{T}} y y T . Accordingly, choosing B K A = y y T \mathbf{B}_{\mathrm{KA}}=\mathbf{y}\mathbf{y}^{\mathsf{T}} B KA = y y T gives the trace objective
J K A ( K ) = tr ( K B K A ) = y T K y . (38) \mathcal{J}_{\mathrm{KA}}(\mathbf{K})=\operatorname{tr}(\mathbf{K}\mathbf{B}_{\mathrm{KA}})=\mathbf{y}^{\mathsf{T}}\mathbf{K}\mathbf{y}. \tag*{(38)} J KA ( K ) = tr ( K B KA ) = y T Ky . (38)
Substituting this choice into (32) yields
q K A , m = z ^ m T B K A z ^ m = ( y T z ^ m ) 2 . (39) q_{\mathrm{KA},m}=\widehat{\mathbf{z}}_m^{\mathsf{T}}\mathbf{B}_{\mathrm{KA}}\widehat{\mathbf{z}}_m=(\mathbf{y}^{\mathsf{T}}\widehat{\mathbf{z}}_m)^2. \tag*{(39)} q KA , m = z m T B KA z m = ( y T z m ) 2 . (39)
Thus, the score favors features with a large absolute inner product with the response vector across bags. For binary classification, the same formulation applies with y i ∈ { − 1 , + 1 } y_i \in\{-1,+1\} y i ∈ { − 1 , + 1 } . For multiclass classification, one may use B K A = L L T \mathbf{B}_{\mathrm{KA}}=\mathbf{L}\mathbf{L}^{\mathsf{T}} B KA = L L T , where L ∈ R n × C \mathbf{L}\in\mathbb{R}^{n\times C} L ∈ R n × C contains one-hot or contrast-coded labels for C C C classes. The corresponding score is then ∥ L T z ^ m ∥ 2 2 \lVert\mathbf{L}^{\mathsf{T}}\widehat{\mathbf{z}}_m\rVert_2^2 ∥ L T z m ∥ 2 2 .
Leverage score
Leverage scores measure contributions relative to the geometry of a linear system and have been widely used in randomized linear algebra and kernel approximation [34 , 17 , 4 , 3 , 33 ] . In random feature setting, the same idea gives larger weights to feature components along directions with smaller regularized kernel eigenvalues.
More specifically, let ν > 0 \nu> 0 ν > 0 be the regularization parameter used for feature scoring. Using the exact finite-bag Gram matrix would give the ideal score matrix B L S i d e a l = ( K N + ν I n ) − 1 \mathbf{B}_{\mathrm{LS}}^{\mathrm{ideal}}=(\mathbf{K}_N+\nu\mathbf{I}_n)^{-1} B LS ideal = ( K N + ν I n ) − 1 and scores
q L S , m i d e a l = z ^ m T B L S i d e a l z ^ m . (40) q_{\mathrm{LS},m}^{\mathrm{ideal}}=\widehat{\mathbf{z}}_m^{\mathsf{T}}\mathbf{B}_{\mathrm{LS}}^{\mathrm{ideal}}\widehat{\mathbf{z}}_m. \tag*{(40)} q LS , m ideal = z m T B LS ideal z m . (40)
The parameter ν \nu ν controls the geometry used for selection, while λ \lambda λ in (37) controls the subsequent ridge fit.
Since forming K N \mathbf{K}_N K N requires exact kernel evaluations across bags, we use the pool approximation K ^ 0 \widehat{\mathbf{K}}_0 K 0 from (27) for computation. The practical score matrix is therefore B ^ L S = ( K ^ 0 + ν I n ) − 1 \widehat{\mathbf{B}}_{\mathrm{LS}}=(\widehat{\mathbf{K}}_0+\nu\mathbf{I}_n)^{-1} B LS = ( K 0 + ν I n ) − 1 , giving
q L S , m = z ^ m T B ^ L S z ^ m . (41) q_{\mathrm{LS},m}=\widehat{\mathbf{z}}_m^{\mathsf{T}}\widehat{\mathbf{B}}_{\mathrm{LS}}\widehat{\mathbf{z}}_m. \tag*{(41)} q LS , m = z m T B LS z m . (41)
All scores can be evaluated through (33) , using B = B ^ L S \mathbf{B} = \widehat{\mathbf{B}}_{\mathrm{LS}} B = B LS .
This construction uses the full candidate pool to estimate the kernel geometry before selecting features. Once B ^ L S \widehat{\mathbf{B}}_{\mathrm{LS}} B LS is formed, it remains fixed across subsets, so the realized-pool optimality result in Proposition 4 applies. For the ideal matrix B L S i d e a l \mathbf{B}_{\mathrm{LS}}^{\mathrm{ideal}} B LS ideal , the conditional expectation identity in (36) also applies.
Distribution variance score
Adaptive kernel learning for distribution regression has also been studied from a geometric perspective [24 ] . A natural objective is to obtain representations that separate the observed distributions. Within A-RaDR, this leads to selecting features whose empirical averages vary substantially across bags.
To formalize this idea, we first recall the distribution variance of kernel mean embeddings [39 ] .
Definition 1. For a collection M = { P 1 , … , P n } \mathcal{M} = \{\mathbb{P}_1, \ldots, \mathbb{P}_n\} M = { P 1 , … , P n } , let μ ˉ = n − 1 ∑ i = 1 n μ P i \bar{\mu} = n^{-1} \sum_{i=1}^{n} \mu_{\mathbb{P}_i} μ ˉ = n − 1 ∑ i = 1 n μ P i . The distribution variance is
V H k ( M ) = 1 n ∑ i = 1 n ∥ μ P i − μ ˉ ∥ H k 2 = 1 n tr ( K ) − 1 n 2 1 T K 1. (42) \mathbb{V}_{\mathcal{H}_k}(\mathcal{M}) = \frac{1}{n} \sum_{i=1}^{n} \left\lVert\mu_{\mathbb{P}_i} - \bar{\mu} \right\rVert_{\mathcal{H}_k}^{2}
= \frac{1}{n}\operatorname{tr}(\mathbf{K}) - \frac{1}{n^2}\mathbf{1}^{\mathsf{T}}\mathbf{K}\mathbf{1}. \tag*{(42)} V H k ( M ) = n 1 i = 1 ∑ n ∥ μ P i − μ ˉ ∥ H k 2 = n 1 tr ( K ) − n 2 1 1 T K1 . (42) where [ K ] i j = ⟨ μ P i , μ P j ⟩ H k [\mathbf{K}]_{ij} = \langle\mu_{\mathbb{P}_i}, \mu_{\mathbb{P}_j} \rangle_{\mathcal{H}_k} [ K ] ij = ⟨ μ P i , μ P j ⟩ H k and 1 ∈ R n \mathbf{1} \in\mathbb{R}^{n} 1 ∈ R n is the all-ones vector.
Notice that with the centering matrix H = I n − n − 1 11 T \mathbf{H} = \mathbf{I}_n - n^{-1}\mathbf{1}\mathbf{1}^{\mathsf{T}} H = I n − n − 1 1 1 T , the variance becomes n − 1 tr ( K H ) n^{-1}\operatorname{tr}(\mathbf{K}\mathbf{H}) n − 1 tr ( KH ) , akin to the variance formulation in kernel PCA [63 ] . Since the factor 1 / n 1/n 1/ n does not affect the maximizing subset, we choose B D V = H \mathbf{B}_{\mathrm{DV}} = \mathbf{H} B DV = H , which gives
J D V ( K ) = tr ( K H ) . (43) \mathcal{J}_{\mathrm{DV}}(\mathbf{K}) = \operatorname{tr}(\mathbf{K}\mathbf{H}). \tag*{(43)} J DV ( K ) = tr ( KH ) . (43)
The same identity applies to the selected empirical embeddings:
1 n J D V ( K ^ S ) = 1 n ∑ i = 1 n ∥ μ ^ i , S − 1 n ∑ j = 1 n μ ^ j , S ∥ 2 2 . \frac{1}{n}\mathcal{J}_{\mathrm{DV}}(\widehat{\mathbf{K}}_{\mathcal{S}}) = \frac{1}{n}\sum_{i=1}^{n}\left\lVert\widehat{\mu}_{i,\mathcal{S}} - \frac{1}{n}\sum_{j=1}^{n}\widehat{\mu}_{j,\mathcal{S}}\right\rVert_{2}^{2}. n 1 J DV ( K S ) = n 1 i = 1 ∑ n μ i , S − n 1 j = 1 ∑ n μ j , S 2 2 .
Thus, maximizing the trace objective maximizes the empirical variance of the selected bag representations.
For convenience, denote the average of candidate m m m across bags by z ˉ m = n − 1 1 T z ^ m \bar{z}_m = n^{-1}\mathbf{1}^{\mathsf{T}}\widehat{\mathbf{z}}_m z ˉ m = n − 1 1 T z m . Its score can then be written as
q D V , m = z ^ m T H z ^ m = ∑ i = 1 n ( z ^ i ( η m ) − z ˉ m ) 2 . (44) q_{\mathrm{DV},m} = \widehat{\mathbf{z}}_m^{\mathsf{T}}\mathbf{H}\widehat{\mathbf{z}}_m = \sum_{i=1}^{n}\left(\widehat{z}_i(\eta_m) - \bar{z}_m\right)^2. \tag*{(44)} q DV , m = z m T H z m = i = 1 ∑ n ( z i ( η m ) − z ˉ m ) 2 . (44)
Consequently, this criterion retains features that maximizes the cross-bag embedding variation.
Unified view of adaptive RaDR
The three criteria fit into the same selection procedure through the following choices of score matrix:
Variant Score matrix Candidate score Kernel alignment B K A = y y T ( y T z ^ m ) 2 Leverage score B ^ L S = ( K ^ 0 + ν I n ) − 1 z ^ m T B ^ L S z ^ m Distribution variance B D V = H z ^ m T H z ^ m (45) \begin{array}{c|c|c}
\text{Variant} & \text{Score matrix} & \text{Candidate score} \\
\text{Kernel alignment} & \mathbf{B}_{\mathrm{KA}} = \mathbf{y}\mathbf{y}^{\mathsf{T}} & (\mathbf{y}^{\mathsf{T}}\widehat{\mathbf{z}}_{m})^{2} \\
\text{Leverage score} & \widehat{\mathbf{B}}_{\mathrm{LS}} = (\widehat{\mathbf{K}}_{0}+\nu\mathbf{I}_{n})^{-1} & \widehat{\mathbf{z}}_{m}^{\mathsf{T}}\widehat{\mathbf{B}}_{\mathrm{LS}}\widehat{\mathbf{z}}_{m} \\
\text{Distribution variance} & \mathbf{B}_{\mathrm{DV}} = \mathbf{H} & \widehat{\mathbf{z}}_{m}^{\mathsf{T}}\mathbf{H}\widehat{\mathbf{z}}_{m} \tag*{(45)}
\end{array} Variant Kernel alignment Leverage score Distribution variance Score matrix B KA = y y T B LS = ( K 0 + ν I n ) − 1 B DV = H Candidate score ( y T z m ) 2 z m T B LS z m z m T H z m (45)
In each case, the selected subset follows (35) , and the predictor follows (37) . Kernel alignment adapts to the responses, leverage scores adapt to the regularized kernel geometry, and distribution variance adapts to the spread of the bag representations.
Through these choices, A-RaDR uses the observed training data to allocate a finite feature budget toward the chosen objective. The selected features then define the kernel used for both training and prediction.
Computational complexity
The additional computation in A-RaDR comes from scoring the candidate pool, followed by feature selection. For instances in R d \mathbb{R}^{d} R d , constructing all candidate bag averages costs O ( n N M 0 ) O(nNM_{0}) O ( n N M 0 ) using direct inner products. Once these averages are available, kernel alignment and distribution variance each require O ( n M 0 ) O(nM_{0}) O ( n M 0 ) operations to evaluate all scores.
Leverage scores require a regularized linear system involving the candidate-pool kernel. Working in the bag space gives a cost of O ( n 2 M 0 + n 3 ) O(n^{2}M_{0}+n^{3}) O ( n 2 M 0 + n 3 ) for forming the kernel and evaluating all scores. When M 0 < n M_{0}<n M 0 < n , the Woodbury inversion lemma can reduce the score computational complexity to O ( n M 0 2 + M 0 3 ) O(nM_{0}^{2}+M_{0}^{3}) O ( n M 0 2 + M 0 3 ) operations. Therefore, leverage score cost is O ( min { n 2 M 0 + n 3 , n M 0 2 + M 0 3 } ) O\left(\min\{n^{2}M_{0}+n^{3},nM_{0}^{2}+M_{0}^{3}\}\right) O ( min { n 2 M 0 + n 3 , n M 0 2 + M 0 3 } ) .
The subsequent ridge fit has the same computational cost as RaDR with D D D features, O ( n D 2 + D 3 ) O(nD^{2}+D^{3}) O ( n D 2 + D 3 ) in the primal form or O ( n 2 D + n 3 ) O(n^{2}D+n^{3}) O ( n 2 D + n 3 ) in the dual form.
Empirical Results
In this section, we evaluate RaDR and A-RaDR variants across a broad collection of synthetic and real-world distribution regression tasks. We carry out three sets of simulations. The first set of simulations is designed to examine the behavior of RaDR/A-RaDR vs vanilla kernel distribution regression under a controlled synthetic setting. The second set of simulations is designed to investigate the impact of training and testing bag sizes on kernel distribution regression and RaDR framework. The last set of simulations is the large scale real-world dataset benchmark, where we will compare the RaDR and A-RaDR frameworks to state-of-the-art distribution regression methods in both kernel and deep learning regime. All simulations carried out in this section focus on classification, which is the predominant distribution regression target problem in the literature [24 ] and across our 41 real-world examples.
A taxonomy of benchmark algorithms
To provide a comprehensive evaluation of RaDR and A-RaDR, we benchmark against a diverse collection of distribution regression algorithms spanning classical kernel methods, deep learning architectures for set-valued inputs, and the random feature based approaches. The benchmark methods represent the major paradigms currently used for learning from distributions and sets.
The first group consists of kernel mean embedding (KME) based distribution regression methods. We include the standard two-stage kernel distribution regression framework of [57 ] . Specifically, KME_Gaussian employs Gaussian kernels for both the embedding and distribution regression stages, while KME_Linear uses a Gaussian embedding kernel together with a linear distribution kernel. We further include two adaptive kernel learning approaches proposed in [24 ] . The first, denoted by AKME_MDKE , learns the embedding kernel using the Maximum Distribution Kernel Entropy (MDKE) criterion [24 ] . The second, denoted by AKME_DV , learns the embedding kernel using the Distribution Variance (DV) criterion. For both adaptive approaches, we consider linear and Gaussian distribution kernels, resulting in the variants AKME_MDKE_Linear , AKME_MDKE_Gaussian , AKME_DV_Linear , and AKME_DV_Gaussian .
The second group consists of deep learning architectures designed for set-valued inputs. We consider Deep Sets (DeS) [66 ] , a permutation-invariant neural architecture that aggregates instance-level representations through a symmetric pooling operation. We also consider the Set Transformer (SeT) [30 ] , which leverages self-attention mechanisms to capture interactions among instances within a bag. Two Set Transformer variants are included: SeT_SAB , which employs Self-Attention Blocks (SAB), and SeT_ISAB , which utilizes Induced Self-Attention Blocks (ISAB) to improve scalability on larger sets.
The final group consists of the random feature based methods. RaDR denotes the vanilla random feature approximation of kernel distribution regression introduced in § 3 . We further consider three adaptive variants developed in § 4 : A-RaDR_KA , which performs kernel-alignment-based feature selection; A-RaDR_LS , which utilizes leverage-score-based feature selection; and A-RaDR_DV , which employs the distribution variance criterion. Similar to the KME-based methods, each RaDR and A-RaDR algorithm is evaluated using both linear and Gaussian second-stage distribution kernels.
Table 1 summarizes the complete benchmark suite used throughout the synthetic and real-data experiments. Note that the kernel column describes the distribution kernel, embedding kernel is always chosen to be Gaussian kernel.
Table 1. Summary of benchmark algorithms used throughout the empirical study.
Experimental Settings
Synthetic Dataset The synthetic benchmark is designed as a distribution-level binary classification problem, where each observation is a bag of exchangeable samples. For bag i i i , we first draw a latent class variable s i ∈ { − 1 , 1 } s_i \in\{-1,1\} s i ∈ { − 1 , 1 } . We then draw a bag-specific nuisance vector
b i ∼ N ( 0 , σ b 2 I 8 ) , \mathbf{b}_i \sim\mathcal{N}(0,\sigma_b^2\mathbf{I}_8), b i ∼ N ( 0 , σ b 2 I 8 ) ,
from an isotropic Gaussian distribution of dimension 8 with noise scale σ b = 0.8 \sigma_b = 0.8 σ b = 0.8 , which induces random between-bag variation unrelated to the class signal. Conditioned on s i s_i s i and b i \mathbf{b}_i b i , the informative coordinates of the bag distribution are shifted according to
μ i = s i α e 1 + 1 2 s i α e 2 + 1 2 b i , \boldsymbol{\mu}_i = s_i\alpha\mathbf{e}_1 + \frac{1}{2}s_i\alpha\mathbf{e}_2 + \frac{1}{2}\mathbf{b}_i, μ i = s i α e 1 + 2 1 s i α e 2 + 2 1 b i ,
where e 1 , e 2 \mathbf{e}_1,\mathbf{e}_2 e 1 , e 2 are coordinate basis vectors pointing to the first and second elements which are the informative elements, and α = 0.7 \alpha= 0.7 α = 0.7 controls the strength of the class-dependent mean shift. The instances in bag i i i are sampled independently as
x i j ∼ N ( μ i , σ w 2 I 8 ) , j = 1 , … , N i , \mathbf{x}_{ij} \sim\mathcal{N}(\boldsymbol{\mu}_i,\sigma_w^2\mathbf{I}_8), \qquad j = 1,\ldots,N_i, x ij ∼ N ( μ i , σ w 2 I 8 ) , j = 1 , … , N i ,
where N i N_i N i is the bag size specified by the corresponding experimental setting, and σ w = 1.6 \sigma_w = 1.6 σ w = 1.6 represents the within group sample noise level. To make the problem less separable from simple sample means, additional independent noise with standard deviation 1 is injected into the non-informative coordinates, i.e., element #3 to #8. Finally, the observed bag label is generated from a noisy nonlinear functional of the empirical distribution,
y i = 1 { 1 N i ∑ j = 1 N i x i j , 1 + 0.35 1 N i ∑ j = 1 N i tanh ( x i j , 2 ) + 0.15 ε i > 0.2 ξ i } , y_i = \mathbf{1}\left\{\frac{1}{N_i}\sum_{j=1}^{N_i}x_{ij,1} + 0.35\frac{1}{N_i}\sum_{j=1}^{N_i}\tanh(x_{ij,2}) + 0.15\varepsilon_i > 0.2\xi_i\right\}, y i = 1 { N i 1 j = 1 ∑ N i x ij , 1 + 0.35 N i 1 j = 1 ∑ N i tanh ( x ij , 2 ) + 0.15 ε i > 0.2 ξ i } ,
with ε i , ξ i ∼ N ( 0 , 1 ) \varepsilon_i,\xi_i \sim\mathcal{N}(0,1) ε i , ξ i ∼ N ( 0 , 1 ) independently, and 1 \mathbf{1} 1 denotes the indicator function. x i j , 1 \mathbf{x}_{ij,1} x ij , 1 denotes the first element in vector x i j \mathbf{x}_{ij} x ij . Training and test bags are generated independently from the same data-generating process. In all synthetic simulations, the true labels y i y_i y i are first generated with 500 vectors by default, and the actual training and testing bags are down-sampled from these 500 vectors if a smaller bag size is required. The total number of training bags is set to 500 by default.
General Experimental Settings. The KME and RaDR algorithms tune the hyperparameters including the embedding and distribution kernel bandwidth, and the SVM cost parameter with 3-fold cross validation on the training sets. For both embedding kernel and distribution kernel bandwidth, the CV list is set to [0.25, 0.5, 1, 2, 4]. The SVM cost parameter CV list is set to [0.1, 1, 10, 100]. For A-RaDR, the embedding and distribution kernel bandwidth is set to 1 by default, and only the SVM cost parameter is cross-validated with the same precision.
The AKME methods adopt the kernel optimization approach proposed in Kachaiev and Recanatesi [24 ] . The kernel trajectory is altered via a neural network encoder f θ : R d → R 16 f_\theta:\mathbb{R}^{d} \to\mathbb{R}^{16} f θ : R d → R 16 , a one-hidden-layer ReLU neural network with fixed hidden dimensions throughout all the simulations. The encoder network is trained via an Adam optimizer [26 ] , a learning rate of 5 × 10 − 4 5 \times10^{-4} 5 × 1 0 − 4 , a bag size of 16, and a total of 150 training epochs.
The DeS model uses a neural network encoder f θ : R d → R 50 f_\theta:\mathbb{R}^{d} \to\mathbb{R}^{50} f θ : R d → R 50 with one hidden layer and ELU activation as recommended by the original paper [66 ] . The classifier is a two hidden layer ELU neural network. For the real-world dataset simulation, there are roughly 30k trainable parameters for each dataset (small variations depending on the input dimension). The whole network (encoder + classifier) is trained via an Adam optimizer, a learning rate of 10 − 3 10^{-3} 1 0 − 3 , a bag size of 16, and a total of 150 training epochs.
The SeT methods use a Transformer architecture with 128 hidden dimensions, 4 attention heads, 2 encoder layers and 2 decoder layers, and layer norm is disabled. The classifier is a linear classification layer. For the real-world dataset simulation, there are around 300k trainable parameters for the SAB variant and 450k trainable parameters for the ISAB variant for each dataset with small variations. The whole network (encoder + classifier) is trained via an Adam optimizer, a learning rate of 10 − 3 10^{-3} 1 0 − 3 , a bag size of 16, and a total of 150 training epochs.
All the simulations included in this section are repeated over 10 Monte-Carlo runs to create error bars. The DeS [66 ] and SeT [30 ] implementations follow the open access repositories published by the authors. When recording training time, we include the tuning time for KME, RaDR, and A-RaDR algorithms as well for fair comparison against the deep learning counterparts. We use classification accuracy as the primary performance metric throughout the experiments, defined as
A c c u r a c y = Number of Correctly Classified Bags Total Number of Bags . \mathrm{Accuracy} = \frac{\text{Number of Correctly Classified Bags}}{\text{Total Number of Bags}}. Accuracy = Total Number of Bags Number of Correctly Classified Bags .
We omit the F1 score, as it exhibits the same overall trends as accuracy across all our simulations.
RaDR and A-RaDR ablation studies
In this subsection, we investigate the empirical behavior of RaDR and A-RaDR on synthetic distribution regression problems. The goal of these experiments is twofold. First, we examine whether random feature based distribution regression can recover the predictive performance of exact kernel distribution regression while substantially reducing computational cost. Second, we study the effectiveness of adaptive random feature selection and quantify how the candidate feature pool size influences the resulting performance gains.
Throughout this subsection, we focus on the comparison between RaDR, A-RaDR, and the corresponding exact kernel mean embedding (KME) methods. Unless otherwise stated, all results are reported over both linear and Gaussian second-stage distribution kernels.
RaDR and A-RaDR versus exact kernel distribution regression
Figure 1 compares the predictive accuracy and training time of RaDR and A-RaDR as the number of random features increases. The dashed horizontal line corresponds to the performance of exact kernel distribution regression, while the remaining curves represent random feature approximations with varying feature budgets.
Figure 1. Accuracy and training time of RaDR and A-RaDR as the number of random features varies. The dashed horizontal line denotes exact KME-based distribution regression.
Several observations can be made. First, RaDR exhibits a clear approximation-improvement pattern. When only a small number of random features are used, the approximation error introduced by random features leads to a noticeable loss of predictive accuracy. However, the performance rapidly improves as additional random features are introduced and eventually approaches that of exact kernel distribution regression. This behavior is observed consistently under both linear and Gaussian distribution kernels.
Second, adaptive random feature selection substantially improves performance in the low-feature regime. When only a small number of random features are available for the second stage, all A-RaDR variants outperform vanilla RaDR, with A-RaDR_KA and A-RaDR_DV exhibiting the largest improvements. This demonstrates that selecting informative random features is considerably more effective than uniform random sampling when the feature budget is limited.
Finally, substantial computational savings are achieved even when predictive performance closely matches that of exact kernel methods. Across both kernel choices, RaDR requires only a fraction of the training time needed by KME while achieving nearly identical predictive accuracy.
Although A-RaDR incurs additional computational cost due to the feature-scoring procedure, its runtime remains substantially lower than exact kernel distribution regression while providing noticeable performance gains when the feature budget is small. These results suggest that RaDR offers significant computational efficiency, while A-RaDR offers an attractive trade-off between efficiency and performance.
Effect of candidate feature pool size
We next examine the effect of the candidate feature pool size in A-RaDR. Recall that A-RaDR first draws a larger candidate pool of random features, scores these candidates according to a task-dependent criterion, and then retains only a subset of selected features for downstream distribution regression. The pool multiplier controls the ratio between the candidate pool size and the final number of selected random features. A larger pool multiplier gives A-RaDR more candidate features to choose from, but also increases the additional scoring cost.
Figure 2 reports the accuracy gain of A-RaDR over vanilla RaDR under different random feature budgets and pool multipliers. The heatmap values are reported in percentage points, with positive values indicating improvement over RaDR.
Figure 2. The feature pool multiplier ablation study. Left two columns: Classification accuracy differences between A-RaDR algorithms vs vanilla RaDR algorithm. Right two columns: Accuracy improvements divided by computational overhead (A-RaDR runtime/RaDR runtime). A-RaDR algorithms shows clear benefits in low random feature regime, but the difference diminishes as the random feature count increases.
The main pattern is that adaptive selection is most beneficial when the final random feature budget is small. When only 10 random features are retained, all three A-RaDR variants produce clear gains over RaDR across both linear and Gaussian distribution kernels. In particular, A-RaDR_KA and A-RaDR_DV provide the largest improvements, often yielding gains of several percentage points, amounting to more than 30% error reduction. This supports that adaptive feature selection is especially useful in the low-dimensional approximation regime, where each selected feature has a large influence on the resulting distribution representation.
As the number of retained random features increases, the marginal benefit of adaptive selection decreases rapidly. For feature budgets of 50, 100, and 200, the gains over RaDR become much smaller and are often close to zero. This is consistent with the intuition, as RaDR and KME methods have already been tuned for the best performance, there leaves little room for improvements for A-RaDR, especially with sufficiently large random feature budget.
The effect of the pool multiplier also exhibits diminishing returns. Increasing the pool multiplier generally improves performance when the feature budget is very small, since A-RaDR can search over a richer candidate set. However, once normalized by computational overhead, the additional gains become limited. This suggests that a relatively small candidate pool is often sufficient to capture most of the benefit of adaptive random feature selection. In practice, this provides a useful computational trade-off where A-RaDR can improve low-budget random feature approximations without requiring an excessively large candidate pool.
Overall, these ablation results support the intended role of A-RaDR. Adaptive feature selection is not primarily needed when the random feature budget is already large, its value lies in improving the statistical efficiency of small random feature representations with mild computational overhead. This makes A-RaDR particularly useful when computation or memory constraints limit the number of features that can be used in the downstream learning tasks.
The role of train and test bag sizes
A unique challenge in distribution regression is the presence of two-stage sampling. Rather than observing distributions directly, each distribution is represented by a finite collection of samples. Consequently, the quality of the learned predictor depends not only on the number of training bags available, but also on the number of observations contained within each bag. Since RaDR is designed specifically to address the computational burden induced by large bags, it is important to understand how training and testing bag sizes influence both predictive performance and computational cost.
To this end, we systematically vary the training and testing bag sizes while keeping all other aspects of the learning problem fixed. We further consider two sampling schemes. In the fixed setting, all bags contain exactly the specified number of instances. In the variable setting, bag sizes are randomly generated around the requested value, which serves as the average bag size. This allows us to evaluate whether variability in bag cardinality changes the qualitative conclusions.
Figure 3 reports the marginal effect of training and testing bag sizes on predictive accuracy. An important observation is that increasing the training bag size produces only limited performance improvements. Across all methods, the prediction accuracy shows only mild improvements as the training bag size increases from 2 to 100 observations per bag. In contrast, increasing the testing bag size results in substantial gains in predictive performance. Under both fixed and variable bag-size settings, the accuracy improves steadily as larger testing bags provide increasingly accurate estimates of the underlying test distributions. This observation echoes the well-established phenomenon of kernel distribution regression [56 ] . On the other hand, we observe a clear performance degradation when moving from fixed to variable bag-size settings, this phenomenon has been theoretically investigated in [28 ] . More importantly, RaDR preserves the same training and testing bag size effects. This shows that the random feature’s approximation effect is very much independent from the two-stage sampling process.
Figure 3. Marginal sensitivity of predictive accuracy to training and testing bag sizes under fixed and variable bag-size settings. Increasing training bag size produces only limited improvements, whereas larger testing bags substantially improve predictive performance. RaDR closely follows the behavior of its exact KME counterparts across all bag-size regimes.
While the statistical behavior of RaDR closely matches that of exact kernel methods, the computational scaling characteristics differ substantially. Figure 4 presents the corresponding runtime surfaces. For KME-based distribution regression, runtime grows rapidly as the training bag size increases. This behavior reflects the expensive pairwise kernel evaluations required to compare distributions during training. As a result, the computational burden is dominated by the training bag size, producing a highly asymmetric runtime surface.
Figure 4. Training-time surfaces as functions of training and testing bag sizes. KME-based distribution regression exhibits strong dependence on training bag size, resulting in highly asymmetric computational scaling. In contrast, RaDR displays nearly symmetric scaling with respect to training and testing bag sizes due to its finite-dimensional random feature representation.
In contrast, RaDR exhibits a fundamentally different scaling pattern. The runtime surfaces for both RaDR variants become nearly symmetric with respect to training and testing bag sizes. Increasing either the training or testing bag size results in a comparable increase in computational cost. This behavior is a direct consequence of the random feature representation. Once each distribution is summarized through finite-dimensional random feature averages, both training and testing bags contribute through the same linear aggregation procedure, eliminating the quadratic dependence on training bag size that characterizes kernel-based distribution regression.
Taken together, these results highlight an important advantage of the RaDR framework. From a statistical perspective, RaDR faithfully preserves the statistical behavior of exact kernel distribution regression. From a computational perspective, however, RaDR fundamentally alters the scaling law of distribution regression by reducing the dominant training-bag bottleneck to the same linear scaling exhibited by testing bags.
Real-world experiments
We evaluate RaDR and its adaptive variants on a diverse collection of 41 real-world multi-instance learning datasets spanning molecular activity prediction, image annotation, histopathology analysis, and audio classification tasks. The benchmark suite includes the Musk and Mutagenesis datasets [16 , 51 ] , the Protein dataset [58 ] , the
Elephant, Fox, and Tiger image datasets [2 ] , twenty Corel image annotation datasets [11 ] , the UCSB Breast Cancer dataset [25 ] , and thirteen bird-species audio classification datasets [8 ] . These datasets exhibit substantial diversity in both feature dimensionality and bag structure, ranging from small image collections to large molecular and audio datasets, thereby providing a comprehensive assessment of predictive performance and computational scalability. We exclude the Musk2 dataset from the final benchmark because its extremely large bag sizes (up to 1,044 instances per bag) cause memory failures for both exact kernel mean embedding methods and Set Transformer baselines. Table 2 provides a summary for all 41 benchmark datasets.
Table 2. Dataset information summary for the 41 real-world benchmark datasets.
The benchmark is carried out over the full set of algorithms presented in Table 1 . Moreover, we introduce a set of low random feature variants to the RaDR and A-RaDR framework to further highlight the efficiency benefit in subsecond territory. Specifically, unlike standard RaDR and A-RaDR algorithms with 256 random features and pool size of 2048, the low variants only use 16 random features for the prediction tasks, and 160 random features for the A-RaDR pool.
Figure 5 , and Table 3 summarize the average predictive accuracy and computational cost across all datasets. We point out several important observations. First, with careful tuning, exact kernel distribution regression remains the strongest statistical benchmark. In particular, KME_Gaussian achieves the highest average predictive accuracy among all methods considered. However, the performance gap between exact kernel methods and the best random-feature-based approaches is small. The strongest A-RaDR variants achieve average accuracies exceeding 0.936, remaining within less than half a percentage point of KME_Gaussian while operating in a finite-dimensional representation space. These results indicate that RaDR successfully preserves the predictive advantages of kernel distribution regression despite replacing expensive kernel evaluations with random feature approximations.
Table 3. Table 3: Average real-data benchmark performance over 41 complete MIL datasets. Reported values are mean ± \pm ± propagated standard error. The top 4 accuracy and the fastest training time are marked in bold .
Figure 5. The performance frontier (best accuracy) across the four algorithm groups. X-axis represents the relative training speed up over KME_Gaussian algorithm, computed as KME_Gaussian Runtime/Algorithm Runtime. A-RaDR frontier strikes a balance between computation and performance, ranking second in both criteria.
More importantly, the adaptive random feature variants emerge as the strongest practical competitors to exact kernel methods. Among all non-KME approaches, A-RaDR_KA_Gaussian achieves the highest average accuracy, followed closely by A-RaDR_DV_Gaussian and A-RaDR_LS_Gaussian. At the same time, these methods require only one to three seconds of average training time, compared with nearly five minutes for exact kernel distribution regression. Consequently, the proposed A-RaDR framework occupies a particularly attractive operating regime, delivering predictive performance that is nearly indistinguishable from the strongest kernel methods while reducing computational cost by over two orders of magnitude.
For adaptive kernel learning methods, although AKME_DV and AKME_MDKE attempt to improve performance by directly optimizing kernel hyperparameters, their predictive performance remains noticeably below both RaDR and A-RaDR while still requiring tens of seconds of training time. This observation is particularly interesting for the distribution variance objective. While AKME_DV directly optimizes the kernel using the same underlying criterion employed by A-RaDR_DV, the score-based random feature framework produces substantially stronger predictive performance together with dramatically lower computational cost. These results suggest that controlling the effective kernel through adaptive random feature selection may be a more effective strategy than directly optimizing kernel parameters themselves.
The deep learning baselines exhibit competitive predictive performance, with Set Transformer in particular achieving accuracy levels comparable to several A-RaDR variants. However, these gains come at a substantially higher computational cost. Moreover, unlike RaDR, both Set Transformer and kernel-based methods inherit quadratic computation growth with respect to bag size due to the underlying attention or kernel computations. This characteristic limits the ability to trade computation for memory through mini-batching or related implementation techniques, which is one of the primary mechanisms that enables modern deep learning methods to scale. In contrast, RaDR maintains a fixed-dimensional representation throughout training and prediction, resulting in substantially lower memory requirements and more favorable scaling behavior as bag sizes increase.
The low-feature variants provide additional insight into the role of adaptive random feature selection. A-RaDR in low random feature count regime continues to deliver advantages in performance. Moreover, its computational overhead becomes milder in this regime. For example, in the Gaussian-kernel setting, A-RaDR_KA_Gaussian_low and A-RaDR_DV_Gaussian_low achieve statistically meaningful improvements over RaDR_Gaussian_low while increasing average training time only marginally, from approximately 0.48 seconds to 0.56 seconds. This result demonstrates that adaptive feature selection can provide measurable performance gains in low-feature regimes at an almost negligible additional computational cost.
Taken together, these results provide strong empirical support for the central premise of this paper. Exact kernel distribution regression remains an exceptionally effective statistical learning framework, but its computational requirements become increasingly restrictive on large-scale problems. RaDR preserves nearly all of the predictive performance of kernel distribution regression while reducing computational cost by several orders of magnitude. Furthermore, A-RaDR provides a practical mechanism for further improving predictive performance, particularly when the random feature budget is constrained. Across a diverse collection of 41 real-world datasets, RaDR and A-RaDR frameworks consistently achieve one of the most favorable accuracy-runtime tradeoffs among all competing methods.
Discussion and Conclusion
In this paper, we investigated two longstanding challenges in distribution regression: scalability and adaptivity. Building on existing computational formulations, which we refer to as Random Feature Distribution Regression (RaDR), we developed a finite-sample analysis under two-stage sampling. Our analysis separates distribution-level sampling error, finite within-bag sampling error, and random feature approximation error. It also establishes sufficient feature-budget conditions for preserving the order of our exact two-stage excess-risk upper bound. We further developed Adaptive Random Feature Distribution Regression (A-RaDR), a unified score-guided framework that incorporates task-aware feature selection to improve representation quality while maintaining computational efficiency. Through theoretical analysis and extensive empirical studies, we demonstrated that scalable and adaptive distribution regression can be achieved simultaneously within a principled random feature framework.
We believe several interesting directions could follow this work. Extending the excess-risk analysis to data-dependent feature selection would help explain how the adaptation criterion and candidate-pool size affect predictive performance. Further analysis could also address nonlinear distribution kernels and classification, connecting the theoretical guarantees more closely to the prevalent empirical settings in distribution regression. The incremental structure of random feature mean embeddings additionally motivates studying how sampling error, feature selection, and model updates interact in streaming settings. Such developments would extend the present analysis to a broader class of learning objectives and evolving distribution-valued data.
Technical Details
This appendix provides the assumptions, auxiliary lemmas, and proofs supporting Section 3 and 4. Our theoretical analysis is based on the linear outer kernel
K ( P , Q ) = ⟨ μ P , μ Q ⟩ H k . K(\mathbb{P},\mathbb{Q}) = \langle\mu_{\mathbb{P}}, \mu_{\mathbb{Q}} \rangle_{\mathcal{H}_k}. K ( P , Q ) = ⟨ μ P , μ Q ⟩ H k .
for simplicity. Extensions to nonlinear outer kernels require an additional perturbation layer for the outer kernel and we leave that analysis for future works. The one-stage and two-stage kernel regression results is heavily inspired by the proof of Szabó et al. [56 ] , and they build the groundwork for our third stage analysis.
Assumptions and auxiliary objects
Throughout the appendix, the latent pairs ( P i , y i ) i = 1 n (\mathbb{P}_i, y_i)_{i=1}^{n} ( P i , y i ) i = 1 n are independent and identically distributed according to a probability measure ρ \rho ρ . Its marginal on distributions is denoted by ρ X \rho_X ρ X , and
f ρ ( P ) = E [ y ∣ P ] . f_\rho(\mathbb{P}) = \mathbb{E}[y \mid\mathbb{P}]. f ρ ( P ) = E [ y ∣ P ] .
Conditional on the latent pairs, the observations within each bag are independent samples from P i \mathbb{P}_i P i , and the bags are conditionally independent. In particular, conditional on P i \mathbb{P}_i P i , the sampling of the observed bag is independent of y i y_i y i . We use the balanced setting N i = N N_i = N N i = N .
The random features (aside from selected features in A-RaDR) are independent of the training data. The regularization parameter λ > 0 \lambda> 0 λ > 0 is considered to be deterministic. Population risks are evaluated on an independent latent pair ( P , y ) ∼ ρ (\mathbb{P}, y) \sim\rho ( P , y ) ∼ ρ . All kernels and feature maps are assumed measurable, and the RKHS-valued expectations below are well defined. We first present the set of assumptions.
Assumption 1. There exist constants κ > 0 \kappa> 0 κ > 0 and C y > 0 C_y > 0 C y > 0 such that
sup x ∈ X k ( x , x ) ≤ κ 2 , ∣ y ∣ ≤ C y almost surely . \sup_{x \in\mathcal{X}} k(x,x) \le\kappa^2,\qquad|y| \le C_y \quad\textit{almost surely}. x ∈ X sup k ( x , x ) ≤ κ 2 , ∣ y ∣ ≤ C y almost surely .
Assumption 2. The instance domain X ⊂ R d \mathcal{X} \subset\mathbb{R}^{d} X ⊂ R d is compact, with diameter
ℓ X = sup x , z ∈ X ∥ x − z ∥ 2 ∈ ( 0 , ∞ ) . \ell_{\mathcal{X}} = \sup_{x,z \in\mathcal{X}} \lVert x-z \rVert_2 \in(0,\infty). ℓ X = x , z ∈ X sup ∥ x − z ∥ 2 ∈ ( 0 , ∞ ) . The base kernel is continuous, real-valued, positive definite, and shift-invariant, with k ( x , x ) = 1 k(x,x)=1 k ( x , x ) = 1 and spectral probability measure Λ \Lambda Λ . Moreover,
0 < σ ρ 2 = ∫ R d ∥ ω ∥ 2 2 d Λ ( ω ) < ∞ . 0 < \sigma_{\rho}^{2} = \int_{\mathbb{R}^{d}} \lVert\boldsymbol{\omega} \rVert_2^{2}\,\mathrm{d}\Lambda(\boldsymbol{\omega}) < \infty. 0 < σ ρ 2 = ∫ R d ∥ ω ∥ 2 2 d Λ ( ω ) < ∞. The dimension, kernel parameters, and domain are considered fixed in the asymptotic statements.
Assumption 3. Let T : H K → H K T : \mathcal{H}_K \to\mathcal{H}_K T : H K → H K denote the covariance operator
T f = ∫ M 1 + ( X ) ⟨ f , K P ⟩ H K K P d ρ X ( P ) , (46) T f = \int_{\mathcal{M}_1^{+}(\mathcal{X})} \langle f, K_{\mathbb{P}} \rangle_{\mathcal{H}_K} K_{\mathbb{P}} \,\mathrm{d}\rho_X(\mathbb{P}), \tag*{(46)} T f = ∫ M 1 + ( X ) ⟨ f , K P ⟩ H K K P d ρ X ( P ) , (46)
where K P = K ( P , ⋅ ) \mathbf{K}_{\mathbb{P}} = K(\mathbb{P}, \cdot) K P = K ( P , ⋅ ) . There exist c ∈ ( 1 , 2 ] c \in(1, 2] c ∈ ( 1 , 2 ] , b > 1 b > 1 b > 1 , R > 0 R > 0 R > 0 , and β > 0 \beta> 0 β > 0 such that
f ρ = T ( c − 1 ) / 2 g for some g ∈ H K with ∥ g ∥ H K 2 ≤ R , f_{\rho} = T^{(c-1)/2}g \quad\text{for some } g \in\mathcal{H}_{K} \text{ with } \lVert g \rVert_{\mathcal{H}_{K}}^{2} \le R, f ρ = T ( c − 1 ) /2 g for some g ∈ H K with ∥ g ∥ H K 2 ≤ R ,
and the effective dimension
N ( λ ) = tr { ( T + λ I ) − 1 T } \mathcal{N}(\lambda) = \operatorname{tr}\{(T + \lambda I)^{-1}T\} N ( λ ) = tr {( T + λ I ) − 1 T }
satisfies
N ( λ ) ≤ β λ − 1 / b . \mathcal{N}(\lambda) \le\beta\lambda^{-1/b}. N ( λ ) ≤ β λ − 1/ b .
Remark 2. The compact-domain and spectral assumptions are required for the uniform RF approximation result. The exact-kernel finite-bag perturbation argument needs only boundedness and the stated sampling model. The source-capacity condition is required to establish a one-stage statistical baseline.
One-stage exact-kernel baseline
The perturbation analysis requires establishing a one-stage KRR bound as an input. The one-stage estimator observes the true distribution embeddings and is defined by
f ^ λ = argmin f ∈ H K { 1 n ∑ i = 1 n ( f ( P i ) − y i ) 2 + λ ∥ f ∥ H K 2 } . \widehat{f}_{\lambda} = \underset{f \in\mathcal{H}_{K}}{\operatorname{argmin}} \left\{ \frac{1}{n}\sum_{i=1}^{n}(f(\mathbb{P}_{i}) - y_{i})^{2} + \lambda\lVert f \rVert_{\mathcal{H}_{K}}^{2} \right\}. f λ = f ∈ H K argmin { n 1 i = 1 ∑ n ( f ( P i ) − y i ) 2 + λ ∥ f ∥ H K 2 } .
Assumption 4. For the sample sizes, regularization parameters, and confidence levels under consideration, there is a nonnegative function B 1 s ( n , λ , δ ) B_{1\mathrm{s}}(n, \lambda, \delta) B 1 s ( n , λ , δ ) such that
P { E ( f ^ λ , f ρ ) ≤ B 1 s ( n , λ , δ ) } ≥ 1 − δ . (47) \mathbb{P}\left\{ \mathcal{E}(\widehat{f}_{\lambda}, f_{\rho}) \le B_{1\mathrm{s}}(n, \lambda, \delta) \right\} \ge1 - \delta. \tag*{(47)} P { E ( f λ , f ρ ) ≤ B 1 s ( n , λ , δ ) } ≥ 1 − δ . (47)
We further assume that any assumptions that establish the above bound will hold in the proceeding perturbation analysis, such that the results will carry over to the two-stage risk bound.
Remark 3. Under Assumptions 1 and 3, the one-stage KRR analysis of Caponnetto and De Vito (2007), with the corrections in Sutherland’s Fixing an Error in Caponnetto and de Vito [10 ] (arXiv:1702.02982), gives the following bound. There are constants C 0 , C 1 > 0 C_{0}, C_{1} > 0 C 0 , C 1 > 0 , depending only on the fixed problem parameters, such that
B 1 s ( n , λ , δ ) = C 1 log 2 ( 6 / δ ) [ λ c + λ c − 2 n 2 + λ c − 1 n + 1 n 2 λ + 1 n λ 1 / b ] , B_{1\mathrm{s}}(n, \lambda, \delta) = C_{1}\log^{2}(6/\delta)\left[\lambda^{c} + \frac{\lambda^{c-2}}{n^{2}} + \frac{\lambda^{c-1}}{n} + \frac{1}{n^{2}\lambda} + \frac{1}{n\lambda^{1/b}}\right], B 1 s ( n , λ , δ ) = C 1 log 2 ( 6/ δ ) [ λ c + n 2 λ c − 2 + n λ c − 1 + n 2 λ 1 + n λ 1/ b 1 ] ,
provided that
0 < λ ≤ min { 1 , ∥ T ∥ o p } , n ≥ C 0 log 2 ( 6 / δ ) λ − ( 1 + 1 / b ) . 0 < \lambda\le\min\{1, \lVert T \rVert_{\mathrm{op}}\}, \qquad n \ge C_{0}\log^{2}(6/\delta)\lambda^{-(1+1/b)}. 0 < λ ≤ min { 1 , ∥ T ∥ op } , n ≥ C 0 log 2 ( 6/ δ ) λ − ( 1 + 1/ b ) .
The constants absorb the source radius, the effective-dimension constant, the kernel bound, and the bounded-output noise constants.
For fixed δ \delta δ and a nonzero covariance operator, the choice
λ n ≍ n − b / ( b c + 1 ) \lambda_{n} \asymp n^{-b/(bc+1)} λ n ≍ n − b / ( b c + 1 )
satisfies the sample-size condition for all sufficiently large n n n , since c > 1 c > 1 c > 1 , and yields
B 1 s ( n , λ n , δ ) = O ( n − b c / ( b c + 1 ) ) . B_{1\mathrm{s}}(n, \lambda_{n}, \delta) = O\left(n^{-bc/(bc+1)}\right). B 1 s ( n , λ n , δ ) = O ( n − b c / ( b c + 1 ) ) .
This is one example of a practical B 1 s ( n , λ n , δ ) B_{1\mathrm{s}}(n, \lambda_{n}, \delta) B 1 s ( n , λ n , δ ) bound that is compatible with our subsequent perturbation analysis. Other valid one-stage baselines can also be used.
Write L = σ p ℓ X > 0 L=\sigma_p\ell_X>0 L = σ p ℓ X > 0 . We use the normalized random-bias cosine map in (3) . For simplicity, we first define the error term ϵ D ( δ ) \epsilon_D(\delta) ϵ D ( δ ) .
Definition 2. For δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and D ≥ 1 D\ge1 D ≥ 1 , define
ϵ D ( δ ) = inf ( { 3 } ∪ { t ∈ ( 0 , min { L , 3 } ] : 98 ( L t ) 2 exp ( − D t 2 32 ( d + 1 ) ) ≤ δ } ) . (48) \epsilon_D(\delta)=\inf\left(\{3\}\cup\left\{t\in(0,\min\{L,3\}]:98\left(\frac{L}{t}\right)^2\exp\left(-\frac{Dt^2}{32(d+1)}\right)\le\delta\right\}\right). \tag*{(48)} ϵ D ( δ ) = inf ( { 3 } ∪ { t ∈ ( 0 , min { L , 3 }] : 98 ( t L ) 2 exp ( − 32 ( d + 1 ) D t 2 ) ≤ δ } ) . (48)
Theorem 5. Under Assumption 2,
P { sup x , z ∈ X ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ ϵ D ( δ ) } ≥ 1 − δ . \mathbb{P}\left\{\sup_{\mathbf{x},\mathbf{z}\in\mathcal{X}}\left|k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})\right|\le\epsilon_D(\delta)\right\}\ge1-\delta. P { x , z ∈ X sup ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ ϵ D ( δ ) } ≥ 1 − δ . For every fixed δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , there is a constant C δ > 0 C_\delta>0 C δ > 0 , depending only on δ \delta δ and the fixed kernel and domain parameters, such that, for all sufficiently large D D D ,
ϵ D ( δ ) 2 ≤ C δ log ( e D ) D . \epsilon_D(\delta)^2\le C_\delta\frac{\log(eD)}{D}. ϵ D ( δ ) 2 ≤ C δ D log ( eD ) .
Proof. Proposition 2 of Sutherland and Schneider [55 ] , applied to the random-bias cosine construction, gives
P { sup x , z ∈ X ∣ k D ( x , z ) − k ( x , z ) ∣ ≥ t } ≤ 98 ( L t ) 2 exp ( − D t 2 32 ( d + 1 ) ) , 0 < t ≤ L . (49) \mathbb{P}\left\{\sup_{\mathbf{x},\mathbf{z}\in\mathcal{X}}\left|k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})\right|\ge t\right\}\le98\left(\frac{L}{t}\right)^2\exp\left(-\frac{Dt^2}{32(d+1)}\right),\qquad0<t\le L. \tag*{(49)} P { x , z ∈ X sup ∣ k D ( x , z ) − k ( x , z ) ∣ ≥ t } ≤ 98 ( t L ) 2 exp ( − 32 ( d + 1 ) D t 2 ) , 0 < t ≤ L . (49)
The right-hand side is continuous and decreasing in t t t , and diverges as t ↓ 0 t\downarrow0 t ↓ 0 . Therefore, if ϵ D ( δ ) < 3 \epsilon_D(\delta)<3 ϵ D ( δ ) < 3 , the infimum in (48) is attained by the probability claim in (49) .
For the edge case where ϵ D ( δ ) = 3 \epsilon_D(\delta)=3 ϵ D ( δ ) = 3 , observe that
∥ ϕ D ( x ) ∥ 2 ≤ 2 , ∣ k D ( x , z ) ∣ ≤ 2 , ∣ k ( x , z ) ∣ ≤ 1. \|\boldsymbol{\phi}_D(\mathbf{x})\|_2\le\sqrt{2},\qquad|k_D(\mathbf{x},\mathbf{z})|\le2,\qquad|k(\mathbf{x},\mathbf{z})|\le1. ∥ ϕ D ( x ) ∥ 2 ≤ 2 , ∣ k D ( x , z ) ∣ ≤ 2 , ∣ k ( x , z ) ∣ ≤ 1.
Consequently,
sup x , z ∈ X ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ 3 \sup_{\mathbf{x},\mathbf{z}\in\mathcal{X}}|k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})|\le3 x , z ∈ X sup ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ 3
deterministically.
For the convergence rate of ϵ D ( δ ) \epsilon_D(\delta) ϵ D ( δ ) , choose A > 32 ( d + 1 ) A>\sqrt{32(d+1)} A > 32 ( d + 1 ) and set
t D = A log ( e D ) D , q = A 2 32 ( d + 1 ) > 1. t_D=A\sqrt{\frac{\log(eD)}{D}},\qquad q=\frac{A^2}{32(d+1)}>1. t D = A D log ( eD ) , q = 32 ( d + 1 ) A 2 > 1.
For sufficiently large D D D , t D ≤ min { L , 3 } t_D\le\min\{L,3\} t D ≤ min { L , 3 } , and
98 ( L t D ) 2 exp ( − D t D 2 32 ( d + 1 ) ) = 98 L 2 e − q A 2 D 1 − q log ( e D ) ⟶ 0. 98\left(\frac{L}{t_D}\right)^2\exp\left(-\frac{Dt_D^2}{32(d+1)}\right)=\frac{98L^2e^{-q}}{A^2}\frac{D^{1-q}}{\log(eD)}\longrightarrow0. 98 ( t D L ) 2 exp ( − 32 ( d + 1 ) D t D 2 ) = A 2 98 L 2 e − q log ( eD ) D 1 − q ⟶ 0.
Hence t D t_D t D is a valid upper bound for all sufficiently large D D D , which proves the stated rate. □ \square □
Concentration of empirical mean embeddings
Lemma 1. Under Assumption 1, there is a universal constant C μ > 0 C_{\mu}>0 C μ > 0 such that, for every distribution P \mathbb{P} P and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) ,
P { ∥ μ ^ P − μ P ∥ H k ≤ C μ κ log ( 2 / δ ) N } ≥ 1 − δ . \mathbb{P}\left\{\left\|\widehat{\mu}_{\mathbb{P}}-\mu_{\mathbb{P}}\right\|_{\mathcal{H}_k}\le C_{\mu}\kappa\sqrt{\frac{\log(2/\delta)}{N}}\right\}\ge1-\delta. P { ∥ μ P − μ P ∥ H k ≤ C μ κ N log ( 2/ δ ) } ≥ 1 − δ . Consequently, with probability at least 1 − δ 1-\delta 1 − δ ,
max 1 ≤ i ≤ n ∥ μ ^ i − μ P i ∥ H k ≤ C μ κ log ( 2 n / δ ) N . (50) \max_{1\le i\le n}\left\|\widehat{\mu}_i-\mu_{\mathbb{P}_i}\right\|_{\mathcal{H}_k}\le C_{\mu}\kappa\sqrt{\frac{\log(2n/\delta)}{N}}. \tag*{(50)} 1 ≤ i ≤ n max ∥ μ i − μ P i ∥ H k ≤ C μ κ N log ( 2 n / δ ) . (50) Proof. Let F = ∥ μ ^ P − μ P ∥ H k F=\left\|\widehat{\mu}_{\mathbb{P}}-\mu_{\mathbb{P}}\right\|_{\mathcal{H}_k} F = ∥ μ P − μ P ∥ H k . Independence and centering give
E F 2 = 1 N E ∥ k ( x , ⋅ ) − μ P ∥ H k 2 ≤ κ 2 N , \mathbb{E}F^2=\frac{1}{N}\mathbb{E}\left\|k(x,\cdot)-\mu_{\mathbb{P}}\right\|_{\mathcal{H}_k}^2\le\frac{\kappa^2}{N}, E F 2 = N 1 E ∥ k ( x , ⋅ ) − μ P ∥ H k 2 ≤ N κ 2 , so E F ≤ κ / N \mathbb{E}F\le\kappa/\sqrt{N} E F ≤ κ / N . Replacing one observation changes F F F by at most 2 κ / N 2\kappa/N 2 κ / N . The bounded-differences inequality therefore gives, with probability at least 1 − δ 1-\delta 1 − δ ,
F ≤ κ N + κ 2 log ( 1 / δ ) N ≤ C μ κ log ( 2 / δ ) N . F\le\frac{\kappa}{\sqrt{N}}+\kappa\sqrt{\frac{2\log(1/\delta)}{N}}\le C_{\mu}\kappa\sqrt{\frac{\log(2/\delta)}{N}}. F ≤ N κ + κ N 2 log ( 1/ δ ) ≤ C μ κ N log ( 2/ δ ) . Therefore, C μ = 3 C_{\mu}=3 C μ = 3 is a sufficient constant. Apply this bound conditionally to each training distribution with failure probability δ / n \delta/n δ / n , and take a union bound gives (50). □
Kernel perturbation at the bag level
For the rest of the appendix, P ^ i \widehat{\mathbb{P}}_i P i denotes the empirical measure of training bag i i i . We use
K N ( P i , P j ) = ⟨ μ ^ i , μ ^ j ⟩ H k , K N ( P i , P ) = ⟨ μ ^ i , μ P ⟩ H k , K_N(\mathbb{P}_i,\mathbb{P}_j)=\left\langle\widehat{\mu}_i,\widehat{\mu}_j\right\rangle_{\mathcal{H}_k},\qquad K_N(\mathbb{P}_i,\mathbb{P})=\left\langle\widehat{\mu}_i,\mu_{\mathbb{P}}\right\rangle_{\mathcal{H}_k}, K N ( P i , P j ) = ⟨ μ i , μ j ⟩ H k , K N ( P i , P ) = ⟨ μ i , μ P ⟩ H k ,
K D , N ( P i , P j ) = ⟨ μ ^ i , D , μ ^ j , D ⟩ 2 , K D , N ( P i , P ) = ⟨ μ ^ i , D , μ P , D ⟩ 2 . K_{D,N}(\mathbb{P}_i,\mathbb{P}_j)=\left\langle\widehat{\boldsymbol{\mu}}_{i,D},\widehat{\boldsymbol{\mu}}_{j,D}\right\rangle_2,\qquad K_{D,N}(\mathbb{P}_i,\mathbb{P})=\left\langle\widehat{\boldsymbol{\mu}}_{i,D},\boldsymbol{\mu}_{\mathbb{P},D}\right\rangle_2. K D , N ( P i , P j ) = ⟨ μ i , D , μ j , D ⟩ 2 , K D , N ( P i , P ) = ⟨ μ i , D , μ P , D ⟩ 2 .
In this part of the analysis, we assume training Gram entries are computed with empirical measures. For test vector entries, only the training argument is empirical unless a finite test bag is explicitly specified.
Lemma 2. On the event of Theorem 5, for all probability measures P \mathbb{P} P and Q \mathbb{Q} Q on X \mathcal{X} X ,
∣ K D ( P , Q ) − K ( P , Q ) ∣ ≤ ϵ D ( δ ) . (51) \left|K_D(\mathbb{P},\mathbb{Q})-K(\mathbb{P},\mathbb{Q})\right|\le\epsilon_D(\delta). \tag*{(51)} ∣ K D ( P , Q ) − K ( P , Q ) ∣ ≤ ϵ D ( δ ) . (51)
Proof. By definition,
K D ( P , Q ) = ∫ X ∫ X k D ( x , z ) d P ( x ) d Q ( z ) , K_D(\mathbb{P},\mathbb{Q})=\int_{\mathcal{X}}\int_{\mathcal{X}} k_D(x,z)\,d\mathbb{P}(x)d\mathbb{Q}(z), K D ( P , Q ) = ∫ X ∫ X k D ( x , z ) d P ( x ) d Q ( z ) ,
and
K ( P , Q ) = ∫ X ∫ X k ( x , z ) d P ( x ) d Q ( z ) . K(\mathbb{P},\mathbb{Q})=\int_{\mathcal{X}}\int_{\mathcal{X}} k(x,z)\,d\mathbb{P}(x)d\mathbb{Q}(z). K ( P , Q ) = ∫ X ∫ X k ( x , z ) d P ( x ) d Q ( z ) .
Therefore,
∣ K D ( P , Q ) − K ( P , Q ) ∣ = ∣ ∫ X ∫ X { k D ( x , z ) − k ( x , z ) } d P ( x ) d Q ( z ) ∣ ≤ ∫ X ∫ X ∣ k D ( x , z ) − k ( x , z ) ∣ d P ( x ) d Q ( z ) ≤ sup x , z ∈ X ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ ϵ D ( δ ) . \begin{aligned}
\left|K_D(\mathbb{P},\mathbb{Q})-K(\mathbb{P},\mathbb{Q})\right|
&=\left|\int_{\mathcal{X}}\int_{\mathcal{X}}\{k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})\}\,\mathrm{d}\mathbb{P}(\mathbf{x})\mathrm{d}\mathbb{Q}(\mathbf{z})\right|\\
&\leq\int_{\mathcal{X}}\int_{\mathcal{X}}\left|k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})\right|\,\mathrm{d}\mathbb{P}(\mathbf{x})\mathrm{d}\mathbb{Q}(\mathbf{z})\\
&\leq\sup_{\mathbf{x},\mathbf{z}\in\mathcal{X}}\left|k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})\right|\\
&\leq\epsilon_D(\delta).
\end{aligned} ∣ K D ( P , Q ) − K ( P , Q ) ∣ = ∫ X ∫ X { k D ( x , z ) − k ( x , z )} d P ( x ) d Q ( z ) ≤ ∫ X ∫ X ∣ k D ( x , z ) − k ( x , z ) ∣ d P ( x ) d Q ( z ) ≤ x , z ∈ X sup ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ ϵ D ( δ ) .
Lemma 3. On the event of Lemma 1, for all i , j ∈ { 1 , … , n } i,j\in\{1,\ldots,n\} i , j ∈ { 1 , … , n } ,
∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ 2 C μ κ 2 log ( 2 n / δ ) N . (52) \left|K_N(\mathbb{P}_i,\mathbb{P}_j)-K(\mathbb{P}_i,\mathbb{P}_j)\right|\leq2C_\mu\kappa^2\sqrt{\frac{\log(2n/\delta)}{N}}. \tag*{(52)} ∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ 2 C μ κ 2 N log ( 2 n / δ ) . (52) Moreover, for any test distribution P \mathbb{P} P ,
∣ K N ( P i , P ) − K ( P i , P ) ∣ ≤ C μ κ 2 log ( 2 n / δ ) N . (53) \left|K_N(\mathbb{P}_i,\mathbb{P})-K(\mathbb{P}_i,\mathbb{P})\right|\leq C_\mu\kappa^2\sqrt{\frac{\log(2n/\delta)}{N}}. \tag*{(53)} ∣ K N ( P i , P ) − K ( P i , P ) ∣ ≤ C μ κ 2 N log ( 2 n / δ ) . (53) Proof. For the training Gram entry,
K N ( P i , P j ) − K ( P i , P j ) = ⟨ μ ^ i , μ ^ j ⟩ H k − ⟨ μ P i , μ P j ⟩ H k . K_N(\mathbb{P}_i,\mathbb{P}_j)-K(\mathbb{P}_i,\mathbb{P}_j)=\langle\widehat{\mu}_i,\widehat{\mu}_j\rangle_{\mathcal{H}_k}-\langle\mu_{\mathbb{P}_i},\mu_{\mathbb{P}_j}\rangle_{\mathcal{H}_k}. K N ( P i , P j ) − K ( P i , P j ) = ⟨ μ i , μ j ⟩ H k − ⟨ μ P i , μ P j ⟩ H k . Add and subtract ⟨ μ ^ i , μ P j ⟩ H k \langle\widehat{\mu}_i,\mu_{\mathbb{P}_j}\rangle_{\mathcal{H}_k} ⟨ μ i , μ P j ⟩ H k :
∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ ∣ ⟨ μ ^ i , μ ^ j − μ P j ⟩ H k ∣ + ∣ ⟨ μ ^ i − μ P i , μ P j ⟩ H k ∣ . \begin{aligned}
\left|K_N(\mathbb{P}_i,\mathbb{P}_j)-K(\mathbb{P}_i,\mathbb{P}_j)\right|
&\leq\left|\langle\widehat{\mu}_i,\widehat{\mu}_j-\mu_{\mathbb{P}_j}\rangle_{\mathcal{H}_k}\right|\\
&\quad+\left|\langle\widehat{\mu}_i-\mu_{\mathbb{P}_i},\mu_{\mathbb{P}_j}\rangle_{\mathcal{H}_k}\right|.
\end{aligned} ∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ ⟨ μ i , μ j − μ P j ⟩ H k + ⟨ μ i − μ P i , μ P j ⟩ H k . By Cauchy–Schwarz,
∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ ∥ μ ^ i ∥ H k ∥ μ ^ j − μ P j ∥ H k + ∥ μ P j ∥ H k ∥ μ ^ i − μ P i ∥ H k . \left|K_N(\mathbb{P}_i,\mathbb{P}_j)-K(\mathbb{P}_i,\mathbb{P}_j)\right|\leq\|\widehat{\mu}_i\|_{\mathcal{H}_k}\|\widehat{\mu}_j-\mu_{\mathbb{P}_j}\|_{\mathcal{H}_k}+\|\mu_{\mathbb{P}_j}\|_{\mathcal{H}_k}\|\widehat{\mu}_i-\mu_{\mathbb{P}_i}\|_{\mathcal{H}_k}. ∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ ∥ μ i ∥ H k ∥ μ j − μ P j ∥ H k + ∥ μ P j ∥ H k ∥ μ i − μ P i ∥ H k . Since ∥ μ ^ i ∥ H k ≤ κ \|\widehat{\mu}_i\|_{\mathcal{H}_k}\leq\kappa ∥ μ i ∥ H k ≤ κ and ∥ μ P j ∥ H k ≤ κ \|\mu_{\mathbb{P}_j}\|_{\mathcal{H}_k}\leq\kappa ∥ μ P j ∥ H k ≤ κ , (50) gives
∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ 2 C μ κ 2 log ( 2 n / δ ) N . \left|K_N(\mathbb{P}_i,\mathbb{P}_j)-K(\mathbb{P}_i,\mathbb{P}_j)\right|\leq2C_\mu\kappa^2\sqrt{\frac{\log(2n/\delta)}{N}}. ∣ K N ( P i , P j ) − K ( P i , P j ) ∣ ≤ 2 C μ κ 2 N log ( 2 n / δ ) . For the test vector entry,
K N ( P i , P ) − K ( P i , P ) = ⟨ μ ^ i − μ P i , μ P ⟩ H k . K_N(\mathbb{P}_i,\mathbb{P})-K(\mathbb{P}_i,\mathbb{P})=\langle\widehat{\mu}_i-\mu_{\mathbb{P}_i},\mu_{\mathbb{P}}\rangle_{\mathcal{H}_k}. K N ( P i , P ) − K ( P i , P ) = ⟨ μ i − μ P i , μ P ⟩ H k . Thus,
∣ K N ( P i , P ) − K ( P i , P ) ∣ ≤ ∥ μ ^ i − μ P i ∥ H k ∥ μ P ∥ H k ≤ C μ κ 2 log ( 2 n / δ ) N . \left|K_N(\mathbb{P}_i,\mathbb{P})-K(\mathbb{P}_i,\mathbb{P})\right|\leq\|\widehat{\mu}_i-\mu_{\mathbb{P}_i}\|_{\mathcal{H}_k}\|\mu_{\mathbb{P}}\|_{\mathcal{H}_k}\leq C_\mu\kappa^2\sqrt{\frac{\log(2n/\delta)}{N}}. ∣ K N ( P i , P ) − K ( P i , P ) ∣ ≤ ∥ μ i − μ P i ∥ H k ∥ μ P ∥ H k ≤ C μ κ 2 N log ( 2 n / δ ) .
Lemma 4. On the event of Theorem 5, for all i , j ∈ { 1 , … , n } i, j \in\{1, \ldots, n\} i , j ∈ { 1 , … , n } ,
∣ K D , N ( P i , P j ) − K N ( P i , P j ) ∣ ≤ ϵ D ( δ ) , (54) \left|K_{D,N}(\mathbb{P}_i,\mathbb{P}_j)-K_N(\mathbb{P}_i,\mathbb{P}_j)\right| \le\epsilon_D(\delta), \tag*{(54)} ∣ K D , N ( P i , P j ) − K N ( P i , P j ) ∣ ≤ ϵ D ( δ ) , (54) and for any test distribution P \mathbb{P} P ,
∣ K D , N ( P i , P ) − K N ( P i , P ) ∣ ≤ ϵ D ( δ ) . (55) \left|K_{D,N}(\mathbb{P}_i,\mathbb{P})-K_N(\mathbb{P}_i,\mathbb{P})\right| \le\epsilon_D(\delta). \tag*{(55)} ∣ K D , N ( P i , P ) − K N ( P i , P ) ∣ ≤ ϵ D ( δ ) . (55)
Proof. We only need to prove (54) as the proof of (55) is identical. Since the empirical bags define probability measures, we can write
K D , N ( P i , P j ) − K N ( P i , P j ) = ∬ X X { k D ( x , z ) − k ( x , z ) } d P ^ i ( x ) d P ^ j ( z ) . K_{D,N}(\mathbb{P}_i,\mathbb{P}_j)-K_N(\mathbb{P}_i,\mathbb{P}_j)=\iint_{\mathcal{X}\ \mathcal{X}}\{k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})\}\,\mathrm{d}\widehat{\mathbb{P}}_i(\mathbf{x})\mathrm{d}\widehat{\mathbb{P}}_j(\mathbf{z}). K D , N ( P i , P j ) − K N ( P i , P j ) = ∬ X X { k D ( x , z ) − k ( x , z )} d P i ( x ) d P j ( z ) .
Therefore,
∣ K D , N ( P i , P j ) − K N ( P i , P j ) ∣ ≤ sup x , z ∈ X ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ ϵ D ( δ ) . \left|K_{D,N}(\mathbb{P}_i,\mathbb{P}_j)-K_N(\mathbb{P}_i,\mathbb{P}_j)\right| \le\sup_{\mathbf{x},\mathbf{z}\in\mathcal{X}}\left|k_D(\mathbf{x},\mathbf{z})-k(\mathbf{x},\mathbf{z})\right| \le\epsilon_D(\delta). ∣ K D , N ( P i , P j ) − K N ( P i , P j ) ∣ ≤ x , z ∈ X sup ∣ k D ( x , z ) − k ( x , z ) ∣ ≤ ϵ D ( δ ) .
Matrix perturbation bounds
Define
a N ( δ ) = 2 C μ κ 2 log ( 2 n / δ ) N , b N ( δ ) = C μ κ 2 log ( 2 n / δ ) N . a_N(\delta)=2C_\mu\kappa^2\sqrt{\frac{\log(2n/\delta)}{N}},\qquad b_N(\delta)=C_\mu\kappa^2\sqrt{\frac{\log(2n/\delta)}{N}}. a N ( δ ) = 2 C μ κ 2 N log ( 2 n / δ ) , b N ( δ ) = C μ κ 2 N log ( 2 n / δ ) .
Recall K \mathbf{K} K denote the population distribution Gram matrix, K N \mathbf{K}_N K N the exact finite-bag Gram matrix, and K ^ D , N \widehat{\mathbf{K}}_{D,N} K D , N the RF finite-bag Gram matrix.
The corresponding test vectors have components
[ v ( P ) ] i = K ( P i , P ) , [\mathbf{v}(\mathbb{P})]_i=K(\mathbb{P}_i,\mathbb{P}), [ v ( P ) ] i = K ( P i , P ) ,
[ v N ( P ) ] i = K N ( P i , P ) , [\mathbf{v}_N(\mathbb{P})]_i=K_N(\mathbb{P}_i,\mathbb{P}), [ v N ( P ) ] i = K N ( P i , P ) ,
[ v ^ D , N ( P ) ] i = K D , N ( P i , P ) . [\widehat{\mathbf{v}}_{D,N}(\mathbb{P})]_i=K_{D,N}(\mathbb{P}_i,\mathbb{P}). [ v D , N ( P ) ] i = K D , N ( P i , P ) .
Thus the three predictors evaluated on a true test distribution are
f ^ λ ( P ) = v ( P ) T ( K + n λ I ) − 1 y , \widehat{f}_\lambda(\mathbb{P})=\mathbf{v}(\mathbb{P})^{\mathsf{T}}(\mathbf{K}+n\lambda\mathbf{I})^{-1}\mathbf{y}, f λ ( P ) = v ( P ) T ( K + nλ I ) − 1 y ,
f ^ λ , N ( P ) = v N ( P ) T ( K N + n λ I ) − 1 y , \widehat{f}_{\lambda,N}(\mathbb{P})=\mathbf{v}_N(\mathbb{P})^{\mathsf{T}}(\mathbf{K}_N+n\lambda\mathbf{I})^{-1}\mathbf{y}, f λ , N ( P ) = v N ( P ) T ( K N + nλ I ) − 1 y ,
f ^ λ , N , D ( P ) = v ^ D , N ( P ) T ( K ^ D , N + n λ I ) − 1 y . \widehat{f}_{\lambda,N,D}(\mathbb{P})=\widehat{\mathbf{v}}_{D,N}(\mathbb{P})^{\mathsf{T}}(\widehat{\mathbf{K}}_{D,N}+n\lambda\mathbf{I})^{-1}\mathbf{y}. f λ , N , D ( P ) = v D , N ( P ) T ( K D , N + nλ I ) − 1 y .
Lemma 5. Assume that the event of Lemma 3 holds. Then
∥ K N − K ∥ 2 ≤ n a N ( δ ) , (56) \left\|\mathbf{K}_N-\mathbf{K}\right\|_2\le n a_N(\delta), \tag*{(56)} ∥ K N − K ∥ 2 ≤ n a N ( δ ) , (56) and for every test distribution P \mathbb{P} P ,
∥ v N ( P ) − v ( P ) ∥ 2 ≤ n b N ( δ ) . (57) \left\|\mathbf{v}_N(\mathbb{P})-\mathbf{v}(\mathbb{P})\right\|_2\le\sqrt{n}\,b_N(\delta). \tag*{(57)} ∥ v N ( P ) − v ( P ) ∥ 2 ≤ n b N ( δ ) . (57)
Proof. Each entry of K N − K \mathbf{K}_N-\mathbf{K} K N − K is bounded in absolute value by a N ( δ ) a_N(\delta) a N ( δ ) . Hence,
∥ K N − K ∥ 2 ≤ ∥ K N − K ∥ F ≤ n a N ( δ ) . \lVert\mathbf{K}_N-\mathbf{K}\rVert_2\le\lVert\mathbf{K}_N-\mathbf{K}\rVert_F\le n a_N(\delta). ∥ K N − K ∥ 2 ≤ ∥ K N − K ∥ F ≤ n a N ( δ ) .
Similarly, each entry of v N ( P ) − v ( P ) \mathbf{v}_N(\mathbb{P})-\mathbf{v}(\mathbb{P}) v N ( P ) − v ( P ) is bounded by b N ( δ ) b_N(\delta) b N ( δ ) in absolute value, so
∥ v N ( P ) − v ( P ) ∥ 2 ≤ n b N ( δ ) . \lVert\mathbf{v}_N(\mathbb{P})-\mathbf{v}(\mathbb{P})\rVert_2\le\sqrt{n}b_N(\delta). ∥ v N ( P ) − v ( P ) ∥ 2 ≤ n b N ( δ ) .
Lemma 6. Assume that the event of Lemma 4 holds. Then
∥ K ^ D , N − K N ∥ 2 ≤ n ϵ D ( δ ) . (58) \lVert\widehat{\mathbf{K}}_{D,N}-\mathbf{K}_N\rVert_2\le n\epsilon_D(\delta). \tag*{(58)} ∥ K D , N − K N ∥ 2 ≤ n ϵ D ( δ ) . (58) and for every test distribution P \mathbb{P} P ,
∥ v ^ D , N ( P ) − v N ( P ) ∥ 2 ≤ n ϵ D ( δ ) . (59) \lVert\widehat{\mathbf{v}}_{D,N}(\mathbb{P})-\mathbf{v}_N(\mathbb{P})\rVert_2\le\sqrt{n}\epsilon_D(\delta). \tag*{(59)} ∥ v D , N ( P ) − v N ( P ) ∥ 2 ≤ n ϵ D ( δ ) . (59) Proof. Each entry of K ^ D , N − K N \widehat{\mathbf{K}}_{D,N}-\mathbf{K}_N K D , N − K N is bounded in absolute value by ϵ D ( δ ) \epsilon_D(\delta) ϵ D ( δ ) . Hence,
∥ K ^ D , N − K N ∥ 2 ≤ ∥ K ^ D , N − K N ∥ F ≤ n ϵ D ( δ ) . \lVert\widehat{\mathbf{K}}_{D,N}-\mathbf{K}_N\rVert_2\le\lVert\widehat{\mathbf{K}}_{D,N}-\mathbf{K}_N\rVert_F\le n\epsilon_D(\delta). ∥ K D , N − K N ∥ 2 ≤ ∥ K D , N − K N ∥ F ≤ n ϵ D ( δ ) . The test-vector bound follows in the same way because each component of v ^ D , N ( P ) − v N ( P ) \widehat{\mathbf{v}}_{D,N}(\mathbb{P})-\mathbf{v}_N(\mathbb{P}) v D , N ( P ) − v N ( P ) is bounded by ϵ D ( δ ) \epsilon_D(\delta) ϵ D ( δ ) . □
Predictor perturbation
Lemma 7. For any symmetric matrices A , B ∈ R n × n \mathbf{A},\mathbf{B}\in\mathbb{R}^{n\times n} A , B ∈ R n × n and λ > 0 \lambda>0 λ > 0 for which both shifted matrices are invertible,
( A + n λ I ) − 1 − ( B + n λ I ) − 1 = ( A + n λ I ) − 1 ( B − A ) ( B + n λ I ) − 1 . (60) (\mathbf{A}+n\lambda\mathbf{I})^{-1}-(\mathbf{B}+n\lambda\mathbf{I})^{-1}=(\mathbf{A}+n\lambda\mathbf{I})^{-1}(\mathbf{B}-\mathbf{A})(\mathbf{B}+n\lambda\mathbf{I})^{-1}. \tag*{(60)} ( A + nλ I ) − 1 − ( B + nλ I ) − 1 = ( A + nλ I ) − 1 ( B − A ) ( B + nλ I ) − 1 . (60) Moreover, if A \mathbf{A} A and B \mathbf{B} B are positive semidefinite, then
∥ ( A + n λ I ) − 1 ∥ 2 ≤ 1 n λ , ∥ ( B + n λ I ) − 1 ∥ 2 ≤ 1 n λ . \lVert(\mathbf{A}+n\lambda\mathbf{I})^{-1}\rVert_2\le\frac{1}{n\lambda},\qquad\lVert(\mathbf{B}+n\lambda\mathbf{I})^{-1}\rVert_2\le\frac{1}{n\lambda}. ∥( A + nλ I ) − 1 ∥ 2 ≤ nλ 1 , ∥( B + nλ I ) − 1 ∥ 2 ≤ nλ 1 . Proof. The identity follows by direct multiplication. The inverse norm bound follows because all eigenvalues of A + n λ I \mathbf{A}+n\lambda\mathbf{I} A + nλ I and B + n λ I \mathbf{B}+n\lambda\mathbf{I} B + nλ I are at least n λ n\lambda nλ when A \mathbf{A} A and B \mathbf{B} B are positive semidefinite. □
Lemma 8. Assume the event of Lemma 5 holds. Then there exists a constant C K , y > 0 C_{K,y}>0 C K , y > 0 , depending only on κ \kappa κ and C y C_y C y , such that for every test distribution P \mathbb{P} P ,
∣ f ^ λ , N ( P ) − f ^ λ ( P ) ∣ ≤ C K , y ( b N ( δ ) λ + a N ( δ ) λ 2 ) . (61) \left|\widehat{f}_{\lambda,N}(\mathbb{P})-\widehat{f}_{\lambda}(\mathbb{P})\right|\le C_{K,y}\left(\frac{b_N(\delta)}{\lambda}+\frac{a_N(\delta)}{\lambda^2}\right). \tag*{(61)} f λ , N ( P ) − f λ ( P ) ≤ C K , y ( λ b N ( δ ) + λ 2 a N ( δ ) ) . (61) Proof. Set
A N = K N + n λ I , A = K + n λ I . \mathbf{A}_N=\mathbf{K}_N+n\lambda\mathbf{I},\qquad\mathbf{A}=\mathbf{K}+n\lambda\mathbf{I}. A N = K N + nλ I , A = K + nλ I . Subtracting the one-stage estimator from the exact two-stage estimator gives
f ^ λ , N ( P ) − f ^ λ ( P ) = ( v N ( P ) − v ( P ) ) T A N − 1 y + v ( P ) T ( A N − 1 − A − 1 ) y . \widehat{f}_{\lambda,N}(\mathbb{P})-\widehat{f}_{\lambda}(\mathbb{P})=(\mathbf{v}_N(\mathbb{P})-\mathbf{v}(\mathbb{P}))^{\mathsf{T}}\mathbf{A}_N^{-1}\mathbf{y}+\mathbf{v}(\mathbb{P})^{\mathsf{T}}(\mathbf{A}_N^{-1}-\mathbf{A}^{-1})\mathbf{y}. f λ , N ( P ) − f λ ( P ) = ( v N ( P ) − v ( P ) ) T A N − 1 y + v ( P ) T ( A N − 1 − A − 1 ) y .
Denote these two terms by B 1 B_1 B 1 and B 2 B_2 B 2 .
For B 1 B_1 B 1 , using Cauchy–Schwarz, Lemma 7, and (57),
∣ B 1 ∣ ≤ ∥ v N ( P ) − v ( P ) ∥ 2 ∥ A N − 1 ∥ 2 ∥ y ∥ 2 ≤ n b N ( δ ) n λ n C y = C y b N ( δ ) λ . |B_1| \le\|\mathbf{v}_N(\mathbb{P})-\mathbf{v}(\mathbb{P})\|_2\|A_N^{-1}\|_2\|\mathbf{y}\|_2 \le\frac{\sqrt{n}\,b_N(\delta)}{n\lambda}\sqrt{n}C_y = \frac{C_yb_N(\delta)}{\lambda}. ∣ B 1 ∣ ≤ ∥ v N ( P ) − v ( P ) ∥ 2 ∥ A N − 1 ∥ 2 ∥ y ∥ 2 ≤ nλ n b N ( δ ) n C y = λ C y b N ( δ ) .
For B 2 B_2 B 2 , the resolvent identity in Lemma 7 gives
A N − 1 − A − 1 = A N − 1 ( K − K N ) A − 1 . A_N^{-1}-A^{-1}=A_N^{-1}(K-K_N)A^{-1}. A N − 1 − A − 1 = A N − 1 ( K − K N ) A − 1 .
Therefore,
∣ B 2 ∣ ≤ ∥ v ( P ) ∥ 2 ∥ A N − 1 ∥ 2 ∥ K N − K ∥ 2 ∥ A − 1 ∥ 2 ∥ y ∥ 2 . |B_2| \le\|\mathbf{v}(\mathbb{P})\|_2\|A_N^{-1}\|_2\|K_N-K\|_2\|A^{-1}\|_2\|\mathbf{y}\|_2. ∣ B 2 ∣ ≤ ∥ v ( P ) ∥ 2 ∥ A N − 1 ∥ 2 ∥ K N − K ∥ 2 ∥ A − 1 ∥ 2 ∥ y ∥ 2 .
Each component of v ( P ) \mathbf{v}(\mathbb{P}) v ( P ) satisfies
∣ K ( P i , P ) ∣ ≤ κ 2 , |K(\mathbb{P}_i,\mathbb{P})| \le\kappa^2, ∣ K ( P i , P ) ∣ ≤ κ 2 ,
so ∥ v ( P ) ∥ 2 ≤ n κ 2 \|\mathbf{v}(\mathbb{P})\|_2 \le\sqrt{n}\,\kappa^2 ∥ v ( P ) ∥ 2 ≤ n κ 2 . Using ∥ y ∥ 2 ≤ n C y \|\mathbf{y}\|_2 \le\sqrt{n}C_y ∥ y ∥ 2 ≤ n C y and (56),
∣ B 2 ∣ ≤ n κ 2 n C y ( n λ ) 2 n a N ( δ ) = κ 2 C y a N ( δ ) λ 2 . |B_2| \le\frac{\sqrt{n}\,\kappa^2\sqrt{n}C_y}{(n\lambda)^2}na_N(\delta) = \frac{\kappa^2C_ya_N(\delta)}{\lambda^2}. ∣ B 2 ∣ ≤ ( nλ ) 2 n κ 2 n C y n a N ( δ ) = λ 2 κ 2 C y a N ( δ ) .
Combining the two bounds and absorbing constants into C K , y C_{K,y} C K , y proves the claim. □
Lemma 9. Assume the event of Lemma 6 holds. Then there exists a constant C K , y > 0 C_{K,y}>0 C K , y > 0 , depending only on κ \kappa κ and C y C_y C y , such that for every test distribution P \mathbb{P} P ,
∣ f ^ λ , N , D ( P ) − f ^ λ , N ( P ) ∣ ≤ C K , y ( ϵ D ( δ ) λ + ϵ D ( δ ) λ 2 ) . (62) |\widehat{f}_{\lambda,N,D}(\mathbb{P})-\widehat{f}_{\lambda,N}(\mathbb{P})| \le C_{K,y}\left(\frac{\epsilon_D(\delta)}{\lambda}+\frac{\epsilon_D(\delta)}{\lambda^2}\right). \tag*{(62)} ∣ f λ , N , D ( P ) − f λ , N ( P ) ∣ ≤ C K , y ( λ ϵ D ( δ ) + λ 2 ϵ D ( δ ) ) . (62)
Proof. Set
A D , N = K ^ D , N + n λ I , A N = K N + n λ I . A_{D,N}=\widehat{K}_{D,N}+n\lambda I,\qquad A_N=K_N+n\lambda I. A D , N = K D , N + nλ I , A N = K N + nλ I .
Subtracting the exact two-stage predictor from the RF two-stage predictor gives
f ^ λ , N , D ( P ) − f ^ λ , N ( P ) = ( v ^ D , N ( P ) − v N ( P ) ) ⊤ A D , N − 1 y + v N ( P ) ⊤ ( A D , N − 1 − A N − 1 ) y . \widehat{f}_{\lambda,N,D}(\mathbb{P})-\widehat{f}_{\lambda,N}(\mathbb{P})=(\widehat{\mathbf{v}}_{D,N}(\mathbb{P})-\mathbf{v}_N(\mathbb{P}))^\top A_{D,N}^{-1}\mathbf{y}+\mathbf{v}_N(\mathbb{P})^\top(A_{D,N}^{-1}-A_N^{-1})\mathbf{y}. f λ , N , D ( P ) − f λ , N ( P ) = ( v D , N ( P ) − v N ( P ) ) ⊤ A D , N − 1 y + v N ( P ) ⊤ ( A D , N − 1 − A N − 1 ) y .
Denote these two terms by C 1 C_1 C 1 and C 2 C_2 C 2 .
For C 1 C_1 C 1 ,
∣ C 1 ∣ ≤ ∥ v ^ D , N ( P ) − v N ( P ) ∥ 2 ∥ A D , N − 1 ∥ 2 ∥ y ∥ 2 ≤ n ϵ D ( δ ) n λ n C y = C y ϵ D ( δ ) λ . |C_1| \le\|\widehat{\mathbf{v}}_{D,N}(\mathbb{P})-\mathbf{v}_N(\mathbb{P})\|_2\|A_{D,N}^{-1}\|_2\|\mathbf{y}\|_2 \le\frac{\sqrt{n}\,\epsilon_D(\delta)}{n\lambda}\sqrt{n}C_y = \frac{C_y\epsilon_D(\delta)}{\lambda}. ∣ C 1 ∣ ≤ ∥ v D , N ( P ) − v N ( P ) ∥ 2 ∥ A D , N − 1 ∥ 2 ∥ y ∥ 2 ≤ nλ n ϵ D ( δ ) n C y = λ C y ϵ D ( δ ) .
For C 2 C_2 C 2 , the resolvent identity gives
A D , N − 1 − A N − 1 = A D , N − 1 ( K N − K ^ D , N ) A N − 1 . A_{D,N}^{-1}-A_N^{-1}=A_{D,N}^{-1}(K_N-\widehat{K}_{D,N})A_N^{-1}. A D , N − 1 − A N − 1 = A D , N − 1 ( K N − K D , N ) A N − 1 .
Thus,
∣ C 2 ∣ ≤ ∥ v N ( P ) ∥ 2 ∥ A D , N − 1 ∥ 2 ∥ K ^ D , N − K N ∥ 2 ∥ A N − 1 ∥ 2 ∥ y ∥ 2 . |C_2| \le\|\mathbf{v}_N(\mathbb{P})\|_2\|A_{D,N}^{-1}\|_2\|\widehat{K}_{D,N}-K_N\|_2\|A_N^{-1}\|_2\|\mathbf{y}\|_2. ∣ C 2 ∣ ≤ ∥ v N ( P ) ∥ 2 ∥ A D , N − 1 ∥ 2 ∥ K D , N − K N ∥ 2 ∥ A N − 1 ∥ 2 ∥ y ∥ 2 .
Since ∣ K N ( P i , P ) ∣ ≤ κ 2 |K_N(\mathbb{P}_i,\mathbb{P})| \le\kappa^2 ∣ K N ( P i , P ) ∣ ≤ κ 2 , we have ∥ v N ( P ) ∥ 2 ≤ n κ 2 \|\mathbf{v}_N(\mathbb{P})\|_2 \le\sqrt{n}\,\kappa^2 ∥ v N ( P ) ∥ 2 ≤ n κ 2 . Combining this with ∥ y ∥ 2 ≤ n C y \|\mathbf{y}\|_2 \le\sqrt{n}C_y ∥ y ∥ 2 ≤ n C y and (58),
∣ C 2 ∣ ≤ n κ 2 n C y ( n λ ) 2 n ϵ D ( δ ) = κ 2 C y ϵ D ( δ ) λ 2 . |C_2| \le\frac{\sqrt{n}\,\kappa^2\sqrt{n}C_y}{(n\lambda)^2}n\epsilon_D(\delta) = \frac{\kappa^2C_y\epsilon_D(\delta)}{\lambda^2}. ∣ C 2 ∣ ≤ ( nλ ) 2 n κ 2 n C y n ϵ D ( δ ) = λ 2 κ 2 C y ϵ D ( δ ) .
Combining the two bounds proves the claim. □
Lemma 10. For squared loss,
E ( f , f ρ ) = ∥ f − f ρ ∥ L 2 ( ρ X ) 2 . (63) \mathcal{E}(f, f_\rho) = \lVert f - f_\rho\rVert_{L^2(\rho_X)}^2. \tag*{(63)} E ( f , f ρ ) = ∥ f − f ρ ∥ L 2 ( ρ X ) 2 . (63) Consequently, for any predictors f f f and g g g ,
E ( f , f ρ ) ≤ 2 E ( g , f ρ ) + 2 ∥ f − g ∥ L 2 ( ρ X ) 2 . (64) \mathcal{E}(f, f_\rho) \le2\mathcal{E}(g, f_\rho) + 2\lVert f - g \rVert_{L^2(\rho_X)}^2. \tag*{(64)} E ( f , f ρ ) ≤ 2 E ( g , f ρ ) + 2 ∥ f − g ∥ L 2 ( ρ X ) 2 . (64) If sup P ∣ f ( P ) − g ( P ) ∣ ≤ Δ \sup_{\mathbb{P}} |f(\mathbb{P}) - g(\mathbb{P})| \le\Delta sup P ∣ f ( P ) − g ( P ) ∣ ≤ Δ , then
E ( f , f ρ ) ≤ 2 E ( g , f ρ ) + 2 Δ 2 . (65) \mathcal{E}(f, f_\rho) \le2\mathcal{E}(g, f_\rho) + 2\Delta^2. \tag*{(65)} E ( f , f ρ ) ≤ 2 E ( g , f ρ ) + 2 Δ 2 . (65) Proof. The identity (63) is the standard orthogonality identity for squared loss:
R [ f ] − R [ f ρ ] = E P ∼ ρ X [ ( f ( P ) − f ρ ( P ) ) 2 ] . \mathcal{R}[f] - \mathcal{R}[f_\rho] = \mathbb{E}_{\mathbb{P}\sim\rho_X}\left[(f(\mathbb{P}) - f_\rho(\mathbb{P}))^2\right]. R [ f ] − R [ f ρ ] = E P ∼ ρ X [ ( f ( P ) − f ρ ( P ) ) 2 ] . Now write
f − f ρ = ( f − g ) + ( g − f ρ ) . f - f_\rho= (f - g) + (g - f_\rho). f − f ρ = ( f − g ) + ( g − f ρ ) . Using ( u + v ) 2 ≤ 2 u 2 + 2 v 2 (u+v)^2 \le2u^2 + 2v^2 ( u + v ) 2 ≤ 2 u 2 + 2 v 2 and integrating with respect to ρ X \rho_X ρ X gives (64). The last claim follows from
∥ f − g ∥ L 2 ( ρ X ) 2 ≤ sup P ∣ f ( P ) − g ( P ) ∣ 2 . \lVert f - g \rVert_{L^2(\rho_X)}^2 \le\sup_{\mathbb{P}} |f(\mathbb{P}) - g(\mathbb{P})|^2. ∥ f − g ∥ L 2 ( ρ X ) 2 ≤ P sup ∣ f ( P ) − g ( P ) ∣ 2 .
Proofs of the exact two-stage and RF risk bounds
For η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) , define the deterministic perturbation error
Δ N ( η ) = C K , y ( b N ( η ) λ + a N ( η ) λ 2 ) , \Delta_N(\eta) = C_{K,y}\left(\frac{b_N(\eta)}{\lambda} + \frac{a_N(\eta)}{\lambda^2}\right), Δ N ( η ) = C K , y ( λ b N ( η ) + λ 2 a N ( η ) ) ,
Δ D ( η ) = C K , y ϵ D ( η ) ( λ − 1 + λ − 2 ) . \Delta_D(\eta) = C_{K,y}\epsilon_D(\eta)\left(\lambda^{-1} + \lambda^{-2}\right). Δ D ( η ) = C K , y ϵ D ( η ) ( λ − 1 + λ − 2 ) .
Lemmas 8 and 9 imply the corresponding uniform predictor bounds on events of probability at least 1 − η 1-\eta 1 − η . Moreover,
Δ N ( η ) 2 ≤ C log ( 2 n / η ) N ( λ − 2 + λ − 4 ) , \Delta_N(\eta)^2 \le C\frac{\log(2n/\eta)}{N}\left(\lambda^{-2}+\lambda^{-4}\right), Δ N ( η ) 2 ≤ C N log ( 2 n / η ) ( λ − 2 + λ − 4 ) ,
and
Δ D ( η ) 2 ≤ C ϵ D ( η ) 2 ( λ − 2 + λ − 4 ) , \Delta_D(\eta)^2 \le C\epsilon_D(\eta)^2\left(\lambda^{-2}+\lambda^{-4}\right), Δ D ( η ) 2 ≤ C ϵ D ( η ) 2 ( λ − 2 + λ − 4 ) ,
where C C C depends only on the fixed boundedness constants.
Proof of Theorem 1. Use failure probability δ / 2 \delta/2 δ /2 for the one-stage baseline and δ / 2 \delta/2 δ /2 for the training-bag concentration event. Their intersection has probability at least 1 − δ 1-\delta 1 − δ . On this intersection, Lemma 10 gives
E ( f ^ λ , N , f ρ ) ≤ 2 B 1 s ( n , λ , δ / 2 ) + 2 Δ N ( δ / 2 ) 2 . \mathcal{E}(\widehat{f}_{\lambda,N}, f_\rho) \le2B_{1s}(n,\lambda,\delta/2) + 2\Delta_N(\delta/2)^2. E ( f λ , N , f ρ ) ≤ 2 B 1 s ( n , λ , δ /2 ) + 2 Δ N ( δ /2 ) 2 .
The concentration term involves log ( 4 n / δ ) \log(4n/\delta) log ( 4 n / δ ) . Since n ≥ 1 n \ge1 n ≥ 1 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) ,
log ( 4 n / δ ) ≤ 2 log ( 2 n / δ ) . \log(4n/\delta) \le2\log(2n/\delta). log ( 4 n / δ ) ≤ 2 log ( 2 n / δ ) .
Absorbing this numerical factor into C 2 C_2 C 2 proves (14). ∎
Proof of Theorem 2. Allocate failure probability δ / 3 \delta/3 δ /3 separately to: the one-stage baseline, the training-bag concentration event, and the uniform RF approximation event. A union bound gives simultaneous validity with probability at least 1 − δ 1-\delta 1 − δ ; independence of these events is not needed.
On their intersection, applying Lemma 10 twice gives
E ( f ^ λ , N , D , f ρ ) ≤ 2 E ( f ^ λ , N , f ρ ) + 2 Δ D ( δ / 3 ) 2 \mathcal{E}(\widehat{f}_{\lambda,N,D},f_{\rho}) \le2\mathcal{E}(\widehat{f}_{\lambda,N},f_{\rho})+2\Delta_{D}(\delta/3)^2 E ( f λ , N , D , f ρ ) ≤ 2 E ( f λ , N , f ρ ) + 2 Δ D ( δ /3 ) 2
≤ 4 E ( f ^ λ , f ρ ) + 4 Δ N ( δ / 3 ) 2 + 2 Δ D ( δ / 3 ) 2 \le4\mathcal{E}(\widehat{f}_{\lambda},f_{\rho})+4\Delta_{N}(\delta/3)^2+2\Delta_{D}(\delta/3)^2 ≤ 4 E ( f λ , f ρ ) + 4 Δ N ( δ /3 ) 2 + 2 Δ D ( δ /3 ) 2
≤ 4 B 1 s ( n , λ , δ / 3 ) + 4 Δ N ( δ / 3 ) 2 + 2 Δ D ( δ / 3 ) 2 . \le4B_{1s}(n,\lambda,\delta/3)+4\Delta_{N}(\delta/3)^2+2\Delta_{D}(\delta/3)^2. ≤ 4 B 1 s ( n , λ , δ /3 ) + 4 Δ N ( δ /3 ) 2 + 2 Δ D ( δ /3 ) 2 .
Finally,
log ( 6 n / δ ) ≤ 2 log ( 3 n / δ ) . \log(6n/\delta)\le2\log(3n/\delta). log ( 6 n / δ ) ≤ 2 log ( 3 n / δ ) .
Substituting the perturbation-radius bounds and absorbing fixed numerical factors into C 3 C_{3} C 3 proves (15) . □
Population excess risk versus deployed empirical test bags
Theorems 1 and 2 are population statements computed on true test distributions P ∼ ρ X \mathbb{P}\sim\rho_{X} P ∼ ρ X . We now analyze the additional perturbation that appears when, at deployment time, a new test distribution is available only through a fresh bag. Conditional on the test distribution, this bag is independent of the training data, the random features, and the test response.
Let
x ~ 1 , … , x ~ N t ∼ i . i . d . P , P ^ N t = 1 N t ∑ r = 1 N t δ x ~ r . \widetilde{\mathbf{x}}_{1},\ldots,\widetilde{\mathbf{x}}_{N_t}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mathbb{P},\qquad\widehat{\mathbb{P}}^{N_t}=\frac{1}{N_t}\sum_{r=1}^{N_t}\delta_{\widetilde{\mathbf{x}}_{r}}. x 1 , … , x N t ∼ i.i.d. P , P N t = N t 1 r = 1 ∑ N t δ x r .
Define the deployed predictors
f ^ λ , N ( N t ) ( P ) = f ^ λ , N ( P ^ N t ) , f ^ λ , N , D ( N t ) ( P ) = f ^ λ , N , D ( P ^ N t ) . \widehat{f}_{\lambda,N}^{(N_t)}(\mathbb{P})=\widehat{f}_{\lambda,N}(\widehat{\mathbb{P}}^{N_t}),\qquad\widehat{f}_{\lambda,N,D}^{(N_t)}(\mathbb{P})=\widehat{f}_{\lambda,N,D}(\widehat{\mathbb{P}}^{N_t}). f λ , N ( N t ) ( P ) = f λ , N ( P N t ) , f λ , N , D ( N t ) ( P ) = f λ , N , D ( P N t ) .
Lemma 11. Under Assumption 1, for any fixed test distribution P \mathbb{P} P and any δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) ,
P ( ∥ μ ^ P N t − μ P ∥ H k ≤ C μ κ log ( 2 / δ ) N t ) ≥ 1 − δ . \mathbb{P}\left(\left\|\widehat{\mu}_{\mathbb{P}}^{N_t}-\mu_{\mathbb{P}}\right\|_{\mathcal{H}_k}\le C_{\mu}\kappa\sqrt{\frac{\log(2/\delta)}{N_t}}\right)\ge1-\delta. P μ P N t − μ P H k ≤ C μ κ N t log ( 2/ δ ) ≥ 1 − δ .
Proof. Condition on the test distribution P \mathbb{P} P . Then
μ ^ P N t − μ P = 1 N t ∑ r = 1 N t ( k ( ⋅ , x ~ r ) − μ P ) , x ~ r ∼ i . i . d . P . \widehat{\mu}_{\mathbb{P}}^{N_t}-\mu_{\mathbb{P}}=\frac{1}{N_t}\sum_{r=1}^{N_t}\left(k(\cdot,\widetilde{\mathbf{x}}_r)-\mu_{\mathbb{P}}\right),\qquad\widetilde{\mathbf{x}}_r\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mathbb{P}. μ P N t − μ P = N t 1 r = 1 ∑ N t ( k ( ⋅ , x r ) − μ P ) , x r ∼ i.i.d. P .
The summands are centered Hilbert-space-valued random variables with norm at most 2 κ 2\kappa 2 κ . Apply Lemma 1 with sample size N t N_t N t to obtain the result. □
Proposition 6. Under Assumption 1, fix the training sample and a test distribution P \mathbb{P} P . Then, with probability at least 1 − δ 1-\delta 1 − δ over the test bag, we have
∣ f ^ λ , N ( N t ) ( P ) − f ^ λ , N ( P ) ∣ ≤ C μ C y κ 2 λ log ( 2 / δ ) N t . (66) \left|\widehat{f}_{\lambda,N}^{(N_t)}(\mathbb{P})-\widehat{f}_{\lambda,N}(\mathbb{P})\right|\le\frac{C_{\mu}C_y\kappa^2}{\lambda}\sqrt{\frac{\log(2/\delta)}{N_t}}. \tag*{(66)} f λ , N ( N t ) ( P ) − f λ , N ( P ) ≤ λ C μ C y κ 2 N t log ( 2/ δ ) . (66)
Proof. By definition,
f ^ λ , N ( N t ) ( P ) − f ^ λ , N ( P ) = ( v N ( P ^ N t ) − v N ( P ) ) T ( K N + n λ I ) − 1 y . \widehat{f}_{\lambda,N}^{(N_t)}(\mathbb{P})-\widehat{f}_{\lambda,N}(\mathbb{P})=\left(\mathbf{v}_{N}(\widehat{\mathbb{P}}^{N_t})-\mathbf{v}_{N}(\mathbb{P})\right)^{\mathsf{T}}(\mathbf{K}_{N}+n\lambda\mathbf{I})^{-1}\mathbf{y}. f λ , N ( N t ) ( P ) − f λ , N ( P ) = ( v N ( P N t ) − v N ( P ) ) T ( K N + nλ I ) − 1 y .
Thus,
∣ f ^ λ , N ( N t ) ( P ) − f ^ λ , N ( P ) ∣ ≤ ∥ v N ( P ^ N t ) − v N ( P ) ∥ 2 ∥ ( K N + n λ I ) − 1 ∥ 2 ∥ y ∥ 2 . \left|\widehat{f}_{\lambda,N}^{(N_t)}(\mathbb{P})-\widehat{f}_{\lambda,N}(\mathbb{P})\right|\leq\|\mathbf{v}_{N}(\widehat{\mathbb{P}}^{N_t})-\mathbf{v}_{N}(\mathbb{P})\|_{2}\|(\mathbf{K}_{N}+n\lambda\mathbf{I})^{-1}\|_{2}\|\mathbf{y}\|_{2}. f λ , N ( N t ) ( P ) − f λ , N ( P ) ≤ ∥ v N ( P N t ) − v N ( P ) ∥ 2 ∥ ( K N + nλ I ) − 1 ∥ 2 ∥ y ∥ 2 .
We have
∥ ( K N + n λ I ) − 1 ∥ 2 ≤ 1 n λ , ∥ y ∥ 2 ≤ n C y . \|(\mathbf{K}_{N}+n\lambda\mathbf{I})^{-1}\|_{2}\leq\frac{1}{n\lambda},\qquad\|\mathbf{y}\|_{2}\leq\sqrt{n}C_{y}. ∥ ( K N + nλ I ) − 1 ∥ 2 ≤ nλ 1 , ∥ y ∥ 2 ≤ n C y .
For each i i i ,
K N ( P i , P ^ N t ) − K N ( P i , P ) = ⟨ μ ^ i , μ ^ P N t − μ P ⟩ H K . K_{N}(\mathbb{P}_{i},\widehat{\mathbb{P}}^{N_t})-K_{N}(\mathbb{P}_{i},\mathbb{P})=\langle\widehat{\boldsymbol{\mu}}_{i},\widehat{\boldsymbol{\mu}}_{\mathbb{P}}^{N_t}-\boldsymbol{\mu}_{\mathbb{P}}\rangle_{\mathcal{H}_{K}}. K N ( P i , P N t ) − K N ( P i , P ) = ⟨ μ i , μ P N t − μ P ⟩ H K .
Since ∥ μ ^ i ∥ H K ≤ κ \|\widehat{\boldsymbol{\mu}}_{i}\|_{\mathcal{H}_{K}}\leq\kappa ∥ μ i ∥ H K ≤ κ , Lemma 11 implies
∣ K N ( P i , P ^ N t ) − K N ( P i , P ) ∣ ≤ C μ κ 2 log ( 2 / δ ) N t . \left|K_{N}(\mathbb{P}_{i},\widehat{\mathbb{P}}^{N_t})-K_{N}(\mathbb{P}_{i},\mathbb{P})\right|\leq C_{\mu}\kappa^{2}\sqrt{\frac{\log(2/\delta)}{N_t}}. K N ( P i , P N t ) − K N ( P i , P ) ≤ C μ κ 2 N t log ( 2/ δ ) .
Therefore,
∥ v N ( P ^ N t ) − v N ( P ) ∥ 2 ≤ n C μ κ 2 log ( 2 / δ ) N t . \|\mathbf{v}_{N}(\widehat{\mathbb{P}}^{N_t})-\mathbf{v}_{N}(\mathbb{P})\|_{2}\leq\sqrt{n}C_{\mu}\kappa^{2}\sqrt{\frac{\log(2/\delta)}{N_t}}. ∥ v N ( P N t ) − v N ( P ) ∥ 2 ≤ n C μ κ 2 N t log ( 2/ δ ) .
Substitution gives (66). □
Lemma 12. For any fixed test distribution P \mathbb{P} P , any set of random features ( ω r , b r ) r = 1 D (\boldsymbol{\omega}_{r},b_{r})_{r=1}^{D} ( ω r , b r ) r = 1 D , and any δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , there exists a universal constant C ϕ > 0 C_{\phi}>0 C ϕ > 0 such that
P ( ∥ μ ^ P , D N t − μ P , D ∥ 2 ≤ C ϕ log ( 2 / δ ) N t ) ≥ 1 − δ . \mathbb{P}\left(\|\widehat{\boldsymbol{\mu}}_{\mathbb{P},D}^{N_t}-\boldsymbol{\mu}_{\mathbb{P},D}\|_{2}\leq C_{\phi}\sqrt{\frac{\log(2/\delta)}{N_t}}\right)\geq1-\delta. P ∥ μ P , D N t − μ P , D ∥ 2 ≤ C ϕ N t log ( 2/ δ ) ≥ 1 − δ .
Proof. Condition on P \mathbb{P} P and on the realized random features. The random-bias cosine map satisfies
∥ ϕ D ( x ) ∥ 2 2 = 2 D ∑ r = 1 D cos 2 ( ω r T x + b r ) ≤ 2. \|\boldsymbol{\phi}_{D}(\mathbf{x})\|_{2}^{2}=\frac{2}{D}\sum_{r=1}^{D}\cos^{2}(\boldsymbol{\omega}_{r}^{\mathsf{T}}\mathbf{x}+b_{r})\leq2. ∥ ϕ D ( x ) ∥ 2 2 = D 2 r = 1 ∑ D cos 2 ( ω r T x + b r ) ≤ 2.
Thus,
∥ ϕ D ( x ‾ r ) − μ P , D ∥ 2 ≤ 2 2 . \|\boldsymbol{\phi}_{D}(\overline{\mathbf{x}}_{r})-\boldsymbol{\mu}_{\mathbb{P},D}\|_{2}\leq2\sqrt{2}. ∥ ϕ D ( x r ) − μ P , D ∥ 2 ≤ 2 2 .
The expectation and bounded-differences argument in Lemma 1, with feature-norm bound 2 \sqrt{2} 2 and sample size N t N_t N t , gives the result. One may take C ϕ = 2 C μ C_{\phi}=\sqrt{2}C_{\mu} C ϕ = 2 C μ . □
Proposition 7. Under Assumption 1 , fix the training sample, the realized random features, and a test distribution P \mathbb{P} P . Then, with probability at least 1 − δ 1-\delta 1 − δ over the test bag,
∣ f ^ λ , N , D ( N t ) ( P ) − f ^ λ , N , D ( P ) ∣ ≤ 2 C ϕ C y λ log ( 2 / δ ) N t . (67) \left|\widehat{f}_{\lambda,N,D}^{(N_t)}(\mathbb{P})-\widehat{f}_{\lambda,N,D}(\mathbb{P})\right|\leq\frac{\sqrt{2}C_{\phi}C_{y}}{\lambda}\sqrt{\frac{\log(2/\delta)}{N_t}}. \tag*{(67)} f λ , N , D ( N t ) ( P ) − f λ , N , D ( P ) ≤ λ 2 C ϕ C y N t log ( 2/ δ ) . (67)
Proof. By definition,
f ^ λ , N , D ( N t ) ( P ) − f ^ λ , N , D ( P ) = ( v ^ D , N ( P ^ N t ) − v ^ D , N ( P ) ) T ( K ^ D , N + n λ I ) − 1 y . \widehat{f}^{(N_t)}_{\lambda,N,D}(\mathbb{P})-\widehat{f}_{\lambda,N,D}(\mathbb{P})=\left(\widehat{\mathbf{v}}_{D,N}(\widehat{\mathbb{P}}^{N_t})-\widehat{\mathbf{v}}_{D,N}(\mathbb{P})\right)^{\mathsf{T}}\left(\widehat{\mathbf{K}}_{D,N}+n\lambda I\right)^{-1}\mathbf{y}. f λ , N , D ( N t ) ( P ) − f λ , N , D ( P ) = ( v D , N ( P N t ) − v D , N ( P ) ) T ( K D , N + nλ I ) − 1 y .
Hence,
∣ f ^ λ , N , D ( N t ) ( P ) − f ^ λ , N , D ( P ) ∣ ≤ ∥ v ^ D , N ( P ^ N t ) − v ^ D , N ( P ) ∥ 2 1 n λ n C y . \left|\widehat{f}^{(N_t)}_{\lambda,N,D}(\mathbb{P})-\widehat{f}_{\lambda,N,D}(\mathbb{P})\right|\leq\left\|\widehat{\mathbf{v}}_{D,N}(\widehat{\mathbb{P}}^{N_t})-\widehat{\mathbf{v}}_{D,N}(\mathbb{P})\right\|_{2}\frac{1}{n\lambda}\sqrt{n}C_y. f λ , N , D ( N t ) ( P ) − f λ , N , D ( P ) ≤ v D , N ( P N t ) − v D , N ( P ) 2 nλ 1 n C y .
For each i i i ,
K D , N ( P i , P ^ N t ) − K D , N ( P i , P ) = ⟨ μ ^ i , D , μ ^ P , D N t − μ P , D ⟩ 2 . K_{D,N}(\mathbb{P}_i,\widehat{\mathbb{P}}^{N_t})-K_{D,N}(\mathbb{P}_i,\mathbb{P})=\left\langle\widehat{\boldsymbol{\mu}}_{i,D},\widehat{\boldsymbol{\mu}}_{\mathbb{P},D}^{N_t}-\boldsymbol{\mu}_{\mathbb{P},D}\right\rangle_2. K D , N ( P i , P N t ) − K D , N ( P i , P ) = ⟨ μ i , D , μ P , D N t − μ P , D ⟩ 2 .
Since ∥ μ ^ i , D ∥ 2 ≤ 2 \|\widehat{\boldsymbol{\mu}}_{i,D}\|_2\leq\sqrt{2} ∥ μ i , D ∥ 2 ≤ 2 , Lemma 12 implies
∣ K D , N ( P i , P ^ N t ) − K D , N ( P i , P ) ∣ ≤ 2 C ϕ log ( 2 / δ ) N t . \left|K_{D,N}(\mathbb{P}_i,\widehat{\mathbb{P}}^{N_t})-K_{D,N}(\mathbb{P}_i,\mathbb{P})\right|\leq\sqrt{2}C_{\phi}\sqrt{\frac{\log(2/\delta)}{N_t}}. K D , N ( P i , P N t ) − K D , N ( P i , P ) ≤ 2 C ϕ N t log ( 2/ δ ) .
Therefore,
∥ v ^ D , N ( P ^ N t ) − v ^ D , N ( P ) ∥ 2 ≤ 2 n C ϕ log ( 2 / δ ) N t . \left\|\widehat{\mathbf{v}}_{D,N}(\widehat{\mathbb{P}}^{N_t})-\widehat{\mathbf{v}}_{D,N}(\mathbb{P})\right\|_2\leq\sqrt{2n}C_{\phi}\sqrt{\frac{\log(2/\delta)}{N_t}}. v D , N ( P N t ) − v D , N ( P ) 2 ≤ 2 n C ϕ N t log ( 2/ δ ) .
Substitution proves (67) .
Remark 4. The population excess-risk theorems measure generalization on true test distributions. The deployment perturbation bounds measure the additional pointwise error caused by replacing a true test distribution by a fresh empirical test bag. The latter contributes a separate N t − 1 / 2 N_t^{-1/2} N t − 1/2 term with only one factor of λ − 1 \lambda^{-1} λ − 1 .
Proof of the no-loss result (Corollary 1)
Proof. Work under the assumptions of Theorem 2 and fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Let N = N n → ∞ N=N_n\to\infty N = N n → ∞ , N n ≤ n p N_n\leq n^p N n ≤ n p , and D n ≍ N n D_n\asymp N_n D n ≍ N n . Theorem 5 gives, for sufficiently large n n n ,
ϵ D n ( δ / 3 ) 2 ≤ C δ log ( e D n ) D n . \epsilon_{D_n}(\delta/3)^2\leq C_{\delta}\frac{\log(eD_n)}{D_n}. ϵ D n ( δ /3 ) 2 ≤ C δ D n log ( e D n ) .
Because D n ≍ N n D_n\asymp N_n D n ≍ N n and N n ≤ n p N_n\leq n^p N n ≤ n p , there are constants c 1 , c 2 > 0 c_1,c_2>0 c 1 , c 2 > 0 such that, for all sufficiently large n n n ,
D n ≥ c 1 N n , log ( e D n ) ≤ c 2 log n . D_n\geq c_1N_n,\qquad\log(eD_n)\leq c_2\log n. D n ≥ c 1 N n , log ( e D n ) ≤ c 2 log n .
Consequently,
ϵ D n ( δ / 3 ) 2 ≤ C log ( 3 n / δ ) N n . \epsilon_{D_n}(\delta/3)^2\leq C\frac{\log(3n/\delta)}{N_n}. ϵ D n ( δ /3 ) 2 ≤ C N n log ( 3 n / δ ) .
Define
G n = log ( 3 n / δ ) N n ( λ n − 2 + λ n − 4 ) . G_n=\frac{\log(3n/\delta)}{N_n}\left(\lambda_n^{-2}+\lambda_n^{-4}\right). G n = N n log ( 3 n / δ ) ( λ n − 2 + λ n − 4 ) .
Theorem 2 therefore implies
E ( f ^ λ n , N n , D n , f ρ ) ≤ 4 B 1 s ( n , λ n , δ / 3 ) + C G n \mathcal{E}(\widehat{f}_{\lambda_n,N_n,D_n},f_{\rho})\leq4B_1s(n,\lambda_n,\delta/3)+CG_n E ( f λ n , N n , D n , f ρ ) ≤ 4 B 1 s ( n , λ n , δ /3 ) + C G n
with probability at least 1 − δ 1-\delta 1 − δ . Here λ n \lambda_n λ n must satisfy the chosen baseline conditions at confidence level δ / 3 \delta/3 δ /3 .
For comparison, applying Theorem 1 with failure probability 2 δ / 3 2\delta/3 2 δ /3 yields
E ( f ^ λ n , N n , f ρ ) ≤ 2 B 1 s ( n , λ n , δ / 3 ) + C 2 G n \mathcal{E}(\widehat{f}_{\lambda_n,N_n},f_\rho) \le2B_{1s}(n,\lambda_n,\delta/3)+C_2G_n E ( f λ n , N n , f ρ ) ≤ 2 B 1 s ( n , λ n , δ /3 ) + C 2 G n
with probability at least 1 − 2 δ / 3 1-2\delta/3 1 − 2 δ /3 . Thus the two guarantees have the same upper-bound order under a common probability. Both estimates can also be controlled simultaneously on the three-event intersection used in the proof of Theorem 2.
For computation, use direct feature construction and dense linear algebra, with fixed instance dimension and fixed kernel parameters. Choosing the less expensive ridge formulation gives
T R a D R = O ( n N D + min { n D 2 + D 3 , n 2 D + n 3 } ) . T_{\mathrm{RaDR}}=O\left(nND+\min\left\{nD^2+D^3,\ n^2D+n^3\right\}\right). T RaDR = O ( n N D + min { n D 2 + D 3 , n 2 D + n 3 } ) .
When N n ≤ n N_n\le n N n ≤ n , the primal formulation and D n ≍ N n D_n\asymp N_n D n ≍ N n give
T R a D R ≤ O ( n N n 2 + N n 3 ) = O ( n N n 2 ) . T_{\mathrm{RaDR}}\le O\left(nN_n^2+N_n^3\right)=O\left(nN_n^2\right). T RaDR ≤ O ( n N n 2 + N n 3 ) = O ( n N n 2 ) .
When N n ≥ n N_n\ge n N n ≥ n , the dual formulation gives
T R a D R ≤ O ( n N n 2 + n 2 N n + n 3 ) = O ( n N n 2 ) . T_{\mathrm{RaDR}}\le O\left(nN_n^2+n^2N_n+n^3\right)=O\left(nN_n^2\right). T RaDR ≤ O ( n N n 2 + n 2 N n + n 3 ) = O ( n N n 2 ) .
The conventional dense exact-kernel implementation has cost
T e x a c t d e n s e = Θ ( n 2 N n 2 + n 3 ) . T_{\mathrm{exact}}^{\mathrm{dense}}=\Theta\left(n^2N_n^2+n^3\right). T exact dense = Θ ( n 2 N n 2 + n 3 ) .
Therefore,
T R a D R T e x a c t d e n s e = O ( n N n 2 n 2 N n 2 + n 3 ) = O ( n − 1 ) . \frac{T_{\mathrm{RaDR}}}{T_{\mathrm{exact}}^{\mathrm{dense}}}
=O\left(\frac{nN_n^2}{n^2N_n^2+n^3}\right)=O\left(n^{-1}\right). T exact dense T RaDR = O ( n 2 N n 2 + n 3 n N n 2 ) = O ( n − 1 ) .
SVM perturbation details
The two-stage analysis above is specific to kernel ridge regression with squared loss. For SVM, the loss is the hinge loss. Here, we derive self-contained objective-perturbation results for two-stage distribution classification and its random-feature approximation.
Throughout this subsection, assume binary labels y i ∈ { − 1 , + 1 } y_i\in\{-1,+1\} y i ∈ { − 1 , + 1 } and define
ℓ h ( u ) = ( 1 − u ) + . \ell_h(u)=(1-u)_+. ℓ h ( u ) = ( 1 − u ) + .
The hinge loss is convex and 1-Lipschitz:
∣ ℓ h ( u ) − ℓ h ( v ) ∣ ≤ ∣ u − v ∣ . |\ell_h(u)-\ell_h(v)|\le|u-v|. ∣ ℓ h ( u ) − ℓ h ( v ) ∣ ≤ ∣ u − v ∣.
For w ∈ H k \mathbf{w}\in\mathcal{H}_k w ∈ H k , define the exact empirical SVM objective based on the latent bag embeddings by
J n ( w ) = 1 n ∑ i = 1 n ℓ h ( y i ⟨ w , μ P i ⟩ H k ) + λ 2 ∥ w ∥ H k 2 . \mathcal{J}_n(\mathbf{w})=\frac{1}{n}\sum_{i=1}^{n}\ell_h\left(y_i\langle\mathbf{w},\mu_{P_i}\rangle_{\mathcal{H}_k}\right)+\frac{\lambda}{2}\|\mathbf{w}\|_{\mathcal{H}_k}^2. J n ( w ) = n 1 i = 1 ∑ n ℓ h ( y i ⟨ w , μ P i ⟩ H k ) + 2 λ ∥ w ∥ H k 2 .
The observable exact two-stage objective is
J n , N ( w ) = 1 n ∑ i = 1 n ℓ h ( y i ⟨ w , μ ^ i ⟩ H k ) + λ 2 ∥ w ∥ H k 2 . \mathcal{J}_{n,N}(\mathbf{w}) = \frac{1}{n}\sum_{i=1}^{n}\ell_h(y_i\langle\mathbf{w},\widehat{\boldsymbol{\mu}}_i\rangle_{\mathcal{H}_k})+\frac{\lambda}{2}\|\mathbf{w}\|_{\mathcal{H}_k}^2. J n , N ( w ) = n 1 i = 1 ∑ n ℓ h ( y i ⟨ w , μ i ⟩ H k ) + 2 λ ∥ w ∥ H k 2 .
For the RF classifier, define
J n , D ( β ) = 1 n ∑ i = 1 n ℓ h ( y i β T μ P i , D ) + λ 2 ∥ β ∥ 2 2 , \mathcal{J}_{n,D}(\boldsymbol{\beta}) = \frac{1}{n}\sum_{i=1}^{n}\ell_h(y_i\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{\mu}_{P_i,D})+\frac{\lambda}{2}\|\boldsymbol{\beta}\|_2^2, J n , D ( β ) = n 1 i = 1 ∑ n ℓ h ( y i β T μ P i , D ) + 2 λ ∥ β ∥ 2 2 ,
and
J n , N , D ( β ) = 1 n ∑ i = 1 n ℓ h ( y i β T μ ^ i , D ) + λ 2 ∥ β ∥ 2 2 . \mathcal{J}_{n,N,D}(\boldsymbol{\beta}) = \frac{1}{n}\sum_{i=1}^{n}\ell_h(y_i\boldsymbol{\beta}^{\mathsf{T}}\widehat{\boldsymbol{\mu}}_{i,D})+\frac{\lambda}{2}\|\boldsymbol{\beta}\|_2^2. J n , N , D ( β ) = n 1 i = 1 ∑ n ℓ h ( y i β T μ i , D ) + 2 λ ∥ β ∥ 2 2 .
Lemma 13. Any minimizer of any one of the four objectives above satisfies the corresponding norm bound
∥ w ∥ H k ≤ 2 λ , or ∥ β ∥ 2 ≤ 2 λ . \|\mathbf{w}\|_{\mathcal{H}_k}\leq\sqrt{\frac{2}{\lambda}},\qquad\text{or}\qquad\|\boldsymbol{\beta}\|_2\leq\sqrt{\frac{2}{\lambda}}. ∥ w ∥ H k ≤ λ 2 , or ∥ β ∥ 2 ≤ λ 2 . Proof. We prove the RKHS case as the Euclidean case is identical. Evaluating the objective at w = 0 \mathbf{w}=0 w = 0 gives value 1. By optimality of the minimizer w ^ \widehat{\mathbf{w}} w ,
J ( w ^ ) ≤ 1. \mathcal{J}(\widehat{\mathbf{w}})\leq1. J ( w ) ≤ 1. Since the hinge-loss term is nonnegative,
λ 2 ∥ w ^ ∥ H k 2 ≤ 1. \frac{\lambda}{2}\|\widehat{\mathbf{w}}\|_{\mathcal{H}_k}^2\leq1. 2 λ ∥ w ∥ H k 2 ≤ 1. Therefore ∥ w ^ ∥ H k ≤ 2 / λ \|\widehat{\mathbf{w}}\|_{\mathcal{H}_k}\leq\sqrt{2/\lambda} ∥ w ∥ H k ≤ 2/ λ .
Lemma 14. Assume the event of Lemma 1. Define
Δ N ( δ ) = C μ κ log ( 2 n / δ ) N . \Delta_N(\delta)=C_{\mu}\kappa\sqrt{\frac{\log(2n/\delta)}{N}}. Δ N ( δ ) = C μ κ N log ( 2 n / δ ) . Then for every w ∈ H k \mathbf{w}\in\mathcal{H}_k w ∈ H k ,
∣ J n , N ( w ) − J n ( w ) ∣ ≤ ∥ w ∥ H k Δ N ( δ ) . |\mathcal{J}_{n,N}(\mathbf{w})-\mathcal{J}_n(\mathbf{w})|\leq\|\mathbf{w}\|_{\mathcal{H}_k}\Delta_N(\delta). ∣ J n , N ( w ) − J n ( w ) ∣ ≤ ∥ w ∥ H k Δ N ( δ ) . Similarly, on the corresponding bounded-vector concentration event for empirical RF means, for every β ∈ R D \boldsymbol{\beta}\in\mathbb{R}^{D} β ∈ R D ,
∣ J n , N , D ( β ) − J n , D ( β ) ∣ ≤ ∥ β ∥ 2 Δ N r f ( δ ) , |\mathcal{J}_{n,N,D}(\boldsymbol{\beta})-\mathcal{J}_{n,D}(\boldsymbol{\beta})|\leq\|\boldsymbol{\beta}\|_2\Delta_N^{\mathrm{rf}}(\delta), ∣ J n , N , D ( β ) − J n , D ( β ) ∣ ≤ ∥ β ∥ 2 Δ N rf ( δ ) , where
Δ N r f ( δ ) = C μ , r f log ( 2 n / δ ) N . \Delta_N^{\mathrm{rf}}(\delta)=C_{\mu,\mathrm{rf}}\sqrt{\frac{\log(2n/\delta)}{N}}. Δ N rf ( δ ) = C μ , rf N log ( 2 n / δ ) .
Proof. Since ℓ h \ell_h ℓ h is 1-Lipschitz,
∣ J n , N ( w ) − J n ( w ) ∣ ≤ 1 n ∑ i = 1 n ∣ ℓ h ( y i ⟨ w , μ ^ i ⟩ H k ) − ℓ h ( y i ⟨ w , μ P i ⟩ H k ) ∣ ≤ 1 n ∑ i = 1 n ∣ ⟨ w , μ ^ i − μ P i ⟩ H k ∣ ≤ ∥ w ∥ H k max 1 ≤ i ≤ n ∥ μ ^ i − μ P i ∥ H k . \begin{aligned}
\left|\mathcal{J}_{n,N}(\mathbf{w})-\mathcal{J}_n(\mathbf{w})\right| \le\frac{1}{n}\sum_{i=1}^{n}\left|\ell_h(y_i\langle\mathbf{w},\widehat{\mu}_i\rangle_{\mathcal{H}_k})-\ell_h(y_i\langle\mathbf{w},\mu_{P_i}\rangle_{\mathcal{H}_k})\right| \\
&\le\frac{1}{n}\sum_{i=1}^{n}\left|\langle\mathbf{w},\widehat{\mu}_i-\mu_{P_i}\rangle_{\mathcal{H}_k}\right| \\
&\le\|\mathbf{w}\|_{\mathcal{H}_k}\max_{1\le i\le n}\|\widehat{\mu}_i-\mu_{P_i}\|_{\mathcal{H}_k}.
\end{aligned} ∣ J n , N ( w ) − J n ( w ) ∣ ≤ n 1 i = 1 ∑ n ∣ ℓ h ( y i ⟨ w , μ i ⟩ H k ) − ℓ h ( y i ⟨ w , μ P i ⟩ H k ) ∣ ≤ n 1 i = 1 ∑ n ∣ ⟨ w , μ i − μ P i ⟩ H k ∣ ≤ ∥ w ∥ H k 1 ≤ i ≤ n max ∥ μ i − μ P i ∥ H k .
Applying Lemma 1 gives the claim. The RF statement follows in the same way, using ∥ ϕ D ( x ) ∥ 2 ≤ 2 \|\boldsymbol{\phi}_D(\mathbf{x})\|_2\le\sqrt{2} ∥ ϕ D ( x ) ∥ 2 ≤ 2 . □
Theorem 8. Let w ^ λ , n \widehat{\mathbf{w}}_{\lambda,n} w λ , n and w ^ λ , n , N \widehat{\mathbf{w}}_{\lambda,n,N} w λ , n , N be minimizers of J n \mathcal{J}_n J n and J n , N \mathcal{J}_{n,N} J n , N , respectively. On the event of Lemma 14, let
B λ = 2 λ . B_\lambda=\sqrt{\frac{2}{\lambda}}. B λ = λ 2 . Then
0 ≤ J n ( w ^ λ , n , N ) − J n ( w ^ λ , n ) ≤ 2 B λ Δ N ( δ ) . 0\le\mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n,N})-\mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n})\le2B_\lambda\Delta_N(\delta). 0 ≤ J n ( w λ , n , N ) − J n ( w λ , n ) ≤ 2 B λ Δ N ( δ ) . Moreover,
∥ w ^ λ , n , N − w ^ λ , n ∥ H k ≤ 2 B λ Δ N ( δ ) λ . \|\widehat{\mathbf{w}}_{\lambda,n,N}-\widehat{\mathbf{w}}_{\lambda,n}\|_{\mathcal{H}_k}\le2\sqrt{\frac{B_\lambda\Delta_N(\delta)}{\lambda}}. ∥ w λ , n , N − w λ , n ∥ H k ≤ 2 λ B λ Δ N ( δ ) . Consequently, for every test distribution P \mathbb{P} P ,
∣ ⟨ w ^ λ , n , N − w ^ λ , n , μ P ⟩ H k ∣ ≤ 2 κ B λ Δ N ( δ ) λ . \left|\langle\widehat{\mathbf{w}}_{\lambda,n,N}-\widehat{\mathbf{w}}_{\lambda,n},\mu_{\mathbb{P}}\rangle_{\mathcal{H}_k}\right|\le2\kappa\sqrt{\frac{B_\lambda\Delta_N(\delta)}{\lambda}}. ∣ ⟨ w λ , n , N − w λ , n , μ P ⟩ H k ∣ ≤ 2 κ λ B λ Δ N ( δ ) . Proof. By Lemma 13, both minimizers lie in the norm ball of radius B λ B_\lambda B λ . Therefore Lemma 14 gives
J n ( w ^ λ , n , N ) ≤ J n , N ( w ^ λ , n , N ) + B λ Δ N ( δ ) . \mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n,N})\le\mathcal{J}_{n,N}(\widehat{\mathbf{w}}_{\lambda,n,N})+B_\lambda\Delta_N(\delta). J n ( w λ , n , N ) ≤ J n , N ( w λ , n , N ) + B λ Δ N ( δ ) . By optimality of w ^ λ , n , N \widehat{\mathbf{w}}_{\lambda,n,N} w λ , n , N for J n , N \mathcal{J}_{n,N} J n , N ,
J n , N ( w ^ λ , n , N ) ≤ J n , N ( w ^ λ , n ) . \mathcal{J}_{n,N}(\widehat{\mathbf{w}}_{\lambda,n,N})\le\mathcal{J}_{n,N}(\widehat{\mathbf{w}}_{\lambda,n}). J n , N ( w λ , n , N ) ≤ J n , N ( w λ , n ) . Applying Lemma 14 again,
J n , N ( w ^ λ , n ) ≤ J n ( w ^ λ , n ) + B λ Δ N ( δ ) . \mathcal{J}_{n,N}(\widehat{\mathbf{w}}_{\lambda,n})\le\mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n})+B_\lambda\Delta_N(\delta). J n , N ( w λ , n ) ≤ J n ( w λ , n ) + B λ Δ N ( δ ) . Combining the three inequalities gives
J n ( w ^ λ , n , N ) − J n ( w ^ λ , n ) ≤ 2 B λ Δ N ( δ ) . \mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n,N})-\mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n})\le2B_\lambda\Delta_N(\delta). J n ( w λ , n , N ) − J n ( w λ , n ) ≤ 2 B λ Δ N ( δ ) . The lower bound follows because w ^ λ , n \widehat{\mathbf{w}}_{\lambda,n} w λ , n minimizes J n \mathcal{J}_n J n .
Next, J n \mathcal{J}_n J n is λ \lambda λ -strongly convex because of the quadratic regularizer. Hence,
J n ( w ^ λ , n , N ) ≥ J n ( w ^ λ , n ) + λ 2 ∥ w ^ λ , n , N − w ^ λ , n ∥ H k 2 . \mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n,N})\ge\mathcal{J}_n(\widehat{\mathbf{w}}_{\lambda,n})+\frac{\lambda}{2}\|\widehat{\mathbf{w}}_{\lambda,n,N}-\widehat{\mathbf{w}}_{\lambda,n}\|_{\mathcal{H}_k}^{2}. J n ( w λ , n , N ) ≥ J n ( w λ , n ) + 2 λ ∥ w λ , n , N − w λ , n ∥ H k 2 . Combining this with the objective gap bound gives the parameter perturbation bound. The score perturbation follows by Cauchy–Schwarz and ∥ μ P ∥ H k ≤ κ \|\mu_{\mathbb{P}}\|_{\mathcal{H}_k}\le\kappa ∥ μ P ∥ H k ≤ κ . □
Lemma 15. Assume the event of Lemma 4. For
A = { α ∈ R n : 0 ≤ α i ≤ 1 / n } , \mathcal{A} = \{\boldsymbol{\alpha} \in\mathbb{R}^{n} : 0 \le\alpha_i \le1/n\}, A = { α ∈ R n : 0 ≤ α i ≤ 1/ n } , define
D N ( α ) = ∑ i = 1 n α i − 1 2 λ α T Y K N Y α , \mathcal{D}_{N}(\boldsymbol{\alpha}) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2\lambda}\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{Y}\mathbf{K}_{N}\mathbf{Y}\boldsymbol{\alpha}, D N ( α ) = i = 1 ∑ n α i − 2 λ 1 α T Y K N Y α , and
D N , D ( α ) = ∑ i = 1 n α i − 1 2 λ α T Y K ^ D , N Y α . \mathcal{D}_{N,D}(\boldsymbol{\alpha}) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2\lambda}\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{Y}\widehat{\mathbf{K}}_{D,N}\mathbf{Y}\boldsymbol{\alpha}. D N , D ( α ) = i = 1 ∑ n α i − 2 λ 1 α T Y K D , N Y α . Then for every α ∈ A \boldsymbol{\alpha} \in\mathcal{A} α ∈ A ,
∣ D N , D ( α ) − D N ( α ) ∣ ≤ ϵ D ( δ ) 2 λ . \left|\mathcal{D}_{N,D}(\boldsymbol{\alpha})-\mathcal{D}_{N}(\boldsymbol{\alpha})\right| \le\frac{\epsilon_D(\delta)}{2\lambda}. ∣ D N , D ( α ) − D N ( α ) ∣ ≤ 2 λ ϵ D ( δ ) . Proof. For feasible α \boldsymbol{\alpha} α ,
∣ D N , D ( α ) − D N ( α ) ∣ = 1 2 λ ∣ α T Y ( K ^ D , N − K N ) Y α ∣ \left|\mathcal{D}_{N,D}(\boldsymbol{\alpha})-\mathcal{D}_{N}(\boldsymbol{\alpha})\right| = \frac{1}{2\lambda}\left|\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{Y}\left(\widehat{\mathbf{K}}_{D,N}-\mathbf{K}_{N}\right)\mathbf{Y}\boldsymbol{\alpha}\right| ∣ D N , D ( α ) − D N ( α ) ∣ = 2 λ 1 α T Y ( K D , N − K N ) Y α ≤ 1 2 λ ∑ i , j = 1 n α i α j ∣ [ K ^ D , N − K N ] i j ∣ \le\frac{1}{2\lambda}\sum_{i,j=1}^{n}\alpha_i\alpha_j\left|\left[\widehat{\mathbf{K}}_{D,N}-\mathbf{K}_{N}\right]_{ij}\right| ≤ 2 λ 1 i , j = 1 ∑ n α i α j [ K D , N − K N ] ij ≤ ϵ D ( δ ) 2 λ ( ∑ i = 1 n α i ) 2 . \le\frac{\epsilon_D(\delta)}{2\lambda}\left(\sum_{i=1}^{n}\alpha_i\right)^2. ≤ 2 λ ϵ D ( δ ) ( i = 1 ∑ n α i ) 2 . Because 0 ≤ α i ≤ 1 / n 0 \le\alpha_i \le1/n 0 ≤ α i ≤ 1/ n , we have ∑ i = 1 n α i ≤ 1 \sum_{i=1}^{n}\alpha_i \le1 ∑ i = 1 n α i ≤ 1 . Therefore
∣ D N , D ( α ) − D N ( α ) ∣ ≤ ϵ D ( δ ) 2 λ . \left|\mathcal{D}_{N,D}(\boldsymbol{\alpha})-\mathcal{D}_{N}(\boldsymbol{\alpha})\right| \le\frac{\epsilon_D(\delta)}{2\lambda}. ∣ D N , D ( α ) − D N ( α ) ∣ ≤ 2 λ ϵ D ( δ ) .
We now proceed to prove Proposition 3.
Proof. The entrywise argument in Lemma 15 is deterministic and applies directly with the approximation radius ϵ D \epsilon_D ϵ D in the proposition, proving its first claim. Let α N ⋆ \boldsymbol{\alpha}_N^\star α N ⋆ and α N , D ⋆ \boldsymbol{\alpha}_{N,D}^\star α N , D ⋆ be maximizers of D N \mathcal{D}_N D N and D N , D \mathcal{D}_{N,D} D N , D over A \mathcal{A} A . Because α N ⋆ \boldsymbol{\alpha}_N^\star α N ⋆ maximizes D N \mathcal{D}_N D N ,
D N ( α N ⋆ ) ≥ D N ( α N , D ⋆ ) . \mathcal{D}_N(\boldsymbol{\alpha}_N^\star) \ge\mathcal{D}_N(\boldsymbol{\alpha}_{N,D}^\star). D N ( α N ⋆ ) ≥ D N ( α N , D ⋆ ) .
Using Lemma 15 at α N , D ⋆ \boldsymbol{\alpha}_{N,D}^\star α N , D ⋆ gives
D N ( α N , D ⋆ ) ≥ D N , D ( α N , D ⋆ ) − ϵ D 2 λ . \mathcal{D}_N(\boldsymbol{\alpha}_{N,D}^\star) \ge\mathcal{D}_{N,D}(\boldsymbol{\alpha}_{N,D}^\star)-\frac{\epsilon_D}{2\lambda}. D N ( α N , D ⋆ ) ≥ D N , D ( α N , D ⋆ ) − 2 λ ϵ D .
Hence,
D N ( α N ⋆ ) − D N , D ( α N , D ⋆ ) ≥ − ϵ D 2 λ . \mathcal{D}_N(\boldsymbol{\alpha}_N^\star)-\mathcal{D}_{N,D}(\boldsymbol{\alpha}_{N,D}^\star) \ge-\frac{\epsilon_D}{2\lambda}. D N ( α N ⋆ ) − D N , D ( α N , D ⋆ ) ≥ − 2 λ ϵ D .
Repeating the same argument with the roles of D N \mathcal{D}_N D N and D N , D \mathcal{D}_{N,D} D N , D interchanged gives
D N ( α N ⋆ ) − D N , D ( α N , D ⋆ ) ≤ ϵ D 2 λ . \mathcal{D}_N(\boldsymbol{\alpha}_N^\star)-\mathcal{D}_{N,D}(\boldsymbol{\alpha}_{N,D}^\star) \le\frac{\epsilon_D}{2\lambda}. D N ( α N ⋆ ) − D N , D ( α N , D ⋆ ) ≤ 2 λ ϵ D .
Therefore the optimal dual objective values differ by at most ϵ D / ( 2 λ ) \epsilon_D/(2\lambda) ϵ D / ( 2 λ ) . By strong duality for soft-margin SVM with quadratic regularization, the same objective-value perturbation holds for the corresponding primal optima. □
Proof of Proposition 4
Proof. We first condition on the training data and a realized candidate pool, so that the feature vectors and score matrix are fixed. Substituting (29) into the trace objective gives
J B ( K ^ S ) = tr ( 1 D ∑ m ∈ S z ^ m z ^ m T B ) = 1 D ∑ m ∈ S tr ( z ^ m z ^ m T B ) = 1 D ∑ m ∈ S z ^ m T B z ^ m = 1 D ∑ m ∈ S q B , m . \mathcal{J}_{\mathbf{B}}(\widehat{\mathbf{K}}_{S}) = \operatorname{tr}\left(\frac{1}{D}\sum_{m\in S}\widehat{\mathbf{z}}_{m}\widehat{\mathbf{z}}_{m}^{\mathsf{T}}\mathbf{B}\right)
= \frac{1}{D}\sum_{m\in S}\operatorname{tr}\left(\widehat{\mathbf{z}}_{m}\widehat{\mathbf{z}}_{m}^{\mathsf{T}}\mathbf{B}\right)
= \frac{1}{D}\sum_{m\in S}\widehat{\mathbf{z}}_{m}^{\mathsf{T}}\mathbf{B}\widehat{\mathbf{z}}_{m}
= \frac{1}{D}\sum_{m\in S}q_{\mathbf{B},m}. J B ( K S ) = tr ( D 1 m ∈ S ∑ z m z m T B ) = D 1 m ∈ S ∑ tr ( z m z m T B ) = D 1 m ∈ S ∑ z m T B z m = D 1 m ∈ S ∑ q B , m .
This proves (34) . Since B \mathbf{B} B is held fixed across subsets, maximizing the objective amounts to selecting the D D D largest scores. Indeed, if a selected score is smaller than an unselected one, exchanging the two increases the objective. Repeating this exchange produces a top-D D D subset.
The first D D D candidates form a feasible subset, and their Gram matrix is
K ^ D , N = 1 D ∑ m = 1 D z ^ m z ^ m T . \widehat{\mathbf{K}}_{D,N}=\frac{1}{D}\sum_{m=1}^{D}\widehat{\mathbf{z}}_{m}\widehat{\mathbf{z}}_{m}^{\mathsf{T}}. K D , N = D 1 m = 1 ∑ D z m z m T .
The maximizing property of S B S_{\mathbf{B}} S B therefore gives
J B ( K ^ S B ) ≥ J B ( K ^ D , N ) \mathcal{J}_{\mathbf{B}}(\widehat{\mathbf{K}}_{S_{\mathbf{B}}})\geq\mathcal{J}_{\mathbf{B}}(\widehat{\mathbf{K}}_{D,N}) J B ( K S B ) ≥ J B ( K D , N )
for every realized pool, including when B \mathbf{B} B is constructed from that pool.
For the expectation statement, we further assume that B \mathbf{B} B is fixed conditional on the training data and independent of the candidate pool. To identify the expected Gram matrix, consider any pair of bags i i i and j j j . By (24) ,
E η ∼ π [ z ^ i ( η ) z ^ j ( η ) ] = 1 N i N j ∑ a = 1 N i ∑ c = 1 N j E ω , b [ 2 cos ( ω T x i a + b ) cos ( ω T x j c + b ) ] = 1 N i N j ∑ a = 1 N i ∑ c = 1 N j k ( x i a , x j c ) = ⟨ μ ^ i , μ ^ j ⟩ H k = [ K N ] i j . \mathbb{E}_{\eta\sim\pi}\left[\widehat{z}_{i}(\eta)\widehat{z}_{j}(\eta)\right]
= \frac{1}{N_iN_j}\sum_{a=1}^{N_i}\sum_{c=1}^{N_j}\mathbb{E}_{\boldsymbol{\omega},b}\left[2\cos\left(\boldsymbol{\omega}^{\mathsf{T}}x_{ia}+b\right)\cos\left(\boldsymbol{\omega}^{\mathsf{T}}x_{jc}+b\right)\right]
= \frac{1}{N_iN_j}\sum_{a=1}^{N_i}\sum_{c=1}^{N_j}k(x_{ia},x_{jc})
= \langle\widehat{\mu}_{i},\widehat{\mu}_{j}\rangle_{\mathcal{H}_{k}}=[\mathbf{K}_{N}]_{ij}. E η ∼ π [ z i ( η ) z j ( η ) ] = N i N j 1 a = 1 ∑ N i c = 1 ∑ N j E ω , b [ 2 cos ( ω T x ia + b ) cos ( ω T x j c + b ) ] = N i N j 1 a = 1 ∑ N i c = 1 ∑ N j k ( x ia , x j c ) = ⟨ μ i , μ j ⟩ H k = [ K N ] ij .
Here the second equality follows by averaging over the uniform phase and then the spectral measure, while the final equality uses the linear distribution kernel. Since the candidates are sampled independently from π \pi π , we obtain
E p o o l [ K ^ D , N ] = K N . \mathbb{E}_{\mathrm{pool}}[\widehat{\mathbf{K}}_{D,N}]=\mathbf{K}_{N}. E pool [ K D , N ] = K N .
The score matrix can now be taken outside the conditional expectation, giving
E p o o l [ J B ( K ^ D , N ) ] = tr ( E p o o l [ K ^ D , N ] B ) = tr ( K N B ) = J B ( K N ) . \mathbb{E}_{\mathrm{pool}}\left[\mathcal{J}_{\mathbf{B}}(\widehat{\mathbf{K}}_{D,N})\right]
= \operatorname{tr}\left(\mathbb{E}_{\mathrm{pool}}[\widehat{\mathbf{K}}_{D,N}]\mathbf{B}\right)
= \operatorname{tr}(\mathbf{K}_{N}\mathbf{B})=\mathcal{J}_{\mathbf{B}}(\mathbf{K}_{N}). E pool [ J B ( K D , N ) ] = tr ( E pool [ K D , N ] B ) = tr ( K N B ) = J B ( K N ) .
Finally, taking expectations of the realized-pool inequality yields
E p o o l [ J B ( K ^ S B ) ] ≥ E p o o l [ J B ( K ^ D , N ) ] = J B ( K N ) , \mathbb{E}_{\mathrm{pool}}\left[J_B\left(\widehat{\mathbf{K}}_{S_B}\right)\right] \ge\mathbb{E}_{\mathrm{pool}}\left[J_B\left(\widehat{\mathbf{K}}_{D,N}\right)\right] = J_B\left(\mathbf{K}_N\right), E pool [ J B ( K S B ) ] ≥ E pool [ J B ( K D , N ) ] = J B ( K N ) ,
which proves (36) . □ \square □
References and Notes