Separation Results between Fixed-Kernel and Feature-Learning Probability Metrics
Authors: Carles Domingo-Enrich
Youssef Mroueh
Venue: NeurIPS 2021 Oral (2021)
Keywords: integral probability metric
kernel
feature
separation
distribution
harmonics
Legendre

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 $\mathcal{F}_2$  and $\mathcal{F}_1$ 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 $(\mathcal{F}_2)$ integral probability metric (IPM) and Stein discrepancy (SD) in high dimensions, but that can be discriminated by their feature learning ($\mathcal{F}_1$) counterparts. To further study the separation we provide links between the $\mathcal{F}_1$ and $\mathcal{F}_2$ 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.

Separation Results between Fixed-Kernel and Feature-Learning Probability Metrics
Carles Domingo-Enrich Courant Institute of Mathematical Sciences (NYU) cd27540nyu
Youssef Mroueh IBM Research AI mr oruuhhuus ibm com
Abstract
Several works in implicit and explicit generative modeling empirically observed that feature-learning discriminators outperform fixed-kerne discriminators in terms of the sample quality of the models. We provide separation results between probability metries with fixed-kernel and feature-learning discriminators using the function classes F2 and Fi 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 (FF1) counterparts. To further study the separation we provide links between the Fi and F2 IPMs with sliced Wasserstein discriminators perform worse than
distances. Our work suggests that their feature learning counterparts because their corresponding metrics are weaker.
1 Introduction
The field of generative modeling, whose aim is to generate artificial samples of some target distri- bution 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 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 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 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 feature-learning over kernel discriminators. For
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the sake of simplicity, we compare the discriminative behavior of two function classes Fi and F2. arising from infinite-wine widhh two-layer neural networks with different norms penalties on its weights (Bach, 2017). Fi displays an adaptive hehavior, while F2 is RKHS which consequently has a lazy behavior. Namely, our main contributions are:
(i) We construct a sequence of pairs of distributions over hyperspheres gd-1 of increasing dimensions, such that the F2 integral probability metrie (IPM) between the pair decreases exponentially in the dimension, while the Fi IPM remains high.
(ii) We construct 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 Fi SD remains high.
(iii) We prove polynomial upper and lower bounds between the F1 IPM and the max-sliced Wasserstein distance for distributions over Euclidean balls. For a class F₂ related to F2, we prove similar upper and lower bounds between the F2 IPM and the sliced Wasserstein distance for distributions over Euclidean balls.
Our findings reinforce the idea that generative models with kernel discriminators have worse per- formance because their corresponding metrics are weaker and thus unable to distinguish between different distributions, especially in high dimensions.
2 Related work
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 Fi space for adapting 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 acciie/feature--laminng and 'kernel/lazy' regimes for supervised learning include Chizat and Bach (2020); Ghorbani al. (2019): Wei al. (2020); Woodworth et al. (2020), and Domingo-Enne Ennich et al. (2021) for energy- based models. We are not aware of any works that study how function classes and kernel classes differ as discriminators for IPMs or Stein discrepancies.
It turns out that the Fg 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 probability metrics that were first introduced by Gretton et al. (2007, 2012) for kernel two- sample tests, and that have enjoyed ample success with the advent of deep-learning- bbasd 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 fixed-kernel MMD. Li al. (2017) introduces an improvement on GMMN by using the MMD loss 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- off-it tests. Liu and Wang (2016) introduced SVGD, the first method to the KSD to obtain samples from a distribution. Barp et al. (2019) employed KSD to train parametric generative SD.
models, and Grathwohl al. (2020) trained models replacing KSD by
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.

---

3 Framework
3.1 Notation
V a normed vector space, we use (3( to denote the closed ball of V of radius B, and By := (1) for the unit ball. If K denotes subset of the Euclidean space, P(K) is the set of Borel probability measures, M(K) is the space of finite signed Radon measures and (K) the set of finite positive Radon measures. Iy is a signed Radon measure over K, then || TV is the total variation (TV) norm of y. Throughout the paper, and unless otherwise specified,
R IR denotes generic non-linear activation function. We use (-)+ R - IR to denote the ReLu activation, defined as (x)+ max æ, 0}. denotes the uniform probability measure over a space that depends on the context. We use S for the d-dimensional hypersphere and log for the natural logarithm.
3.2 Overparametrized two-layer neural network spaces
Feature-learning regime. We define Fi as the Banach space of functions f K + I such that for some 7 E M(S)), for all E K we have f(x)) = Ssr ((0,x)) dy(0) for some signed Radon measure (Bach, 2017). The norm of Fi is defined as || inf |1llrr If(.) = foa ((0,,)) (x(0))
Kernel regime. We define F2 as the (reproducing kernel) Hilbert space of functions f: K TR such that for some absolutely continuous E M(Sd) with E (3(dd) (where T is the uniform probability measure over 84), we have that for all x E K, f(x) = Iga o (0),))) dp(0). The norm of F2 is defined as Ilf = inf { {Sgu h(0)2 dr(O) f(-) = fgr ((0, h(0) dr(0)} As an RKHS, the kernel F2 is
k(x, y) = -/o a(xx, ())0((((0)) (2, (O)
(I)
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 ((O))dT(O) S (J h())² dr(0)) by the Cauchy-Schward Schwarz inequality, we have F2 C Fi. In particular, when is the ReLu unit, Bach (2017) shows that two-layer networks with single neuron belong to F, but not to Fz. and their L approximations norm in the dimension. Informally, one should understand Fi 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 infinit-wiidt 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.
F2 have exponentially high
4 Fi and F2 Integral Probability Metrics
Let K be subset of Rd+1 Integral probability metrics (IPM) are pseudometrics P(K) of the form
v) sup [x) Exzuf(I),
feF
where F is a class of functions from K to RR
F2 IPM or F, MMD. One possible choice for F is the unit ball By, of F2. Since F₂ is an RKHS with kernel k;, the corresponding IPM is in fact maximum 2007) and it can be shown (Lemma in App. A) to take the form
discrepancy (MMD) (Gretton et al.,
dez (1, f (/x (((2, 0))d(( - -1(o)) dr(0).
3

---

Notice that for any feature E St, (z) (22,0) 0)) can be seen as a generalized moment of p. dBy, can be seen as the L distance between generalized moments of ş and functions of 0 Sd.
Fi IPM. An alternative choice for F is the unit ball By, of Fi. The IPM for the unit ball of Fi can be developed (Lemma App. A) into
ds,, (1,2) sup / o((x,)))d(u v)(x))
6E3* k
Observe that d8,, is the 7 distance between generalized moments of 1s and la as functions of 0 E 84, 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 = =gd, we obtain neural network discriminators without bias term which are amenable to analysis using the theory of spherical harmonics; and (ii) for K Rd x {1}. we obtain neural networks discriminators with bias term which is encoded by the last component (notice that probability measures over IR can be mapped trivially to probability measures over Rd x {1)). We will write Fi (i(K) or F2(K) for specific K when it is not clear by the context.
A function f R + I is c--positive homogeneous function if for all 2 0, E IR, f(xx) r ((x). One-dimensional a-positive homogeneous functions can be written in a general form as
f(x) a(x)] + b(-))
(3)
where a, b R are arbitrary. When the activation function a a--ossitve homogeneous, Theorem 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 = $d See Theorem 6 and Theorem 7 in App. B for the proof.
Theorem 1. For any non-negative integer a, let : + R be an a-positive homogeneous activation function of the form (3). If (-1)aa b F and K Rd x (1), both the Fi and F2 IPMs are distances P(K). K = SA, both the Fi and F2 IPMs are not distances on P(K), as there exist puirs 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 (2017) is indeed distance.
5 Separation between the F, and F2 IPMs
In this section for each dimension d 2 2, we construct a pair of probability measures μa, Va over P(()-11) such that the F, IPM between pa and stays constant along the dimension, while the F2 IPM decreases exponentially.
Legendre harmonics and Legendre polynomials. Let ea E Rd be the d-th vector of the canonical basis. There is a unique homogeneous harmonic polynomial Lx,d of degree over Rd such that: (i) (Ax) Ta,a(<;) for all orthogonal matrices that leave ea invariant, and (ii) La,a(ea) = 1. This polynomial receives the name of Legendre harmonic, and its restriction to gd-1 is indeed spherical harmonic of order k. If we express arbitrary E(d) gd-1 as E(a) = lea + (1 -1))1/2 where fid-1) 1. Cd, we can define the Legendre polynomial of degree l in dimension d as (R.a(t) := LR.a(E(a)) ) by the invariance of Lx.d (it is not straightforward that Pt.a(t) is polynomial on f, see Sec. 2.1.2 of Atkinson and Han (2012)). Conversely, Lx,a(z) = PR.a Pr.a((ea,a7) for any E $d-1, and by homogeneity, Le,((x) = | Peea((ea, x) [| for any Rd Legendre polynomials can also be characterized as the orthogonal sequence of polynomials on [-1, 1] such that (k.a(1) = 1 and
[' Pr. -t 4-3 dt O, for k &

---

100
3.5
0.75
20 Pat
atelo2olot
-3.07-0 0. 60
Figure 1: 3D polar plot representing the densities of the measures pa (left) and Va (right). for the choices d 3, k 4. In each direction, the distance from the origin the surface proportional to the density of the measure.
The pair pa and va. We define pla and Va as the probability measures over gd-1 with densities
dpd dx
Tk. ak.aka g4-11
if L (x) > 0
if Lx,a(r)) 5
(4)
dvd
if Lu,a(x) > 0
dx
abb 18d-1|
if Lx,a(x) S
for some and some ",,d 0, where A is the Hausdorff measure over Sd-1, Namely,
Proposition 1. If we choose nk.d (Ig.. [Lxa(()) dr(x)) then pa and are probability measures.
Figure shows representation of the measures Ma, Ma for d they allocate mass in different regions of the sphere. We are now ready to state our separation result, which is proved in App.
4, where one can see that
Theorem 2. Let a: R - R be an activation function that is bounded in [-1, 1]. For any d 2 2 and 2 1, if we set a as in Proposition I we have that
d8,, (Ma, va) = 51 Pk. (t)
-1 dt
(5)
1 (t. -12) dt
and
dBy, (Jaa, Va)
(2k d dd2))(k 2)(k d 3)!
/ /N.dd
(6)
dBr, (Jaa va)
k:ldd 2)!
where Nk.d is the dimension of the space of spherical harmonics of order over 8d-1, That is,
dBz, (Hlas Va) dBy, (Jids va)
1
k k dd3
1 d d-3 3
))
log
klog
k + (d - (i)-2)lon 20g
+ O(log(k: d)).
d -
From (7) we see that choosing the parameter lt of the same order as d, ds,, (Ja M2) is exponentially larger than dB,, (Pa, v2) in the dimension d. Equation (5) holds regardless of the choice of the acti- vation function a, and decreases very slowly in d the ReLu activation, as shown in Figure This result suggests that in high dimensions there exist high frequency densities that can be distinguished by featune-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 - norm equal to I (see equation (26) in App. C), but their 1,² norm decreases as 1/N (see equation (32) in App. D). The proof boils down to relating d8,, (pd, va) to the - norm of Li.d, and dB,, (Ha va) to its L norm.
6 Separation between Fi and F2 Stein discrepancies
The arguments to derive the separation result in Sec. 5 can leveraged to obtain similar separation for the Stein discrepancy, which helps explain why for Stein discrepancy energy-based models (EBMs) and SVGD feature learning yields improved performance.
6.1 Stein operator and Stein discrepancy
As shown by Domingo-Enrich et al. (2021), for probability measure y on the sphere gd-1 with du continuous and almost everywhere differentiable density dF. the Stein operator A Sd + Rdxd defined as
du (r (()) - (d 1)x h(x))()))))))))))) + Vh(x),
(A) = V VVlog log
(8)
for any h : Rd that is continuous and almost everywhere differentiable, where V denotes the Riemannian gradient. That is, for any h: gd-1 7 & that is continuous and almost everywhere differentiable, the Stein identity holds: E ((A)h())(
O.
If H. is class of functions from gd-1 to Rd the Stein discrepancy (Gorham and Mackey, 2015; Liu et al., 2016) for H. is a non- symmetric functional defined on pairs of probability measures over K as
SDH(vI,
sup Ey, (Tr(A,, hEW
When H = BB ((h:) E Hg/ E Ho S $ for some reproducing kemnel Hilbert space (RKHS) Ho with kernel A with continuous second order partial derivatives, there exists closed form for the problem (9) and the corresponding object known as kernelized Stein discrepancy (KSD) Liu et al. (2016); Gorham and Mackey (2017). When the domain is $d-1, the KSD takes the following form (Lemma 5, Domingo-Enrich
Enrich et al. (2021)):
KSD(v1, v2) = SD3 *d
(2), = Ex, mms [M (2,,
where we have uz x²) = (x) - (d - 1)x) (sy(x') (d- 1)2')((zz x') + (sx(x) (d 1)x) Vark(z, x²) + (sy(x') - (d - T) V,k(r, + (VV,,.'(zz,z') and we use (x, to denote the sum of the first three terms (remark that the fourth term does not depend on v). Here dr (z)), which is known the score function.
have used the notation sn (z) V log( de
6.2 Separation result
We show a separation result between the two cases:
Fi Stein discrepancy: H By = ((+)) E E 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 al. (2021).
F2 Stein discrepancy: H- Byz = ((h)) E E
< 11. Since Fg is an RKHS,
this corresponds that the kernel has continuous second order partial derivatives, which might not always be the case (i.e. with a 1).
KSD with the kernel k. However, particular care must be taken in checking

---

The pair Aa and va- For d 2 2, we set to be the uniform Borel probability measure over S We define Va as the probability measure g with density
dyd dA
exp (T
(10)
Jga-1 exp a dd(x)
for some 7Kddd E R that will specify later and some k 2.
Theorem 3. Let 0 IR + such that () O. For all k. 1, 2 can choose "Kkdd [-1,1] such that By (Dd, va) = and
be an a-pasitive homogeneous activation function of the form (3)
SDB,, 84 (Hid va)
k(d+k-3)
2
a+1
(1I)
SD (Mds va)
V
Na.d
k(k: + d 222
(ata-2)
a+1
)
+
((d=+-3) 2 at1
That is.
SDB (Ha.Va) SDB (14d Val
k + -3)
k + d-3
) + Olog(k + +d)
log
k log
+ (d - log
k
d
(12)
As in Theorem 2, from (12) we see that choosing the parameter k of the same order as d. SD (Hd. va) is exponentially larger than SD (Ha, pa) in the dimension d. This result sug- gests that in high dimensions there exist high frequency densities that can be distinguished by feature-learning Stein Discrepancy diseriminators 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).
7 Bounds of Fi and F2 IPMs by sliced Wasserstein distances
Fi and F2 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 one- dimensional subspaces, and then maximizes or averages over the subspaces. Unlike the Wasserstein distance, which has been used for generative models such WGAN (Arjovsky 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 discriminators.
The goal of this section is to show that Fi IPMs are equivalent to max-sliced Wasserstein distances up to constant power, while sliced Wasserstein distances are similarly equivalent fxen-kernel IPM with kernel that is slightly different from the F2 kernel. These bounds are helpful to get quantitative understanding of how strong leature-learning and fxed-kernel IPMs are, and provide novel bridge between sliced optimal transport and generative modeling discriminators.
7.1 Spiked and sliced Wasserstein distances
Throughout this section k denotes an integer such that 1 < k: < d. The Stiefel manifold Va is the set of matrices U Rexd such that UU = Lexk (i.e. the rows of are orthonormal). We define the k-dimensional projection robust p- Wasserstein distance between p,, P(R.)
/ f dulldd(a,,
W U) max min UE rEI((..)
(13)
where (J,,, v) denotes the set of couplings between μt, i.e. of measures P(K K) with projections ja and v. This is the distance studied by Niles Weed and Rigollet (2019) as good estimator for the Wasserstein distance for a certain class of target densities with low dimensional structure.
7

---

The integral k-dimensional projection robust p- Wasserstein distance between J.N P(R*) is defined as
1/2 where T is the uniform measure over VE. Nadjahi et al. (2020) studied statistical aspects of this distance in the case in which k: = 1, while Lin al. (2021) considers the case with general k. Notice trivially that Wp, k (H, 2 (M,
/ |U - Uyledd(a, )d(UU)
Wp, 2))
min TEI(a.))
(14)
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 I-dimensional projection robust Wasserstein distance W p. and the max-sliced Wasserstein distance the 1 1-dimensional projection robust Wasserstein distance p. Some arguments easier for the case k because the Stiefel manifold is the sphere $6-1
7.2 Results
We prove in Theorem 4 that for K = fx e R> 13 [1}. for which the Fi space corresponds to overparametrized two-layer neural networks with bias, the Fi IPM can be upper and lower- bounded by the projection robust Wasserstein distance WI,+(1, up to a constant power (not depending on the dimension).
Theorem 4. Let ô > 0 be larger than a certain constant depending on k and a. Let (()) (x)2 I be the a-th power of the ReLu activation function, where is non-negative integer. Let u,v v be Borel probability measures with support included in {a E [R S 1} x (1}. Let dsy, be as defined in (2) and W1,t k as defined in (13). Then,
8W SWi,( v) 2 Ödzz, (H,u) 2 Wi,e(u, v) - (k, ai) --(--177 log (ō),
(15)
where C(k, ai) a constant that depends only k and a. we optimize the lower bound in (15) with respect to 5, we obtain WI, v) 2 d8,, v) 2 (1, ++) where hides log factors.
A+1
While for the F2 IPM the link with the sliced Wasserstein distance is not straightforward. it can be established when we switch from uniform 5 to alternative feature measure F. We define the class F2 of functions IRd + R as the RKHS associated with the following kernel
[ (((a, 1),0))((((()) 1), d+)
Me. y)
gM
1
{ ((,,
a ((Vv, 1), (V1 P(,1)) (V1--( (1-2)-111 di dd(d-1)(f).
Proposition (7 as a rescaling of uniform measure) The measure dł (F(VI- (VII-PE5t) 1 (1
π
1221 di dr dT(a-1)(E) is probability measure. For comparison, the uniform measure over Sd can be written as dr (r[ P2, 1) (=I(d/2) (1 - di dr(d-1)(E)-
(((d+1)/2)
That is, F2 and Fg 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 Fg if we replace 7 by F. In analogy with the F2 IPM, the Fr IPM is given below.
&a 52 (U, = { (/x (((2, ((( -m(()) di).
(16)
Analogously to Theorem 4, Theorem 5 establishes that the Fr IPM is upper and lower-bounded by the sliced Wasserstein distance W,, (H, v) up to a constant power (not depending on the dimension).
The reason to introduce the space Fr is that in the proof, the argument that makes the connection with the sliced Wasserstein distance requires the base measure of the kernel to F and does not work for However, we do not imply that similar result for the F₂ IPM is false.
8

---

Theorem 5. Let 5 > 0 be larger than a certain constant depending on k and a. Let (et (x) be the a-th power of the ReLu activation function, where a non-negative integer. Let p.v be Borel probability measures with support included in {ir E IR. || S 1) x (1). Let ds,, be as defined in (16) and W1,1 defined in (14). Then,
1/3
8d 3d (1,
8. (H.
12TTo2af22
(Wi, (4, -2(( log (6)
(17)
and rd8 (1,1) S W1, (M,, v). If we optimize the lower bound in (17) with respect to d, we obtain 8 (4, 2 S2W (14, 21) t))))
8 Experiments
To validate and clarify our findings, we perform experiments the settings studied Sec. 5, Sec. and Sec. 7. We use the ReLu activation function (zx) = (2:) although remark that the results of Sec. hold for 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.
F1 and F2 IPM estimates (k = 6)
Ratios F1 IPM / F2 IPM (k 6)
Ratio F1 IPM/7 IPM
Ratio (theory)
10
10a
F; IPM
Ratios
IPMS
F: IPM (theory)
Fx IPM
10
10
12
16
10
12
14
16
Dimension
Dimension d
Figure 2: Fi and F2 IPM estimates for the pairs Pat and My defined in (4) for = 6 and varying dimension d. (Left) The blue and red curves (superposed) show two different estimates of the Fi IPM. The purple curve shows estimates for the F2 IPM. (Right) The blue curve shows the theoretical ratio between the F, and the Fz IPMs (see equation (6)). The red curve shows empirical estimate of the ratio obtained by dividing the IPM estimates. 4400 million samples of μu and Vaa are used.
Separation between F1 and F2 IPMs. Figure 2 shows F1 and F2 IPM estimates for the pairs pa and Ma defined in (4) for the Legendre polynomial of degree k = 6 and varying dimension d, and its ratios. We observe that while the Fi IPM remains nearly constant in the dimension, the F2 IPM experiences significant decrease. The ratios between IPMs closely track those predicted by our Theorem 2, the mismatch being due the overestimation of the F2 IPM caused by statistical errors. We were constrained in the values of and d that we could choose; when the F₂ IPM is small, which the case when and/or d are large, we need a high number samples from the distributions Md, Va to make the statistical error smaller than dry, (Da, va) and get good estimate.
Separation between Fi and F2 SDs. Figure 3 shows Fi and F2 SD estimates for the pairs pat and My 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 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.
Fi, F2, Fr IPMs versus max-sliced and sliced Wasserstein. Figure 4 shows several metrics between a standard multivariate Gaussian and a Gaussian with unit variance all directions except for one of smaller variance 0. in varying dimensions. We observe that while the Fi IPM and the max- max-sliced Wasserstein distance are constant, the F2, F₂ IPMs and the sliced Wasserstein distance

---

F1 and F2 SD estimates (k = 5)
Ratios F1 SD / F2 SD (k = 5)
10
Ratios
SDs
lower bound (theory)
SD/F; (theory)
10
10
10
Dimension d
Dimension d
Figure 3: Fi and F2 SD estimates for the pairs Jaa and Ma defined in Subsec. 6.2 for k 5 and varying dimension d. (Left) The red curve shows an empirical estimate of the Fi SD, the blue curve shows theoretical lower bound (Lemma 10 in App. E) the Fi SD, the purple curve shows estimate of the F2 SD. (Right) The blue curve represents the theoretical lower bound on the ratio between the Fi and the F2 SDs (see equation (1)),, while the red curve shows an empirical estimate of the ratio obtained by dividing the SD estimates. 30 million samples are used.
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.
Fi, F2 IPM vs. sliced Wasserstein
Figure 4: For varying dimension d, we plot Fi F2. F2 IPM, sliced and max-sliced Wasserstein es- timates between a standard multivariate Gaussian and Gaussian with unit variance in all directions except for one smaller variance 0.1. The esti- mates computed using 100000 samples of each distribution. For comparison, the same estimates are shown between standard multivariate Gaus- sian and itself, using two different sets of 100000 samples.
10
Max siiced w.
Distances
Slieed
baseline
10
Sliced baseline
10-3
101
102 Dimension d
10a
Conclusions and discussion
We have shown pairs of distributions over hyperspheres for which the Fi IPM and SD are expo- nentially larger than the F2 IPM and SD. In parallel, have also provided links between the Fi IPM and max-sliced Wasserstein distance, and between the Fg IPM and the sliced Wasserstein distance. The densities of the distributions constructed in Sections Sec. 5 and Sec. 6 are based on Legendre harmonies of increasing degree. Keeping in mind that spherical harmonics basis for (g()) (in the sense that they constitute an orthonormal basis of eigenvalues of the Laplace-Beltee Beltrami operator), one can infer simple overarching idea from our constructions: *Fi discriminators are better than F2 discriminators at telling apart distributions whose densities have only high frequency differences. It would be interesting 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.
the Fourier
We thank Joan Bruna for useful discussions. CD acknowledges partial support by "la Caixa" Foundation (ID 100010434). under agreement LCF/BQ/AA18//168000000
Acknowledgements.
10

---

References
Arjovsky, M., Chintala, S., and Bottou, L. (2017). Wasserstein gan. arXiv preprint arXiv:1701.0720
Arora, S., Ge, R., Liang, Y., Ma, T., and Zhang, Y. (2017). Generalization and equilibrium in generative adversarial nets (GANs). In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 224-232, JMLR. org.
Atkinson, K. and Han, W. (2012). Spherical Harmonics and Approximations on the Unit Sphere: An Introduction, volume 2044. Springer.
Bach, F. (2017). Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-53.
Barp, A., Briol, F.-X., Duncan, A., Girolami, M., and Mackey, L. (2019). Minimum stein discrepancy estimators. In Advances in Neural Information Processing Systems, pages 29964-12970
Bateman, H. and Erdélyi, (1954). Tables of integral transforms. McGraw-Hill.
Bonneel, N., Rabin, J., Peyré, G., and Pfister, H. (2014). Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51.
Chang, W.-C., Li, C.-L.,, Mroueh, Y., and Yang, Y. (2020). Kernel stein generative modeling.
Chizat, L. and Bach, F. (2020). Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338, PMLR.
Cho. Y. and Saul, L. K. (2009). Kernel methods for deep learning. In Advances in Neural Information Processing Systems 22, pages 342-350. Curran Associates, Inc.
Chwialkowski, K., Strathmann, H., and Gretton, A. (2016). A kemel test of goodness of fit. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2606-2615. PMLR.
Domingo-Enricn Ennicc, C.,, Bietti, A., Vanden- Fijnden,, E., and Bruna, J. (2021). energy- models with overparametrized shallow neural networks. In Proceedings of the 38th International Con- ference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2771-2782. PMLR.
Dziugaite, G. K., Roy, M., and Ghahramani, Z. (2015). Training generative neural networks via maximum mean discrepancy optimization. UAI.
Efthimiou, and Frye, C. (2014). Spherical Harmonics in Dimensions.
Eldan, R. and Shamir, O. (2016). The power of depth for feedforward neural networks. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 907-940. PMLR.
Genevay, A., Peyre, G., and Cuturi, M. (2018). Learning generative models with sinkhorn divergences. In Proceedings of the Twenty-Firs, International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1608-1617. PMLR.
Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. (2019). Limitations of lazy training of two-layers neural network. In NeurIPS.
Goodfellow, I., Pouget-Abadic, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014). Generative adversarial nets. In NIPS.
Gorham, and Mackey, L. (2015). Mcasuring sample quality with stein's 's method. Advances in Neural Information Processing Systems, pages 226-234.
Gorham, and Mackey, (2017). Measuring sample quality with kernels. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 1292-1301. PMLR.

---

Grathwohl, W., Wang, K.-C., Jacobsen, J.-H., Duvenaud, D., and Zemel, R. (2020). Learning the stein discrepancy for training and evaluating energy-based models without sampling. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 3732-3747.
Gretton, A., Borgwardt, M., Rasch, M., Schölkopf, B., and Smola, (2007). A kernel method for the two-sample-problem. In Advances in neural information processing systems, pages 513-520.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. (2012). A kernel tao-s test. Journal of Machine Learning Research, 13(25):22-773.
Huggins, J. and Mackey, L. (2018). Random feature stein discrepancies. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianche N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
Jacot, A., Gabriel, F,, and Hongler, C. (2018). Neural tangent kernel:
Convergence and generalization in neural networks. Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Resa-Bianchhi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31, pages 8571-8580. Curran Associates, Inc.
Kammler, D. (2000). A first course in Fourier analysis. Prentice Hall.
Kolouri, S., Nadjahi, K., Simsekli, U., Badeau, R., and Rohde, G. (2019). Generalized sliced wasserstein distances. In Advances in Neural Information Processing Systems, volume 32.
Kolouri, S., Zou, Y., and Rohde, G. K. (2016). Sliced wasserstein kernels for probability distributions. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 5258-5267.
Li, C.-L., Chang, W.-C., Cheng, Y., Yang, Y., and Poczos, B. (2017). Mmd gan: Towards deeper understanding of moment matching network. In Advances in Neural Information Processing Systems, volume 30.
Li, Y., Swersky, K., and Zemel, R. (2015). Generative moment matching networks. In ICML.
Lin, T., Zheng, Z., Chen, E. Y., Cuturi, M., and Jordan, M. I. (2021). On projection robust optimal transport: Sample complexity and model misspecification.
Liu, Q., Lee, J., and Jordan, M. (2016). A kernelized stein discrepancy for goodness-off of-fit tests. In Proceedings of The 33rd International Conference on Machine Learning. volume 48, pages 276-2844 New York, New York, USA. PMLR.
Liu, Q. and Wang. D. (2016). Stein variational gradient descent: general purpose bayesian inference algorithm. In Advances in Neural Information Processing Systems, volume 29, pages 2378-2386 Curran Associates, Inc.
Mohamed, S. and Lakshminarayanan, B. (2017). Learning in implicit generative models. In ICLR.
Nadjahi, K., Durmus, A., Chizat, L., Kolouri, S., Shahrampour, S., and Simsekli, U. (2020). Statistical and topological properties of sliced probability divergences. In Advances in Neural Information Processing Systems, volume 33, pages 20802-20812.
Niles-Weed, and Rigollet, P. (2019). Estimation of wasserstein distances in the spiked transport model.
Ongie. G. Willett, R., Soudry, D., and Srebro, N. (2019). A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning Representations (ICLR 2020).
Paty, F.PP. and Cuturi, M. (2019). Subspace robust wasserstein distances.
Rezende, J. and Mohamed, S. (2015). Variational inference with normalizing flows. arXiv preprint 1r51v.150..05770
12

---

Roux, N. L. and Bengio, Y. (2007). Continuous neural networks. In Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 404-411, San Juan, Puerto Rico.
Santos, C. N. D., Mroueh, Y., Padhi, I., and Dognin, P. (2019). Learning implicit generative models by matching perceptual features. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 4460-4469.
Savarese, P., Evron, I., Soudry, D., and Srebro, N. (2019). How do infinite width bounded norm networks look in function space? In Conference on Learning Theory.
Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory, pages 583-602
Venturi, I.., Jelassi, S., Ozuch, T., and Bruna, J. (2021). Depth separation beyond radial functions.
Wei, C., Lee, J. D., Liu, Q., and Ma, T. (2020). Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel.
Williams, F., Trager, M., Silva, C.,, Panozzo, D., Zorin, D., and Bruna, J. (2019). Gradient dynamics of shallow univariate relu networks. Advances Neural Information Processing Systems (NeurIPS).
Woodworth, B., Gunasekar, S., Lee, J. D., Moroshko, E., Savarese, P., Golan, I., Soudry, D., and Srebro, N. (2020), Kernel and rich regimes in overparametrized models. In Conference on Learning Theory.
13


Reviews:
[{"review_id": "eTh7c2pOIId", "reviewer": "Reviewer_tbhZ", "summary": "The authors study two classes of functions, F1 and F2, which are related to\n\"infinite-width\" two-layer neural nets and fixed-kernel RKHSes. They show\nthat in the regime where d goes to infinity, the sensitivity of MMDs based\non F2 decreases exponentially comapred to F1 for specific pairs of measures\non the hypersphere S^d. The authors corroborrate this theoretical find with\nsome simulations.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While mostly a theoretical contribution, the work here seems like a concrete\naddition to understanding the differences between F1 and F2. There are also\nsome nice connections made to the sliced and max-sliced Wasserstein metrics\nwhich establishes some nice bounds for these quantities.\n\nOriginality:\nThe constructive examples given in the paper seem quite carefully\nconstructed. While this work builds upon much other recent work, the core\ntheorems are original and elucidating.\n\nQuality:\nThe claims in the paper look correct. Outside of a couple ambiguous parts,\nthe paper was well written.\n\nClarity:\nDespite the difficulty of the subject, the paper was quite pleasant to read.\n\nSignificance:\nWhile the paper may not have any immediate practical import, it does made a\ntheoretical contribution to an important problem in discriminator theory. In\norder to bolster this area, I would suggest that the authors expound a bit\nmore on F1 and F2 and how they related to modern NNs/GANs in a bit more\ndetail at the beginning of the paper.\n\nDetailed Comments:\n\nL110-111: It might be worthwhile to expound a bit on what \"single units\"\nare, as this is a key fact for claims that F1 is better than F2.\n\nL155: \"as x = r zeta_{(d)} with zeta_{(d)},\" should belong to S^(d-1)\nTheorem 2: The wording here is a little ambiguous. Does \"we can choose k >=\n0 and gamma_{k,d} in [-1, 1]\" mean that we can choose any such values and\n(5-7) will hold? Or does this mean we need a speciifc choice of values for\nthese to hold? Moreover, why does (5) not depend on gamma_{k,d}?\n\nL194: Where is s_{nu} defined?\n\nL276: Can you explain exactly what \"by statistical errors\" means?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not include an impact on the societal impact of their work\nand should add one!", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Y6Mw4lRqVxQ", "reviewer": "Reviewer_7tHG", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written very cleanly, and it has a clear message and demonstration of that message: learned features have greater discrimination power than a fixed kernel. The theoretical nature of the paper complements previous empirical demonstrations of this message.\n\nThe results also appear very clean. I am not familiar with constructions involving spherical harmonics, but within this area, they seem natural. A sequence of pairs of probability distributions defined by the Legendre harmonic is defined which exhibits an exponential gap between the F_1 IPM and the F_2 IPM, and the authors obtain closed form expressions for the IPMs, which is nice. I also found it interesting that Theorem 1 sheds light on when a previously defined \"neural net distance\" is actually a distance. The separation in terms of Stein discrepancy is also interesting since the Stein discrepancy is another popular metric used in discrimination tasks, and the within polynomial factor correspondences between F_1 IPM and max-sliced Wasserstein distance and between F_2 IPM and sliced Wasserstein distance is an interesting, unifying characterization. \n\nSince the paper is so clean and has useful results, I vote to accept. I seems like it would be a useful reference to other researchers in this area. \n\nA question that I have about the technical novelty of the paper is, how different is the usage of spherical harmonics here from the Bach 2017 reference. What did Bach 2017 use spherical harmonics for, and how similar are any constructions involving them between this paper and that one? \nA note: I did not see s_{nu} defined anywhere, in the definition of the kernelized stein discrepancy.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Wxs0FXVRtXs", "reviewer": "Reviewer_e39f", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe results and the presentation of the mathematical results are clean and solid (however I have not had a chance to check the proofs in detail). The story that feature learning is beneficial as opposed to fixed kernel is not very surprising not only empirically but also theoretically if the reader is familiar with the F_1 vs F_2 literature. Still, showing it for generative modeling explicitly is novel and could be valuable. \n\nConstructive comments:\n\nIn order to make the results more impactful within the ML community however, the results seem to directly suggest an experiment to link back the theoretical insights to the practical motivation: i.e. can you design an experiment that illustrates that the insight from the distribution pairs (different high frequency components) that are indistinguishable as d-> infty for F_2, carries over to the image scenarios that motivate this study?For example, something that immediately comes to mind is that you could remove/project out the high frequency components and see if the FID without feature learning then gets better\n\nMoreover, the presentation could be much improved. Here is some more detailed feedback \n\n- The figures are quite poorly presented - use different linestyle. The two red curves in Figure 3 - which is which?\n\n- For IPM your theoretical prediction is quite accurate. For Stein discrepancy - it’s not clear that the ratio is actually increasing with d empirically albeit being high in general. I’m missing a discussion on these Stein discrepancy simulations in general\n\n- Section 7 and appendix generally seem relatively underdeveloped - the relevance of assumptions and implications of Theorem 5 should be directly discussed and interpreted in order for the reader to know what to focus on while parsing it and perhaps the proof. Furthermore, the switch from F_2 to Ftilde_2 is not well motivated - what do we learn about F_2 by looking at Ftilde_2 instead? \n\n- You mention setting k=d near the discussion of the implications of the theorem and later in the experiments set k constant for all d - discussion would help\n\n- Dimensionality - In sections 3, 4, and 7, the inputs are considered to lie in a subset K of the (d+1)-dimensional space (l. 114), and the paper considers statistical distances between distributions \\mu and \\nu over K, for two special cases: K=R^d \\times {1} or K=S^d. However in sections 5 and 6, the distributions \\mu_d and \\nu_d are defined over S^{d-1}. Might be useful to keep it consistent\n\nMinor comments\n\n- l. 178: define the acronym EBM, and add the relevant references again\n- line 171 it seems like eq (6) should read eq (5)\n- eq (33) is the same as (6) - was a bit confusing in the main text \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "purely theoretical work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "3m-xRScFRYe", "reviewer": "Reviewer_tnLw", "summary": "The authors propose theoretical results about separation between probability metrics with fixed-kernel and feature-learning discriminators in overparameterized two-layer neural network spaces.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors propose theoretical results about separation between probability metrics with fixed-kernel and feature-learning discriminators in overparameterized two-layer neural network spaces.\n\nIn Theorem 2 and 3, the authors derive the ratio between feature-learning $F_1$ and fixed-kernel $F_2$ integral probability metrics (IPM), and for $F_1$ and $F_2$ Stein respectively. The authors illustrate that on the hyper-spheres, the $F_1$ IPM/Stein has much larger values than $F_2$ IPM/Stein which seems to infer that the separation of $F_1$ IPM/Stein is better than $F_2$ IPM/Stein (line 170-175 and line 214-217). \n+ Do the $F_1$ IPM/Stein have different range values than $F_2$ IPM/Stein? (since it is unclear whether their values have a same range)\n+ Does the separation relate to the range value of a discrepancy d? since with k>1, the discrepancy kd is k-times larger than discrepancy d, does it imply the separation of discrepancy kd is better than that of discrepancy d? \n--> It is better in case the authors give a more formal definition of \"separation\". How does the \"separation\" relate to the value of a discrepancy between probability measures?\n\nSome other concerns:\n+ in line 108, $F_2 \\subset F_1$, could the authors elaborate this property with more details? Can one use this property for $F_1$ and $F_2$ IPM directly since the IPM is maximum over $F$ space?\n+ For results in Section 7.2, what is the relation between $F_2$ and $\\tilde{F}_2$?\n+ In experiments, how does the degree of Legendre polynomial affect the results?\n\nSome minor concerns:\n+ For the sliced Wasserstein, I think it is better to cite the work of Rabin et al, 2011 which is the first paper about sliced-Wasserstein.\n\nReferences:\n+ Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision, pages 435–446, 2011.\n\n------After the rebuttal-----\nI thank the authors for the rebuttal. I think that it is better in case the authors improve the clarification about those raised points (I feel that there are several implications that make it hard for the readers to access its contributions. \nFrom the discussions with other reviewers, the theoretical part is good, but the contribution can be further improved with some well-designed experiments to illustrate the proposed theoretical results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present interesting theoretical analysis with wide-reaching implications; they are able to exhibit sequences of distributions which are distinguished by F1 integral probability metrics (based on an infinite width neural network function class that performs "feature learning") but not F2 integral probability metrics (a function class that does not perform "feature learning"), and in doing so they provide theoretical support for the notion that feature learning is an important property for discriminators (e.g. an argument against the use of "MMD GANs", which have previously appeared in NeurIPS).  The analysis is extended to cover Stein discrepancy, again based on F1 and F2.  All reviewers agreed that the paper was well-written and correct.  I believe these results will be of significant interest to the participants of NeurIPS.
Decision: Accept (Oral)