Separation Results between Fixed-Kernel and Feature-Learning Probability Metrics
Year: 2022

Abstract:
Several works in implicit and explicit generative modeling empirically observed that feature-learning discriminators outperform fixed-kernel discriminators in terms of the sample quality of the models. We provide separation results between probability metrics with fixed-kernel and feature-learning discriminators using the function classes F2 and F1 respectively, which were developed to study overparametrized two-layer neural networks. In particular, we construct pairs of distributions over hyper-spheres that can not be discriminated by fixed kernel (F2) integral probability metric (IPM) and Stein discrepancy (SD) in high dimensions, but that can be discriminated by their feature learning (F1) counterparts. To further study the separation we provide links between the F1 and F2 IPMs with sliced Wasserstein distances. Our work suggests that fixed-kernel discriminators perform worse than their feature learning counterparts because their corresponding metrics are weaker.

text: Several works in implicit and explicit generative modeling empirically observed that feature-learning discriminators outperform fixed-kernel discriminators in terms of the sample quality of the models. We provide separation results between probability metrics with fixed-kernel and feature-learning discriminators using the function classes F2 and F1 respectively, which were developed to study overparametrized two-layer neural networks. In particular, we construct pairs of distributions over hyper-spheres that can not be discriminated by fixed kernel (F2) integral probability metric (IPM) and Stein discrepancy (SD) in high dimensions, but that can be discriminated by their feature learning (F1) counterparts. To further study the separation we provide links between the F1 and F2 IPMs with sliced Wasserstein distances. Our work suggests that fixed-kernel discriminators perform worse than their feature learning counterparts because their corresponding metrics are weaker.

heading: 1 Introduction
text: The field of generative modeling, whose aim is to generate artificial samples of some target distribution given some true samples of it, is broadly divided into two types of models (Mohamed and Lakshminarayanan, 2017): explicit generative models, which involve learning an estimate of the log-density of the target distribution which is then sampled (e.g. energy-based models), and implicit generative models, where samples are generated directly by transforming some latent variable (e.g. generative adversarial networks (Goodfellow et al., 2014), normalizing flows (Rezende and Mohamed, 2015)).
Several works have observed experimentally that both in implicit and in explicit generative models, using ‘adaptive’ or ‘feature-learning’ function classes as discriminators yields better generative performance than ‘lazy’ or ‘kernel’ function classes. Within implicit models, Li et al. (2017) show that generative moment matching networks (GMMN) generate significantly better samples for the CIFAR-10 and MNIST datasets when using maximum mean discrepancy (MMD) with learned instead of fixed features. For a related method and in a similar spirit, Santos et al. (2019) show that for image generation, fixed-feature discriminators are only successful when we take an amount of features exponential in the intrinsic dimension of the dataset. Genevay et al. (2018) study implicit generative models with the Sinkhorn divergence as discriminator, and they also show that other than for simple datasets like MNIST, learning the Wasserstein cost is crucial for good performance.
As to explicit models, Grathwohl et al. (2020) train energy-based models with a Stein discrepancy based on neural networks and show improved performance with respect to kernel classes. Chang et al. (2020) show that Stein variational gradient descent (SVGD) fails in high dimensions, and that learning the kernel helps. Given the abundant experimental evidence, the aim of this work is to provide some theoretical results that showcase the advantages of feature-learning over kernel discriminators. For
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the sake of simplicity, we compare the discriminative behavior of two function classes F1 and F2, arising from infinite-width two-layer neural networks with different norms penalties on its weights (Bach, 2017). F1 displays an adaptive behavior, while F2 is an RKHS which consequently has a lazy behavior. Namely, our main contributions are:
(i) We construct a sequence of pairs of distributions over hyperspheres Sd−1 of increasing dimensions, such that the F2 integral probability metric (IPM) between the pair decreases exponentially in the dimension, while the F1 IPM remains high.
(ii) We construct a sequence of pairs of distributions over Sd−1 such that the F2 Stein discrepancy (SD) between the pair decreases exponentially in the dimension, while the F1 SD remains high.
(iii) We prove polynomial upper and lower bounds between theF1 IPM and the max-sliced Wasserstein distance for distributions over Euclidean balls. For a class F̃2 related to F2, we prove similar upper and lower bounds between the F̃2 IPM and the sliced Wasserstein distance for distributions over Euclidean balls.
Our findings reinforce the idea that generative models with kernel discriminators have worse performance because their corresponding metrics are weaker and thus unable to distinguish between different distributions, especially in high dimensions.

heading: 2 Related work
text: A recent line of research has studied the question of how neural networks compare to kernel methods, with a focus on supervised learning problems. Bach (2017) shows the approximation benefits of the F1 space for adapting to low-dimensional structures compared to the (kernel) space F2; an analysis that we leverage. The function space F1 was also studied by Ongie et al. (2019); Savarese et al. (2019); Williams et al. (2019), which focus on the ReLU activation function. More recently, several works showed that wide neural networks trained with gradient methods may behave like kernel methods in certain regimes (see, e.g., Jacot et al., 2018). Examples of works that compare ‘active/feature-learning’ and ‘kernel/lazy’ regimes for supervised learning include Chizat and Bach (2020); Ghorbani et al. (2019); Wei et al. (2020); Woodworth et al. (2020), and Domingo-Enrich et al. (2021) for energy-based models. We are not aware of any works that study how feature-learning function classes and kernel classes differ as discriminators for IPMs or Stein discrepancies.
It turns out that the F2 integral probability metric that we study is in fact MMD for certain kernels that often admit a closed form (Roux and Bengio, 2007; Cho and Saul, 2009; Bach, 2017). MMDs are probability metrics that were first introduced by Gretton et al. (2007, 2012) for kernel twosample tests, and that have enjoyed ample success with the advent of deep-learning-based generative modeling as discriminating metrics: Li et al. (2015) and Dziugaite et al. (2015) introduced GMMN, which differ from GANs in that the discriminator network is replaced by a fixed-kernel MMD. Li et al. (2017) introduces an improvement on GMMN by using the MMD loss on learned features. From this viewpoint, our separation results in Sec. 5 can be interpreted as instances in which a given fixed-kernel MMD provably has less discriminative power than adaptive discriminators.
Other related work includes the Stein discrepancy literature. Stein’s method (Stein, 1972) dates to the 1970s. Gorham and Mackey (2015) introduced a computational approach to compute the Stein discrepancy in order to assess sample quality. Later, Chwialkowski et al. (2016), Liu et al. (2016) and Gorham and Mackey (2017) introduced the more practical kernelized Stein discrepancy (KSD) for goodness-of-fit tests. Liu and Wang (2016) introduced SVGD, the first method to use the KSD to obtain samples from a distribution. Barp et al. (2019) employed KSD to train parametric generative models, and Grathwohl et al. (2020) trained models replacing KSD by a neural-network-based SD.
Our work also touches on sliced and spiked Wasserstein distances. Sliced Wasserstein distances were introduced first by Kolouri et al. (2016); Kolouri et al. (2019). Spiked Wasserstein distances, which are a generalization, were studied later by Paty and Cuturi (2019), and they also appear in Niles-Weed and Rigollet (2019) as a good statistical estimator. Nadjahi et al. (2020) and Lin et al. (2021) have studied statistical properties of sliced and spiked Wasserstein distances, respectively.

heading: 3 Framework

heading: 3.1 Notation
text: If V is a normed vector space, we use BV (β) to denote the closed ball of V of radius β, and BV := BV (1) for the unit ball. If K denotes a subset of the Euclidean space, P(K) is the set of Borel probability measures,M(K) is the space of finite signed Radon measures andM+(K) is the set of finite positive Radon measures. If γ is a signed Radon measure over K, then ‖γ‖TV is the total variation (TV) norm of γ. Throughout the paper, and unless otherwise specified, σ : R→ R denotes a generic non-linear activation function. We use (·)+ : R→ R to denote the ReLu activation, defined as (x)+ = max{x, 0}. τ denotes the uniform probability measure over a space that depends on the context. We use Sd for the d-dimensional hypersphere and log for the natural logarithm.

heading: 3.2 Overparametrized two-layer neural network spaces
text: Feature-learning regime. We define F1 as the Banach space of functions f : K → R such that for some γ ∈ M(Sd), for all x ∈ K we have f(x) = ∫ Sd σ(〈θ, x〉) dγ(θ)
for some signed Radon measure γ (Bach, 2017). The norm of F1 is defined as ‖f‖F1 = inf { ‖γ‖TV |f(·) = ∫ Sd σ(〈θ, ·〉) dγ(θ) } .
Kernel regime. We define F2 as the (reproducing kernel) Hilbert space of functions f : K → R such that for some absolutely continuous ρ ∈ M(Sd) with dρdτ ∈ L
2(Sd) (where τ is the uniform probability measure over Sd), we have that for all x ∈ K, f(x) = ∫ Sd σ(〈θ, x〉) dρ(θ). The norm
of F2 is defined as ‖f‖2F2 = inf {∫ Sd h(θ) 2 dτ(θ) | f(·) = ∫ Sd σ(〈θ, ·〉) h(θ) dτ(θ) } . As an RKHS, the kernel of F2 is
k(x, y) = ∫ Sd σ(〈x, θ〉)σ(〈y, θ〉)dτ(θ). (1)
Such kernels admit closed form expressions for different choices of activation functions, among which ReLu (Roux and Bengio, 2007; Cho and Saul, 2009; Bach, 2017).
Remark that since ∫ |h(θ)|dτ(θ) ≤ ( ∫ h(θ)2 dτ(θ))1/2 by the Cauchy-Schwarz inequality, we have F2 ⊂ F1. In particular, when σ is the ReLu unit, Bach (2017) shows that two-layer networks with a single neuron belong to F1 but not to F2, and their L2 approximations in F2 have exponentially high norm in the dimension. Informally, one should understand F1 as the space of two-layer networks where both the input layer and output layer parameters are trained, in the limit of an infinite number of neurons. On the other hand, F2 is the space of infinite-width two-layer networks where only the output layer parameters are trained while the input layer parameters are sampled uniformly on the sphere and kept fixed.

heading: 4 F1 and F2 Integral Probability Metrics
text: Let K be a subset of Rd+1. Integral probability metrics (IPM) are pseudometrics on P(K) of the form
dF (µ, ν) = sup f∈F
Ex∼µf(x)− Ex∼νf(x),
where F is a class of functions from K to R.
F2 IPM or F2 MMD. One possible choice for F is the unit ball BF2 of F2. Since F2 is an RKHS with kernel k, the corresponding IPM is in fact a maximum mean discrepancy (MMD) (Gretton et al., 2007) and it can be shown (Lemma 1 in App. A) to take the form
d2BF2 (µ, ν) = ∫ Sd (∫ K σ(〈x, θ〉)d(µ− ν)(x) )2 dτ(θ).
Notice that for any feature θ ∈ Sd, Ex∼pσ(〈x, θ〉) can be seen as a generalized moment of p. dBF2 can be seen as the L2 distance between generalized moments of µ and ν as functions of θ ∈ Sd.
F1 IPM. An alternative choice for F is the unit ball BF1 of F1. The IPM for the unit ball of F1 can be developed (Lemma 2 in App. A) into
dBF1 (µ, ν) = sup θ∈Sd ∣∣∣∣∫ K σ(〈x, θ〉)d(µ− ν)(x) ∣∣∣∣ . (2)
Observe that dBF1 is the L ∞ distance between generalized moments of µ and µ as functions of θ ∈ Sd. That is, instead of averaging over features, all the weight is allocated to the feature at which the generalized moment difference is larger.
We will provide separate results for two interesting choices for K: (i) for K = Sd, we obtain neural network discriminators without bias term which are amenable to analysis using the theory of spherical harmonics; and (ii) for K = Rd × {1}, we obtain neural networks discriminators with a bias term which is encoded by the last component (notice that probability measures over Rd can be mapped trivially to probability measures over Rd × {1}). We will write F1(K) or F2(K) for specific K when it is not clear by the context.
A function f : R→ R is α-positive homogeneous function if for all r ≥ 0, x ∈ R, f(rx) = rαf(x). One-dimensional α-positive homogeneous functions can be written in a general form as
f(x) = a(x)α+ + b(−x)α+. (3)
where a, b ∈ R are arbitrary. When the activation function σ is α-positive homogeneous, Theorem 1 shows that the F1 and F2 IPMs are distances when K = Rd × {1} if a, b fulfill a certain condition which is satisfied by the ReLu activation, but they are not distances when K = Sd. See Theorem 6 and Theorem 7 in App. B for the proof.
Theorem 1. For any non-negative integer α, let σ : R→ R be an α-positive homogeneous activation function of the form (3). If (−1)αa − b 6= 0 and K = Rd × {1}, both the F1 and F2 IPMs are distances on P(K). If K = Sd, both the F1 and F2 IPMs are not distances on P(K), as there exist pairs of different measures for which the IPMs evaluate to zero.
In other words, Theorem 1 states that certain fixed-kernel and feature-learning infinite neural networks with RELU or leaky RELU non-linearity, yield distances when we include a bias term, but not when the inputs lie in a hypersphere. This result sheds light on when the “neural net distance” introduced by Arora et al. (2017) is indeed a distance.

heading: 5 Separation between the F1 and F2 IPMs
text: In this section for each dimension d ≥ 2, we construct a pair of probability measures µd, νd over P(Sd−1) such that the F1 IPM between µd and νd stays constant along the dimension, while the F2 IPM decreases exponentially.
Legendre harmonics and Legendre polynomials. Let ed ∈ Rd be the d-th vector of the canonical basis. There is a unique homogeneous harmonic polynomial Lk,d of degree k over Rd such that: (i) Lk,d(Ax) = Lk,d(x) for all orthogonal matrices that leave ed invariant, and (ii) Lk,d(ed) = 1. This polynomial receives the name of Legendre harmonic, and its restriction to Sd−1 is indeed a spherical harmonic of order k. If we express an arbitrary ξ(d) ∈ Sd−1 as ξ(d) = ted + (1 − t2)1/2ξ(d−1), where ξ(d−1) ⊥ ed, we can define the Legendre polynomial of degree k in dimension d as Pk,d(t) := Lk,d(ξ(d)) by the invariance of Lk,d (it is not straightforward that Pk,d(t) is a polynomial on t, see Sec. 2.1.2 of Atkinson and Han (2012)). Conversely, Lk,d(x) = Pk,d(〈ed, x〉) for any x ∈ Sd−1, and by homogeneity, Lk,d(x) = ‖x‖kPk,d(〈ed, x〉/‖x‖) for any x ∈ Rd. Legendre polynomials can also be characterized as the orthogonal sequence of polynomials on [−1, 1] such that Pk,d(1) = 1 and∫ 1 −1 Pk,d(t)Pl,d(t)(1− t 2) d−3 2 dt = 0, for k 6= l.
The pair µd and νd. We define µd and νd as the probability measures over Sd−1 with densities
dµd dλ =
{ γk,dLk,d(x) |Sd−1| if Lk,d(x) > 0
0 if Lk,d(x) ≤ 0 ,
dνd dλ = { 0 if Lk,d(x) > 0 −γk,dLk,d(x) |Sd−1| if Lk,d(x) ≤ 0 .
(4)
for some k ≥ 2 and some γk,d ≥ 0, where λ is the Hausdorff measure over Sd−1. Namely, Proposition 1. If we choose γk,d = 2 (∫ Sd−1 |Lk,d(x)| dτ(x) )−1
, then µd and νd are probability measures.
Figure 1 shows a representation of the measures µd, νd for d = 3, k = 4, where one can see that they allocate mass in different regions of the sphere. We are now ready to state our separation result, which is proved in App. D. Theorem 2. Let σ : R→ R be an activation function that is bounded in [−1, 1]. For any d ≥ 2 and k ≥ 1, if we set γk,d as in Proposition 1 we have that
dBF1 (µd, νd) = 2 ∣∣∣∫ 1−1 Pk,d(t)σ(t)(1− t2) d−32 dt∣∣∣∫ 1 −1 |Pk,d(t)|(1− t2) d−3 2 dt , (5)
and
dBF1 (µd, νd) dBF2 (µd, νd) = √ Nk,d =
√ (2k + d− 2)(k + d− 3)!
k!(d− 2)! , (6)
where Nk,d is the dimension of the space of spherical harmonics of order k over Sd−1. That is,
log
( dBF1 (µd, νd)
dBF2 (µd, νd)
) = 1
2
( k log ( k + d− 3
k
) + (d− 2) log ( k + d− 3 d− 2 )) +O(log(k + d)).
(7)
From (7) we see that choosing the parameter k of the same order as d, dBF1 (µd, νd) is exponentially larger than dBF2 (µd, νd) in the dimension d. Equation (5) holds regardless of the choice of the activation function σ, and decreases very slowly in d for the ReLu activation, as shown in Figure 2. This result suggests that in high dimensions there exist high frequency densities that can be distinguished by feature-learning IPM discriminators but not by their fixed-kernel counterpart, and that may explain the differences in generative modeling performance for GMMN and Sinkhorn divergence (Sec. 1).
The key idea for the proof of Theorem 2 is that the Legendre harmonics Lk,d have constant L∞ norm equal to 1 (see equation (26) in App. C), but their L2 norm decreases as 1/Nk,d (see equation (32) in App. D). The proof boils down to relating dBF1 (µd, νd) to the L
∞ norm of Lk,d, and dBF2 (µd, νd) to its L2 norm.

heading: 6 Separation between F1 and F2 Stein discrepancies
text: The arguments to derive the separation result in Sec. 5 can be leveraged to obtain a similar separation for the Stein discrepancy, which helps explain why for Stein discrepancy energy-based models (EBMs) and SVGD feature learning yields improved performance.

heading: 6.1 Stein operator and Stein discrepancy
text: As shown by Domingo-Enrich et al. (2021), for a probability measure ν on the sphere Sd−1 with a continuous and almost everywhere differentiable density dνdτ , the Stein operator Aν : S
d−1 → Rd×d is defined as
(Aνh)(x) = ( ∇ log ( dν
dτ (x)
) − (d− 1)x ) h(x)> +∇h(x), (8)
for any h : Sd−1 → Rd that is continuous and almost everywhere differentiable, where ∇ denotes the Riemannian gradient. That is, for any h : Sd−1 → Rd that is continuous and almost everywhere differentiable, the Stein identity holds: Eν [(Aνh)(x)] = 0.
IfH is a class of functions from Sd−1 to Rd, the Stein discrepancy (Gorham and Mackey, 2015; Liu et al., 2016) forH is a non-symmetric functional defined on pairs of probability measures over K as
SDH(ν1, ν2) = sup h∈H Eν1 [Tr(Aν2h(x))]. (9)
WhenH = BHd0 = {(hi) d i=1 ∈ Hd0 | ∑d i=1 ‖hi‖2H0 ≤ 1} for some reproducing kernel Hilbert space (RKHS)H0 with kernel k with continuous second order partial derivatives, there exists a closed form for the problem (9) and the corresponding object is known as kernelized Stein discrepancy (KSD) Liu et al. (2016); Gorham and Mackey (2017). When the domain is Sd−1, the KSD takes the following form (Lemma 5, Domingo-Enrich et al. (2021)):
KSD(ν1, ν2) = SD2BHd0 (ν1, ν2) = Ex,x′∼ν1 [uν2(x, x′)],
where we have uν(x, x′) = (sν(x) − (d − 1)x)>(sν(x′) − (d − 1)x′)k(x, x′) + (sν(x) − (d − 1)x)>∇x′k(x, x′) + (sν(x′) − (d − 1)x′)>∇xk(x, x′) + Tr(∇x,x′k(x, x′)), and we use ũν(x, x′) to denote the sum of the first three terms (remark that the fourth term does not depend on ν). Here we have used the notation sν(x) = ∇ log(dνdτ (x)), which is known as the score function.

heading: 6.2 Separation result
text: We show a separation result between the two cases:
• F1 Stein discrepancy: H = BFd1 = {(hi) d i=1 ∈ Fd1 | ∑d i=1 ‖hi‖2F1 ≤ 1}. This discriminator set
initially appeared as a particular configuration in the framework of Huggins and Mackey (2018), and its statistical properties for energy based model training were later studied by Domingo-Enrich et al. (2021).
• F2 Stein discrepancy: H = BFd2 = {(hi) d i=1 ∈ Fd2 | ∑d i=1 ‖hi‖2F2 ≤ 1}. Since F2 is an RKHS,
this corresponds to a KSD with the kernel k. However, particular care must be taken in checking that the kernel k has continuous second order partial derivatives, which might not always be the case (i.e. with α = 1).
The pair µd and νd. For d ≥ 2, we set µd to be the uniform Borel probability measure over Sd−1. We define νd as the probability measure over Sd−1 with density
dνd dλ (x) = exp
( γk,dLk,d(x) )∫ Sd−1 exp ( γk,dLk,d(x) ) dλ(x)
(10)
for some γk,d ∈ R that we will specify later on and some k ≥ 2. Theorem 3. Let σ : R → R be an α-positive homogeneous activation function of the form (3) such that a + (−1)k+1b 6= 0. For all k ≥ 1, d ≥ 2 we can choose γk,d ∈ [−1, 1] such that SDBFd1 (µd, νd) = 1 and
SDBFd1 (µd, νd) SDBFd2 (µd, νd) ≥ k(d+k−3) α+1√
2 Nk,d
( k(k + d− 2) ( d+α−2 α+1 )2 + ( k(d+k−3) α+1 )2) (11) That is,
log SDBFd1 (µd, νd) SDBFd2 (µd, νd)  ≥1 2 ( k log ( k + d− 3 k ) + (d− 2) log ( k + d− 3 d− 2 )) +O(log(k + d))
(12)
As in Theorem 2, from (12) we see that choosing the parameter k of the same order as d, SDBFd1 (µd, νd) is exponentially larger than SDBFd2 (µd, νd) in the dimension d. This result suggests that in high dimensions there exist high frequency densities that can be distinguished by feature-learning Stein Discrepancy discriminators but not by their fixed-kernel counterpart, and that may explain the differences in generative modeling performance for Stein discrepancy EBMs and SVGD (Sec. 1).

heading: 7 Bounds of F1 and F2 IPMs by sliced Wasserstein distances
text: F1 andF2 IPMs measure differences of densities by slicing the input space and then maximizing (resp. averaging) the appropriate quantities. Max-sliced and sliced Wasserstein distances work, which have been studied by several works, work in an analogous fashion; one projects the distributions onto onedimensional subspaces, and then maximizes or averages over the subspaces. Unlike the Wasserstein distance, which has been used for generative models such as WGAN (Arjovsky et al., 2017) but whose estimation suffers from the curse of dimensionality, max-sliced and sliced Wasserstein enjoy parametric estimation rates which make them more suitable as discriminators.
The goal of this section is to show that F1 IPMs are equivalent to max-sliced Wasserstein distances up to a constant power, while sliced Wasserstein distances are similarly equivalent to a fixed-kernel IPM with a kernel that is slightly different from the F2 kernel. These bounds are helpful to get a quantitative understanding of how strong feature-learning and fixed-kernel IPMs are, and provide a novel bridge between sliced optimal transport and generative modeling discriminators.

heading: 7.1 Spiked and sliced Wasserstein distances
text: Throughout this section k denotes an integer such that 1 ≤ k ≤ d. The Stiefel manifold Vk is the set of matrices U ∈ Rk×d such that UU> = Ik×k (i.e. the rows of U are orthonormal). We define the k-dimensional projection robust p-Wasserstein distance between µ, ν ∈ P(Rd) as
Wp,k(µ, ν)p = max U∈Vk min π∈Γ(µ,ν)
∫ ‖Ux− Uy‖pdπ(x, y), (13)
where Γ(µ, ν) denotes the set of couplings between µ, ν, i.e. of measures P(K×K) with projections µ and ν. This is the distance studied by Niles-Weed and Rigollet (2019) as a good estimator for the Wasserstein distance for a certain class of target densities with low dimensional structure.
The integral k-dimensional projection robust p-Wasserstein distance between µ, ν ∈ P(Rd) is defined as
Wp,k(µ, ν)p = ∫ Vk ( min π∈Γ(µ,ν) ∫ ‖Ux− Uy‖pdπ(x, y) ) dτ(U), (14)
where τ is the uniform measure over Vk. Nadjahi et al. (2020) studied statistical aspects of this distance in the case in which k = 1, while Lin et al. (2021) considers the case with general k. Notice trivially thatWp,k(µ, ν) ≥ Wp,k(µ, ν).
Sliced Wasserstein distances are spiked Wasserstein distances with k = 1, but they were studied first chronologically (Bonneel et al., 2014; Kolouri et al., 2016; Kolouri et al., 2019). Namely, the sliced Wasserstein distance is the integral 1-dimensional projection robust Wasserstein distanceWp,k, and the max-sliced Wasserstein distance is the 1-dimensional projection robust Wasserstein distance Wp,k. Some arguments are easier for the case k = 1 because the Stiefel manifold is the sphere Sd−1.

heading: 7.2 Results
text: We prove in Theorem 4 that for K = {x ∈ Rd|‖x‖2 ≤ 1}×{1}, for which the F1 space corresponds to overparametrized two-layer neural networks with bias, theF1 IPM can be upper and lower-bounded by the projection robust Wasserstein distanceW1,k(µ, ν) up to a constant power (not depending on the dimension). Theorem 4. Let δ > 0 be larger than a certain constant depending on k and α. Let σ(x) = (x)α+ be the α-th power of the ReLu activation function, where α is a non-negative integer. Let µ, ν be Borel probability measures with support included in {x ∈ Rd|‖x‖2 ≤ 1} × {1}. Let dBF1 be as defined in (2) andW1,k as defined in (13). Then,
δW1,k(µ, ν) ≥ δdBF1 (µ, ν) ≥ W1,k(µ, ν)− 2C(k, α)δ − 1 α+(k−1)/2 log (δ) , (15)
where C(k, α) is a constant that depends only on k and α. If we optimize the lower bound in (15) with respect to δ, we obtainW1,k(µ, ν) ≥ dBF1 (µ, ν) ≥ Ω̃(W1,k(µ, ν)
α+ k+12 ) where Ω̃ hides log factors.
While for the F2 IPM the link with the sliced Wasserstein distance is not straightforward, it can be established when we switch from uniform τ to an alternative feature measure τ̃ . We define the class F̃2 of functions Rd → R as the RKHS associated with the following kernel
k̃(x, y) = ∫ Sd σ(〈(x, 1), θ〉)σ(〈(y, 1), θ〉) dτ̃(θ) =
1
π ∫ Sd−1 ∫ 1 −1 σ ( 〈(x, 1), ( √ 1− t2ξ, t)〉 ) σ ( 〈(y, 1), ( √ 1− t2ξ, t)〉 ) (1− t2)−1/2 dt dτ(d−1)(ξ).
Proposition 2. (τ̃ as a rescaling of uniform measure) The measure dτ̃( √
1− t2ξ, t) = 1π (1 − t2)−1/2 dt dτ(d−1)(ξ) is a probability measure. For comparison, the uniform measure over Sd can be written as dτ( √ 1− t2ξ, t) = Γ((d+1)/2)√
πΓ(d/2) (1− t2) d−12 dt dτ(d−1)(ξ).
That is, F2 and F̃2 are both fixed-kernel spaces with a similar kernel. They differ only in the weighing measure of the kernel; all the expressions which are valid in the F2 setting are also valid for F̃2 if we replace τ by τ̃ . In analogy with the F2 IPM, the F̃2 IPM is given below.
d2BF̃2 (µ, ν) = ∫ Sd (∫ K σ(〈x, θ〉)d(µ− ν)(x) )2 dτ̃(θ). (16)
Analogously to Theorem 4, Theorem 5 establishes that the F̃2 IPM is upper and lower-bounded by the sliced Wasserstein distanceW1,1(µ, ν) up to a constant power (not depending on the dimension). The reason to introduce the space F̃2 is that in the proof, the argument that makes the connection with the sliced Wasserstein distance requires the base measure of the kernel to be τ̃ and does not work for τ . However, we do not imply that a similar result for the F2 IPM is false.
Theorem 5. Let δ > 0 be larger than a certain constant depending on k and α. Let σ(x) = (x)α+ be the α-th power of the ReLu activation function, where α is a non-negative integer. Let µ, ν be Borel probability measures with support included in {x ∈ Rd|‖x‖2 ≤ 1} × {1}. Let dBF̃2 be as defined in (16) andW1,1 as defined in (14). Then,
δd 2/3
F̃2 (µ, ν) ≥
( 5
12πα2α/2
)1/3 ( W1,1(µ, ν)− 2C(1, α)δ− 1 α log (δ) ) . (17)
and πd2BF̃2 (µ, ν) ≤ W1,1(µ, ν). If we optimize the lower bound in (17) with respect to δ, we obtain d 2/3
F̃2 (µ, ν) ≥ Ω̃(W1,1(µ, ν)1+α).

heading: 8 Experiments
text: To validate and clarify our findings, we perform experiments of the settings studied Sec. 5, Sec. 6 and Sec. 7. We use the ReLu activation function σ(x) = (x)+, although remark that the results of Sec. 5 hold for a generic activation function, and the results of Sec. 6 and Sec. 7 hold for non-negative integer powers of the ReLu activation. The empirical estimates in the plots are detailed in App. G. They are averaged over 10 repetitions; the error bars show the maximum and minimum.
Separation between F1 and F2 IPMs. Figure 2 shows F1 and F2 IPM estimates for the pairs µd and νd defined in (4) for the Legendre polynomial of degree k = 6 and varying dimension d, and its ratios. We observe that while the F1 IPM remains nearly constant in the dimension, the F2 IPM experiences a significant decrease. The ratios between IPMs closely track those predicted by our Theorem 2, the mismatch being due to the overestimation of the F2 IPM caused by statistical errors. We were constrained in the values of k and d that we could choose; when the F2 IPM is small, which is the case when k and/or d are large, we need a high number of samples from the distributions µd, νd to make the statistical error smaller than dBF2 (µd, νd) and get a good estimate.
Separation between F1 and F2 SDs. Figure 3 shows F1 and F2 SD estimates for the pairs µd and νd defined in equation Subsec. 6.2 for the Legendre polynomial of degree k = 5 and varying dimension d, and its ratios. The fact that the empirical ratio is significantly above the theoretical lower bound indicates that our lower bound (although exponential) is not tight. This can be guessed by looking at the slackness in the inequalities of Lemma 10 and Lemma 11.
F1, F2, F̃2 IPMs versus max-sliced and sliced Wasserstein. Figure 4 shows several metrics between a standard multivariate Gaussian and a Gaussian with unit variance in all directions except for one of smaller variance 0.1, in varying dimensions. We observe that while the F1 IPM and the max-sliced Wasserstein distance are constant, the F2, F̃2 IPMs and the sliced Wasserstein distance
decrease. For high dimensions they match the corresponding distances between two datasets of standard multivariate Gaussian, which means that the statistical noise precludes discrimination in these metrics.

heading: 9 Conclusions and discussion
text: We have shown pairs of distributions over hyperspheres for which the F1 IPM and SD are exponentially larger than the F2 IPM and SD. In parallel, we have also provided links between the F1 IPM and max-sliced Wasserstein distance, and between the F̃2 IPM and the sliced Wasserstein distance. The densities of the distributions constructed in Sections Sec. 5 and Sec. 6 are based on Legendre harmonics of increasing degree. Keeping in mind that spherical harmonics are the Fourier basis for L2(Sd−1) (in the sense that they constitute an orthonormal basis of eigenvalues of the Laplace-Beltrami operator), one can infer a simple overarching idea from our constructions: ‘F1 discriminators are better than F2 discriminators at telling apart distributions whose densities have only high frequency differences. It would be interesting to develop this intuition into a more general theory. Another avenue of future work is to understand how deep discriminators perform versus shallow ones, in analogy with the work of Eldan and Shamir (2016) for regression.
Acknowledgements. We thank Joan Bruna for useful discussions. CD acknowledges partial support by “la Caixa” Foundation (ID 100010434), under agreement LCF/BQ/AA18/11680094.

Review summaries:
This paper provides a theoretical justification for why feature learning (theoretical proxy for that is the F_1 space) may be crucial as opposed to learning with fixed features (theoretical proxy for that is the RKHS with NTK or F_2 space) when using statistical pseudometrics that are computed using the sup over function spaces (e.g. IPM pseudometrics and Stein discrepancy) to train a generative model to match a given training distribution. In particular, they construct sequences of pairs of distributions for which they can prove that as d increases, F_1 pseudometrics yield much higher “distance” between the distributions than F_2 pseudometrics. In particular, the mathematical exercise suggests that distributions that differ in high frequency components benefit more from feature learning.

The authors study two classes of functions, F1 and F2, which are related to "infinite-width" two-layer neural nets and fixed-kernel RKHSes. They show that in the regime where d goes to infinity, the sensitivity of MMDs based on F2 decreases exponentially comapred to F1 for specific pairs of measures on the hypersphere S^d. The authors corroborrate this theoretical find with some simulations.

This paper argues that discriminators based on learned features have significantly more discrimination power than discriminators based on fixed features. It does so by defining two function classes that can be interpreted as infinite width one hidden layer neural networks, one corresponding to the learned, or adaptive regime (F_1), and another corresponding to the fixed, or kernel regime (F_2). Various interesting separation and characterization results are shown between F_1 and F_2, using practically relevant metrics.