Year: 2020

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.

text: 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 Fré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.

heading: 1 INTRODUCTION
text: Divergence measures quantify the dissimilarity between probability distributions. They are fundamental 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 witness function ω(·) whose level-sets identify the specific subsets that are not well matched between the distributions, specifically, subsets which have much higher or much lower probability under one distribution versus the other. Localizing these discrepancies is useful for understanding and compensating for differences between two samples or distributions, to detect covariate shift (Shimodaira, 2000; Quionero-Candela et al., 2009; Lipton et al., 2018) or to evaluate generative models (Heusel et 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-theoretic perspective, the most natural witness function is the logarithm of the ratio of the densities (Kullback & Leibler, 1951) as in the KullbackLeibler divergence. Applying other convex functions to the density ratio constitutes the family of f -divergences (Ali & Silvey, 1966; Rényi, 1961), which include the Hellinger, Jensen-Shannon, and others. However, without a parametric model estimating the densities from samples is challenging (Vapnik, 2013). Following Vapnik’s advice to “try to avoid solving a more general problem as an intermediate step,” previous work has sought to directly model the density ratio via kernel learning (Nguyen et al., 2008; Kanamori et al., 2009; Yamada et al., 2011; 2013; Saito et al., 2018; Lee et al., 2019) or to estimate an f -divergence by optimizing a function from a suitable family (Nguyen et al., 2010) such as a neural network Nowozin et al. (2016).
Witness functions need not rely on the density ratio. A wide class of divergences called integral probability metrics (IPMs) (Müller, 1997), which include total variation, the Wasserstein-1 distance, maximum mean discrepancy (MMD) (Gretton et al., 2007), and others (Mroueh et 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 ω?(·) has a greater expectation in one distribution compared to the other distribution. An IPM between two measures µ and ν is expressed as supω∈F |EX∼µ[ω(X)]− EY∼ν [ω(Y )]| for a given family of functions F . A class of related divergences are the max-sliced Wasserstein-p distances, which seek a linear (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. However, there are two difficulties with computing the max-sliced Wasserstein distance for two samples. The first is that it is a saddlepoint optimization problem, whose objective evaluation requires sorting the samples. Previous work has sought to approximate it using a first moment approximation (Deshpande et al., 2019) or to use a finite number of steps of a local optimizer (Kolouri et al., 2019), without any guarantee of obtaining an optimal witness function. Another difficulty is in the interpretation of the obtained witness function. Unlike the density ratio, there is no 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 we propose a 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 between positive semidefinite operators. It is well-known in quantum information theory (Nielsen & Chuang, 2000; Koltchinskii & Xia, 2015) and machine learning (Brockmeier et al., 2017; Muzellec & Cuturi, 2018; Zhang et al., 2020; Oh et al., 2020; De Meulemeester et al., 2020).

heading: 1.1 CONTRIBUTION
text: 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 supω∈S
∣∣∣√EX∼µ[ω2(X)]−√EY∼ν [ω2(Y )]∣∣∣, where S is an appropriate family of functions. As |∆| = max{∆,−∆}, the max-sliced Bures can be expressed as the maximum of one-sided max-sliced divergences with optimal witness functions, ωµ>ν = arg maxω∈S √ Eµ[ω2(X)]− √ Eν [ω2(Y )], and ωµ<ν = arg maxω∈S √ Eν [ω2(Y )]− √ Eµ[ω2(X)]. If the distributions are not well-matched, then ωµ>ν has large magnitude function evaluations under a ‘localized’ subset of µ and smaller magnitude values for ν, and the opposite for ωµ<ν . The two samples {xi}mi=1, {yi}ni=1 can be sorted by the magnitude of the witness function evaluations.1
Crucially, we detail a tractable optimization procedure that is guaranteed to yield a 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 ∈ Sd−1}, where Sd−1 denotes the unit sphere in Rd. The optimal witness function for the one-sided max-sliced Bures divergence ωµ>ν(·) = 〈·,wµ>ν〉 coincides with the subspace with the greatest difference in RMS, wµ>ν = arg maxw∈Sd−1 √ w>E[XX>]w − √ w>E[Y Y >]w. This optimization problem depends on the dimension d; after computation of the covariance matrices, it is independent of the sample sizes m ≥ n. In comparison, the optimal slice for the max-sliced Wasserstein may not be obtained, and even gradient ascent to a local optimum requiresO(m logm) at each function/gradient evaluation. Furthermore, the slice that maximizes the max-sliced Wasser-
1Four groups of ‘witness points’ (top-K instances) can be inspected to identify any discrepancies:
ω2µ>ν(xπ̀(1)) ≥ · · · ≥ ω2µ>ν(xπ̀(K))︸ ︷︷ ︸ π̀ sorts {xi}mi=1 to reveal examples from µ̂ with large ω 2 µ>ν ̃ ω2µ>ν(yσ̀(1)) ≥ · · · ≥ ω2µ>ν(yσ̀(K))︸ ︷︷ ︸ σ̀ sorts {yi}ni=1 to find the examples from ν̂ with large ω 2 µ>ν , (1)
ω2µ<ν(xπ́(1)) ≥ · · · ≥ ω2µ<ν(xπ́(K))︸ ︷︷ ︸ π́ sorts {xi}mi=1 to find examples from µ̂ with large ω 2 µ<ν ̃ ω2µ<ν(yσ́(1)) ≥ · · · ≥ ω2µ<ν(yσ́(K))︸ ︷︷ ︸ σ́ sorts {yi}ni=1 to find the examples from ν̂ with large ω 2 µ<ν , (2)
where π̀, π́, σ̀, σ́ denote permutations and ̃ and ̃ denote expected inequalities with a large difference.
stein lacks an intrinsic ordering, and it is left to the user to determine whether instances from µ or ν 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 a reproducing kernel Hilbert space (RKHS) H with the family of witness functions S = {ω(·) = 〈φ(·), ω〉H : ω, φ(·) ∈ H, 〈ω, ω〉H = 1}. An example with Gaussian kernels is shown in Figure 1. Secondly, we use a pre-trained neural network to create a task-relevant mapping, computing the second-order statistics of the hidden-layer activations, and apply this in the context of samples of natural images. This enables interpretation of the Fréchet Inception distance (FID) (Heusel et 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 a lower bound on the max-sliced Fréchet distance.
Because of 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 are novel contributions themselves. The max-sliced total variation distance is a special case of the covariance feature matching proposed by Mroueh et al. (2017).
In experimental results, we show applications of the linear and kernel-based versions to detect imbalances in class distributions of natural images and to critique GANs. We compare to other divergences expressed in terms of witness functions including MMD. Finally, we propose algorithms to reweight an empirical distribution in order to minimize max-sliced divergences (with applications to generating conditional distributions and covariate shift correction).

heading: 2 METHODOLOGY
text: Consider a topological space X , a Borel σ-algebra BX , and the set Pr(X ) of Borel probability measures on X . Let µ, ν ∈ Pr(X ) denote two probability measures, and X ∼ µ and Y ∼ ν be two random variables X,Y ∈ X . Let κ denote a positive-definite, bounded kernel function κ : X × X → B ⊂ R. For any κ, there is an implicit mapping φ : X → H that maps any element x ∈ X to an element in the reproducing kernel Hilbert space (RKHS) φ(x) ∈ H such that κ(x, y) = 〈φ(x), φ(y)〉H = 〈κ(·, x), κ(·, y)〉H for x, y ∈ X , and ∀ω ∈ H, ω(x) = 〈ω, κ(·, x)〉H (Aronszajn, 1950). ∀ω ∈ H, ‖ω‖2 = √ 〈ω, ω〉H. When clear, we drop the H subscript on the inner product. A rank-1 RKHS operator is denoted as ω ⊗ ψ ∈ H × H with 〈(ω ⊗ ψ)φ(x), φ(y)〉 = 〈ψ, φ(x)〉〈ω, φ(y)〉 = ψ(x)ω(y) for x, y ∈ X . Denote by mX = EX∼µ[φ(X)] ∈ H and mY = E Y∼ν [φ(Y )] ∈ H the first moments of the random variables in the RKHS. The uncentered second moments are ρX = E [φ(X)⊗φ(X)] ∈ H×H and ρY = E [φ(Y )⊗φ(Y )] ∈ H×H. The covariance operators are ΣX = ρX −mX ⊗mX and ΣY = ρY −mY ⊗mY .

heading: 2.1 DIVERGENCES AS DISTANCE METRICS
text: Let D(µ, ν) denote a divergence D : Pr(X ) × Pr(X ) → [0,∞). It is a distance metric between measures (a probability metric) if all of the following statements hold: (i) µ = ν =⇒ D(µ, ν) = 0, (ii) D(µ, ν) = 0 =⇒ µ = ν, (iii) D(µ, ν) = D(ν, µ), (iv) D(µ, ν) ≤ D(µ, ξ) + D(ν, ξ). It is a semi-metric if all properties aside from (ii) hold. Müller (1997) defines the class of integral probability metrics as the supremum of the absolute difference between expectations
DF (µ, ν) = sup ω∈F ∣∣∣∣∫ X ω(x)dµ(x)− ∫ X ω(x)dν(x) ∣∣∣∣ = sup ω∈F ∣∣E[ω(X)]− E[ω(Y )]∣∣. With appropriate choice of the family of functions F , this form yields well-known divergences (Sriperumbudur et al., 2010), e.g., when F is the set of functions with Lipschitz constant less than 1, the resulting divergence is the Wasserstein-1 distance metric. Another example of an IPM is when F = {ω ∈ H : ‖ω‖2 ≤ 1}, which yields MMD (Gretton et al., 2007), defined as
DHMMD(µ, ν) = sup ω∈H:‖ω‖2≤1 {E[ω(X)]− E[ω(Y )] = E[〈φ(X)− φ(Y ), ω〉]} = ‖mX −mY ‖2
= √ EX∼µ,X′∼µ[κ(X,X ′)] + EY∼ν,Y ′∼ν [κ(Y, Y ′)]− 2EX∼µ,Y∼ν [κ(X,Y )]. (3)
For characteristic kernels such as the Laplacian and Gaussian kernels, the mean embedding EX∼µ[φ(X)] : Pr(X ) → H is an injective function (Sriperumbudur et al., 2008; Fukumizu et al., 2009; Sriperumbudur et al., 2010), capturing the full statistics of µ. In these cases, MMD is a distance metric on Pr(X ); likewise, distance metrics between the operators ρX = E [φ(X) ⊗ φ(X)] and ρY = E [φ(Y )⊗φ(Y )] induce probability metrics for characteristic kernels (Zhang et al., 2020).

heading: 2.2 OPERATOR DISTANCES FOR DEFINING DIVERGENCES
text: Total variation (TV) is a well-known probability metric and an integral probability metric (Müller, 1997), taking the form (1/2) ∑ i|pi−qi| for discrete measures, for which pi = µ(xi) and qi = ν(xi) where {xi}i = X . The TV distance between operators in the RKHS is a divergence
DHTV (µ, ν) , dTV (ρX , ρY ) , 1
2 ‖ρX − ρY ‖1, (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) ∑ i( √ pi − √ qi)2 to positive semidefinite operators (Fuchs & Van De Graaf, 1999; Bromley et al., 2014; Bhatia et al., 2019). The kernel Bures divergence DHB (µ, ν) and the Bures distance dB(ρX , ρY ) are defined as
DHB (µ, ν) = dB(ρX , ρY ) , √ ‖ρX‖1 + ‖ρY ‖1−2 ‖ √ ρX √ ρY ‖1. (5)
The Bures distance is used to define the Wasserstein-2 (W2) distance between Gaussian measures, i.e., the Fréchet distance (Fréchet, 1957; Dowson & Landau, 1982). The multivariate Fréchet distance provides a lower bound for the W2 distance (Gelbrich, 1990).2 The kernel Gauss-Wasserstein distance (Zhang et al., 2020; Oh et al., 2020) is defined as
DHGW (µ, ν) , √ ‖mX −mY ‖22 + d2B(ΣX ,ΣY ) = √ [DHMMD(µ, ν)] 2 + d2B(ΣX ,ΣY ). (6)
Zhang et al. (2020) also proposed the kernel Wasserstein-p distance between µ and ν,
WHp (µ, ν) ,
( inf
γ∈Γ(µ,ν) E (X,Y )∼γ [dpκ(X,Y )]
) 1 p
, p ≥ 1, (7)
where Γ(µ, ν) defines the set of all joint distributions coupling µ and ν, and dpκ(X,Y ) = ‖φ(X)− φ(Y )‖p2. For p = 2, d2κ(X,Y ) = κ(X,X)+κ(Y, Y )−2κ(X,Y ). When p = 2 and φ(x) 7→ x ∈ Rd such thatH = Rd, the standard W2 distance WRd2 (µ, ν) is obtained. 2In the finite-dimensional case, the multivariate Fréchet distance (squared) is often expressed as ‖mX − mY ‖22 + tr(ΣX +ΣY −2 √
ΣXΣY ); the trace term is the squared Bures distance d2B(ΣX ,ΣY ) = tr(ΣX + ΣY )− 2 ∥∥√ΣX√ΣY ∥∥1, where ∥∥√ΣX√ΣY ∥∥1 = tr(√ΣXΣY ) (Dowson & Landau, 1982).

heading: 2.3 DIVERGENCES BASED ON SLICING HILBERT SPACES
text: The sliced Wasserstein distance (Wu et al., 2019; Deshpande et al., 2018; Kolouri et al., 2018), and max-sliced Wasserstein distance (Deshpande et al., 2019; Kolouri et al., 2019) evaluate discrepancies in linear or non-linear one-dimensional subspaces. A motivation for this is the analytic solution of the Wasserstein-p distance in one dimension. The max-sliced Wasserstein-p distance takes the form max-WR d
p (µ, ν) ∝ supw∈Sd−1 infγ∈Γ(µ,ν) E (X,Y )∼γ [〈X − Y,w〉p], p ≥ 1. Similarly, we propose the max-sliced Bures, the kernel TV, and the kernel Wasserstein-p distances using the rank1 operator Ω = ω ⊗ ω ∈ H × H, which projects (slices) the RKHS along a one-dimensional subspace defined by the ray ω ∈ H, with 〈ω, φ(X)〉 = ω(X), due to the reproducing property. In this formulation, ω : X → R is the witness function from the set S={ω ∈ H : ‖ω‖2 =1}. Notably, a linear slice in the RKHS is a possibly non-linear function in the input space.
For conciseness, we denote the mean square witness function evaluations E [ω2(X)] = 〈ω, ρXω〉 = ‖√ρXω‖22 as ‖ω‖2µ, and E [ω2(Y )] = 〈ω, ρY ω〉 = ‖ √ ρY ω‖22 as ‖ω‖2ν . The RMS ‖ω‖µ is an L2
semi-norm on ω induced by the positive semidefinite operator √ ρX . The max-sliced kernel TV, Bures, and W2 distances, derived in appendix A.1, are expressed as
max-DHTV (µ, ν) , 1
2 max { sup ω∈S ‖ω‖2µ − ‖ω‖2ν , sup ω∈S ‖ω‖2ν − ‖ω‖2µ } , (8)
max-DHB (µ, ν) , max {
sup ω∈S ‖ω‖µ − ‖ω‖ν , sup ω∈S ‖ω‖ν − ‖ω‖µ
} , and (9)
max-WH2 (µ, ν) , sup ω∈S
√ ‖ω‖2µ + ‖ω‖2ν − sup
γ∈Γ(µ,ν) E (X,Y )∼γ [2ω(X)ω(Y )], (10)
respectively. The inner supremums in equation 8 and equation 9 are the one-sided divergences.
The max-sliced TV distance is an IPM with F = {ω2(x) = 〈φ(x), ω〉2 : ∀ω ∈ S} and is a special case of the IPMΣ divergence proposed by Mroueh et al. (2017). While not an IPM, the max-sliced kernel Bures distance can be directly related to max-sliced versions of the TV, Fré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-DHB (µ, ν) ≤ √ 2 ( max-DHTV (µ, ν) ) .
Theorem 2. The max-sliced Bures distance in the RKHS H is a lower bound on the kernel maxsliced Gauss-Wasserstein distance, max-DHB (µ, ν) ≤ maxL-DHGW (µ, ν) ≤ maxU -DHGW (µ, ν).
Theorem 3. The max-sliced Bures distance in the RKHS is a lower bound on the kernel max-sliced W2 distance, max-DHB (µ, ν) ≤ max-WH2 (µ, ν).
These results trivially translate to the linear kernel case H = Rd, S = Sd−1, ω(x) = 〈w,x〉, for w,x ∈ Rd and X ⊆ Rd. The latter two show that the max-sliced Bures distance is a lower-bound on the max-sliced Fréchet distance, which is a lower-bound on the max-sliced W2 distance. The proofs and other relationships among the divergences are in Appendix A.2.

heading: 2.4 COMPUTING THE MAX-SLICED DIVERGENCES
text: 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 a neural network. In this context, Goodfellow et al. (2014) use the divergence DA(µ, ν) = maxω E [logω(X)] + E [log (1− ω(Y ))], where ω : X → (0, 1). In comparison, the Wasserstein-1 distance DW 1(µ, ν) = supω∈Lip1 E[ω(X)] − E[ω(Y )] requires a Lipschitz con-
straint (Arjovsky et al., 2017; Gulrajani et al., 2017).3 Table 1 compares the form and constraints.

heading: 2.5 SAMPLE-BASED ESTIMATORS FOR MAX-SLICED DIVERGENCES
text: We consider the case of finite samples expressed as empirical measures µ̂ = ∑m i=1 µiδxi and ν̂ =∑n
i=1 νiδyi for the samples {xi}mi=1 and {yi}ni=1 with discrete probability masses denoted as column vectors [µ1, . . . , µm]> = µ ∈ [0, 1]m, 〈µ,1〉 = 1, and [ν1, . . . , νn]> = ν ∈ [0, 1]n, 〈ν,1〉 = 1. The kernel-based max-sliced divergences optimize the witness function ω(·) = ∑l i=1 αiκ(·, zi) in terms of the dual variablesα ∈ Rl corresponding to a subset of the pooled sample {xi}mi=1∪{yi}ni=1. The optimization problems and algorithms are detailed in appendix A.4.
For clarity, we proceed to the linear kernel case for a finite-dimensional embedding φ(x) = x ∈ Rd. After embedding, kernel evaluations correspond to vector inner-products κ(x, y) = 〈φ(x), φ(y)〉 = x>y. Let X = [x1, . . . ,xm] ∈ Rd×m and Y = [y1, . . . ,yn] ∈ Rd×n denote the sample points with corresponding masses µ and ν, respectively. The witness function is the inner product ω(x) = w>x, where the variable w defines the slice with ‖ω‖2µ̂ = w>ρXw with ρX = XDµX> and ‖ω‖2ν̂ = w>ρY w with ρY = YDνY>, where Dv is diagonal with entries v. For i.i.d. samples, Dµ = 1 mI and Dν = 1 nI. The max-sliced TV, Bures, and W2 divergences are
max-DR d
TV (µ̂, ν̂) = max w:‖w‖2≤1 ∣∣w>(ρX − ρY )w∣∣ = λ1(ρX − ρY ), (11) max-DR d
B (µ̂, ν̂) = max w:‖w‖2≤1 ∣∣∣√w>ρXw −√w>ρY w∣∣∣ , and (12) max-WR d
2 (µ̂, ν̂) = max w:‖w‖2≤1
√ w>(ρX + ρY )w − 2 max
P∈Pµ̂,ν̂ w>XP>Y>w, (13)
where λ1(·) denotes the largest magnitude eigenvalue of the argument and Pµ̂,ν̂ = {P ∈ [0, 1]m×n|P1n = µ,P>1m = ν} is a transportation polytope. These three optimizations differ in difficulty. The first two require only the sample means mX ,mY and covariance matrices ΣX ,ΣY , since ρX = mXm>X + m−1 m ΣX and ρY = mY m > Y + n−1 n ΣY (assuming unbiased covariance estimates). The one-sided max-sliced TV divergences can be solved by finding the eigenvectors associated to the largest eigenvalues of ρX−ρY and ρY −ρX . Likewise the optimal slice for each one-sided max-sliced Bures divergence requires solving a series of eigenvector problems. Specifically, if ρX and ρY are strictly positive definite, then the optimal witness function is ωµ>ν(·) = 〈wγ? , ·〉, where γ? ∈ (0, 1] solves the optimization problem
γ? = arg max 0<γ≤1
√ w>γ ρXwγ − √ w>γ ρY wγ , wγ = arg max
w:‖w‖2≤1 w>(γρX − ρY )w. (14)
The general case involves checking the nullspace of ρY and is given in the Appendix A.5. In comparison, the max-sliced W2 distance is a saddlepoint optimization problem (Deshpande et al., 2019).
3In the context of GANs, the sum of the one-sided max-sliced Bures divergences may prove more appropriate 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-version of the sliced Bures distance akin to the recent distributional-sliced Wasserstein proposal (Anonymous, 2021a) or the Bures distance itself (Anonymous, 2021b) could be used. Nonetheless, this localization property is what makes the max-sliced Bures interpretable.
Following Kolouri et al. (2019), gradient ascent on 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, 2015) and quasi-Newton approaches, such as MINFUNC (Schmidt, 2012). The same approaches can be used to approximate max-DB after smoothing √ · as √ ·+ 0.01.

heading: 3 EXPERIMENTS
text: We present various examples of using the proposed max-sliced divergences to identify the discrepancies 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) as in the Fréchet Inception distance (Heusel et 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 ν to compensate for covariate shift. Finally, we use the one-sided max-sliced Bures divergence to monitor mode dropping during GAN training.

heading: 3.1 INTERPRETING THE FRÉCHET INCEPTION DISTANCE
text: We use a linear witness function to identify instances that are not well matched between two samples of real or fake images represented by internal activations of the Inception object classifying network (Szegedy et al., 2016). Specifically, we search for witness functions with the form ω (x) = 〈w, φ(x)〉, where the vector φ(x) ∈ R2048 is an Inception code—the internal activations of penultimate layer of the network after pooling (Heusel et al., 2017).
Figure 2 shows the performance of the proposed measure to identify instances associated with imbalanced representation of particular classes. In particular, µ̂ 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 ωµ>ν and apply it to the imbalanced sample ν̂, identifying the top-10 witness points with the largest magnitude witness function evaluations ω2µ>ν(yσ̀(1)) ≥ . . . ≥ ω2µ>ν(yσ̀(10)), where σ̀ is a permutation corresponding to sorting {yi}ni=1 by descending magnitude. (While this may seem counterintuitive as it is expected that max1≤i≤m ω 2 µ>ν(xi) max1≤i≤n ω2µ>ν(yi), since ωµ>ν corresponds to a one-dimensional subspace, {yσ̀(i)}Ki=1 are theK 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 witness 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 a 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-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.
Next we generate a set of 50,000 synthetic images for an AutoGAN instance pre-trained on CIFAR10 (Gong et al., 2019), which has an Inception score of 8.525 and a FID score of 12.41. We applied both one-sided max-sliced Bures divergences to identify the two subspaces that maximize the difference in RMS between fake and real images. Figure 3 details the top-10 images in
each subspace and their realism scores R (Kynkäänniemi et al., 2019).4 Applying the max-sliced Wasserstein-2 distance yielded almost the same solution as wReal<Fake (a linear correlation of 0.992).

heading: 3.2 BASELINE COMPARISON ON COVARIATE SHIFT DETECTION
text: We compare the proposed max-sliced Bures distance and the resulting max-sliced Fréchet distance to the max-sliced W2 distance for linear witness functions. Figure 4 compares the divergence estimates instances associated with a simple case of covariate shift with the MNIST data set. Notably, the precision of detecting class imbalances is higher for smaller samples using a kernel (Appendix A.8).

heading: 3.3 COVARIATE SHIFT CORRECTION BY REWEIGHTING
text: We consider the task of reweighting the instances in one sample to minimize the max-sliced Bures distance. This optimization problem can be expressed as minν∈Rn≥0: ∑ i νi=1
J(ν), where J(ν) ∝ max-DR d
B (µ̂, ν̂). As shown in appendix A.7, this is a convex minimization problem with a simplex constraint on ν. 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 Fré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 and 72.5 for the mini-batch W2 and max-sliced W2. (See Table 4 in the Appendix for full results).
4We also compute the realism scores of the entire set of fake images using the set of 10,000 test images and 3-nearest neighbor distances. The Spearman rank correlation between the realism scores for the full set of fake images and the witness function evaluations is -0.70 for ω2Real<Fake and it is 0.17 for ω 2 Real>Fake. This means the realism score has a strong inverse correlation with ω2Real<Fake ∝ −R, and a weak correlation forR ∝ ω2Real>Fake.
Figure 5 shows results of a reweighting uniform distributions to match target distributions using either linear slices or random Fourier bases (Rahimi & Recht, 2008) for approximating a Gaussian kernel.5 For the latter, using the max-sliced Bures as a loss achieves the lowest reweighted W2 distance, which is computed by solving a discrete transportation problem (Flamary & Courty, 2017).

heading: 3.4 DETECTING MODE DROPPING
text: We create a 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 µ̂ has 1000 possible modes corresponding to all 3-digit combinations. At the end of each training epoch (1000 iterations), a fake sample n = 104 is generated. To verify mode coverage we use a 4-layer conv. net trained on 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.

heading: 4 CONCLUSION
text: 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 kernelbased 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-representation between two samples, which can be used to identify systematic discrepancies.
5https://github.com/anon-author-dev/gsw

heading: A APPENDIX
text: The appendix details the derivation of the proposed divergences, formal results relating them to existing divergences, algorithms, and additional experimental results.

heading: A.1 DERIVATION OF THE MAX-SLICED KERNEL DIVERGENCES
text: Let U1 = {ω ⊗ ω : |ω|2 ≤ 1, ω ∈ H} denote the set of rank-1 symmetric operators with bounded trace norm. Let d denote either the TV distance (d = dTV ) or the squared Bures distance (d = d2B), defined in equation 4 and equation 5, respectively. In these cases, the expression of the max-sliced distance can be simplified as
max-d(ρX , ρY ) = sup Ω∈U1 d(ΩρXΩ,ΩρY Ω) = sup Ω∈U1 d(〈Ω, ρX〉HSΩ, 〈Ω, ρY 〉HSΩ)
= sup Ω∈U1 δ(〈Ω, ρX〉HS , 〈Ω, ρY 〉HS) = sup ω∈H:‖ω‖2≤1 δ(〈ω, ρXω〉H, 〈ω, ρXω〉H),
where 〈·, ·〉HS : (H×H)× (H×H)→ R denotes the inner-product defining the Hilbert-Schmidt (Schatten-2 norm), 〈Ω, ρ〉HS = 〈ω ⊗ ω, ρ〉HS = 〈ω, ρω〉H, and δ(p, q) = d(pΩ, qΩ) denotes the distance between scaled versions of Ω, for p ∈ R≥0 and q ∈ R≥0. The equalities follow from the fact that ΩρΩ = (ω ⊗ ω) ρ (ω ⊗ ω) = 〈ω, ρω〉Ω. The max-sliced TV distance and squared max-sliced Bures distance yield expressions for δ(p, q) that match the form of the underlying TV and Hellinger divergences: dTV (pΩ, qΩ) yields δ(p, q) = 12 |p−q|, and d 2 B(pΩ, qΩ) yields δ(p, q) = ( √ p−√q)2:
max-dTV (ρX , ρY ) , sup ω∈S
1 2 |〈ω, ρXω〉 − 〈ω, ρY ω〉|, and (15)
max-dB(ρX , ρY ) , sup ω∈S | √ 〈ω, ρXω〉 − √ 〈ω, ρY ω〉|, (16)
where S = {ω ∈ H : ‖ω‖2 = 1}. The kernel-based divergences can be expressed in terms of the witness functions since 〈ω, ρXω〉 = E [〈φ(X), ω〉〈φ(X), ω〉] = E [ω2(X)] and likewise for ρY . The underlying divergences and distances are listed in Table 2.
Table 2: Relationship between scalar discrepancy δ, divergence D between continuous µ, ν and discrete measures µ,ν, 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).
TV (Bures)2
δ(p, q) 12 |p− q| | √ p−√q|2 D(µ,ν) 12 ∑ i|µi − νi| ∑ i (√ µi − √ νi )2
D(µ, ν) 12 ∫ X |dµ(x)− dν(x)|
∫ X (√ dµ(x)− √ dν(x) )2 d(ρX , ρY ) 1 2‖ρX − ρY ‖1 ‖ρX‖1 + ‖ρY ‖1 − 2 ∥∥∥ρ 12Xρ 12Y ∥∥∥ 1
max-d(ρX , ρY ) 12 supω∈S |〈ω, ρXω〉 − 〈ω, ρY ω〉| supω∈S (√ 〈ω, ρXω〉 − √ 〈ω, ρY ω〉 )2 max-D(µ, ν) 12 supω∈S |E [ω 2(X)]− E [ω2(Y )]| supω∈S (√ E [ω2(X)]− √ E [ω2(Y )]
)2 Slicing is natural for the operator-based distances, as it is 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 δ(·, ·) can be accumulated across a complete set of slices to obtain the original distances. Consider a set (or countably infinite sequence) of orthogonal trace-norm operators O = {Ω1 = ω1 ⊗ ω1,Ω2 = ω2 ⊗ ω2, . . . ,Ωk = ωk ⊗ ωk}. Since these operators are orthogonal and have unit trace-norm ‖ ∑k i=1 Ωi‖∞ = 1,
d(ρX , ρY ) ≥ k∑ i=1 d(〈Ωi, ρX〉HSΩi, 〈Ωi, ρY 〉HSΩi) = k∑ i=1 δ(〈Ωi, ρX〉HS , 〈Ωi, ρY 〉HS)
= k∑ i=1 δ(pi(O), qi(O)), (17)
where pi(O) = 〈Ωi, ρX〉HS and qi(O) = 〈Ωi, ρY 〉HS . To obtain the equality, one must optimizeO over all possible sets of orthogonal trace-norm operators.

heading: A.1.1 MAX-SLICED TOTAL VARIATION DISTANCE
text: The sliced kernel total variation distance is
dTV (ΩρXΩ,ΩρY Ω) = 1
2 ‖Ω(ρX − ρY )Ω‖1 =
1 2 ‖〈Ω, ρX − ρY 〉Ω‖1 = 1 2 |〈Ω, ρX − ρY 〉|‖Ω‖1.
Maximizing over slices yields
1 2 sup Ω∈U1 |〈Ω, ρX − ρY 〉|‖Ω‖1 = 1 2 sup Ω∈U1 |〈Ω, ρX − ρY 〉| = 1 2 sup ω:‖ω‖2≤1 |‖ω‖2µ − ‖ω‖2ν |, (18)
where the first equality follows from the fact that distance is maximized when ‖Ω‖1 = 1. This yields the expression
max-DHTV (µ, ν) , 1
2 sup ω:‖ω‖2=1 |‖ω‖2µ − ‖ω‖2ν |. (19)
Notably, the penultimate expression in equation 18 can be related to the operator norm,
sup Ω∈U1 |〈Ω, ρX − ρY 〉| ≤ sup Ω∈{O∈H×H:‖O‖1≤1} 〈Ω, ρX − ρY 〉 = ‖ρX − ρY ‖∞, (20)
due to the dual norm definition. Since ρX − ρY is symmetric, the equality is achieved. Thus, max-DHTV (µ, ν) = 1 2‖ρX − ρY ‖∞. For a linear kernel, this can be computed by finding the largest magnitude eigenvalue of ρX − ρY = EX∼µ[XX>]− EY∼ν [Y Y >] ∈ Rd×d.

heading: A.1.2 MAX-SLICED BURES DISTANCE
text: The sliced version of the Bures distance is
dB(ΩρXΩ,ΩρY Ω) = √ ‖ΩρXΩ‖1 + ‖ΩρY Ω‖1 − 2‖(ΩρXΩ) 1 2 (ΩρY Ω) 1 2 ‖1,
which can be simplified since ‖ΩρXΩ‖1 = tr((ω ⊗ ω)ρX(ω ⊗ ω)) = 〈ω, ρXω〉‖ω‖22 = ‖ω‖2µ‖ω‖22, and ‖(ΩρXΩ) 1 2 (ΩρY Ω) 1 2 ‖1 = √ 〈ω, ρXω〉〈ω, ρY ω〉‖Ω‖1 = √ ‖ω‖2µ‖ω‖2ν‖Ω‖1 =
‖ω‖µ‖ω‖ν‖ω‖22. Using these expressions, the max-sliced Bures distance is
sup Ω∈U1 dB(ΩρXΩ,ΩρY Ω) = sup ω∈H:‖ω‖2≤1
‖ω‖2 √ ‖ω‖2µ + ‖ω‖2ν − 2‖ω‖µ‖ω‖ν .
The expression is monotonic with the norm of ω yielding
max-DHB (µ, ν) , sup ω∈H:‖ω‖2≤1
√ (‖ω‖µ − ‖ω‖ν)2 = sup
ω∈H:‖ω‖2≤1 ∣∣‖ω‖µ − ‖ω‖ν∣∣ (21) = sup ω∈H:‖ω‖2=1
∣∣∣∣√EX∼µ[ω2(X)]−√EY∼ν [ω2(Y )]∣∣∣∣ .

heading: A.1.3 MAX-SLICED GAUSS-WASSERSTEIN DISTANCES
text: Two max-sliced versions of the Gauss-Wasserstein or Fréchet distance in the RKHS are
maxL-DHGW (µ, ν) = sup Ω∈U1
√ ‖Ω(mX −mY )‖22 + d2B(ΩΣXΩ,ΩΣY Ω)
= sup ω∈H:‖ω‖2≤1
‖ω‖2 √ 〈mX −mY , ω〉2 + (√ 〈ω,ΣXω〉 − √ 〈ω,ΣY ω〉 )2 = sup ω∈H:‖ω‖2≤1 √ 〈mX −mY , ω〉2 + (√ 〈ω,ΣXω〉 − √ 〈ω,ΣY ω〉
)2 = sup ω∈H:‖ω‖2≤1 √ (EX∼µ[ω(X)]− EY∼ν [ω(Y )])2 + ( σω(X) − σω(Y ) )2 , (22)
where σω(X) = √
E[(ω(X)− 〈mX , ω〉)2] is the standard deviation of ω(X), and σω(Y ) =√ E[(ω(Y )− 〈mY , ω〉)2], and
maxU -DHGW (µ, ν) = (
sup Ω∈U1 ‖Ω(mX −mY )‖22 + sup Ω∈U1 d2B(ΩΣXΩ,ΩΣY Ω)
) 1 2
= √ MMD2(µ, ν) + sup
ω∈H:‖ω‖2≤1
( σω(X) − σω(Y ) )2 = √
MMD2(µ, ν) + max-d2B(ΣX ,ΣY ). (23)
Notably, maxL-DHGW (µ, ν) is the supremum of the Fréchet distance over all witness functions.

heading: A.1.4 MAX-SLICED KERNEL WASSERSTEIN
text: A sliced version of the kernel Wasserstein distance between µ and ν relies on the the sliced distance
dκ,ω(X,Y ) = ‖(ω ⊗ ω) (φ(X)− φ(Y ))‖2 = ‖〈ω, φ(X)− φ(Y )〉ω‖2 = |〈ω, φ(X)− φ(Y )〉|‖ω‖2 = |〈ω, φ(X)〉 − 〈ω, φ(Y )〉|‖ω‖2 = |ω(X)− ω(Y )|‖ω‖2.
This distance is monotonic with the norm of ω and convex with respect to ω. The max-sliced kernel Wasserstein-p distance, p ≥ 1, is
max-WHp (µ, ν) = sup ω∈H:‖ω‖2≤1 inf γ∈Γ(µ,ν)
[ E
(X,Y )∼γ (dκ,ω(X,Y ))
p
] 1 p
= sup ω∈H:‖ω‖2≤1 inf γ∈Γ(µ,ν)
[ E
(X,Y )∼γ |ω(X)− ω(Y )|p
] 1 p
, (24)
which is a one-dimensional optimal transport problem. Let ω#µ and ω#ν denote the pushforward measures, then the divergence can be written as
max-WHp (µ, ν) = sup ω∈H:‖ω‖2≤1 inf π∈Π(ω#µ,ω#ν)
[ E
(S,T )∼π |S − T |p
] 1 p
, (25)
where Π(ω#µ, ω#ν) is the set of all joint distributions coupling the pushforward measures.
Assuming the measures are absolutely continuous and adopting the notation from Santambrogio (2015), let Fω,µ(w) = ∫ w −∞ dω#µ = ω#µ((−∞, w]) and Fω,ν(w) = ∫ w −∞ dω#ν = ω#ν((−∞, w]) denote the cumulative distribution functions of the pushforward measures with pseudo-inverses F−1ω,µ(q) = inf{w ∈ R : Fω,µ(w) ≥ q} and F−1ω,ν(q) = inf{w ∈ R : Fω,ν(w) ≥ q}. As shown in Lemma 2.8 (Santambrogio, 2015), then the optimal transport plan π∗ has cumulative distribution Gω(wX , wY ) = min{Fω,µ(wX), Fω,ν(wY )} and the divergence is
max-WHp (µ, ν) = sup ω∈H:‖ω‖2≤1 [∫ 1 0 ∣∣F−1ω,µ(q)− F−1ω,ν(q)∣∣p dq] 1p , (26) and for the case p = 1 (Santambrogio, 2015, Proposition 2.17),
max-WH1 (µ, ν) , sup ω∈H:‖ω‖2≤1 ∫ R |Fω,µ(w)− Fω,ν(w)| dw. (27)
The objective in the last quantity is an L1-norm version of the Cramér–von Mises criterion (Schmid & Trede, 1995; Anderson, 1962). That is, the max-sliced kernel Wasserstein-1 distance is equivalent to a max-sliced L1-norm version of the Cramér–von Mises criterion, where the slicing corresponds to a function in the RKHS that witnesses the largest discrepancies between the measures. The choice of p = 2 simplifies, yielding the following optimization problem
max-WH2 (µ, ν) = sup ω∈H:‖ω‖2≤1 inf γ∈Γ(µ,ν)
( E
(X,Y )∼γ
[ ω2(X) + ω2(Y )− 2ω(X)ω(Y ) ]) 12 = sup ω∈H:‖ω‖2≤1 ( ‖ω‖2µ + ‖ω‖2ν − sup γ∈Γ(µ,ν) E (X,Y )∼γ [2ω(X)ω(Y )] ) 1 2
(28)
= sup ω∈H:‖ω‖2≤1
( ‖ω‖2µ + ‖ω‖2ν − 2 ∫ 1 0 F−1ω,µ(q)F −1 ω,ν(q)dq ) 1 2 . (29)

heading: A.2 RELATIONSHIP BETWEEN THE KERNEL-BASED MAX-SLICED DIVERGENCES
text: The Bures distance can be used to lower bound the TV distance, d2B(ρX , ρY ) ≤ ‖ρX − ρY ‖1 = 2dTV (ρX , ρY ) (Fuchs & Van De Graaf, 1999). This inequality stems from the inequality between the squared Hellinger and total variation distances for discrete probability laws. ∑ i‖ √ pi− √ qi‖22 ≤∑
i|pi − qi|, where the inequality holds for each summand, | √ pi − √ qi|2 ≤ | √ pi − √ qi|( √ pi +√
qi) = |pi − qi|. This inequality holds for the max-sliced divergences as stated in Theorem 1.
Proof of Theorem 1. (‖ω‖µ − ‖ω‖ν)2 ≤ ∣∣‖ω‖2µ − ‖ω‖2ν∣∣, where the inequality is a consequence of the inequality between the arithmetic and geometric means, let a = ‖ω‖2µ and b = ‖ω‖2ν , then ( √ a − √ b)2 ≤ | √ a − √ b|( √ a + √ b) = |a − b|. Taking the supremum over ω ∈ H with the
constraint ‖ω‖2 ≤ 1 yields the desired the result ( max-DHB (µ, ν) )2 ≤ 2 (max-DHTV (µ, ν)). We now consider the relationship between the Gauss-Wasserstein or Fréchet distance—which combines the distances between the first and second-order moments—with the max-sliced Bures when it is applied directly to the uncentered covariance matrices. For this we need the following lemma. Lemma 4 (Reverse triangle inequality). For two vectors in R2, the difference between their Euclidean norms is less than or equal to the Euclidean norm of their differences. For a, b, c, d ∈ R,∣∣√a2 + b2 −√c2 + d2∣∣ ≤√(a− c)2 + (b− d)2. Proof. Let e = (√ a2 + b2 − √ c2 + d2 )2 and f = (a− c)2 + (b− d)2.
e = a2 + b2 + c2 + d2 − 2 √ (a2 + b2)(c2 + d2)
= a2 + b2 + c2 + d2 − 2 √ a2c2 + b2d2 + b2c2 + a2d2
≤ a2 + b2 + c2 + d2 − 2 √ a2c2 + b2d2 + 2 √ a2b2c2d2, by the arithmetic and geometric mean inequality
= a2 + b2 + c2 + d2 − 2 √ ( √ a2c2 + √ b2d2)2 = a2 + b2 + c2 + d2 − 2( √ a2c2 + √ b2d2)
≤ a2 + b2 + c2 + d2 − 2(ac+ bd) = (a− c)2 + (b− d)2 = f. Taking the square root of each side yields the inequality √ e ≤ √ f .
Proof of Theorem 2. To relate the sliced Bures and Gauss-Wasserstein distances, we note that ‖ω‖2µ = 〈ρX , ω ⊗ ω〉HS = 〈ΣX +mX ⊗mX , ω ⊗ ω〉HS = σ2ω(X) + 〈mX , ω〉
2 and likewise for ‖ω‖2ν . Then, ∣∣∣√‖ω‖2µ −√‖ω‖2ν∣∣∣ = ∣∣∣√〈mX , ω〉2 + σ2ω(X) −√〈mY , ω〉2 + σ2ω(Y )∣∣∣
≤ √ 〈mX −mY , ω〉2 + (σω(X) − σω(Y ))2, (30)
where the inequality relies on Lemma 4, with a = 〈mX , ω〉, b = σω(X), c = 〈mY , ω〉, and d = σω(Y ). Taking supremum over slices yields the desired inequality.
Theorem 2 shows that the max-sliced kernel Bures distance is a lower-bound on the max-sliced kernel Wasserstein-2 distance, since the latter is lower bounded by the max-sliced kernel GaussWasserstein distance.
Proof of Theorem 3. Let ω(X) = 〈mX , ω〉+ ω̃(X) and ω(Y ) = 〈mY , ω〉+ ω̃(Y ), where ω̃(X) = 〈φ(X) − mX , ω〉 and ω̃(Y ) = 〈φ(Y ) − mY , ω〉 are zero mean, and E [ω̃2(X)] = σ2ω(X) and E [ω̃2(Y )] = σ2ω(Y ). The squared Fréchet distance between random variables ω(X) and ω(Y ) is
(E [ω(X)]− E [ω(Y )])2 + (σω(X) − σω(Y ))2 = 〈mX −mY , ω〉2 + (σω(X) − σω(Y ))2
= 〈mX , ω〉2 + σ2ω(X) + 〈mY , ω〉 2 + σ2ω(Y ) − 2 ( 〈mX , ω〉〈mY , ω〉+ σω(X)σω(Y ) ) = E [ω2(X)] + E [ω2(Y )]− 2 ( E [ω(X)]E [ω(Y )] + √ E [ω̃2(X)]E [ω̃2(Y )] ) .
By Hölder’s inequality, E [ω̃(X)ω̃(Y )] ≤ σω(X)σω(Y ) = √ E [ω̃2(X)]E [ω̃2(Y )]. Consequently,
E [ω2(X)] + E [ω2(Y )]− 2 ( E [ω(X)]E [ω(Y )] + √ E [ω̃2(X)]E [ω̃2(Y )] ) (31)
≤ E [ω2(X)] + E [ω2(Y )]− 2 (E [ω(X)]E [ω(Y )] + E [ω̃(X)ω̃(Y )]) = E [ω2(X)] + E [ω2(Y )]− 2E [ω(X)ω(Y )] = E [(ω(X)− ω(Y ))2]. (32)
Taking the infimum over all possible joint distributions (X,Y ) ∼ γ that are within the coupling distribution γ ∈ Γ, yields the sliced Wasserstein-2 distance on the right hand side. Maximizing over slices, yields maxU -DHGW (µ, ν) ≤ max-WH2 (µ, ν) and combining with Theorem 2 yields the desired result.

heading: A.3 RELATIONSHIP TO OTHER DIVERGENCES
text: Finally, we note that the terms in the max-sliced Gauss-Wasserstein divergences are related to kernel Fischer discriminant analysis (KFDA) (Mika et al., 1999). KFDA objective is based on the ratio of the difference in means to the pooled variances:
DHFDA(µ, ν) = sup ω
〈ω,mX −mY 〉2
σ2ω(X) + σ 2 ω(Y )
= sup ω
〈ω,mX −mY 〉2
〈ω, (ΣX + ΣY )ω〉 . (33)
KFDA seeks a witness function which has widely separated means for the two measures, and minimal variance.

heading: A.4 COMPUTING THE MAX-SLICED KERNEL DIVERGENCES
text: We assume the witness function6 ω ∈ H is of the form ω = ∑n+m i=1 αiφ(zi) with ω(·) =∑n+m
i=1 αiκ(·, zi) where zi = { xi, 1 ≤ i ≤ m yi−m, m < i ≤ n+m and α ∈ Rm+n. In this case,
‖ω‖2µ̂ = 〈ω ⊗ ω, (φ⊗ φ)#µ̂)〉 = m∑ j=1 µj〈ω ⊗ ω, φ(xj)⊗ φ(xj)〉 = m∑ j=1 µj〈ω, φ(xj)〉2
= m∑ j=1 µj〈 n+m∑ i=1 αiφ(zi), φ(xj)〉2 = m∑ j=1 µj ( n+m∑ i=1 αiκ(zi, xj) )2 = 〈µ, (KXZα)◦2〉
= α>K>XZdiag(µ)KXZα = ‖D 1 2 µKXZα‖22,
where κ(zi, zj) = Kij , K = [ KXX ,KXY KY X ,KY Y ] = [ KXZ KY Z ] , (·)◦2 denotes the elementwise squaring of a matrix/vector, and Dv = diag(v) denotes a diagonal matrix whose diagonal entries are the vector v. Similarly, ‖ω‖2ν̂ = 〈ν, (KY Zα)◦2〉 = ‖D 1 2 ν KY Zα‖22.
In order for the constraint ‖ω‖22 ≤ 1 =⇒ α>Kα ≤ 1 to ensure a bounded solution, we assume K is strictly positive definite. For this purpose, we add a small value to its diagonal K + 10−9I when necessary in the optimization procedures. For computational purposes when m or n are large, a subset (possibly random) of landmark points of size l < n + m can be used to form the witness function ω = ∑l i=1 αiφ(zτi), where {τi}li=1 ⊂ {1, . . . ,m + n}. In this case, KXZ ∈ Rm×l and KY Z ∈ Rn×l with [KXZ ]i,j = κ(xi, zτj ) and [KY Z ]i,j = κ(yi, zτj ). In this case, the constraint also needs to be adjusted.

heading: A.4.1 MAX-SLICED KERNEL TV DISTANCE
text: Using these expressions, the max-sliced kernel TV distance is
max-DHTV (µ̂, ν̂) = max α:α>Kα≤1
1
2 ∣∣∣‖D 12µKXZα‖22 − ‖D 12ν KY Zα‖22∣∣∣ (34) = max
α:α>Kα≤1
1 2 |α>(K>XZDµKXZ −K>Y ZDνKY Z)α|. (35)
The solution is the generalized eigenvector corresponding to the largest magnitude eigenvalue of the generalized eigenvalue problem Av = λKv, where A = K>XZDµKXZ − K>Y ZDνKY Z . α? = arg maxα α>Aα α>Kα . The witness function is ω?(·) = ∑m+n i=1 α ? i κ(·, zi).
6Similar to kernel PCA, the constraint ‖ω‖2 ≤ 1 allows the use of the representer theorem for the RKHS.

heading: A.4.2 MAX-SLICED KERNEL BURES DISTANCE
text: The sample-based max-sliced kernel Bures distance is
max-DHB (µ̂, ν̂) = max α:α>Kα≤1 ∣∣∣‖D 12µKXZα‖2 − ‖D 12ν KY Zα‖2∣∣∣ (36) = max s∈{−1,+1} max α:α>Kα≤1 s‖D 1 2 µKXZα‖2 − s‖D 1 2 ν KY Zα‖2 (37)
The last expression shows that the max-sliced Bures distance can be expressed as a bilevel optimization problem, where the inner optimization problem—which we refer to as one-sided max-sliced Bures divergence—is a difference of convex functions:
max-DHB (µ̂, ν̂) = max {[
min α:α>Kα≤1
g(α)− h(α) ] , [ min
α:α>Kα≤1 h(α)− g(α)
]} , (38)
g(α) = ‖D 1 2 ν KY Zα‖2, (39)
h(α) = ‖D 1 2 µKXZα‖2. (40)
Without loss of generality, we will consider the first case (s = 1),
min α:α>Kα≤1
g(α)− h(α). (P)
Inspired by the approach Landsman (2008), we relate this problem to a quadratic program, specifically, the quadratically constrained quadratic program
min α:α>Kα≤1
c1g 2(α)− c2h2(α) = min α:α>Kα≤1 α>(c1K > Y ZDνKY Z − c2K>XZDµKXZ)α, (Q),
for c1, c2 ∈ R≥0. The solution of which can be obtained as in the max-sliced kernel TV distance by solving a generalized eigenvalue problem. For (P), the Lagrangian function is
L(α, λ) = g(α)− h(α)− λ(α>Kα− 1). (41) Let G = {α : g(α) > 0, h(α) > 0} denote the set of points where g and h are differentiable. Then for α ∈ G and K positive definite, L(α, λ) is differentiable, and
∇αL(α, λ) = ∇αg(α)−∇αh(α)− 2λKα = 1
2g(α) ∇αg2(α)−
1
2h(α) ∇αh2(α)− 2λKα,
where the equality follows from ∇αg2(α) = 2g(α)∇αg(α) and likewise ∇αh2(α) = 2h(α)∇αh(α). For (Q), the Lagrangian function and its gradient are
L̄(α, λ) = c1g 2(α)− c2h2(α)− λ(α>Kα− 1), (42)
∇αL̄(α, λ) = c1∇αg2(α)− c2∇αh2(α)− 2λKα. (43)
If c1 = 12g(α) and c2 = 1 2h(α) , then ∇αL(α, λ) = ∇αL̄(α, λ).
Let α∗ denote a global optimum of (Q). If c1 = 12g(α∗) and c2 = 1 2h(α∗) , then∇αL(α, λ)|α=α∗ = ∇αL̄(α, λ)|α=α∗ . Consequently, α∗ is a local optimum of (P). By the Karush–Kuhn–Tucker conditions, it is a necessary condition for all optima of (P) in G to have this form. Thus, any global optimum of (P) that lies in G corresponds to a global optimum of (Q) for particular values of c1, c2. The family of solutions to (Q) that includes all local optima of (P) in G, is
α∗γ = arg max α:α>Kα≤1 γh2(α)− g2(α), γ = c2 c1 ∈ (0, 1], (44)
where the bounds are due to the non-negative functions and h2(α∗γ) ≥ g2(α∗γ) =⇒ 12c2 ≥ 1 2c1 =⇒ c1 ≥ c2 =⇒ c2c1 ≤ 1. Notably, γ = 1 =⇒ c1 = c2 corresponds to the one-sided max-sliced TV. The global optimum of (P) within G is necessarily within {α∗γ}γ∈(0,1] and can be found as the solution to the bound scalar optimization problem minγ∈(0,1] g(α∗γ)− h(α∗γ).
A remaining case for a global optimum is a non-differentiable point α? /∈ G, specifically, g(α?) = 0 (the case of h(α?) = 0 is trivial), which corresponds to α? ∈
Null(DνKY Z). In this case, the generalized eigenvalue problem must be restricted to the nullspace α∗∅ = arg maxα∈Null(DνKY Z):α>Kα≤1 h
2(α). Let V ∈ R(m+n)×p denote a matrix of p orthonormal columns that spans the nullspace, then α∗∅ = Vβ ∗, where β∗ = arg maxβ∈Rp:β>V>KVβ≤1‖D 1 2 µKXZVβ‖22. Overall, the one-sided max-sliced kernel Bures distance can be computed using a combination of a line search for γ ∈ (0, 1] and checking the solution in the nullspace as described in Algorithm 1.
Algorithm 1: One-sided max-sliced kernel Bures divergence Input: {(xi, µi)}mi=1, {(yi, νi)}ni=1, κ(·, ·), τ ⊆ {1,m+ n}
1 zi = { xi i ≤ m, yi−m i+ 1 ≤ i ≤ m+ n 2 D 1 2 µKXZ = [ √ µiκ(xi, zτj )] m, |τ | i=1,j=1 3 D 1 2 ν KY Z = [ √ νiκ(yi, zτj )] n, |τ | i=1,j=1 4 A = K>XZDµKXZ 5 B = K>Y ZDνKY Z 6 K = [κ(zτi , zτj )] m, |τ | i=1,j=1 7 α? = ONESIDEDMAXSLICEDKERNELBURES(A,B,K) 8 ωµ>ν(z) : z 7→ ∑|τ | i=1 α ? i κ(z, zτi)
Output: ωµ>ν
1 ONESIDEDMAXSLICEDKERNELBURES (A,B,K) 2 αγ : γ 7→ arg maxα:α>Kα≤1α>(γA−B)α 3 γ? = arg max0<γ≤1 √ α>γ Aαγ − √ α>γ Bαγ
4 α∅ = arg max α∈Null(B):α>Kα≤1
α>Aα
5 if √ α>∅Aα∅ > √ α>γ?Aαγ? − √ α>γ?Bαγ? then 6 α? = α∅ 7 else 8 α? = αγ? 9 end
10 return α?

heading: A.4.3 MAX-SLICED KERNEL WASSERSTEIN
text: The empirical version of max-sliced kernel Wasserstein divergence can be expressed in terms of either equation 24 or equation 26,
max-WHp (µ̂, ν̂) = max ω∈H:‖ω‖2≤1 min P∈Pµ̂,ν̂  m,n∑ i=1,j=1 Pi,j |ω(xi)− ω(yj)|p  1p (45)
= max ω∈H:‖ω‖2≤1 [∫ 1 0 |F−1ω,µ̂(q)− F −1 ω,ν̂(q)| pdq ] 1 p , (46)
where Pµ̂,ν̂ = {P ∈ [0, 1]m×n|P1n = µ,P>1m = ν} is a transportation polytope. The empirical distribution functions are Fω,µ̂(w) = ∑m i=1 µiIω(xi)≤w and Fω,ν̂(w) = ∑n i=1 νiIω(yi)≤w with inverses F−1ω,µ̂(q) = min{ω(xi), i ∈ {1, . . . ,m} : Fω,µ̂(ω(xi)) ≥ q} and F −1 ω,ν̂(q) = min{ω(yi), i ∈ {1, . . . , n} : Fω,ν̂(ω(yi)) ≥ q}. For fixed ω, the optimal transport plan Ṕ is based on the sorted values ω(x(1)) ≤ ω(x(2)) ≤ · · · ≤ ω(x(m)) and ω(y(1)) ≤ ω(y(2)) ≤ · · · ≤ ω(y(m)). Denote the sorted values as vectors ώX and ώY , with [ώX ]i = ω(x(i)) and [ώY ]i = ω(y(i)), and denote by µ́ and ν́ the corresponding permuted versions of µ and ν.
In the case of equal samples sizes of uniform measure, m = n and µ = 1m1m and ν = 1 n1n, elements in Pµ̂,ν̂ are scaled elements in the Birkhoff polytope (the set of doubly stochastic matrices), and the solution to the linear program is a permutation and max-WHp (µ̂, ν̂) =
supω∈H:‖ω‖2≤1 {[∑m i=1 ∣∣ω(x(i))− ω(y(i))∣∣p] 1p = ‖ώX − ώY ‖p}, where ‖·‖p denotes the `p norm in m dimensions. As in the continuous case, the discrete transport plan between the sorted measures has the cumulative distribution Ǵ ∈ [0, 1]m×n with Ǵi,j = min{ ∑i k=1 µ́k, ∑j k=1 ν́k}. The optimal transport plan between the sorted measures is given by taking the first difference over both rows and columns of Ǵ, Ṕ1,1 = Ǵ1,1, Ṕ1,j = Ǵ1,j − Ǵ1,j−1, Ṕi,1 = Ǵi,1 − Ǵi−1,1, and Ṕi,j = Ṕi,j − Ṕi−1,j − Ṕi,j−1. Using the sorted witness function evaluations the distance can be written as
max-WHp (µ̂, ν̂) = max ω∈H:‖ω‖2≤1  m,n∑ i=1,j=1 Ṕi,j ∣∣ω(x(i))− ω(y(j))∣∣p  1p . (47) We now turn our attention to the optimization of the function ω parametrized in terms of α, ω(·) =∑m+n i=1 αiκ(·, zi). For arbitrary sample sizes with p = 2, the max-sliced kernel W2 distance is
max-WH2 (µ̂, ν̂) = max ω∈H:‖ω‖2≤1
( ‖ω‖2µ̂ + ‖ω‖2ν̂ − 2 max
P∈Pµ̂,ν̂ 〈P,ωXω>Y 〉
) 1 2
, (48)
with unsorted values ωX = [ω(x1), . . . , ω(xm)]> = KXZα and ωY = [ω(y1), . . . , ω(yn)]> = KY Zα.
The max-sliced kernel W2 distance can be expressed in terms of equation 45 or equation 48:
[ max-WH2 (µ̂, ν̂) ]2 = max
α:α>Kα≤1 min P∈Pµ̂,ν̂ m,n∑ i=1,j=1 Pij ∣∣∣∣∣ m+n∑ k=1 (κ(xi, zk)− κ(yj , zk))αk ∣∣∣∣∣ 2
= max α:α>Kα≤1
{ α>K>XZDµKXZα+α >K>Y ZDνKY Zα
− 2 max P∈Pµ̂,ν̂
α>K>XZPKY Zα }
= max α:α>Kα≤1 min P∈Pµ̂,ν̂ α>QPα = max α
minP∈Pµ̂,ν̂ α >QPα
α>Kα , (49)
where QP = K>XZDµKXZ+K > Y ZDνKY Z−K>XZPKY Z−K>Y ZP>KXZ is a symmetric matrix positive semidefinite matrix. (This can be seen since the objective is greater than or equal to zero for all choices of α.) For fixed P, equation 49 is a convex maximization, that can be solved as a generalized eigenvalue problem. For fixed α, the optimization in terms of P is a linear program with the solution detailed above. However, when maximizing with respect toα, P is a matrix-valued function of α. To find a local maximum for α we use the unconstrained optimization equation 49 and perform gradient ascent with respect to α, 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. (2019).

heading: A.5 COMPUTING THE MAX-SLICED DIVERGENCES FOR THE LINEAR CASE
text: The linear case follows from the kernel case with some further simplification. The objectives 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 versions of the one-sided max-sliced TV divergence. Assuming the covariance matrices are strictly positive definite max-DR d
B (µ̂, ν̂) = max0<γ<1 ∣∣∣√w>γ ρXwγ −√w>γ ρY wγ∣∣∣ , where wγ = arg maxw:‖w‖2≤1 w
>(γρX − ρY )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 is described in Algorithm 2.
Algorithm 2: One-sided max-sliced Bures divergence

heading: Input: ρX ,ρY ∈ Rd×d
text: 1 wγ : γ 7→ arg maxw:‖w‖2≤1 w >(γρX − ρY )w
2 γ? = arg max0<γ≤1 √ w>γ ρXwγ − √ w>γ ρY wγ
3 if rank(ρY ) = d then 4 wµ>ν = wγ? 5 else 6 v = arg max
w∈Null(ρY ):‖w‖2≤1 w>ρXw
7 if √ v>ρXv > √ w>γ?ρXwγ? − √
w>γ?ρY wγ? then 8 wµ>ν = v 9 else
10 wµ>ν = wγ? 11 end 12 end
Output: wµ>ν
As an alternative to Algorithm 2, first-order algorithms can be applied, nevertheless, obtaining a global optimal cannot be guaranteed easily in this case. To make the objective differentiable, the square root, which is non-differentiable at 0, should be smoothed √ · ≈ √ ·+ 2 (e.g., 2 = 0.01).

heading: A.6 SAMPLE-BASED MAX-SLICED BURES DISTANCE IS A RELAXATION OF THE MAX-SLICED WASSERSTEIN-2 DISTANCE
text: We show that the max-sliced Bures distance is a relaxation of the max-sliced W2 distance. Let ρ = ZZ> with Z ∈ Rd×p denote a strictly positive definite matrix, such that √ w>ρw > 0, √ w>ρw =√
w>ZZ>w = maxθ∈Sp−1〈θ,Z>w〉, where θ∗ = arg maxθ∈Sp−1〈θ,Z>w〉 = 1√w>ZZ>wZ >w. Using this form, when ρX and ρY are non-singular, the one-sided sliced Bures can be expressed as
max θ1∈Sd−1
〈θ1, √ ρXw〉 − max θ2∈Sd−1 〈θ2, √ ρY w〉 = max θ3∈Sm−1 〈θ3,D 1 2 µX >w〉 − max θ4∈Sn−1 〈θ4,D 1 2 ν Y >w〉,
since ρX = XD 1 2 µ(XD 1 2 µ)> and ρY = YD 1 2 ν (YD 1 2 ν )>. 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-DR d
B (µ̂, ν̂) = max w:‖w‖2≤1
√ w>(ρX + ρY )w − 2 max
Q∈Qµ̂,ν̂ w>XQY>w, (50)
where Qµ̂,ν̂ = {D 1 2 µΘD 1 2 ν : Θ ∈ Rm×n, ‖Θ‖1 ≤ 1}. This holds since
max Θ:‖Θ‖1≤1
w>XD 1 2 µΘD 1 2 ν Y >w = max
θ3∈Sm−1,θ4∈Sn−1 〈θ3,D
1 2 µX >w〉〈θ4,D 1 2 ν Y >w〉 (51)
= √ w>ρXw √ w>ρY w. (52)

heading: A.7 COVARIATE SHIFT CORRECTION ALGORITHMS
text: 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 ν∈Rn≥0:〈ν,1〉=1 J(ν), (53)
where J(ν) = ( max-DHB (µ̂, ν̂) )2 = max
α:α>Kα≤1 J̃(ν,α)
= max α:α>Kα≤1 〈µ, (KXZα)◦2〉︸ ︷︷ ︸ Cα +〈ν, (KY Zα)◦2︸ ︷︷ ︸ kα
〉 − 2 √ 〈µ, (KXZα)◦2〉〈ν, (KY Zα)◦2〉
= max α:α>Kα≤1
Cα + 〈ν,kα〉 − 2 √ Cα √ 〈ν,kα〉.
For fixed α the function J̃(·,α) is a sum of a linear function and a convex function f(·) = − √ · is convex since √ · is concave. J(ν) = maxα:α>Kα≤1 J̃(ν,α) is convex since maximizing over α preserves convexity (Nesterov, 2018, Theorem 3.1.8).
In the linear kernel case, the cost is J(ν) = ( max-DR d B (µ̂, ν̂) )2
= max w:‖w‖2≤1
{ J̃(ν,w) = (√ 〈µ, (X>w)◦2〉 − √ 〈ν, (Y>w)◦2〉 )2} = max
w:‖w‖2≤1 (〈µ, (X>w)◦2〉+ 〈ν, (Y>w)◦2〉 − 2
√ 〈µ, (X>w)◦2〉〈ν, (Y>w)◦2〉.
Again, J(ν) is convex since J̃(·,w) is convex for fixed w. In this case, the gradient has the intuitive form of
∇νJ(ν) = (
1− ‖ω‖µ̂ ‖ω‖ν̂
) (ω>Y) ◦2 = ( 1− √ 〈µ, (X>wν)◦2〉√ 〈ν, (Y>wν)◦2〉 ) (Y>wν) ◦2. (54)
To solve this convex minimization over a probability simplex we apply the Frank-Wolfe (conditional gradient) algorithm Jaggi (2013) to iteratively adjust the weight of one instance ν ← (1−γ)ν+γei, where ei is an indicator vector, i = arg min1≤j≤n[∇νJ(ν)]j , and γ ∈ [0, 1] is the stepsize. A benefit of the Frank-Wolfe scheme is that it requires only rank-1 updates of YDνY>, which are needed for updating w.

heading: A.8 ADDITIONAL EXPERIMENTAL RESULTS
text: We start by comparing the proposed max-sliced Bures distance to 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 using ADAM with parameters lr = 1e-3, beta1 = 0.9, beta2 = 0.999, epsilon = 1e-08, capping the number of iterations at 1000 or until the change in the slice is minimal ‖w −wold‖∞ < 10−6. In two-dimensions, a near optimal slice can be obtained by a fine grid search of the sliced Bures and sliced W2 distance as shown in Figure 7 for two zero-mean Gaussian distributions. Figure 8 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 is 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 of the same differences. Figure 10 details witness function evaluations of each for six data sets generated from two-dimensional 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.

heading: A.9 COVARIATE SHIFT DETECTION WITH MAX-SLICED KERNEL DIVERGENCES
text: We proceed to generalize the comparisons in Figure 4 on imbalanced samples on MNIST to the kernel case. We use a Gaussian kernel κσ with the parameter σ set as the median Euclidean distance
in the pooled sample. To ease computation for large-sample sizes, we let τ be a random subset of the pooled samples {xi}mi=1∪{yi}ni=1 of size l = min{500,m+n}. In this case, the max-sliced Fréchet refers to maxL-DHGW , 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, as in equation 23. The kernel-based max-sliced W2 distance should be an upper bound of the max-sliced Fréchet. However, in practice the optimal slice (witness function) may not be obtained.
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 ω(x) = Pr(H0|X = x) = 1−Pr(H1|X = x), where H0 : X ∼ ν̂ and H1 : X ∼ µ̂. 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 estimation (uLSIF) (Kanamori et al., 2009), and relative density-ratio estimation (RuLSIF) (Yamada et al., 2011), but all methods were outperformed by logistic regression with kernel bases. We also compare 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 κσ is used with the parameter σ 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 a mismatched probability for one class l ∈ {0, . . . , 9} and the other sample has a balanced sample: (Scenario 1) µ̂ is balanced and ν̂ is missing l; (Scenario 2) µ̂ is imbalanced with l only appearing in 2% of the cases, compared to 10.8̄% for the other classes and ν̂ is balanced; (Scenario 3) µ̂ is balanced and ν̂ consists of only images from l. In each case, µ̂ is a sample of 500 images from the training set and ν̂ is a sample of 500 images from the test set. A threshold-free way to assess covariate shift detection is to use the area-under-the-curve (AUC) of the receiver operator curve (ROC), where positive instances correspond to class l. 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 underor 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.
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 a separate set of runs we also compute the realism scores (Kynkäänniemi et al., 2019) with k = 3 where ν̂ is considered the real set, and µ̂ are synthetic, to prioritize instances; results for the three scenarios are 0.75±0.11, 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.

heading: A.10 COVARIATE SHIFT CORRECTION FOR CLASS-CONDITIONAL SUBSAMPLING
text: Figure 12 shows 20 synthetic images—generated by AutoGAN trained on CIFAR10 (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.29). Figure 14 shows the same but based on the weights optimized by using the max-sliced W2 distance with the mini-batch optimization. The realism scores of the selected images have a median and range of 0.97 (0.65–1.25). Finally, Figure 15 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 simplex constraints. The default step-size schedule γ = 2k+2 and the same stopping criterion is used max1≤i≤n|ν(k)i − ν (k−1) i | < 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 Fré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-batch approximation assigns high weight to high-quality synthetic images, but the diversity of the highly weighted instances may not capture the full distribution for a class. In this regard, the max-sliced Bures better captures the diversity of the class, albeit choosing less realistic images.

Review summaries:
This 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 .

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.