Interpretable Distribution Features with Maximum Testing Power

Introduction

We address the problem of discovering features of distinct probability distributions, with which they can most easily be distinguished. The distributions may be in high dimensions, can differ in non-trivial ways (i.e., not simply in their means), and are observed only through i.i.d. samples. One application for such divergence measures is to model criticism, where samples from a trained model are compared with a validation sample: in the univariate case, through the KL divergence (Cinzia Carota and Polson, 1996), or in the multivariate case, by use of the maximum mean discrepancy (MMD) (Lloyd and Ghahramani, 2015). An alternative, interpretable analysis of a multivariate difference in distributions may be obtained by projecting onto a discriminative direction, such that the Wasserstein distance on this projection is maximized (Mueller and Jaakkola, 2015). Note that both recent works require low dimensionality, either explicitly (in the case of Lloyd and Gharamani, the function becomes difficult to plot in more than two dimensions), or implicitly in the case of Mueller and Jaakkola, in that a large difference in distributions must occur in projection along a particular one-dimensional axis. Distances between distributions in high dimensions may be more subtle, however, and it is of interest to find interpretable, distinguishing features of these distributions.

Our approach builds on the analytic representations of probability distributions of Chwialkowski et al. (2015), where differences in expectations of analytic functions at particular spatial or frequency locations are used to construct a two-sample test statistic, which can be computed in linear time. Despite the differences in these analytic functions being evaluated at random locations, the analytic tests have greater power than linear time tests based on subsampled estimates of the MMD (Gretton et al., 2012b; Zaremba et al., 2013). Our first theoretical contribution, in Sec. 3, is to derive a lower bound on the test power, which can be maximized over the choice of test locations. We propose two novel tests, both of which significantly outperform the random feature choice of Chwialkowski et al.. The (ME) test evaluates the difference of mean embeddings at locations chosen to maximize the test power lower bound (i.e., spatial features); unlike the maxima of the MMD witness function, these features are directly chosen to maximize the distinguishability of the distributions, and take variance into account. The Smooth Characteristic Function (SCF) test uses as its statistic the difference of the two smoothed empirical characteristic functions, evaluated at points in the frequency domain so as to maximize the same criterion (i.e., frequency features). Optimization of the mean embedding kernels/frequency smoothing functions themselves is achieved on a held-out data set with the same consistent objective.

As our second theoretical contribution in Sec. 3, we prove that the empirical estimate of the test power criterion asymptotically converges to its population quantity uniformly over the class of Gaussian kernels. Two important consequences follow: first, in testing, we obtain a more powerful test with fewer features. Second, we obtain a parsimonious and interpretable set of features that best distinguish the probability distributions. In Sec. 4, we provide experiments demonstrating that the proposed linear-time tests greatly outperform all previous linear time tests, and achieve performance that compares to or exceeds the more expensive quadratic-time MMD test (Gretton et al., 2012a). Moreover, the new tests discover features of text data (NIPS proceedings) and image data (distinct facial expressions) which have a clear human interpretation, thus validating our feature elicitation procedure in these challenging high-dimensional testing scenarios.

ME and SCF tests

One can intuitively think of the ME test statistic as a squared normalized (by the inverse covariance $\mathbf{S}_{n}^{-1}$) $L^{2}(\mathcal{X},V_{J})$ distance of the mean embeddings (Smola et al., 2007) of the empirical measures $P_{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{\mathbf{x}_{i}}$, and $Q_{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{\mathbf{y}_{i}}$ where $V_{J}:=\frac{1}{J}\sum_{i=1}^{J}\delta_{\mathbf{v}_{i}}$, and $\delta_{\mathbf{x}}$ is the Dirac measure concentrated at $\mathbf{x}$. The unnormalized counterpart (i.e., without $\mathbf{S}_{n}^{-1}$) was shown by Chwialkowski et al. (2015) to be a metric on the space of probability measures for any $\mathcal{V}$. Both variants behave similarly for two-sample testing, with the normalized version being a semimetric having a more computationally tractable null distribution, i.e., $\chi^{2}(J)$.

In this work, we modify the statistic with a regularization parameter $\gamma_{n}>0$, giving $\hat{\lambda}_{n}:=n\mathbf{\overline{z}}_{n}^{\top}\left(\mathbf{S}_{n}+\gamma_{n}I\right)^{-1}\mathbf{\overline{z}}_{n}$, for stability of the matrix inverse. Using multivariate Slutsky’s theorem, under $H_{0}$, $\hat{\lambda}_{n}$ still asymptotically follows $\chi^{2}(J^{\prime})$ provided that $\gamma_{n}\to 0$ as $n\to\infty$.

Lower bound on test power, consistency of empirical power statistic

Proposition 1 suggests that for large $n$ it is sufficient to maximize $\lambda_{n}$ to maximize a lower bound on the ME test power. The same conclusion holds for the SCF test (result omitted due to space constraints). Assume that $k$ is characteristic (Sriperumbudur et al., 2011). It can be shown that $\lambda_{n}=0$ if and only if $P=Q$ i.e., $\lambda_{n}$ is a semimetric for $P$ and $Q$. In this sense, one can see $\lambda_{n}$ as encoding the ease of rejecting $H_{0}$. The higher $\lambda_{n}$, the easier for the test to correctly reject $H_{0}$ when $H_{1}$ holds. This observation justifies the use of $\lambda_{n}$ as a maximization objective for parameter tuning.

Contributions The statistic $\hat{\lambda}_{n}$ for both ME and SCF tests depends on a set of test locations $\mathcal{V}$ and a kernel parameter $\sigma$. We propose to set $\theta:=\{\mathcal{V},\sigma\}=\arg\max_{\theta}\lambda_{n}=\arg\max_{\theta}\bm{\mu}^{\top}\bm{\Sigma}^{-1}\bm{\mu}$. The optimization of $\theta$ brings two benefits: first, it significantly increases the probability of rejecting $H_{0}$ when $H_{1}$ holds; second, the learned test locations act as discriminative features allowing an interpretation of how the two distributions differ. We note that optimizing parameters by maximizing a test power proxy (Gretton et al., 2012b) is valid under both $H_{0}$ and $H_{1}$ as long as the data used for parameter tuning and for testing are disjoint. If $H_{0}$ holds, then $\theta=\arg\max 0$ is arbitrary. Since the test statistic asymptotically follows $\chi^{2}(J^{\prime})$ for any $\theta$, the optimization does not change the null distribution. Also, the rejection threshold $T_{\alpha}$ depends on only $J^{\prime}$ and is independent of $\theta$.

To avoid creating a dependency between $\theta$ and the data used for testing (which would affect the null distribution), we split the data into two disjoint sets. Let $\mathsf{D}:=(\mathsf{X},\mathsf{Y})$ and $\mathsf{D}^{tr},\mathsf{D}^{te}\subset\mathsf{D}$ such that $\mathsf{D}^{tr}\cap\mathsf{D}^{te}=\emptyset$ and $\mathsf{D}^{tr}\cup\mathsf{D}^{te}=\mathsf{D}$. In practice, since $\bm{\mu}$ and $\bm{\Sigma}$ are unknown, we use $\hat{\lambda}_{n/2}^{tr}$ in place of $\lambda_{n}$, where $\hat{\lambda}_{n/2}^{tr}$ is the test statistic computed on the training set $\mathsf{D}^{tr}$. For simplicity, we assume that each of $\mathsf{D}^{tr}$ and $\mathsf{D}^{te}$ has half of the samples in $\mathsf{D}$. We perform an optimization of $\theta$ with gradient ascent algorithm on $\hat{\lambda}_{n/2}^{tr}(\theta)$. The actual two-sample test is performed using the test statistic $\hat{\lambda}_{n/2}^{te}(\theta)$ computed on $\mathsf{D}^{te}$. The full procedure from tuning the parameters to the actual two-sample test is summarized in Sec. A.

for $j=1,2,3$ and $\zeta_{1}=1,\zeta_{2}=\zeta_{3}=2$.

The idea is to lower bound the difference with an expression involving $\sup_{\mathcal{V},k}\|\overline{\mathbf{z}}_{n}-\bm{\mu}\|_{2}$ and $\sup_{\mathcal{V},k}\|\mathbf{S}_{n}-\bm{\Sigma}\|_{F}$. These two quantities can be seen as suprema of empirical processes, and can be bounded by Rademacher complexities of their respective function classes (i.e., $\mathcal{F}_{1},\mathcal{F}_{2},$ and $\mathcal{F}_{3}$). Finally, the Rademacher complexities can be upper bounded using Dudley entropy bound and VC subgraph properties of the function classes. Proof details are given in Sec. D. ∎

Experiments

In this section, we demonstrate the effectiveness of the proposed methods on both toy and real problems. We consider the isotropic Gaussian kernel class $\mathcal{K}_{g}$ in all kernel-based tests. We study seven two-sample test algorithms. For the SCF test, we set $\hat{l}(\mathbf{x})=k(\mathbf{x},\mathbf{0})$. Denote by ME-full and SCF-full the ME and SCF tests whose test locations and the Gaussian width $\sigma$ are fully optimized using gradient ascent on a separate training sample $(\mathsf{D}^{tr})$ of the same size as the test set $(\mathsf{D}^{te})$. ME-grid and SCF-grid are as in Chwialkowski et al. (2015) where only the Gaussian width is optimized by a grid search,Chwialkowski et al. (2015) chooses the Gaussian width that minimizes the median of the p-values, a heuristic that does not directly address test power. Here, we perform a grid search to choose the best Gaussian width by maximizing $\hat{\lambda}_{n/2}^{tr}$ as done in ME-full and SCF-full.and the test locations are randomly drawn from a multivariate normal distribution. MMD-quad (quadratic-time) and MMD-lin (linear-time) refer to the nonparametric tests based on maximum mean discrepancy of Gretton et al. (2012a), where to ensure a fair comparison, the Gaussian kernel width is also chosen so as to maximize a criterion for the test power on training data, following the same principle as (Gretton et al., 2012b). For MMD-quad, since its null distribution is given by an infinite sum of weighted chi-squared variables (no closed-form quantiles), in each trial we randomly permute the two samples 400 times to approximate the null distribution. Finally, $T^{2}$ is the standard two-sample Hotelling’s T-squared test, which serves as a baseline with Gaussian assumptions on $P$ and $Q$.

Optimization The parameter tuning objective $\hat{\lambda}_{n/2}^{tr}(\theta)$ is a function of $\theta$ consisting of one real-valued $\sigma$ and $J$ test locations each of $d$ dimensions. The parameters $\theta$ can thus be regarded as a $Jd+1$ Euclidean vector. We take the derivative of $\hat{\lambda}_{n/2}^{tr}(\theta)$ with respect to $\theta$, and use gradient ascent to maximize it. $J$ is pre-specified and fixed. For the ME test, we initialize the test locations with realizations from two multivariate normal distributions fitted to samples from $P$ and $Q$; this ensures that the initial locations are well supported by the data. For the SCF test, initialization using the standard normal distribution is found to be sufficient. The parameter $\gamma_{n}$ is not optimized; we set the regularization parameter $\gamma_{n}$ to be as small as possible while being large enough to ensure that $(\mathbf{S}_{n}+\gamma_{n}I)^{-1}$ can be stably computed. We emphasize that both the optimization and testing are linear in $n$. The testing cost $\mathcal{O}(J^{3}+J^{2}n+dJn)$ and the optimization costs $\mathcal{O}(J^{3}+dJ^{2}n)$ per gradient ascent iteration. Runtimes of all methods are reported in Sec. C in the appendix.

We begin with a demonstration that the proxy $\hat{\lambda}_{n/2}^{tr}(\theta)$ for the test power is informative for revealing the difference of the two samples in the ME test. We consider the Gaussian Mean Difference (GMD) problem (see Table 1), where both $P$ and $Q$ are two-dimensional normal distributions with the difference in means. We use $J=2$ test locations $\mathbf{v}_{1}$ and $\mathbf{v}_{2}$, where $\mathbf{v}_{1}$ is fixed to the location indicated by the black triangle in Fig. 1. The contour plot shows $\mathbf{v}_{2}\mapsto\hat{\lambda}_{n/2}^{tr}(\mathbf{v}_{1},\mathbf{v}_{2})$.

Fig. 1 (top) suggests that $\hat{\lambda}_{n/2}^{tr}$ is maximized when $\mathbf{v}_{2}$ is placed in either of the two regions that captures the difference of the two samples i.e., the region in which the probability masses of $P$ and $Q$ have less overlap. Fig. 1 (bottom), we consider placing $\mathbf{v}_{1}$ in one of the two key regions. In this case, the contour plot shows that $\mathbf{v}_{2}$ should be placed in the other region to maximize $\hat{\lambda}_{n/2}^{tr}$, implying that placing multiple test locations in the same neighborhood will not increase the discriminability. The two modes on the left and right suggest two ways to place the test location in a region that reveals the difference. The non-convexity of the $\hat{\lambda}_{n/2}^{tr}$ is an indication of many informative ways to detect differences of $P$ and $Q$, rather than a drawback. A convex objective would not capture this multimodality.

The results are shown in Fig. 2 where type-I error (for SG problem), and test power (for GMD, GVD and Blobs problems) are plotted against test sample size. A number of observations are worth noting. In the SG problem, we see that the type-I error roughly stays at the specified level: the rate of rejection of $H_{0}$ when it is true is roughly at the specified level $\alpha=0.01$.

GMD with 100 dimensions turns out to be an easy problem for all the tests except MMD-lin. In the GVD and Blobs cases, ME-full and SCF-full achieve substantially higher test power than ME-grid and SCF-grid, respectively, suggesting a clear advantage from optimizing the test locations. Remarkably, ME-full consistently outperforms the quadratic-time MMD across all test sample sizes in the GVD case. When the difference of $P$ and $Q$ is subtle as in the Blobs problem, ME-grid, which uses randomly drawn test locations, can perform poorly (see Fig. 2d) since it is unlikely that randomly drawn locations will be placed in the key regions that reveal the difference. In this case, optimization of the test locations can considerably boost the test power (see ME-full in Fig. 2d). Note also that SCF variants perform significantly better than ME variants on the Blobs problem, as the difference in $P$ and $Q$ is localized in the frequency domain; ME-full and ME-grid would require many more test locations in the spatial domain to match the test powers of the SCF variants. For the same reason, SCF-full does much better than the quadratic-time MMD across most sample sizes, as the latter represents a weighted distance between characteristic functions integrated across the entire frequency domain (Sriperumbudur et al., 2010, Corollary 4).

We next investigate how the dimension ($d$) of the problem can affect type-I errors and test powers of ME and SCF tests. We consider the same artificial problems: SG, GMD and GVD. This time, we fix the test sample size to 10000, set $J=5$, and vary the dimension. The results are shown in Fig. 3. Due to the large dimensions and sample size, it is computationally infeasible to run MMD-quad.

We observe that all the tests except the T-test can maintain type-I error at roughly the specified significance level $\alpha=0.01$ as dimension increases. The type-I performance of the T-test is incorrect at large $d$ because of the difficulty in accurately estimating the covariance matrix in high dimensions. It is interesting to note the high performance of ME-full in the GMD problem in Fig. 3b. ME-full achieves the maximum test power of 1.0 throughout and matches the power T-test, in spite of being nonparametric and making no assumption on $P$ and $Q$ (the T-test is further advantaged by its excessive Type-I error). However, this is true only with optimization of the test locations. This is reflected in the test power of ME-grid in Fig. 3b which drops monotonically as dimension increases, highlighting the importance of test location optimization. The performance of MMD-lin degrades quickly with increasing dimension, as expected from Ramdas et al. (2015).

Type-I errors and test powers are summarized in Table. 2. The first column indicates the categories of the papers in the two samples. In Bayes-Bayes problem, papers on Bayesian inference are randomly partitioned into two samples in each trial. This task represents a case in which $H_{0}$ holds. Among all the linear-time tests, we observe that ME-full has the highest test power in all the tasks, attaining a maximum test power of 1.0 in the Bayes-Neuro problem. This high performance assures that although different test locations $\mathcal{V}$ may be selected in different trials, these locations are each informative. It is interesting to observe that ME-full has performance close to or better than MMD-quad, which requires $O(n^{2})$ runtime complexity. Besides clear advantages of interpretability and linear runtime of the proposed tests, these results suggest that evaluating the differences in expectations of analytic functions at particular locations can yield an equally powerful test at a much lower cost, as opposed to computing the RKHS norm of the witness function as done in MMD. Unlike Blobs, however, Fourier features are less powerful in this setting.

In the final experiment, we study how well ME and SCF tests can distinguish two samples of photos of people showing positive and negative facial expressions. Our emphasis is on the discriminative features of the faces identified by ME test showing how the two groups differ. For this purpose, we use Karolinska Directed Emotional Faces (KDEF) dataset (Lundqvist et al., 1998) containing 5040 aligned face images of 70 amateur actors, 35 females and 35 males. We use only photos showing front views of the faces. In the dataset, each actor displays seven expressions: happy (HA), neutral (NE), surprised (SU), sad (SA), afraid (AF), angry (AN), and disgusted (DI). We assign HA, NE, and SU faces into the positive emotion group (i.e., samples from $P$), and AF, AN and DI faces into the negative emotion group (samples from $Q$). We denote this problem as “$+$ vs. $-$”. Examples of six facial expressions from one actor are shown in Fig. 4. Photos of the SA group are unused to keep the sizes of the two samples the same. Each image of size $562\times 762$ pixels is cropped to exclude the background, resized to $48\times 34=1632$ pixels ($d$), and converted to grayscale.

We run the tests 500 times with the same setting used previously i.e., Gaussian kernels, and $J=1$. The type-I errors and test powers are shown in Table 3. In the table, “$\pm$ vs. $\pm$” is a problem in which all faces expressing the six emotions are randomly split into two samples of equal sizes i.e., $H_{0}$ is true. Both ME-full and SCF-full achieve high test powers while maintaining the correct type-I errors.

As a way to interpret how positive and negative emotions differ, we take an average across trials of the learned test locations of ME-full in the “$+$ vs. $-$” problem. This average is shown in Fig. 4g. We see that the test locations faithfully capture the difference of positive and negative emotions by giving more weights to the regions of nose, upper lip, and nasolabial folds (smile lines), confirming the interpretability of the test in a high-dimensional setting.

Acknowledgement

We thank the Gatsby Charitable Foundation for the financial support.

References

Appendix A Algorithm

The full algorithm for the proposed tests from parameter tuning to the actual two-sample testing is given in Algorithm 1.

Appendix B Experiments on NIPS text collection

The full procedure for processing the NIPS text collection is summarized as following.

Download all 5903 papers from 1988 to 2015 from https://papers.nips.cc/ as PDF files.

Convert each PDF file to text with pdftotextpdftotext is available at http://poppler.freedesktop.org..

Remove all stop words. We use the list of stop words from http://www.ranks.nl/stopwords.

Keep only nouns. We use the list of nouns as available in WordNet-3.0WordNet is available online at https://wordnet.princeton.edu/wordnet/citing-wordnet/..

Keep only words which contain only English alphabets i.e., does not contain punctuations or numbers. Also, word length must be between 3 and 20 characters (inclusive).

Keep only words which occur in at least 5 documents, and in no more than 2000 documents.

Convert all characters to small case. Stem all words with SnowballStemmer in NLTK (Bird et al., 2009). For example, “recognize” and “recognizer” become “recogn” after stemming.

Categorize papers into disjoint collections. A paper is treated as belonging to a group if its title has at least one word from the list of keywords for the category. Papers that match the criteria of both categories are not considered. The lists of keywords are as follows.

Bayesian inference (Bayes): graphical model, bayesian, inference, mcmc, monte carlo, posterior, prior, variational, markov, latent, probabilistic, exponential family.

Deep learning (Deep): deep, drop out, auto-encod, convolutional, neural net, belief net, boltzmann.

Learning theory (Learn): learning theory, consistency, theoretical guarantee, complexity, pac-bayes, pac-learning, generalization, uniform converg, bound, deviation, inequality, risk min, minimax, structural risk, VC, rademacher, asymptotic.

Neuroscience (Neuro): motor control, neural, neuron, spiking, spike, cortex, plasticity, neural decod, neural encod, brain imag, biolog, perception, cognitive, emotion, synap, neural population, cortical, firing rate, firing-rate, sensor.

Randomly select 2000 words from the remaining words.

Treat each paper as a bag of words and construct a feature vector with TF-IDF (Manning et al., 2008).

In this section, we provide full lists of discriminative terms following the procedure described in Sec. 4. The top ten words in each problem are as follows.

Bayes-Bayes: collabor, traffic, bay, permut, net, central, occlus, mask, draw, joint.

Bayes-Deep: infer, bay, mont, adaptor, motif, haplotyp, ecg, covari, boltzmann, classifi.

Bayes-Learn: infer, markov, graphic, segment, bandit, boundari, favor, carlo, prioriti, prop.

Bayes-Neuro: spike, markov, cortex, dropout, recurr, iii, gibb, basin, circuit, subsystem.

Learn-Deep: deep, forward, delay, subgroup, bandit, recept, invari, overlap, inequ, pia.

Learn-Neuro: polici, interconnect, hardwar, decay, histolog, edg, period, basin, inject, human.

Appendix C Runtimes

In this section, we provide runtimes of all the experiments. The runtimes of the “Test power vs. sample $n$” experiment are shown in Fig. 5. The runtimes of the “Test power vs. dimension $d$” experiment are shown in Fig. 6. Table 4, 5 give the runtimes of the two real-data experiments.

In the cases where $n$ is large (Fig. 5), MMD-quad has the largest runtime due to its quadratic dependency on the sample size. In the extreme case where the test sample size is $10000$ (Fig. 6), it is computationally infeasible to run MMD-quad. We observe that the proposed ME-full and SCF-full have a slight overhead from the parameter optimization. However, since the optimization procedure is also linear in $n$, we are able to conduct an accurate test in less than 10 minutes even when the test sample size is 10000 and $d=1500$ (see Fig. 6a, 6b). We note that the actual tests (after optimization) for all ME and SCF variants take less than one second in all cases. In the ME-full, we initialize the test locations with realizations from two multivariate normal distributions fitted to samples from $P$ and $Q$. When $d$ is large, this heuristic can be expensive. An alternative initialization scheme for $\mathcal{V}$ is to randomly select $J$ points from the two samples.

Appendix D Proof of theorem 2

Let $\mathcal{C}$ be a collection of subsets of $\mathcal{M}$ ($C\subseteq 2^{\mathcal{M}}$). $\mathcal{C}$ is said to shatter an $\left\{p_{1},p_{2},\ldots,p_{i}\right\}\subseteq\mathcal{M}$ set, if for any $S\subseteq\left\{p_{1},p_{2},\ldots,p_{i}\right\}$ there exist $C\in\mathcal{C}$ such that $S=C\cap\left\{p_{1},p_{2},\ldots,p_{i}\right\}$; in other words, arbitrary subset of $\left\{p_{1},p_{2},\ldots,p_{i}\right\}$ can be cut out by an element of $\mathcal{C}$. The VC index of $\mathcal{C}$ is the smallest $i$ for which no set of size i is shattered:

For brevity, we will interchangeably use $\mathbf{S}_{n}$ for $\mathbf{S}_{n}(\mathcal{V})$ and $\overline{\mathbf{z}}_{n}$ for $\overline{\mathbf{z}}_{n}(\mathcal{V})$. $\mathbf{S}_{n}(\mathcal{V})$ and $\overline{\mathbf{z}}_{n}(\mathcal{V})$ will be used mainly when the dependency of $\mathcal{V}$ needs to be emphasized. We start with $\sup_{\mathcal{V},k}\left|\overline{\mathbf{z}}_{n}^{\top}(\mathbf{S}_{n}+\gamma_{n}I)^{-1}\overline{\mathbf{z}}_{n}-\bm{\mu}^{\top}\bm{\Sigma}^{-1}\bm{\mu}\right|$and upper bound the argument of $\sup_{\mathcal{V},k}$ as

where at (a) we use $\|\left(\bm{\Sigma}+\gamma_{n}I\right)^{-1}\|_{F}\leq\|\bm{\Sigma}^{-1}\|_{F}$ and at (b) we use $\|(\mathbf{S}_{n}+\gamma_{n}I)^{-1}\|_{F}\leq\sqrt{J}\|(\mathbf{S}_{n}+\gamma_{n}I)^{-1}\|_{2}\leq\sqrt{J}/\gamma_{n}$.

Combining the upper bounds for $(\square_{1})$ and $(\square_{2})$, we arrive at

using that $\left\|\mathbf{a}\right\|_{2}=\sup_{\mathbf{b}\in B(1,\mathbf{0})}\left<\mathbf{a},\mathbf{b}\right>_{2}$. Let us bound the argument of the supremum:

by the triangle inequality and exploiting that $\left\|\mathbf{b}\right\|_{1}\leq\sqrt{J}\left\|\mathbf{b}\right\|_{2}\leq\sqrt{J}$ with $\mathbf{b}\in B(1,\mathbf{0})$. Thus, we have

using the triangle inequality, the sub-additivity of $\sup$, $\left\|\mathbf{a}\mathbf{b}^{T}\right\|_{F}=\left\|\mathbf{a}\right\|_{2}\left\|\mathbf{b}\right\|_{2}$, $\left\|\bar{\mathbf{z}}_{n}(\mathcal{V})\right\|_{2}\leq 2B\sqrt{J}$, $\left\|\mathbf{z}_{a}(\mathcal{V})\right\|_{2}\leq 2B\sqrt{J}$ [see Eq. (5)] and

with Eq. (6). Considering the first term in Eq. (8)

by exploiting that $\left\|\mathbf{A}\right\|_{F}=\sup_{\mathbf{B}\in B(1,\mathbf{0})}\left<\mathbf{B},\mathbf{A}\right>_{F}$, and $\sum_{i,j=1}^{J}|B_{ij}|\leq J\left\|\mathbf{B}\right\|_{F}\leq J$ with $\mathbf{B}\in B(1,\mathbf{0})$. Using the bounds obtained for the two terms of Eq. (8), we get

D.5 Bounding by concentration and the VC property

Applying Lemma 3 with $\frac{\delta}{5}$, we get the statement with a union bound. $\square$

a uniformly bounded ($\left\|f\right\|_{L^{\infty}(\mathcal{M})}\leq K<\infty,\forall f\in\mathcal{F}$) separable Carathéodory family.

where the universal constant $C$ is associated according to Lemma 7(iv).

Hence, applying Lemma 8, and using symmetrization Steinwart and Christmann (2008) (Prop. 7.10) for the uniformly bounded separable Carathéodory $\mathcal{F}$ class, for arbitrary $\delta\in(0,1)$ with probability at least $1-\delta$

Uniform boundedness of $\mathcal{F}_{i}$-s [see Eqs. (1)-(2)]: If $\mathcal{K}$ is uniformly bounded, i.e., $\exists B<\infty$ such that $\sup_{k\in\mathcal{K}}\sup_{(\mathbf{x},\mathbf{y})\in\mathcal{X}^{2}}\left|k(\mathbf{x},\mathbf{y})\right|\leq B$; then $\mathcal{F}_{1}$, $\mathcal{F}_{2}$ and $\mathcal{F}_{3}$ [Eqs. (1)-(2)] are also uniformly bounded with $B$, $B^{2}$, $B^{2}$ constants, respectively. That is, $\sup_{k\in\mathcal{K},\mathbf{v}\in\mathcal{X}}|k(\mathbf{x},\mathbf{v})|\leq B$, $\sup_{k\in\mathcal{K},(\mathbf{v},\mathbf{v}^{\prime})\in\mathcal{X}^{2}}|k(\mathbf{x},\mathbf{v})k(\mathbf{x},\mathbf{v}^{\prime})|\leq B^{2}$, $\sup_{k\in\mathcal{K},(\mathbf{v},\mathbf{v}^{\prime})\in\mathcal{X}^{2}}|k(\mathbf{x},\mathbf{v})k(\mathbf{y},\mathbf{v}^{\prime})|\leq B^{2}$.

Separability of $\mathcal{F}_{i}$: since $\mathcal{F}_{1}$, $\mathcal{F}_{2}$ and $\mathcal{F}_{3}$ is parameterized by $\Theta=\mathcal{K}\times\mathcal{X}$, $\mathcal{K}\times\mathcal{X}^{2}$, $\mathcal{K}\times\mathcal{X}^{2}$, separability of $\mathcal{K}$ implies that of $\Theta$.

Measurability of $\mathcal{F}_{i}$: $\forall k\in\mathcal{K}$ is measurable, then the elements of $\mathcal{F}_{i}$ ($i=1,2,3$) are also measurable. $\square$

Appendix E Example kernel families

Below we give examples for $\mathcal{K}$ kernel classes for which the associated $\mathcal{F}_{i}$-s are VC-subgraph and uniformly bounded separable Carathéodory families. The VC property will be a direct consequence of the VC indices of finite-dimensional function classes and preservation theorems (see Lemma 7); for a nice example application see Srebro and Ben-David (2006) (Section 5) who study the pseudo-dimension of $(\mathbf{x},\mathbf{y})\mapsto k(\mathbf{x},\mathbf{y})$ kernel classes, for different Gaussian families. We take these Gaussian classes (isotropic, full) and use the preservation trick to bound the VC indices of the associated $\mathcal{F}_{i}$-s.

VC-subgraphs with indices $VC(\mathcal{F}_{1})\leq d+4$, $VC(\mathcal{F}_{2})\leq d+4$, $VC(\mathcal{F}_{3})\leq 2d+4$, and

uniformly bounded separable Carathéodory families, with $\left\|f\right\|_{L^{\infty}(\mathcal{M})}\leq 1$ for all $f\in\{\mathcal{F}_{1},\mathcal{F}_{2},\mathcal{F}_{3}\}$.$\mathcal{M}=\mathcal{X}$ for $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, and $\mathcal{M}=\mathcal{X}^{2}$ in case of $\mathcal{F}_{3}$.

$\mathcal{F}_{2}$: Since $\mathcal{F}_{2}=\left\{\mathbf{x}\mapsto k(\mathbf{x},\mathbf{v})k(\mathbf{x},\mathbf{v}^{\prime})=e^{-\frac{\left\|\mathbf{x}-\mathbf{v}\right\|_{2}^{2}+\left\|\mathbf{x}-\mathbf{v}^{\prime}\right\|_{2}^{2}}{2\sigma^{2}}}:\sigma>0,\mathbf{v}\in\mathcal{X},\mathbf{v}^{\prime}\in\mathcal{X}\right\}$, and $\left\{\mathbf{x}\mapsto\frac{\left\|\mathbf{x}-\mathbf{v}\right\|_{2}^{2}+\left\|\mathbf{x}-\mathbf{v}^{\prime}\right\|_{2}^{2}}{2\sigma^{2}}:\sigma>0,\mathbf{v}\in\mathcal{X},\mathbf{v}^{\prime}\in\mathcal{X}\right\}\subseteq S=span\left(\mathbf{x}\mapsto\left\|\mathbf{x}\right\|_{2}^{2},\{\mathbf{x}\mapsto x_{i}\}_{i=1}^{d}\hskip 4.26773pt,\mathbf{x}\mapsto 1\right)$, $VC(\mathcal{F}_{2})\leq d+4$.

from the result on $\mathcal{F}_{1}$ we get that $VC(\mathcal{F}_{3})\leq 2d+4$.

VC-subgraphs with indices $VC(\mathcal{F}_{1})\leq\frac{d(d+1)}{2}+d+2$, $VC(\mathcal{F}_{2})\leq\frac{d(d+1)+2}{2}+d+2$, $VC(\mathcal{F}_{3})\leq d(d+1)+2d+3$,

uniformly bounded separable Carathéodory families, with $\left\|f\right\|_{L^{\infty}(\mathcal{M})}\leq 1$ for all $f\in\{\mathcal{F}_{1},\mathcal{F}_{2},\mathcal{F}_{3}\}$.4

We prove the VC index values; the rest is essentially identical to the proof of Lemma 5.

$\mathcal{F}_{1}$: Using that $\mathcal{G}=\left\{\mathbf{x}\mapsto(\mathbf{x}-\mathbf{v})^{\top}\mathbf{A}(\mathbf{x}-\mathbf{v}):\mathbf{A}\succeq\mathbf{0},\mathbf{v}\in\mathcal{X}\right\}\subseteq S:=span\left(\{\mathbf{x}\mapsto x_{i}x_{j}\}_{1\leq i\leq j\leq d},\{\mathbf{x}\mapsto x_{i}\}_{1\leq i\leq d},\mathbf{x}\mapsto 1\right)$, we have $VC(\mathcal{F}_{1})\leq VC(\mathcal{G})\leq dim(S)+2\leq\frac{d(d+1)}{2}+d+3$.

$\mathcal{F}_{2}$: Since $\mathcal{F}_{2}=\left\{\mathbf{x}\mapsto k(\mathbf{x},\mathbf{v})k(\mathbf{x},\mathbf{v}^{\prime})=e^{-\left[(\mathbf{x}-\mathbf{v})^{\top}\mathbf{A}(\mathbf{x}-\mathbf{v})+\left(\mathbf{x}-\mathbf{v}^{\prime}\right)^{\top}\mathbf{A}\left(\mathbf{x}-\mathbf{v}^{\prime}\right)\right]}:\mathbf{A}\succeq\mathbf{0},\mathbf{v}\in\mathcal{X},\mathbf{v}^{\prime}\in\mathcal{X}\right\}$, and

we have $VC(\mathcal{F}_{2})\leq VC(S)=dim(S)+2\leq\frac{d(d+1)}{2}+d+3$.

and $\left\{(\mathbf{x},\mathbf{y})\mapsto(\mathbf{x}-\mathbf{v})^{\top}\mathbf{A}(\mathbf{x}-\mathbf{v})+(\mathbf{y}-\mathbf{v}^{\prime})^{\top}\mathbf{B}(\mathbf{y}-\mathbf{v}^{\prime})\right\}\subseteq S:=span\left(\{(\mathbf{x},\mathbf{y})\mapsto x_{i}x_{j}\}_{1\leq i\leq j\leq d},\{(\mathbf{x},\mathbf{y})\mapsto x_{i}\}_{1\leq i\leq d},(\mathbf{x},\mathbf{y})\mapsto 1,\{(\mathbf{x},\mathbf{y})\mapsto y_{i}y_{j}\}_{1\leq i\leq j\leq d},\{(\mathbf{x},\mathbf{y})\mapsto y_{i}\}_{1\leq i\leq d}\right)$, we have $VC(\mathcal{F}_{3})\leq VC(S)=dim(S)+2\leq d(d+1)+2d+3$.

Appendix F Proof of proposition 1

We will bound each of the three terms in (12).

where we used the fact that $\|\mathbf{b}\|_{1}\leq\sqrt{J}\|\mathbf{b}\|_{2}$. It can be seen that $-2B\leq G_{i}\leq 2B$ because

We can upper bound $(*_{2})$ by applying Hoeffding’s inequality to bound $\|\overline{\mathbf{z}}_{n}-\bm{\mu}\|_{2}$ giving

Applying a union bound on (13), (14), and (16) with $t=\alpha/3$, we can conclude that

Define $\xi_{1}:=\frac{1}{3^{2}\cdot 8B^{2}\overline{c}_{2}^{2}J},\xi_{2}:=24B^{2}\overline{c}_{1}J,\xi_{3}:=3^{2}\cdot 32B^{4}\overline{c}_{1}^{2}J^{2},\xi_{4}:=32B^{4}J^{2}\overline{c}_{1}^{2}$. We have

Appendix G External lemmas

In this section we detail some external lemmas used in our proof.

Finite-dimensional vector space: if $\mathcal{G}$ is a finite-dimensional vector space of measurable functions, then $VC(\mathcal{G})\leq dim(\mathcal{G})+2$.

for any $r\in(0,1)$ with a universal constant $C$.

bounded difference property holds. Then for arbitrary $\delta\in(0,1)$

Equivalently, for any $\delta\in(0,1)$, with probability at least $1-\delta$, it holds that