Max-sliced Bures Distance for Interpreting Discrepancies
Authors: Austin J. Brockmeier
Claudio Cesar Claros
Carlos H. Mendoza-Cardenas
Yüksel Karahan
Matthew S. Emigh
Luis Gonzalo Sanchez Giraldo
Venue:  (2021)
Keywords: covariance
covariate shift
distance metrics
divergence
generative adversarial networks
interpretable approaches
kernel methods
probability metric
RKHS

Abstract: We propose the max-sliced Bures distance, a lower bound on the max-sliced Wasserstein-2 distance, to identify the instances associated with the maximum discrepancy between two samples. The max-slicing can be decomposed into two asymmetric divergences each expressed in terms of an optimal slice or equivalently a witness function that has large magnitude evaluations on a localized subset of instances in one distribution versus the other. We show how witness functions can be used to detect and correct for covariate shift through reweighting and to evaluate generative adversarial networks.  Unlike heuristic algorithms for the max-sliced Wasserstein-2 distance that may fail to find the optimal slice, we detail a tractable algorithm that finds the global optimal slice and scales to large sample sizes.  As the Bures distance quantifies differences in covariance, we generalize the max-sliced Bures distance by using non-linear mappings, enabling it to capture changes in higher-order statistics. We explore two types of non-linear mappings: positive semidefinite kernels where the witness functions belong to a reproducing kernel Hilbert space, and task-relevant mappings corresponding to a neural network. In the context of samples of natural images, our approach provides an interpretation of the Fréchet Inception distance by identifying the synthetic and natural instances that are either over-represented or under-represented with respect to the other sample. We apply the proposed measure to detect imbalances in class distributions in various data sets and to critique generative models.

Under review as a conference paper at ICLR 2021
MAX-SLICED BURES DISTANCE FOR INTERPRETING DISCREPANCIES
Anonymous authors Paper under double-bling review
ABSTRACT
We propose the max-sliced Bures distance, lower bound the max-sliced Wasserstein-2 distance, to identify the instances associated with the maximum discrepancy between two samples. The max-slicing can be decomposed into two asymmetric divergences each expressed in terms of an optimal slice or equiva- lently 'witness" function that has large magnitude evaluations subset of instances in one distribution versus the other. We show how witness functions can be used to detect and correct for covariate shift through reweighting and to evaluate generative adversarial networks. Unlike heuristic algorithms for the max- saxx-siced Wasserstein-2 distance that may fail find the optimal slice, we detail a tractable algorithm that finds the global optimal slice and scales to large sample sizes. As the Bures distance quantifies differences in covariance, we gen- eralize the max-sliced Bures distance by using non-linear mappings, enabling it to capture changes higher-order statistics. We explore two types of non-linear mappings: positive semidefinite kernels where the witness functions belong to reproducing kernel Hilbert space, and task-relevant mappings corresponding to a neural network. In the context of samples of natural images, our approach pro- vides an interpretation of the Fréchet Inception distance by identifying the syn- thetic and natural instances that are either over-represented or under-represented with respect to the other sample. We apply the proposed measure to detect imbal- ances in class distributions in various data sets and to critique generative models.
localized
INTRODUCTION
Divergence measures quantify the dissimilarity between probability distributions. They are funda- mental to hypothesis testing and the estimation and criticism of statistical models, and serve as cost functions for optimizing generative adversarial neural networks (GANs). Although a multitude of divergences exists, not all of them are interpretable. A divergence is interpretable if can be expressed in terms of a real-valued wimess function w-)) whose level-sets identify the specific subsets that are not well matched between the distributions, specifically, subsets which have much higher much lower probability under one distribution versus the other. Localizing these discrepancies is useful for understanding and compensating for differences between two samples distributions, detect covariate shift (Shimodaira, 20000 Quuonero-Candell et al. 2009: Lipton et al.) 2018) or to evaluate generative models (Heusel al. 2017).
While many divergences can be posed in terms of witness functions, not all witness functions are readily obtained or interpreted. From an information-theoree function is the logarithm of the ratio of the densities (Kullback & Leibler 195T) as in the Kullback- Leibler divergence. Applying other convex functions to the density ratio constitutes the family of f f-divergences (Ali & Silvey 1966. Rényl 1961), which include the Hellinger, Jensen- and others. However, without a parametric model estimating the densities from samples challeng- ing [Vapnik 2013). Following Vapnik's 's advice to "try to avoid solving more general problem an intermediate step." previous work has sought to directly model the density ratio via kernel learning (guuynn al. 2008 Kanamori et al.) [2009] Yamada et al. 2011 2013 Saito et al. 2018 Lee al. 2019) or to estimate an f-divergence by optimizing a function from a suitable family (Nguyen et al. 2010 such neural network Nowozin et al. (0016).
perspective, the most natural witness

---

Under review as a conference paper at ICLR 2021
Witness functions need not rely on the density ratio. A wide class of divergences called integral probability metrics (IPMs) (Müller) 1997). which include total variation, the Wasserstein- 1 distance, maximum mean discrepancy (MMD) (Gretton et al. 2007), and others (Mrouch al. 2017). seek a witness function that maximizes the distance between the first moments of the witness function evaluations. In these cases the optimal witness function w+(+) has greater expectation in one distribution compared to the other distribution. An IPM between two measures μt and V/ is expressed as suP (xx=((((())
Y (x)() }]] for a given family of functions F.
A class of related divergences are the max-sliced Wasserstein-p distances, which seek a lin- ear (Deshpande et al. 2019) or non-linear slicing function (Kolouri et al.] 2019) that maximizes the Wasserstein-p distance between the witness function evaluations for the two distributions. How- ever, there are two difficulties with computing the max-sliced Wasserstein distance for two samples. The first is that it is saddlepoint optimization problem, whose objective evaluation requires sorting the samples. Previous work has sought to approximate using a first moment approximation (Desh-) pande et al. 2019) or to use a finite number of steps of local optimizer (Kolouri et al. 2019), without any guarantee of obtaining an optimal witness function. Another difficulty is in the inter- pretation of the obtained witness function. Unlike the density ratio, there is notion of whether the witness function will take higher values for points associated to one distribution versus the other. To address both of these issues propose max-sliced distance that replaces the Wasserstein-2 distance with a second-moment approximation based on the Bures distance (Dowson & Landau 1982 Gelbrich| 1990). The Bures distance (Bures) 1969 Uhlmann 1976) is a distance metric be- tween positive semidefinite operators, is well-known in quantum information theory (Nielsen &
Chuang 2000, Koltchinski & Xia 2013) and machine learning (Brockmeier al. 2017 Muzellec
& Cuturi 2018, Zhang et al.
2020 Oh et al. 2020 De Meulemeester et al.) 2020
1.1 CONTRIBUTION
We propose a novel IPM-like divergence measure, the "max-sliced Bures distance", to identify localized regions and instances associated with the maximum discrepancy between two samples. The distance is expressed as the maximal difference between the root mean square (RMS) of the witness function evaluations supwes /Exxal=²(X)) (Ey where S is an ap- propriate family of functions. As | max A},, the max-sliced Bures can be expressed as the maximum of one-sided max max-sliced divergences with optimal witness functions, wyse
arg max_es /
(Y)] ware = arg max [x(([] the distributions are not well-matched, then Wa>D has large magnitude function evaluations under 'localized' subset of μ and smaller magnitude values for v, and the opposite for wy<n. The two samples {.,) ) can be sorted by the magnitude of the witness function evaluations
Crucially, we detail a tractable optimization procedure that is guaranteed to yield global optimum witness function for the one-sided max-sliced Bures divergence. When X' = Rd and the first or second moments distinguish the distributions, linear witness functions can be used S = =-((-) = (:, w) w gd-1), where gdt11 denotes the unit sphere in Rd. The optimal witness function for the one-sided max-sliced Bures divergence (-) = (', Wase) coincides with the subspace with the greatest difference in RMS, WH>0 = arg wax 1 V w E[XX |w /w" EE(YYT] This optimization problem depends on the dimension d; after computation of the covariance matrices, it is independent of the sample sizes 2 n. In comparison, the optimal slice for the max-sliced Wasserstein may not be obtained, and even gradient ascent to a local optimum requires O(m log m) at each imnction/gradient evaluation. Furthermore, the slice that maximizes the max-sliced Wasser-
I Four groups of 'witness points' (top-K K instances) can be inspected to identify any discrepanciex:
((+()))) 2 ... 2 (
(H 2 ... 2 w (Mb(K)
(1)
sorts (mm) revevval exampies from f with large 2
sorts [v. to find the exampies from with large - pa
w weec((E 2 ... w(cu(FE(K))
w (Hre(Hor)) 2 ... we
(2)
sorts [x:) find eximples from (i with large wi sorts 1or12- to find the exsmples from with lirge i
where it, 4, .. denote permutations and S and denote expected inequalities with large difference.
2

---

Under review as a conference paper at ICLR 2021
Filll (40
g
Y Ao le
Fa(1]+
Reals Fake
Mai M)
Real-<
Wollyr -...
Za0h-
Reales Pale
Ma
Real-Fake
Vo(1)--- (00
Figure 1: The magnitude of the witness functions obtained from max-sliced Bures indicate dis- crepancies. (Left) A Gaussian kernel used to construct non-linear witness functions and identify witness points. (Right) Witness points for real and fake images from stacked MNIST and CIFAR 10. In each of the 6 frames, instances corresponding to the left hand sides of equation | and equation 2 on the top; the bottom instances correspond to the right hand sides of the expected inequalities.
stein lacks an intrinsic ordering, and it left to the user to determine whether instances from or v have high or low values or magnitudes.
As second-order moments may be insufficient for distinguishing the distributions, we explore non-linear mappings of the random variables. Firstly, we consider reproducing kernel Hilbert space (RKHS) H with the family of witness functions S fw(-) = (o(-).w)x w, Φ(-) E H. (w, 1}. An example with Gaussian kernels is shown in Figure Secondly, we use pre-trained neural network to create task-relevant mapping, computing the second-order statistics of the hidden-layer activations, and apply this the context of samples of natural images. This enables interpretation of the Fréchet Inception distance (FID) (Heusel al. 2017) by identifying the subspace and images associated with discrepancies between synthetic and natural images. We prove that the max-sliced Bures distance provides lower bound on the max-sliced Fréchet distance.
Because their similarity, we develop the max-sliced Bures distance in the context of max-sliced versions of the total variation and Wasserstein-2 distances. The kernel-based versions of these novel contributions themselves. The max-sliced total variation distance a special case of the covariance feature matching proposed by Mroueh al. (2017).
In experimental results, we show applications of the linear and kernel-based versions to detect im- balances in class distributions of natural images and to critique GANs. We compare other diver- gences expressed in terms of witness functions including MMD. Finally, we propose algorithms to reweight an empirical distribution in order minimize max-sliced divergences (with applications to generating conditional distributions and covariate shift correction).
METHODOLOGY
Consider a topological space X, a Borel o-algebra Bx, and the set Pr(x') of Borel probability measures X. Let μ,, E Pr(X)) denote two probability measures, and X μ and Y be two random variables X,Y E X. Let k denote a positive-definite, bounded kernel function X x X B C R. For any K. there is implicit mapping Ø X + H that maps any element E X' to an element in the reproducing kernel Hilbert space (RKHS) d(x) E H. such that <(x,)) y) = (o(z). o( n (x( x(- v) for z, E X, and Yu E H.w(x))
(wo, k(,,))H (Aron- szajn 1950 Yw E H. ||]]2 = /ww,w)m When clear, we drop the H subscript on the inner product. A rank-1 RKHS operator is denoted as @ th E H x H with ((w & ())(()) o(y))
(1,, (())) (w, ((v)) = (z))(y)) for F, E X. Denote by mx = E Ex~a (xxx))(X) E 76 and my E Yo [o()) E H. the first moments of the random variables in the RKHS. The uncen- tered second moments are Px = E [x(X) @ x(X) E H. x H and py = E (o(Y) @ o(Y) E H x H. The covariance operators Σx px mx mx and Ey = PV my ( my.
3

---

Under review as a conference paper at ICLR 2021
2.1 DIVERGENCES AS DISTANCE METRICS
Let Diu, v) denote a divergence D Pr(œ)) x Pr(x) + [0, x). It is a distance metric between
measures probability metric) if all of the following statements hold: (i) μr = = D(,, v) O. (ii) D(u, v) = 0 =
v, (iii) D(u, v) = D(v, jr), (iv) Din, v) v E(,,E) + E) semi-metric if all properties aside from (ii) hold. Müller (1997) defines the class of integral probability metrics as the supremum of the absolute difference between expectations
/ w(z)du(x)) - -fx (=(())dd()))))
(y(,, sup WEF
sup [[w(X)] B|W(Y)| WEF
With appropriate choice of the family of functions F, this form yields well-known diver- gences (Sriperumbudur et al., 2010), e.g., when F is the set of functions with Lipschitz constant less than I, the resulting divergence is the Wasserstein- I distance metric. Another example of an IPM is when F {w E H ||w||2 S 1}. which yields MMD (Gretton et al. 2007). defined as
(H, sup
[X]] - E[w(Y)) = (xx) - ((Y), wl)l = ||mx my lla
w WEH:1WllaS1
(xXx,,X'xlIXXXXX + Ey (K( Y, Y() - XEx~p,y (x(X, Y)]. (3)
For characteristic kernels such as the Laplacian and Gaussian kernels, the mean embedding E [xxnul((X)) [x()] Pr(X') H is injective function (Sriperumbudur et al. 2008 Fukumizu al.
2009 Sriperumbudur et al. 2010), capturing the full statistics of μ.. In these cases, MMD Is a dis-
tance metric on Pr(x);; likewise, distance metrics between the operators px E [ @ o and py = E (o( &0 ({Y) induce probability metrics for characteristic kernels (Zhang et al. 2020
2.2
OPERATOR DISTANCES FOR DEFINING DIVERGENCES
Total variation (TV) a well-known probability metric and an integral probability metric (Müller
1997.. taking the form (1/2) E.lp: for discrete measures, for which p; = u(x;)) and g, vzx,)
where {Ii}= = X. The TV distance between operators in the RKHS is a divergence
DHV (M, v) drv (px, pY) 2 lpx - py 11a,
(4)
where ||-1| denotes the trace norm (Schatten 1-norm), which is the sum of the singular values.
The Bures distance generalizes the Hellinger distance (1/2) (vP:
/ 2 to positive
semidefinite operators (Fuchs Van De Graaf 1999 Bromley et al. 2014 Bhatia et al. 2019
The kernel Bures divergence D (1, v) and the Bures distance d (Px, Pr) are defined
DE v) d dn v |ex|i + ||pr||| - 2 |V I
(5)
The Bures distance is used to define the Wasserstein-2 (W2) distance between Gaussian measures,
i.e. the Fréchet distance (Fréchet 1957 Dowson & Landau 1982). The multivariate Fréchet dis-
tance provides lower bound for the W2 distance (Gelbrich, 1990h The kernel Gasse--Wsserstein
distance (Zhang et al. 2020 Oh et al. 2020 is defined as
D (n, v) A v |mx my my d2x Σv)
V D (M, + dy (Ex Ey).
(6)
Zhang al. 2020) also proposed the kernel Wasserstein-p distance between ls and v,
p (p, v) e
inf (EI (X,Y)
de (X(
p p21, 1,
(7)
where I'(2, v) defines the set of all joint distributions coupling μ and v, and (x, (X) (()) For p- = 2, (X, Y) = <(X, +)+x<YY; kY ( (7))2((xXX)) When p = and Φ(x) + x E Rd such that H = ddd the standard W2 distance w (p, 1/) is obtained.
PIn the fiite-dimensionna case, the multivariate Fréchet distance (squared) is often expressed as || my [| + tr(xx + Ey- 2/ Ey the trace term is the squared Bures distance (Ex, Ev) = Lr (x +
Σy) EE where E/vEx>> tr(v Ex (Dowson & Landau 1982..
4

---

Under review as a conference paper at ICLR 2021
2.3 DIVERGENCES BASED ON SLICING HILBERT SPACES
The sliced Wasserstein distance (Wu al. 2019 Deshpande et al. 2018 Kolouri et 2018), and max-sliced Wasserstein distance (Deshpande et al. 2019 Kolouri et 2019 evaluate discrepancies in linear or non-linear one-dimensional subspaces. motivation for this the analytic solution of the Wasserstein-p distance in one dimension. The max-sliced Wasserstein-p distance takes the form maxx-W?t p (j, 2) x suPwesá-1 infrer(p..)) (xxx)>>><X Y,,)),, p 1. Similarly, we propose the max-sliced Bures, the kernel TV, and the kernel Wasserstein-p distances using the rank- w @ w E H. x H. which projects (slices) the RKHS along a mee-iimnsiooal subspace defined by the ray E H. with (w, ((X)) = w(X). due to the reproducing property. In this formulation, w : X ->
operator
the witness function from the set S= [ E H. || Notably, a linear slice in the RKHS is possibly non-linear function in the input space.
For conciseness, we denote the mean square witness function evaluations E (X)] (w. pxw) |lypxwll3 as || and E [Y)) = (w, pYw) = l1ypywll2 as ||ll| The RMS ||0|| is an L semi-norm on w induced by the positive semidefinite operator vpx. The max-sliced kernel TV, Bures, and W2 distances, derived in appendix A. are expressed as
max-DTv (u,
max
sup WEE
Supl|w/l 1w WES
sup || 1 - u
(8)
2
max-D (H,
max
sup||/ll, -1lwlles WES
sup
sup WES
sup||/||. - ||l|| and
(9)
max- (x,-W,"(,,1)
sup WES
/|wl3 + ||w|1
sup vET(Mw) (X.Y)
E
(10)
respectively. The inner supremums in equation g and equation 9 are the one-sided divergences.
The max-sliced TV distance is an IPM with F= (w² (ó(z), w)² Vas E S} and is a special
case of the IPMs divergence proposed by Mrouch et al. (2117). While not an IPM, the max-sliced kernel Bures distance can be directly related to max-sliced versions of the TV, Fréchet, and W2 distance, as detailed by the following results.
Theorem 1.
The square of the max-sliced Bures distance in the RKHS H. is less than or equal to twice the max-sliced TV distance, max-D (1.,) I 2/ (2aa--DD (H,v).
Theorem 2.
The max-sliced Bures distance in the RKHS H. lower bound on the kernel max- sliced Gauss-Was Wasserstein distance, max-D (H, & maxx-DDt GW (p, v) S Da (p, (H,v).
Theorem 3. The max-sliced Bures distance in the RKHS is a lower bound on the kernel max-sliced W2 distance, max- D (p, v) S. max-WHH (p,
These results trivially translate to the linear kernel case 7/ = S= ,((x (w. x),, for w, x E Rd and X' C Rd. The latter two show that the max-sliced Bures distance is lower-bound on the max-sliced Fréchet distance, which is a lower-bound proofs and other relationships among the divergences are in Appendix A.2
the max-sliced W2 distance. The
2.4 COMPUTING THE MAX-SLICED DIVERGENCES
The max-sliced kernel Bures, TV, and W2 distances require solving optimization problems to find the optimal witness function. As noted by others investigating IPMs (Mroueh et al.) 2017 Li et al. 2017 Kolouri et al.] 2019). the witness function can be defined using a family of functions implemented as neural network. In this context, Goodffllow et all (2014) use the divergence ( = max, E [log (X)] ] + E [log (1 (Y))). where w : X (0, 1). In comparison,
the Wasserstein-1 distance Dwy (n,, v) suPwELip R[w(X)) - E(w((Y) requires a Lipschitz
5

---

Under review as a conference paper at ICLR 2021
straint
AArovssy al. 2017 Gulrajani et al. 2017 B Table |
compares the form and constraints.
Table I: Divergences written in terms of witness functions. Closed-form solutions denoted w
DA(L,V)
māX,=))EE(.)) E w (X)] Bllog (1 w(Y)),, w (-(-) [X]
dpl
Dwi (H,,2 v)
supweLip' (X))
(Y))
DMMD (H,, v)
SUPWEH:||/|aass R |
E. (l
ma my ma -my
max- Div
E w (X)] El
max- max-D' (u,
sUPucH:|ollas] [X)] -- VE(w
2.5 SAMPLE-BASED ESTIMATORS FOR MAX-SLICED DIVERGENCES
We consider the case of finite samples expressed as empirical measures jt = Di=1 P,g and i = E 146g, for the samples {a;; 1 1 and {yr Y with discrete probability masses denoted as column vectors [.1.....
= E [0, (,,1) 1, and [V1..... "v]' = E [0, 1]" (v,1) 1. The kemnel-based max-sliced divergences optimize the witness function w(-) = Σ Di=1 ap 2.) in terms of the dual variables E TRe corresponding to subset of the pooled sample (2r = (vr
The optimization problems and algorithms are detailed in appendix [A.4]
For clarity, we proceed to the linear kernel case for finiteddimensional embedding ((x)
Rdd
After embedding, kernel evaluations correspond to vector inner-products k(z, y) = (0(z), ozy)
yyy. Let X ix,,..., x d and Y [y ,. ynl E _x denote the sample points with corresponding masses μe and V, respectively. The witness function is the inner product w(z) w x, where the variable w defines the slice with ||w/| w p. with px XD and
||wl1 = w Py with PY = YD,YT, where Dv is diagonal with entries v. For i.idd samples, D2 I and D2 L. The max-sliced TV, Bures, and W2 divergences are
max-Dry (), max w: 12S1
w (px - pY) \1 px);
(11)
max-D D3' (0,0)=
max w:
w PXW W PYW and
(12)
max- (0, 0)
max w:llwaassi
w TTx fox+PPX pr - 2 max w XP w,
(13)
PEP
where (-) denotes the largest magnitude eigenvalue of the argument and Pa.e. [0,
(P
μ. P 1m / is transportation polytope.
These three optimizations differ in difficulty. The first two require only the sample means mxx my and covariance matrices Σx. Ey, since px mx + m -x and py = my + n-1 Ey (assuming unbiased covariance estimates). The one-sided max-sliced TV divergences can be solved by finding the eigenvectors associated to the largest eigenvalues of px px-Py Py and py - -xx Likewise the optimal slice for each one-sided max-sliced Bures divergence requires solving a series of eigen- vector problems. Specifically, if px and py are strictly positive definite, then the optimal witness function is (-) (Wyr:"), :), where 7 E (0, solves the optimization problem
= arg max wT PxW, W. Wys 0<>511
W,, arg max W T(Tpx - pry). w:llw]laS1
(14)
The general case involves checking the nullspace of py and is given in the Appendix A.5| In com- parison, the max-sliced W2 distance a saddlepoint optimization problem (Deshpande al. 2019)
'In the context of GANs, the sum of the one-sided max-sliced Bures divergences may prove more appro- priate for training, since it allows for separate witness functions for over- and under-representation. However, as its witness functions tend to localize discrepancies, even two witness functions may not make efficient use of the generator's samples. Instead, a distributional-vertee cent distributional--lice. Wasserstein proposal (Anonymous) T02 or the Bures distance itself (Anonymous) 202Th) could be used. Nonetheless, this localization property what makes the max-sliced Bures interpretable.
of the sliced Bures distance akin to the re-

---

Under review as a conference paper at ICLR 2021
Following Kolouri et al. 2019), gradient ascent w can be performed with first-order solves. Each
gradient evaluation requires solving the transport map by sorting X w and Y w. For this, we use ADAM (Kingma & Ba 2013) and quasi-Newton approaches, such as MINFUNC (Schmidt 2012).
The same approaches can be used to approximate max-D after smoothing v as V +.01.
EXPERIMENTS
We present various examples of using the proposed max max-sliced divergences to identify the discrep- ancies between two samples. We apply the proposed approach to detect mismatched distributions of natural and fake images using the internal representation of the Inception Network (Szegedy et al.) 2016) in the Fréchet Inception distance (Heusel al. 2017) and the Inception score (Salimans) et al. 2016). We investigate whether the witness functions detect covariate shift caused by class imbalances. Then, we propose optimizing the weights compensate for covariate shift. Finally, we use the one-sided max-sliced Bures divergence to monitor mode dropping during GAN training.
3.1 INTERPRETING THE FRÉCHET INCEPTION DISTANCE
We use linear witness function to identify instances that are well matched between two sam- ples of real or fake images represented by internal activations of the Inception object classify- ing network (Szegedy et al. 2016). Specifically, we search for witness functions with the form w (x) = (w, [(x)), where the vector <(x)) E 1R is an Inception code the internal activations of penultimate layer of the network after pooling (Heusel al. 2017).
Figure 2 shows the performance of the proposed measure to identify instances associated with im- balanced representation of particular classes. In particular, j is a uniform sample from the training set and á is a sample from the test set with less instances from one class. Using the one-sided max-sliced Bures divergence we obtain the optimal slice Wasv and apply it to the imbalanced sample D. identifying the top- 10 witness points with the largest magnitude witness function eval- where is a permutation corresponding to sorting {ys )im by descending magnitude. (While this may seem counterintuitive as is expected that maxigism "//0(zz)) >> maxigign wht (Ut), since Wasv corresponds to mne-iimnniional sub- space, (Vars) )== are the K instances from á with the largest norm after projection to this subspace.) The performance is quantified by the precision of the labels of these instances (ideally, these wit- ness points should be from the underrepresented class). Notably, the mean precision of the top- 10 instances is 0.79 or better across the classes with mean average precision (MAP) of 0.94 when the class probabilities differ by 2% (10.2% for majority and 8.2% for minority). This is compared to a MAP of 0.82 for the first frst-moment based surrogate of the max-sliced W2 distance (Deshpande et al. 2019). Computing the max-sliced W2 distance takes much longer to run on this sample size.
uations w (bb)) 2 ... 2
Min Gliced Bures
Firsi-tooentt Appros, to May Slood Wasserstenn
Ugan Ug peotoon 10
0.8
sppliis jull
2.3
aapanso
Bus
94
0.4
org
62
0.2
AP10
0.5
11125 05
Dilinance in reprosentatir for minority clasd (5)
Dffanance in reprose dalion mi horlityylaaaa cleas (5%)
Figure 2: Max-sliced divergences using the Inception Network representation are applied to samples with mismatched class distributions in CIFARI0. The first sample consists of the training set (bal- anced classes with m=50,000), and the second sample is an imbalanced subset of the test set with n=10,000. Each curve is the mean precision @ 10 (averaged across 10 random draws) for test sets where the given class is subsampled at different levels of imbalance and other classes are balanced.
Next we generate a set of 50,000 synthetic images for an AutoGAN instance pre-trained on CI- FAR10 (Gong et al. 2019), which has an Inception score of 8.525 and FID score of 12.41. We applied both one-sided mlxcsl Bures divergences to identify the two subspaces that max- imize the difference in RMS between fake and real images. Figure details the top-10 images in
7

---

Under review as a conference paper at ICLR 2021
each subspace and their realism scores R (Kynkäänniemi et al. 2019 Applying the max-sliced
Wasserstein-2 distance yielded almost the same solution as Fake (a linear correlation of 0.992).
B
Max-slicing Inception codes to illustrate the AutoGAN discrepancies. One-sided max- sliced Bures is used to identify two witness function (as linear subspaces of the Inception codes) that differentiate the real from fake samples. (Left: A,C) Images in subspace under-represented by fake WReal>-aake (Right: B,D) Images in subspace over-represented by fake WReal-<Fae- (Top: A,B) Real CIFARIO test images. (Bottom: C,D) Fake images. (C) Realism scores (median and range): 0.92 (0.84-1.03) (D) Realism scores (median and range): 0.68 (0.62-0.73)
Figure 3:
3.2 BASELINE COMPARISON ON COVARIATE SHIFT DETECTION
We compare the proposed max-sliced Bures distance and the resulting max-sliced Fréchet distance to the max-sliced W2 distance for linear witness functions. Figure@comaane the divergence estimates instances associated with simple of covariate shift with the MNIST data set. Notably, the precision of detecting class imbalances is higher for smaller samples using a kernel (Appendix (A8)
1P
13'
Campla sox
Sumple sww On
Sumple v0d In
Figure 4: Max-sliced distances applied to two samples from MNIST. The first sample fi is m images drawn uniformly from the training set, and the second sample e is n images from the test set where one digit is a minority class E fo. .0...... 9} with prevalence of 5%. (Left) Divergence estimates across sample size with I = 7. For m < 2000, gradient-based approaches for the max-sliced W2 distance fail to obtain the optimal slice as should upper bound the max-sliced Fréchet distance. (Center) Computation time. (Right) Each curve is the average precision @ 10 (averaged across the 10 classes). The one-sided max-sliced Bures yields the witness function (. = (w, :). which is applied to reliably identify the instances from f that are from the minority class for 1000.
3.3 COVARIATE SHIFT CORRECTION BY REWEIGHTING
We consider the task of reweighting the instances in one sample to minimize the max-sliced Bures distance. This optimization problem be expressed minlpeRs, EE m==1 J(V), where J(v) x
DE' (p, D). As shown in appendix A.7 this is a convex minimization problem with a simplex constraint We apply the Frank- Wolfe algorithm (Jaggi 2013) to iteratively adjust the weight of one instance at each iteration. The performance is quantified in terms of the Fréchet Inception distance between the real-test images of the class and the reweighted sample of fake images. For comparison, we also optimize reweightings that minimize the W2 distance and the max-sliced W2 distance (using 10 mini-batches of size n m = 100 at each iteration). The average FID distance across the classes is 49.15 for the max-sliced Bures reweighting compared to 68.1 1 and 72.5 for the mini-batch W2 and max- max-sliced W2. (See Table the Appendix for full results).
max-D
We also compute the realism scores of the entire of fake images using the of 10,000 images and 3-nearest neighhor distances. The Spearman rank correlation between the realism scores for the full set fake images and the witness function evaluations is -0.70 for Waat and it is 0.17 for Faae This means the realism has strong inverse correlation with Weell
and weak correlation for R Feee
8

---

Under review as a conference paper at ICLR 2021
Figure 5
shows results of reweighting uniform distributions to match target distributions using
either linear slices or random Fourier bases (Rahimi & Recht 2008) for approximating a Gaussian
kernel For the latter, using the max-sliced Bures loss achieves the lowest reweighted W2
distance, which is computed by solving a discrete transportation problem Flamary& & Courty 2017)
Loqu//nwweigtted
Uncar
Random Fourter Basos (2000)
Ow0
umD.1
Unner
C-
four Bases (2000)
Fow dlsed
Maunlgee
Feiestone (1-2991
Mivill oad In2 Liner
lou diod fund
Maiie sume los intie hures
Mare and We Unear
Vra cliid furn,
Hou dioed furre
Nav Bure
Mis di and nins oxb.
Man oicce lest mne owth
Hus al cod bunco TMD 2
Mar- of Bann nin un
Ioppu//wwwighteed Wi)
legulleeenigted
(1-2391
Varakaa Barns
15-330)
Tra baraaaaeee nlaned Yow saria
facerianive
Figure 5: Reweighting a uniform distribution to match various target distributions by minimizing the max-sliced W2 distance or the max-sliced Bures distance with either linear kernel ran- dom Fourier bases (d=2,000, a E 0.2)). Examples follow Kolouri et al. (2019) and uses ADAM Kingma & Ba 2015) defaults and learning of 10-2 A point's size is proportional to their weights after 100 iterations. Learning curves are the weighted W2 distance (log-scale).
3.4 DETECTING MODE DROPPING
We create 3-channel "Stacked MNIST" data set with 500,000 images from the MNIST training set to test mode dropping detection throughout GAN training (DCGAN architecture). The training set ji has 1000 possible modes corresponding to all 3-digit combinations. At the end of each training epoch (1000 iterations), a fake sample n 10a is generated. To verify mode coverage we use a 4-layer conv. net trained single-channel MNIST; any missing combination of 3-digit labels is considered a dropped mode. Figure 6 details using the proposed approach to detect missing modes.
Prece ergit Paodicas Dani
Pracrinnpu Mandl ond Booes
62
A
Epccta
B
Spocio
Figure 6: Detecting dropped modes using one-sided max-sliced Bures distance. The slice Faea used to identify the top- 10 real training images with the largest magnitude witness function values at each epoch. Precision @ 10 measures the fraction that correspond to dropped modes, compared to random selection. The curves are the mean (A) and median (B) across 100 GAN training trials.
4 CONCLUSION
We propose the max-sliced Bures distance, a lower-bound on the max-sliced W2 distance, which can be computed optimally with a tractable algorithm. We show increased performance with kemel- based witness functions for covariate shift detection and correction, and also highlight its utility in the linear case when the feature space is the internal representation of a pre-trained network. Importantly, the one-sided max-sliced Bures divergences enable direct interpretation of under- and over-represeentation between two samples, which can be used to identify systematic discrepancies.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Syed Mumtaz Ali and Samuel D Silvey, A general class of coefficients of divergence of one distri- bution from another. Journal of the Royal Statistical Society: Series (Methodological), 28(1): 131-142, 1966.
Theodore W Anderson. On the distribution of the two-sample Cramer-von Mises criterion. The Annals of Mathematical Statistics, pp. 1148-1159, 1962.
Anonymous. Distributional sliced- Wassersesnn and applications to generative modeling. In Sub- mitted to International Conference on Learning Representations, 2021a. URL https:// openreview. hwtp:/nee/eeeeee forum (
under review.
Anonymous. The Bures metric for taming mode collapse in generative adversarial networks. In Submitted to International Conference Learning Representations, 2021b. URL https://
under review.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning-Vain Voluuee 70, pp. 214 223, 2017.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, pp. 337-404, 1950.
Rajendra Bhatia, Tanvi Jain, and Yongdo Lim. On the Hanes-Wassersteiie distance between positive definite matrices. Expositiones Mathematicae, 15- 2019.
Austin J. Brockmeier, Tingting Mu, Sophia Ananiadou, and John Y. Goulermas. Quantifying the informativeness of similarity measurements. The Journal of Machine Learning Research, 18(1): 2592-2652, 2017.
Thomas R. Bromley, Marco Cianciaruso, Rosario Lo Franco, and Gerardo Adesso. Unifying ap- proach to the quantification of bipartite correlations by Bures distance. Journal of Physics A: Mathematical and Theoretical, 47(40):405302, 2014.
Donald Bures, An extension of Kakutani's theorem on infinite product measures to the tensor prod- of semifinite -**algebras. Transactions of the American Mathematical Society, pp. 199-212, 1969.
Hannes De Meulemeester. Joachim Schreurs. Michaël Fanuel, Bart De Moor, and Johan AK Suykens. The bures metric for taming mode collapse in generative adversarial networks. arXiv preprint arXiv:2006.00000 2020.
Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing. Generative modeling using the sliced W Wasserstein distance. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 3483-3491, 2018.
Ishan Deshpande, Yuan-Tie Ting Hu, Ruoyu Sun, Ayis Pyrros, Nasir Siddiqui, Sanmi Koyejo, Zhizhen Zhao, David Forsyth, and Alexander Schwing. Max-sliced Wasserstein distance and its use for GANs. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp- 10648-10656, 2019.
D. C. Dowson and B. V. Landau. The Fréchet distance between multivariate normal distributions. Journal of Multivariate Analysis, 12(3):450-455, 1982.
Rémi Flamary and Nicolas Courty. POT python optimal transport library, 2017. URL https: peyythoot..iitiiee
Maurice Fréchet. Sur la distance de deux lois de probabilité. C. R. Math. Acad. Sci, Paris. 244(6): 689-692, 1957.
Christopher Fuchs and Jeroen Van De Graaf. Cryptographic distinguishability measures for
quantun-mechanical states. Information Theory, IEEE Transactions on, 1216):1216-1227, 1999.
10

---

Under review as a conference paper at ICLR 2021
Kenji Fukumizu, Arthur Gretton, Gert R Lanckriet, Bernhard Schölkopf, and Bharath K Sriperum- budur. Kernel choice and classifiability for RKHS embeddings of probability distributions. In Advances in Neural Information Processing Systems, pp. 1750-1758, 2009.
Matthias Gelbrich. On a formula for the L2 Wasserstein metric between measures on Euclidean and Hilbert spaces. Mathematsccee Nachrichten, 147(1):185-003, 1990.
Xinyu Gong, Shiyu Chang, Yifan Jiang, and Zhangyang Wang. AutoGAN: Neural architecture
search for generative adversarial networks. In The IEEE International Conference on Computer Vision (ICCV), Oct 2019.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, pp. 2672-2680, 2014.
Arthur Gretton, Karsten M. Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel method for the two wwo-sample-pobleee In B. Schölkopf, J. Platt, and T. Hoffman (eds.), Advances Neural Information Processing Systems 19, pp. 513-520, MIT Press, Cambridge, MA, 2007.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of Wasserstein GANs. In Advances in Neural Information Processing Systems, pp. 5767-5777, 2017.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to local Nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626 6666-6637,40 2017.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Cor- recting sample selection bias by unlabeled data. In Advances in Neural Information Processing Systems, pp. 601-608, 2007.
Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, pp. 427-435, 2013.
Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach direct im- portance estimation. The Journal of Machine Learning Research, 10:1391-1445, 2009.
Diederík Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Soheil Kolouri, Gustavo K Rohde, and Heiko Hoffmann. Sliced Wasserstein distance for learn- ing Gaussian mixture models. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3427-3436, 2018
Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Generalized sliced Wasserstein distances. In Advances in Neural Information Processing Systems, pp. 261- 272, 2019.
Vladimir Koltchinskii and Dong Xia. Optimal estimation of low rank density matrices. The Journal of Machine Learning Research, 16:1757-1792, 2015.
Solomon Kullback and Richard Leibler. On information and sufficiency. The Annals of Mathe- matical Statistics, 22(1):79-88) 1951.
Tuomas Kynkäänniemi, Tero Karras, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Improved precision and recall metric for assessing generative models. In Advances in Neural Information Processing Systems, pp. 3927-3936, 2019.
Zinoviy Landsman. Minimization of the root of a quadratic functional under an affine equality constraint. Journal of Computational and Applied Mathematics, 216(():319-321 2008.
Chen- Yu Lee, Tanmay Batra, Mohammad Haris Baig, and Daniel Ulbricht. Sliced Wasserstein discrepancy for unsupervised domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 10285-10295, 2019.
11

---

Under review as a conference paper at ICLR 2021
Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos. MMD GAN: Towards deeper understanding of moment matching network. In Advances in Neural Information Processing Systems, pp. 2203-2213 2017.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning, pp. 3122-3130, 2018.
Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhard Scholkopf, and Klaus-Robert Mullers. Fisher discriminant analysis with kernels. In Neural Networks for Signal Processing IX: Proceed- ings of the 1999 IEEE Signal Processing Society Workshop, pp- 48. IEEE, 1999.
Youssef Mroueh, Tom Sercu, and Vaibhava Goel. McGan: Mean and covariance feature matching GAN. In International Conference on Machine Learning, pp. 2527-2535, 2017.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, pp. 429-442, 1997.
Boris Muzellec and Marco Cuturi. Generalizing point embeddings using the Wasserstein space el- liptical distributions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31, pp. 10237- 10248. Curran Associates, Inc., 2018.
Yurii Nesterov. Lectures Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization. In Advances in Neural Informa- tion Processing Systems, pp. 1089-1096, 2008.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11):5847-586 2010.
Michael A. Nielsen and Isaac I.. Chuang. Quantum Computation and Quantum Information. Cam- bridge University Press, 2000.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-GAN: Training generative neural sam- plers using variational divergence minimization. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp- 271-279. Curran Associates, Inc., 2016.
Jung Hun Oh, Maryam Pouryahya, Aditi Iyer, Aditya P Apte, Joseph O Deasy, and Allen Tannen- baum. A novel kernel Wasserstein distance on Gaussian measures: An application of identifying dental artifacts in head and neck computed tomography. Computers Biology and Medicine, pp- 103731, 2020.
Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset Shift Machine Learning. The MIT Press, 2009.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, pp. 1177-1184, 2008
Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume I: Contributions to the Theory of Statistics. The Regents of the University of California, 1961.
Kuniaki Saito, Kohei Watanabe, Yoshitaka Ushiku, and Tatsuya Harada. Maximum classifier dis- crepancy for unsupervised domain adaptation. In Proceedings of the IEEE Conference on Com- puter Vision and Pattern Recognition, pp. 3723-3732, 2018.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. In Advances in Neural Information Processing Systems, pp. 2234-2242, 2016.
12

---

Under review as a conference paper at ICLR 2021
Filippo Santambrogio. Optimal transport for applied mathematicians, Birkäuser, NY, 55(58-63):94, 2015.
Friedrich Schmid and Mark Trede. A distribution free test for the two sample problem for general alternatives. Computational Statistics & Data Analysis, 20(4))409 419, 1995.
Mark Schmidt. minFunc, 2012. Software available at http: httt:::/wwwww.. di ens. fr msshmmid/
SSoftwaremmi unc. html
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-
likelihood function. Journal of Statistical Planning and Inference, 90(2):27-2244, 2000.
Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert Lanckriet, and Bernhard Schölkopf. Injective Hilbert space embeddings of probability measures. In 21st Annual Con- ference on Learning Theory (COLT 2008), pp. 111 112-22.. Omnipress, 2008.
Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert RG Lanckriet. Hilbert space embeddings and metrics on probability measures. The Journal of Ma- chine Learning Research, 11:1517-1561, 2010.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 2818-28260 2016.
Armin Uhlmann. The transition probability in the state space of a -a-algebra. Reports on Mathemat- ical Physics, 9(2):273-277 1976.
Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer Science & Business Media, 2013.
Jiqing Wu, Zhiwu Huang, Dinesh Acharya, Wen Li, Janine Thoma, Danda Pani Paudel, and Lue Van Gool. Sliced Wasserstein generative models. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pp. 3713-3722, 2019.
Makoto Yamada, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, and Masashi Sugiyama. Rel- ative density-ratio estimation for robust distribution comparison. In Advances in Neural Informa- tion Processing Systems, pp.
2011.
Makoto Yamada, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, and Masashi Sugiyama. Rel- ative density-ratio estimation for robust distribution comparison. Neural Computation, 25(5):
1370, 2013.
Zhen Zhang, Mianzhi Wang, and Arye Nehorai. Optimal transport in reproducing kernel Hilbert spaces: theory and applications. IEEE Transactions on Patlern Analysis and Machine Intelli- gence, 42(7): 2020.
A APPENDIX
The appendix details the derivation of the proposed divergences, formal results relating them to existing divergences, algorithms, and additional experimental results.
A.1 DERIVATION OF THE MAX-SLICED KERNEL DIVERGENCES
wwl2 1, E H) denote the of rank-1 symmetric operators with bounded trace norm. Let d denote either the TV distance (d = drv) or the squared Bures distance (d d defined in equation 4 and equation respectively. In these cases, the expression of the max-sliced distance can be simplified as
Let Ui (w
max-d(px.Pr py))
sup d( (2 sup nell
(Ω, (r,
nell
sup sup 6((2, (x(2,xx)ss) (R. (R. WEHi||ullaS1 neth
8((w, pxw)m (ws, pxw)x)
13

---

Under review as a conference paper at ICLR 2021
where (,, (:))s:: us: (H H) x (H H.) - R denotes the inner-product defining the Filbeet-Schmile (Schatten-2 norm), (L, Hs us = (w 8 w. H) = (w, pw)),, and ö(p, q) = d(ps2, g92) denotes the distance between scaled versions of for E Rz0 and E Rz0- The equalities follow from the fact that 92p52 = (w @ w) p (w @ w) = (w: pw). The max-sliced TV distance and squared max-sliced Bures distance yield expressions for 5(p 9) that match the form of the underlying TV and Hellinger
divergences: drv (plt, 922) yields 8(p, q) = 1ppp- 1lp-gg: g). and dg (pl2, 992) yields ö(p, q) = (vP //>
mux-drv(px,py _ sup WES 2
(wo, pxw) (w, prw)l, and
(15)
max-da(px pr) - sup V (w, pxw) Vww, pr WES
(16)
where = {w H ||0||2 1}. The kernel-based divergences be expressed in terms of the witness functions since (w, ( = [@(X), ), w) (X), ].))] E [ (X)] and likewise for py.
The underlying divergences and distances are listed in Table 2
Relationship between scalar discrepancy 6, divergence D between continuous μ4, and discrete measures μ. v, operator dissimilarity d, max-sliced dissimilarity, and kernel max-sliced divergence for the TV and squared Bures divergences (squared Bures is twice the squared Hellinger).
Table 2:
TV
(Bures)²
8(p,4)
p ql
D(u,))
2 Eilu vil
E, (VTh -vi)²
D(,,V)
2 {xldu(xx) du(x))
Jx /du(x) vdvlx))
d(px,px)
pllxx -prlli
||xx + 11pxl111 2 211220
max-d(px.Py.
supwes (uw pxw) - prw))
supwes
(w)) v (w, prww)
max-D(p,v)
supwes
E 2 (X)] [ (Y)]
supwes
VE (X)]
/ (V)
Slicing is natural for the operator-based distances, as it inherent in their definition such that they coincide with the corresponding divergences between discrete probability laws (Fuchs & Van De Graaf 1999). The scalar discrepancy measure 8(,, -) can be accumulated across complete set of slices obtain the original distances. Consider
(or countably infinite sequence) of orthogonal S2 = wk & wx). Since these trace-norm operators O (Ω₁ = W1 @ W1 = We @ W2 w2,
operators are orthogonal and have unit trace-norm || - D41120 1,
d(px,py) N
Σ d(O,, (x),sx))ssll (2 pY) pY)s(.))
Σ
((s
= Σ (p))()),(()).
(17)
pr) To obtain the equality, one must optimize O over all possible sets of orthogonal trace-norm operators.
where pi( = (4,, px) and (O) = (Do, pY) ns.
A.1.1 MAX-SLICED TOTAL VARIATION DISTANCE
The sliced kernel total variation distance is
1 110(px pr) 1 11,0px - -x)00112 1(00pp--p)000 2 1(2 px 1|
drv (SV Spy ?.)
2
Maximizing over slices yields
1 sup ((2, px - px))= neth
sup (Ω, px - pr) geih
sup
||| 11 - ||-1 (18)
2
w:Ilwlla31
14

---

Under review as a conference paper at ICLR 2021
where the first equality follows from the fact that distance is maximized when ||2||1 yields the expression
1. This
maxx DDv (14, v) _ sup || - ||
(19)
w:|lw|||=1
Notably, the penultimate expression in equation 18 can be related the operator norm, sup (22, pX - -pr>) 5 DE(OEH=<:][Oliss) DEel
sup
(S2 PX py) llxx - py llo.
(20)
due the dual norm definition. Since px Py is symmetric, the equality is achieved. Thus, max- max-DDy (1, lllxx loo. For linear kernel, this can be computed by finding the largest magnitude eigenvalue of px PY Ex- [XX] Ey (YY Rdddd
A.1.2 MAX-SLICED BURES DISTANCE
The sliced version of the Bures distance is
(, Ppr / /10px + [[ -11(((xx1x))) (Spr Il:: which can be simplified since [|Ωxx0t11 tr((w @ w) @ w)) = (wi (xw) قا [klll [e and (2) (1) ((w,px)) (w, | = V 11113111111111
[wllaa || [[ Using these expressions, the max-sliced Bures distance is
sup (px = sup
|| || + || - 2||
f 1wwl
nal
WEHt:|ull251
The expression is monotonic with the norm wf yielding
V(Iwlla - [|W]|o)2
max- (H, A sup WEH:||WllaS1
sup wEH:1Wulla51
||w/|| [Wlll||
(21)
sup WEH:||
A.1.3 MAX-SLICED GAUSS- WASSS-ASSSSSNNNN DISTANCES
Two mlx-sliced versions of the Gauss- Wasserstein or Fréchet distance in the RKHS are max1- (p, v) sup satth
VIl0(mx - my (0EX0,0000)
11wl22/ (mx- - w)2 ( (V(w,, Exw) v (w, 2yww
sup WEH:||u|laS1
V (mx (mx + (v (w, Exw) v (w., Erws
sup WEHt:|ullaS1
sup WEH:
(wx))(w(X)) Eyyolu(Y))) + (ow(x)
aw(r))? (22)
where Ow(X) / (X)
is the standard deviation of w(X), and ow(Y) =
V[[(w(Y)- (mY,,))) and
max (1, = sup [|[mmx my) + sup (10 sweth
Sech
(M
(aw(X)-ow o
sup WEHt|W|laSS
MMD +
(23)
Notably, max (1,, v) is the supremum of the Fréchet distance all witness functions.
15

---

Under review as a conference paper at ICLR 2021
1.1.4 MAX-SLICED KERNEL WASSERSTEIN
A sliced version of the kernel Wasserstein distance between jr and relies on the the sliced distance (x, Y) = [ 8 w) (x(X) - ((Y))l2 - ((X) (2W222
(w>, ((x) (Y))l//))2 = o())) (w, MY)llll = (x(() w ||m|||
This distance is monotonic with the norm of w and convex with respect to w. The max-sliced kernel Wasserstein-p distance, p 2 1, is
max-W p v),
sup inf
E L(x,t)m
WEHil|lllas1 rET(u,))
sup inf W TEl(ar) [(x,y)a
R
(x(X) - w())
(24)
which is a one-dimensional optimal transport problem. Let wy and way v denote the pushforward measures, then the divergence can be written as
max- max-W p (1, v)=
inf = (elggreg
sup
S - TTPP (8.T)~m
(25)
where o[ pl, w) is the set of all joint distributions coupling the pushforward measures.
Assuming the measures are absolutely continuous and adopting the notation from Santambro - dwzz w*)u((-o0, w)) and (w,
gio (015 let (w))
I_x du
Wy'h( 1/( (- oc, w)) denote the cumulative distribution functions of the pushforward measures with pseudo-inverses Fir (4) inf E R Fas, (s.u(r) (wr) q} and (g) = inf E TR (w, 2 9)-
As shown in Lemma 2.8 (Santambrogio) 2015), then the optimal transport plan x² has cumulative distribution Gw(ux wy) .min Fu xx)) Pu.. (www(wy) and the divergence
J (F (2) dg sup
max- W W. (H, v) (1. p
(26)
WeH:l|=laa
and for the case p- (aattabroogio
2015 Proposition 2.17).
/ (w) (w)) dw.
max- WiT (p,
sup
(27)
WE WeHillollas
The objective in the last quantity is an Loomo version of the Cramér-von Mises criterion (Schmid & Trede 1995| Anderson 1962). That is, the max-sliced kernel Wasserstein-1 distance is equivalent to max-sliced L Lorm version of the Cramér-von Mises criterion, where the slicing corresponds to function in the RKHS that witnesses the largest discrepancies between the measures. The choice of p = simplifies, yielding the following optimization problem
(CE E [x²(X)+ + + 2w X (u((M))
sup inf max- W (1,, v)= = WeH: TEI(HIN) (x)Y))
$/
sup dEH:1W|laS1
[|ml|/ + 11wl12 - sup
E
1w (x)(
(28)
TEl(UN)) (X,Y)ay
[|]]2 + 1|wl1? -2 2f (o) (o
sup WEHiiWllasT
(29)
A.2 RELATIONSHIP BETWEEN THE KERNEL-BASS BASED MAX-SLICED DIVERGENCES
The Bures distance can be used to lower bound the TV distance, (ex py) S Ilex -pyll = 2drv (px, Py) (Fuchs& & Van De Graaf 1999). This inequality stems from the inequality between the squared Hellinger and total variation distances for discrete probability laws. E, v < E,lr, qul. where the inequality holds for each summand, Iyp: / < Iyp, / pt +
v/ai) = 1pc 4:l- This inequality holds for the max-sliced divergences stated in Theorem
16

---

We now consider the relationship between the Gauss- Wasserstein or Fréchet distance which com- bines the distances between the first and second-ords -odeer moments- with the max-sliced Bures when is applied directly to the uncentered covariance matrices. For this we need the following lemma. Under review as a conference paper at ICLR 2021
|| I || | where the inequality is consequence of the inequality between the arithmetic and geometric means, let || and || then (vā- vv]² I Iv vbl(vä vb) = la b/. Taking the supremum over E H. with the (max-Dyyvv
Proof of Theorem | (||W|
constraint ||0||| I 1 yields the desired the result (max-D) (u,,
Lemma 4 (Reverse triangle inequality). For two vectors in R2, the difference between their Eu- clidean norms is less than or equal to the Euclidean norm of their differences. For a, c, d E R. VV +
Ve d S
V (a c)² + (b- d)3.
Proof. Lete Lete= (v e= -=
VC and f (a - c)² (b- (b-d)2.
= - o2d
<d++++C+6-2 000 by the arithmetic and geometric mean inequality
= = (2++2++0-21000
= aa 2d+ V
2(ac bd) = (a c)² + (b d)² = f. Taking the square root each side yields the inequality ve S vT.
12
Proof of Theorem 2 To relate the sliced Bures and Gauss Wasse-Waserrntein distances, we note that |wll = (px,w w & w) = (Ex + mx & mx, w @ w) HS oxx) + (mxx w/² and likewise for k Then,
(mmx, w) + oz obxxx= - / /mmr, w/2 o² owir)
(imx- - wy, + (ow(X) - ow(r))
(30)
where the inequality relies on Lemma 4 with (mx, w), b Jw(X), (my, w), and d (Y)Y). Taking supremum over slices yields the desired inequality.
Theorem 2 shows that the max-sliced kernel Bures distance is lower-bound on the max-sliced kernel W distance, since the latter is lower bounded by the max-sliced kernel Gauss- Wasserstein distance.
Proof of Theorem 3 Let Let X) = (mx, w) + (XX) and w(Y) = (my, w) + +Y). where ((X) (x(X) mx w) and wYY) = (o(Y) wy are zero mean, and E. [a²(X))
(xx) and
E 100 (Y) = - The squared Fréchet distance between random variables w (XX and (YY is
(E [[ (Y))) + (ow(x) - 2 (mx - m) (aw - ow(r))
- = (mx + + (my, w/ 2 + - ((mx +
=E E
[ (
By Hölder's inequality,
S - -
Consequently,
(31)
s E - (
E - ((x (
(32)
17

---

Under review as a conference paper at ICLR 2021
Taking the infimum over all possible joint distributions (X, 7y that are within the coupling distribution y E [ yields the sliced Wasserstein-2 distance on the right hand side. Maximizing over slices, yields maxy-Daa -D (H, v) I max-W? (H, v/) and combining with Theorem 2 yields the desired result.
A.3 RELATIONSHIP TO OTHER DIVERGENCES
Finally, we note that the terms in the max-sliced Gauss- Wasserstein divergences are related kernel Fischer discriminant analysis (KFDA) (Mika et al. 1999). KFDA objective is based on the ratio of the difference in means the pooled variances:
(w, mxx my) D'i (w, v) = sup
(w) m my
sup
(33)
(((x) + o ((()
(w, [E + Σy )om
KFDA seeks witness function which has widely separated means for the two measures, and mini- mal variance.
A.4 COMPUTING THE MAX-SLICED KERNEL DIVERGENCES
We assume the witness functior
H is of the form E o:0(2z) with w(+)
Ent" ack((;2)) 2)) where 2, = Tze
1 i S m and a E R tm In this case,
m < i < + m
|w| = (w 8 (6 x1)) =
Uylw @ w, o 0
Σ
My Hglw, x(2)))
=
==1
j=1
0,0(2))
Σ Mí
Σ an)(
(M, (K (Kxza)
a K Xxz K xxza = |D Kx x
where x(zi, Kij, K = Kxx,
Kxz
(-) denotes the elementwise squaring of
Kyx: Kyy
Kyz
a matrix/vector, and Dv = diag(v v) denotes a diagonal matrix whose diagonal entries are the vector
v. Similarly, ||0|3 = (v, (Kyza)²) 20 = Ky
In order for the constraint || < 1 = a Ka S 1 to ensure bounded solution, we assume K is strictly positive definite. For this purpose, we add small value its diagonal K + 10 when necessary in the optimization procedures. For computational purposes when m or n are large, subset (possibly random) of landmark points of size 1 < + function w Ei= a; where (Ta)L= {I,..., m n). In this case, Kxz E gmxx and Kyz E Raxt with [Kxz|,, (((,,27,) and [Kyzi.j k(ys, 2r,). In this case, the constraint also needs to be adjusted.
be used form the witness
A.4.1 MAX-SLICED KERNEL TV DISTANCE
Using these expressions, the max-sliced kernel TV distance is
(A, a:a Kasi
1 2
D k
DD
(34)
max Ka 2
a (KxzD,Kxz - DyKzjaa)
(35)
The solution is the generalized eigenvector corresponding to the largest magnitude eigenvalue of the generalized eigenvalue problem Av XKv, where A KxzD, KyzD,Kyz. a = arg max, Ka
Aa
The witness function is (-())= Σm m+n a7K(;2).
"Similar to kernel PCA, the constraint ||w||| allows the of the representer theorem for the RKHS.
18

---

Under review as a conference paper at ICLR 2021
A.4.2
KERNEL BURES DISTANCE
The sample-based max-sliced kernel Bures distance is
max-D (i,, D)
D [D
(36)
0.00 Kaši
maX xE(-1,+1) aa Kagi
max
D Dakxza 2yāKyz
(37)
The last expression shows that the max-sliced Bures distance can be expressed as a bilevel optimiza- tion problem, where the inner optimization moblem-which we refer one-sided max-sliced Bures divergence is a difference of convex functions:
{
h(a) - olao)
max-D (A, D) max
min a.a Kaş1
g(a)
-((a))
min a. Kas1
(38)
g(a) | Dy
(39)
h(a) x
(40)
Without loss of generality, we will consider the first case (s 1).
min Ka51
g(a) h((x). (P)
Inspired by the approach Landsman (2008). we relate this problem to quadratic program, specifi- cally, the quadratically constrained quadratic program
min a:a Kas1
cag²(a) - (a) min a:a Kasi
a T
(Q).
for c1, E R2n- The solution of which can be obtained as in the max-sliced kernel TV distance by solving generalized eigenvalue problem. For (P), the Lagrangian function
L(a; A) g(a) h((a) A(x2 Ka 1).
(41)
Let g = fa: g(a)) > 0, h(a)) > 0} denote the set of points where g and h are differentiable. Then for and K positive definite, L(a,, A) is differentiable, and
Val(a, = Vag(a) - Vah(a) - 2AKa = 29(a) Vag Vag
Vali(a) - 2AKa,
2h(a)
where the equality follows from (a) 2g(a) voo)aac Vag(a) and likewise Vali(a)) 2h(a)vah(a)) For (Q), the Lagrangian function and its gradient are
X(x Ka 1)) Val(a, ei Va) 02 vali - 21Ka.
M( A) cag c2))(a)
(42)
(43)
1 and C2 2M then VaL(a, Va If c1 2g(a)
Let a² denote a global optimum of (Q). If 23(a* and 02 " then VaL(a, A)la=a Vai(a, A) Consequently, ax is local optimum of (P). By the Karush Karush-Kuhn- ditions, it is a necessary condition for all optima of (P) in g to have this form. Thus, any global optimum of (P) that lies corresponds to a global optimum of (Q) for particular values of Ct 02. 02,02.
con-
The family of solutions to (Q) that includes all local optima of (P) in is
C2
= arg max a:a Kagl
-
=
(0, 1].
(44)
where the bounds are due to the non-negative functions and (a > g²(
2ez
< 1. Notably, 7 = - c 02 corresponds to the one-sided max-sliced TV. The global optimum of (P) within G is necessarily within {a:;) (a:))e((0,)) and can be found as the solution to the bound scalar optimization problem min 9(x;,) h(ox))
201 - Ci 02
A remaining case for a global optimum a non-differentiable point a* & G. specif- ically, g(a²) (the case of h((x)) is trivial), which corresponds to a'
19

---

Under review as a conference paper at ICLR 2021
2y In this case, the generalized eigenvalue problem must be restricted the nullspace 0g arg Nell
Kaş1 (a).. Let V (m denote ma- trix of p orthonormal columns that spans the nullspace, then a VB", where 3r
arg ma v kvØŞı X V Overall, the one-sided max-sliced kemnel Bures dis- tance can be computed using a combination of line search for E (0, 1] and checking the solution in the nullspace as described in Algorithm
Algorithm 1: One-sided max-sliced kernel Bures divergence
Input:
(1r,, (1)) (.) S {1,m + n)
Tj i m,
12
Vi-m i ++lsis m + f
DiKxz x [Vuin( 2Tz )] ==1
|r|
D Kyz = (VusA(Ui 2r, |
A xxzDuKxz
B KýzDuKy
K [K(ET 2xz ) j=1
ls|
a COUSSIDDNNNNSLIICEEEEEEEEEEEED
B, K)
wp)s(==: :2 + En a ((2
Output: WasR
ONSSUDEDMANSLIICOOAANEEEEE (A,B,K) Ory : 7 + arg max Ta KasI a (7A B)a
y" = arg maxo< a AC,
a Ba,
ag arg max QENullBB:a KaS!
α Aa
TKa
if 2 Aag
a Aa,
v J,,,Ba, then
a' = 0g
else
a' a.,*
end
10
return ax*
A.4.3 MAX-SLICED KERNEL WASSERSTEIN
The empirical version of max-sliced kernel Wasserstein divergence be expressed in terms of either equation 24 or equation 26
max- W ((,
min PEPP
Σ
Pas (u(x))) w(i))
(45)
WE WEHiIW
Lo (F - (2
max
(46)
where PR.e = (P E m0 Pl, u. 1m = 2} is a transportation polytope. The empirical distribution functions are (w, T M4 wwe and (w) Σi= Mi ww with in- verses F. (g) minfw(x;), i (1...., m) Fu,a (wxx)) 2 /) and F
min(w(y.), nI....,n). Fu, (w))(w())) q). For fixed w, the optimal transport plan P is based on the sorted values ((((1)) S (I((2) < ... I (())) and w(M())) S ((M(2)) < ... < w(M())) Denote the sorted values as vectors w'x and why with [wxc] = w((()) and Wyy = w (((e)) and denote by çi and ú the corresponding permuted versions of μ and
20

---

Under review as a conference paper at ICLR 2021
In the case of equal samples sizes of uniform measure, n and μ 2 Im and n I, elements in PR.e D scaled elements in the Birkhoff polytope (the set of doubly stochas- tic matrices), and the solution the linear program is permutation and max-W; (f.
sU [E (=(((())) (v(()) = ||wóx - wóylle) where 11-1pp denotes the fp norm m dimensions. As in the continuous case, the discrete transport plan between the sorted measures has the cumulative distribution G E [o, 1jmxn with G. = min (Ei= lkx Σx=1 v }- The optimal transport plan between the sorted measures is given by taking the first difference over both rows and columns of G, f11 G1,1 Pi, G₁,- GLJ-1. Pa.1 G., G and P.,- = P., - Pi-1s - Pis-1. Using the sorted witness function evaluations the distance can be written
m.n
max- W (p,
max
Σ
As (w(()))))
(47)
WE WEH:||allaS1
i=1j==
We now turn our attention to the optimization of the function w parametrized in terms of a, w(+) Ems a,)(: For arbitrary sample sizes with p 2, the max-sliced kernel W2 distance is
max- max-W? W2 (),
max
[1w122 + 1w 2 max (P (P,wxwF)
(48)
WEHi||ullaS1
PEPp.o
with unsorted values wx- = [w(x)), w(mm)] K Kxza and wy (wy)). w..,,,,,))))) (w,))
Kyza.
The max-sliced kernel W2 distance can expressed terms of equation 45 or equation 48
[max-W9 WTa (2, ()],
max a:a Kaši PEPA.
min
Pg
(n(x,, 2m) k(y;- 2x)) )0x
i=ij=1
aa K D
T KKy Ky,za
max
0:0 Kas1
max a K xz XKyza PEP
min a 2'Qpa= max minpePa. a Qpa
(49)
a: Ka P
Ka
where QP - - = x D,Ky2 PKyz K. K is symmetric matrix positive semidefinite matrix. (This can be seen since the objective is greater than or equal to zero for all choices of a.) For fixed P. equation 49 is convex maximization, that can be solved as a generalized eigenvalue problem. For fixed a, the optimization in terms of P is linear program with the solution detailed above. However, when maximizing with respect a, is a matrix-valued function of a. To find local maximum for a we use the unconstrained optimization equation (49 and perform gradient ascent with respect to a, wherein each iteration we compute the optimal transport plan. This approach is also used in computing the generalized max-sliced Wasserstein distance Kolouri et al. (011)).
A.5 COMPUTING THE MAX- SLICED DIVERGENCES FOR THE LINEAR CASE
The linear case follows from the kernel case with some further simplification. The objec- tives of the one-sided max-sliced Bures divergences are each a difference of convex functions, whose stationary points are maximum eigenvalue problems, and correspond to reweighted ver- sions of the one-sided max-sliced TV divergence. Assuming the covariance matrices are strictly
positive definite max-D5 (f,, = maxusy<1 V W. PxW, V / Py Py where Wy =
arg max | w TTppx pr)w for the one-sided case. If the matrices are singular, then cases where w is in the nullspace must be checked. Without loss of generality, the algorithm to obtain the optimal slice for the one-sided max-sliced Bures divergence described in Algorithm 2
21

---

Under review as a conference paper at ICLR 2021
Algorithm 2: One-sided max-sliced Bures divergence
Input: Px, PY E Rdddd
Wy 17:77 ++ arg max maxw:||wllas w:||w]|aS11 w (xpxx py) jw
7" = arg max0 W. px V W Py
if (prn = d then
WHzV Wy
else
V
arg max
W Pxw
WeNull (py) ::lllllss
PXV2
W PxW,,
W. W...Pyy. w. then
W WAVV =
else
10
NOv Wy
end
12 end
Output: WaSe
As an alternative to Algorithm 2 first-order algorithms can be applied, nevertheless, obtaining global optimal cannot be guaranteed easily in this case. To make the objective differentiable, the square root, which is non-differentiable at should be smoothed V v. e² (e.g., e² 0.01).
A.6 SAMPLE-BASED MAX-SLICED BURES DISTANCE IS A RELAXATION OF THE MAX-SLICED WASSERSTEIN-2 DISTANCE
We show that the max-sliced Bures distance is relaxation of the max-sliced W2 distance. Let p ZZ with Z dx denote a strictly positive definite matrix, such that v pw > 0, pw Vw ZZ w ma (0, w). where H" = arg maxpesp-1 (8, w)
zz w. Using this form, when px and py are non-singular, the one-sided sliced Bures can be expressed as
max (01, PPW)) 8. E84-1
max (62, P) 8.
max (0g. DEX w) E8
max (04. D Y w), 6.E8
since px XD ) and py YDÉ Squaring this quantity and taking the square root yields the objective of the max-sliced Bures distance in a similar form to the max-sliced W2 distance,
max- D (0,
max w|l
w T(x + + ww 2 max w TXXQY w, Qe@a.
(50)
where 2j = (D) Rmxn ||01| S 13. This holds since
max w ODD e:
8m BB (0z. DAXT D w)
(51)
w p W pyw.
(52)
A.7 COVARIATE SHIFT CORRECTION ALGORITHMS
For covariate shift correction the goal is to minimize the divergence by adjusting the weights of the instances in one sample Đ. This results in the following convex optimization problem:
min
J(V),
(53)
PER - 1111
22

---

Under review as a conference paper at ICLR 2021
where
J(v) (max)
J(v a)
max Kasl
max a:a Kas1
(M, (Kxza) +(U (Ky (Kyza) - -2 (Kxza)33(x,, (Kyza)
(Ky
Ca
ka
Co + (U, - 2/ 2 V Kas1
max
For fixed a the function J(,, a) is sum of linear function and convex function f(-) = - convex since V is concave. J(V) max Kag1 [v, a)) is convex since maximizing over or preserves convexity (Nesterov 2018 Theorem 3.1.8).
In the linear kernel case, the cost is
(VV) (max-D (A, (1)
j(v.w)= (V.))=(Va((XTWe0 (e, (YT (TTw))2)
max w: w
max ((1, (X w) + (M,, (Y )) ( -2 (M, (XT ( (Y w))2).
(YTw)o2).
willwilaS1
Again, J(z) is convex since J(,, w) is convex for fixed In this case, the gradient has the intuitive form of
| VoJ(w)= = (1 11- |wll
v (u, (X We )o) (v, Y (YTw,) )o2)
(woT)o²=
(YT wo)
(54)
To solve this convex minimization over probability simplex we apply the Frank- Wolfe (conditional gradient) algorithm Jaggi (2013) to iteratively adjust the weight of one instance v +- (1 - + where e₁ is an indicator vector, i = arg min [v)]( and E [0, 1] is the stepsize. A benefit of the Frank-Wold scheme is that it requires only rank-1 updates of YD, YT, which needed for updating w.
A.8 ADDITIONAL EXPERIMENTAL RESULTS
We start by comparing the proposed max-sliced Bures distance the max-sliced W2 distance for two-dimensional data. We compare the fixed-point algorithm for solving each one-sided
max-sliced Bures divergence with gradient-based approaches for the max-sliced W2 distance us- ing ADAM with parameters ir 1e-3, betal 0,9, beta2 0. 09999, epsilon 1e-08, capping the number of iterations at 1000 or until the change the slice is minimal |ww Wotallao 1
In two-dimensions, a near optimal slice can be obtained by a fine grid search the sliced Bures and sliced W2 distance as shown in Figure foo two zero-mean Gaussian distributions. Figure g shows the cases for success rate of the gradient-based optimizations across 10 trials at varying sample sizes for 2- and 1000-dimensional zero-mean Gaussians. The effect of the number of gradient iterations reported in Figure 9
For kernel-based divergences, maximum mean discrepancy (MMD) detects differences in the first moments of the distributions in the RKHS. Using uncentered second-moments, the kernel-based max-sliced Bures distance (MSB) may detect some the same differences. Figure TO details wit- ness function evaluations of each for six data sets generated from wooddimensional distributions, where a Gaussian kernel function is used. Notably, the one-sided MSB divergences correspond to localized regions, which are not distributed outliers. This is beneficial for the 'precision' of the witness function, but the 'recall' of MMD is better. This benefit of this localization depends on the task.
A.9 COVARIATE SHIFT DETECTION WITH MAX-SLICED KERNEL DIVERGENCES
We proceed to generalize the comparisons in Figure on imbalanced samples on MNIST to the kernel case. We Gaussian kernel Kg with the parameter the median Fuclidean distance
23

---

Under review as a conference paper at ICLR 2021
Divergence between 2D Goussians with snown covariance
Estimated divergence between 2D Gaussians (m-n- 100)
Wassersien
Wassersten
10
Baros
0.3
0.3
sided loed BurestY)3
max-slicd Bures (4D444))
0.2
0.2
0.1
0.1
0.5
angle (racians) dofninn site
angle (radians) dotining siice
Gaussians (m=n=100)
divergence between 2D Goussiane (m-en 1000)
Estimated divergenze between Gaueslans (m-n- 10000)
0.5
Slood Wasserster
Slood Wasparztin
0.4
glood Buros
0.4
@lood Bunos
maa-- ilad Wasee steen (ADAM)
man- cnd Wasseetten- (ADAN))
0.3
maas slced Eurs
0.3
man-- ind Euro
maxd lced Bume (AM40
0.2
0.2
0.1
0.1
0 0.5
1.5
2
2.5
0
0.5
1.5
2.5
(racians)
(radians)
Figure 7: Sliced and max-sliced Bures and Wasserstein-2 distances compared population statistics and samples of varying sizes. l = (O, C) and v = (O, I), where = ZZ T_ and Z E R2x2 with entries that originally standard normals and then row normalized such that C is a correlation matrix. In the population case and for zero-mean Gaussians, the Bures distance is equivalent to the W2 distance (Gelbrich) 1990). In the sample case, it is lower bound. At both m 100 and m 10 the gradient optimization of the max-sliced W2 distance fails to obtain the global optimal slice (instead obtaining local optimum).
Success rate (wein 1% of exxex)
aliced Wasserstain JADAMI
max Bures
0.8
mac-sloadd Bures (ACAM)
0.8
0.8
6.6
0.1d
0.4
0.20
Wassersiem (ADMM) slicdd Buros
(ADAM 99% Surea
Rowee
10
12
18
14
15
log (sample size)
log lsampe size)
Figure 8: Success rate of finding optimal slices for the max-sliced Bures and W2 distances across samples of varying sizes (10 random runs per size). The distributions are zero-mean Gaussians, with a = = C) and // (0, I), where C = ZZ" and E ddxd with entries that are originally standard normals and then of d = 2, success is obtained for a distance within 1 1% of the value obtained by fine-grid search of angles. In this case, the gradient approach for the max-sliced Bures fails more often than the max-sliced W2. (Right) For d = 1000 the eigenvalue-based approach (Algorithm A.5) defines the global optimum. In the larger dimension, the gradient approach for the max-sliced Bures (ADAM) succeeds in almost all of the cases, within 1% of the optimal value obtained by Algorithm A.5 (MSB), whereas the max- mliced W2 distance fails to upper bound the mlxesliced Bures on roughly half the trials.
normalized such that C is a correlation matrix. (Left) In the case
24

---

Under review as a conference paper at ICLR 2021
Figure 9: Performance of gradient algorithms for max-sliced Bures and max-sliced W2 distances across 1000 dimensional samples varying sizes (10 random runs per size) and number of iterations in ADAM (Left to right: 50, 100, 200, 500. 1000). The samples are from zero-mean Gaussians distributions, with μ = (O, C) and v = (0 I), where
ZZ and E Rddd with entries that originally standard normals and then row normalized such that C a correlation matrix. (Top) For the max-sliced W2 a successful run is obtained when it is greater than or equal to the optimal solution to the max-sliced Bures (blue solid line) when it is greater than 95% of max-sliced Bures (red dotted with circles). For the gradient approach to max-sliced Bures, success when the difference the optimal is 5% of the optimal (yellow solid with diamonds). (Bottom) Divergence values obtained across the 10 trials with increasing sample size.
MMD
MSB
MMD
MSB
MMD
MSB
MMD
MSB
MMD
MSB
MMD
MSB
Figure 10: Maximum mean discrepancy (MMD) and max-sliced Bures distance (MSB) applied to two-dimensional samples using a Gaussian kernel. For each data set (shown as a two-by-two subplot), the contour plots indicate the squared magnitude of the witness function evaluations. For MMD, positive witness function values are plotted in the top row and negative evaluations are the second row, For MSB, the rows correspond to the two one-sided divergences. The witness functions for the one-sided MSB divergences correspond to localized regions.
25

---

Under review as a conference paper at ICLR 2021
in the pooled sample. To ease computation for sangle sizes, we let r be random subset of the pooled samples {2, )= U U(y))= of size = min (500, m +.). , In this case, the max-sliced Fréchet refers to maxx--D2 D2 which is equal to the square root of the sum of square of MMD and the square of the max-sliced Bures using centered kernels, in equation 23 The kernel-based max-sliced W2 distance should be an upper bound of the max-sliced Fréchet. However, in practice the optimal slice (witness function) may not be obtained.
the larnd NZ me abodd laand CNN
UN
END lar Blon
Coree wewe..soonnnee
Precsionato
0.00
O
(oo?? seees
0.
0.06
0.
0.06
Sample strw (1- m5)
Sumple stow
Sumple sinw (n-
Figure 11: Kernel-based max-sliced distances are applied to balanced and imbalanced samples from MNIST. The first sample ğ consists of the training set (balanced classes with size m), and the second sample is a n-sized sample from the test set with a minority class I {0. ..... 77 with prevalance of 5%. (Left) Divergence estimates for increasing sample size for I = 7. Notably, for m < 2000 the max-sliced Wasserstein-2 distance fails to obtain the optimal slice as it should upper bound the max-sliced kernel Gauss- Wasserstein (Fréchet) distance. (Center) Corresponding computation time. (Right) Each curve is the average precision @ 10 (averaged across the 10 classes). The witness function for the one-sided max-sliced Bures waso can be used to reliably identify instances from ğ associated to the missing class.
We now compare the proposed kernel-based max-sliced divergences to existing baselines. A primary baseline for this task is to train a logistic regression model with kernel basis functions to distinguish the two samples, and then use the probability estimates of the instances as the witness function evaluations w(x)= = Pr( Ho = x) = 1- Pr(H, = z). where Hu : X ~ D and H1 X ~ f. As additional baselines we also tested three methods for importance reweighting and density ratio estimation: kernel mean matching (KMM) (Huang et al.) 2007). least-squares importance estima- tion (ul.SIF) (Kanamori et al., 2009), and relative density-ratio estimation (RuL.SIF) (Yamada et al.) 2011}. but all methods were outperformed by logistic regression with kernel bases. We also com- pare with kernel Fischer discriminant analysis (KFDA) (Mika et al. 1999), and the linear cases of max-sliced Wasserstein-2 distance, its first moment approximation, max-sliced Bures, and logistic regression. For all kernel methods, a Gaussian kernel Rig is used with the parameter o set as the median Euclidean distance in the pooled sample.
Using the MNIST data set again, we test three scenarios of covariate shift. For each, one sample has mismatched probability for one class I E {0. ......... 9) and the other sample has balanced sample: (Scenario 1) ja is balanced and is missing 1; (Scenario 2) fa is imbalanced with only appearing in 2% of the cases, compared to 10.8% for the other classes and balanced and e consists of only images from l. In each case, á is a sample of 500 images from the training set and covariate shift detection is to use the pee--under-the-cume (ROC), where positive instances correspond class 1. For some methods, the witness function (or its magnitude) may be ambiguous in sign, i.e., the values may be high (or large) for either the under- or over-sampled instances (namely, max-sliced W2). To be generous, on each run we choose the ordering with the highest AUC. The results are reported in Table 3
balanced; (Scenario 3) f is
sample of 500 images from the test set. threshold-free way to assess (AUC) of the receiver operator curve
The other baselines KMM, uLSIF, and RuLSIF are not shown (their AUC scores across the scenarios are worse than the logistic regression with kernel baseline). In separate set of runs we also compute the realism scores (Kynkääännemmi et al. 2019) with A = 3 where D is considered the real set, and f are synthetic, to prioritize instances; results for the three scenarios are 0.75 0.67+0.12, and 0.94+0.04, which is better than linear logistic regression and KFDA, but far worse than the kernel logistic regression baseline.
26

---

Under review as a conference paper at ICLR 2021
Table 3: Unsupervised covariate shift outlier detection MNIST. The goal is identify instances associated with an over- or underrepresented class / E {O..... 9}. Values are AUC where positives are instances from class I. We report the mean and standard deviation and the number of times each method has the highest AUC (including ties) across 100 trials (10 for each case E (0,...9)))
(Scenario 1)
(Scenario 2)
(Scenario 3)
(l)
(2)
(3)
logistic regression-linear
0.60 (0.05)
0.60 (0.08)
0.91 (0.06)
Max-Sliced Bures
0.89 (0.12)
0.86 (0.13)
0.95 (0.03)
2
Max-Sliced W2 (approx.)
0.86 (0.10)
0.84 (0.13)
0.96 (0.02)
1
2
0
Max Max-Sliced W22
0.87 (0.14)
0,85 (0.14)
0.96 (0.02)
2
12
0
logistic regression-keman
0.90 (0.07)
0,86 (0.10)
0.99 (0.01)
10
15
KFDA
0.58 (0.03)
0.61 (0.12)
0.91 (0.03)
0
MMD
0.87 (0.10)
0.85 (0.12)
0.97 (0.02)
1
0
Max-Slicek Kernel TV
0.85 (0.10)
0.83 (0.14)
0.96 (0.03)
2
0
Max-Sliced Kerne Bures
0.92 (0.11)
0.88 (0.14)
0.97 (0.02)
21
32
Max-Sliced Kernel W2
0.92 (0.11)
0.88 (0.13)
0.97 (0.02)
61
35
A.10 COVARIATE SHIFT CORRECTION FOR CLASS-CONDITIONS SUBSAMPLING
Figure 12 shows 20 synthetic images generated by AutoGAN trained on CIFARIO (n=50,000) with the largest weights after reweighting in order to minimize the max-sliced Bures distance to the subset of training images for each class separately (m=5,000). Computing the max-sliced Bures distance with the entire training set of 50,000 points is tractable since it does not depend on the sample size. The realism scores of the selected images have a median and range of 0.96 (0.63- 1.34). Figure 13 shows the same but based on the weights optimized by using the W2 distance with the mini-batch optimization as the cost function. The realism scores of the selected images have a median and range of 1.1 (0.93-1.22) 1.29. Figure shows the same but based the weights optimized by using the max-sliced W2 distance with the mini-batch optimization. The realism scores of the selected images have median and range of 0.97 (0.65-1.25). Finally, Figure shows the synthetic images selected for having the highest realism scores; notably this set lacks class correspondence.
The optimizations in the first three cases use the Frank-Wolfe algorithm (Jaggi 2013) with sim- plex constraints. The default step-size schedule = E+2 2 and the same stopping criterion is used
maxigisnl1> (x(40) - < 10-3, where k is the iteration index. This yields roughly the same number of iterations for each method. The optimization starts from a uniform weighting, which means the weights for only 2000 instances are actually individually adjusted (the rest are adjusted by common scaling). The Fréchet Inception distances after reweighting are detailed in Table 4 Based on the quantitative and qualitative results it appears that the W2 distance with mini-bate approximation assigns high weight to high-quality synthetic images, but the diversity of the highly weighted instances may not capture the full distribution for class. In this regard, the max-sliced Bures better captures the diversity of the class, albeit choosing less realistic images.
27

---

Under review as a conference paper at ICLR 2021
Table 4: Fréchet Inception distances (FID) between CIFARIO test set images in each class and reweighted sample of synthetic images from AutoGAN. The second column shows the FID to the corresponding training set. The third column a uniform weighting over all 50,000 synthetic im- ages. The reweighting that minimizes the max-sliced Bures distance (MSB) the subset of training images performs the best on average. Using the W2 distance estimated through 10 mini-batches of 100 images each perrationperffomms best only one-class. The max-sliced W2 (MSW2) distance also uses mini-batches. The realism scores R the 20 images with the highest weight for each class (200 images for each method) summarized by the median and range.
Training set
Uniform
MSB
W2
MSW2
airplane automobile
28.00
108.67
57.82
74.67
81.85
20.20
133.10
39.88
66.76
74.81
bird
30.25
86.23
58.71
57.17
76.98
cat
35.53
84.63
61.27
83.89
75.57
deer
26,46
85.55
46.81
60.21
56.44
dog
28.99
106.76
56.88
67.94
78.77
frog
29.88
107.88
51.14
75.23
66.93
horse
24.33
111.30
42.68
66.77
63.24
ship
21.49
131.92
37.35
65.05
74.47
truck
17.77
141.56
38.97
63.73
76.05
Average
26.29
109.76
49.15
68.14
72.51
Median R
0.96
1.10
0.97
Range R
0.63-1.34
0.93-1.29
0.65-1.25
Figure 12: Distribution matching based minimizing max-sliced Bures distance max-D (p, D). Synthetic images shown are those with the highest values of u, where á is the u-weighted distribu- tion over 50,000 synthetic images from AutoGAN and consists of CIFAR10 training images for a single class in each row. Rows (top to bottom) correspond to airplane, automobile, bird, cat, deer, dog, frog. horse, ship, and truck classes.
28

---

Under review as a conference paper at ICLR 2021
Distribution matching based on minimizing the Wasserstein-2 distance through mini- batch. Synthetic images shown are those with the higest values of v, where & is the v-weighted distribution over 50,000 synthetic images from AutoGAN and á consists CIFARIO training im- ages for single class in each row, Rows (top to bottom) correspond to airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck classes.
Figure 13:
Distribution matching based on minimizing the max-sliced Wasserstein-2 distance max-WR" (fa, D) through mini-batch approximation. Synthetic images shown those with the highest values of v, where is the u-weighted distribution over 50,000 synthetic images from Au- toGAN and á consists of CIFARIO training images for single class in each row. Rows (top to bottom) correspond to airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck classes.
Figure 14:
29

---

Under review as a conference paper at ICLR 2021
Figure 15: Selecting images directly with the highest realism scores. Synthetic images shown are those with the highest realism values over 50,000 synthetic images generated by AutoGAN when the realism scores used in each row are computed using the CIFARIO 10 training images for single class. Rows (top to bottom) correspond to airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck classes. Realism score correctly identifies "realistic" imagery, but is unable to find samples that cover the real distribution. For example, the top row is missing airplanes, the third row missing birds, the fourth row is missing cats, etc.
30


Reviews:
[{"review_id": "c0k8VtYr3_6", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a family of integral probability metric (IPM) divergence on Hilbert spaces. This family can be characterized by the choice of the witness function, and specific witness function may give rise to the Bures distance, the MMD, Wasserstein, as well as many sliced variants. While this family has been well understood for distributions on finite dimensional space, this paper extends this insight to distributions on (possibly infinite dimensional) Hilbert space. By leveraging the representer theorem, the paper provides the finite dimensional optimization problems that can be solved to estimate the divergence from samples. The power of the method is demonstrated on the covariate shift experiments.\n\nPositive points:\n1. Extending previous results of IPM-type distance to the Hilbert space is a natural ideas. There are in fact many applications that can be nicely solved in the RKHS framework, and thus novel divergences that can substitute the MMD is desirable. The results can boost further learning tasks, and thus are relevant to the machine learning community.\n\nNegative points:\nI find that the exposition of this paper is extremely difficult to follow, and this downplays the contributions of this paper.\n\n1. The title is misleading: the title implies that the paper will study the max-sliced Bures distance in-depth. However, the content of the paper is a general (more width and depth) on a general family of IPM on RKHS.\n2. All results of this paper is provided in Section 2, and there is a tremendous difficulty to identify which results are from the literature, and which results are new in this paper.\n3. From the theoretical viewpoint, it is still not clear to the reader why a divergence on a Hilbert space is necessary. Is it because of the possibility to have better sample complexity?\n\nI think that the paper contains good results, but the paper needs to be thoroughly restructured. Currently, the main results of the papers are included in the Appendix. These results (theorems) should be streamlined into the main text. The introduction should be rewritten with a clear exposition of the contributions.\n\nMinor comments:\n- In page 5, the authors claim that a \"local ascent algorithm will often yield the global optimum\". Can the authors clarify how \"often\" is this? Otherwise, I would recommend to refrain from making unquantifiable claims.\n- The first two lines in page 6 is difficult to parse.\n- The word \"optimizations\" should be replaced by \"optimization problems\"\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y99PGewzVnB", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary: This work proposes the max-sliced Bures (MSB) distance, a distance metric for comparing probability distributions. This work adds to the existing literature on transport based slicing techniques for comparing probability distributions, such as sliced-Wasserstein (SW), max-sliced-Wasserstein (MSW), generalized sliced Wasserstein (GSW).\n\nNovel applications in (1) interpreting datasets and (2) critiquing generative models are claimed due to the assignment of energy-based scores to instances, which allows identification of specific subsets that are not well-matched.\n\nThe authors present several experiments demonstrating their technique\n(1) detecting class-imbalance [Figure 2] \n(2) identifying under/over-represented data subsets in GAN generative models [Figure 3]\n(3) detecting \"covariate shift outlier detection\" [Table 2]\n(4) identifying covariate-shift through reweighting on synthetic CIFAR-10 [Figure 4]\n(5) distribution matching on toy distributions (grid of 25 Gaussians) [Figure 5]\n\n##########################################################################\n\nReasons for score: \n\nOverall I vote for acceptance, but with some reservations on the experiments. \n \nI found the mathematical analysis to be interesting and a potentially valuable contribution to the ML literature on probability distance. I did not check the math in detail, but the authors appears to know what they are talking about.\n\nI was intrigued by the claimed applications. The technique is sold as a tool for (1) interpreting datasets (2) critiquing generative models. The community could benefit from more such tools. \n\nAt first read I found the empirical results lacking, but after a second reading I concluded they are reasonable. As I understand it, one difficulty that arises in interpreting the experiments is their novelty, i.e. at present there is no standard set of experiments for these applications. This seems unavoidable, but I have still have some doubts whether these experiments are optimal.\n\nWhat I was hoping to see was a compelling demonstration of the technique on common problem arising in the practice of machine learning.  For instance in the conclusion the authors write \"Additionally, the one-sided max-sliced Bures divergences ... can be used to identify systematic discrepancies such as **mode dropping**\" [emphasis mine]. \n\n\n##########################################################################\n\nPros: \n* Interesting mathematics\n* Important problem\n\n##########################################################################\n\nCons: \n* Some difficulty in interpreting experiments\n* More compelling applications (e.g. solving mode-dropping are desired)\n* Comparison with other methods where possible seems weak (Figure 5)\n\n##########################################################################\n\nQuestions during rebuttal period: \n\nMode-dropping is a very common problem. Can the authors show an example on which their technique identifies and helps solve mode dropping? \n\nFigure 5 compares max-sliced Bures (cases C,D) against max-sliced W2 (case A,B) on matching a grid of Gaussians starting from uniform, an example taken from Kolouri et al. (2019). Qualitatively, case D beats case B. Why didn't the authors consider the other cases (8 circular Gaussians, swiss-roll, half-moons, circle) as in Figure 2 Kolouri et al. (2019)? \n\n#########################################################################\n\nAdditional Feedback:\n\nA code release will  improve this submission.\n\n#########################################################################\n\nPOST-REBUTTAL RESPONSE:\n\nI found the author's further work on (1) the mode-collapse experiments (2) quantitative comparisons with other slicing methods interesting and convincing. I have decided to increase my score. I reiterate that I have not checked the mathematical content of this paper in detail.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Uh1Fil5I7CP", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes a sliced version of the Bures distance, which is a lower bound on the 2-Wasserstein distance. The purpose behind this is to identify instances that are have the highest contribution towards the discrepancy between two distributions. But compared to other sliced OT distances, this one operates on a the Bures lower bound, which yields a more tractable solution. The paper presents experimental results on image classification datasets, which are claimed to show an advantage of the proposed variant over the full sliced Wasserstein distance .\n\nStrengths:\n* Timely and relevant problem: designing faster, sliced versions of OT distances is a very active area of research\n* Some interesting ideas, and lots of connections to other distances\n\nWeaknesses:\n* Limited novelty. This paper heavily builds on recent work on sliced wasserstein distances (e.g. Kolouri), and combines it with recent work on OT on RKHS (Zhang et al)\n* Clarity/Intuition. Various aspects of the paper could be better motivated, discussed and analyzed (see below).\n* Unconvincing / confusing experimental evaluation, misses necessary quantitative experiments and includes two many qualitative ones \n\nDetailed comments:\n* The original sliced and max-sliced Wasserstein distances are never introduced here, which is surprising given how closely related they are. I would suggest prioritizing this over other (perhaps unnecessary) aspects of the background present in sections 2.1 and 2.2.\n* The introduction of the proposed distances (6, 7, 8) could be better motivated. E.g., it is not immediately clear why (7) corresponds to a sliced version of (4). Going through the derivations in the Appendix sheds some light on this, but given that the main contribution of the paper is all contained in section 2.3, one would expect a more thorough discussion and presentation of this contribution\n* Introducing RKHS and then falling back to finite dimensional embeddings (2.5.1) feels like an overkill. Also, under this setting, how is this different from just embedding all samples as a pre-processing step and then using the usual sliced Wasserstein?\n* As for any lower/upper bound on a distance, the first question that the experiments should try to answer is: \"how tight / good approximation is this bound\"? Such an experiment is necessary to gauge the approximation-quality tradeoff that such a lower bound entails. In this case, I would have expected to see a vis-a-vis comparison of the three proposed distances, and the original sliced Wasserstein ones, on synthetic datasets of increasing size, to get a sense of their asymptotic behavior\n* It might be just me, but I find the setup of the experiments in 3.1 very confusing, and have a hard time parsing the results. E.g. why is the one-sided version of the m-s-Bures distance used here? Is the plot on the right the usual sliced Wasserstein distance or the kernel one? Why is a first-moment approximation used? What is the relevance of the x-axis used here?\n* A good chunk of the experimental results are purely qualitative and rely on the user comparing specific instances of images (Fig 3 and 4). Leaving aside the fact that the size/resolution is pretty small, I'm not sure what I'm looking for here. What should one expect to see here? Are these results good or bad? \n* The covariate shift detection experiments suffer from a similar lack of explanation for the various experimental design choices (e.g., why/how were these scenarios chosen?). In addition, the results exhibit very very wide s.d. confidence intervals, to the point that all the max-sliced distances have intersecting intervals, making it almost impossible to draw any statistically significant results from this table. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The goal in this submission is to find interpretable samples discriminating two probability distributions. In order to tackle this task the authors propose to use a sliced variant of the Bures distance (where the slicing is implemented via a one-rank tensor) and the associated witness function, and illustrate the idea in the discrimination task of fake and real images, and in the detection of covariate shift. 

Interpretable discrimination of probability measures with witness functions is a hot topic of machine learning with a large number of applications and available tools (including linear time ones in the sample size, and methods capable of handling independence testing, goodness-of-fit testing, relative tests among others, beyond the considered two sample setting). 

1)The motivation of the paper and the efficiency of the proposed method compared to available baselines are not clear; the relevance of the demos is questionable. 
2)Unfortunately, the submission also lacks mathematical contributions: for instance 
i)Is the proposed divergence a semi-metric or metric, and under what conditions on the domain and the kernel?
ii)Does the proposed estimator converge, under what assumptions, and how quickly (rates)?

The contribution represents a potentially interesting idea, but significantly more work is needed before publication.
Decision: Reject