Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances
Authors: Sloan Nietert
Ziv Goldfeld
Ritwik Sadhu
Kengo Kato
Venue: NeurIPS 2022 Accept (2022)
Keywords: sliced optimal transport
Wasserstein distances
empirical convergence
robust statistics

Abstract: Sliced Wasserstein distances preserve properties of classic Wasserstein distances while being more scalable for computation and estimation in high dimensions. The goal of this work is to quantify this scalability from three key aspects: (i) empirical convergence rates; (ii) robustness to data contamination; and (iii) efficient computational methods. For empirical convergence, we derive fast rates with explicit dependence of constants on dimension, subject to log-concavity of the population distributions. For robustness, we characterize minimax optimal, dimension-free robust estimation risks, and show an equivalence between robust sliced 1-Wasserstein estimation and robust mean estimation. This enables lifting statistical and algorithmic guarantees available for the latter to the sliced 1-Wasserstein setting. Moving on to computational aspects, we analyze the Monte Carlo estimator for the average-sliced distance, demonstrating that larger dimension can result in faster convergence of the numerical integration error. For the max-sliced distance, we focus on a subgradient-based local optimization algorithm that is frequently used in practice, albeit without formal guarantees, and establish an $O(\epsilon^{-4})$ computational complexity bound for it. Our theory is validated by numerical experiments, which altogether provide a comprehensive quantitative account of the scalability question.

Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances
Sloan Nietert Cornell University
Ritwik Sadhu Cornell University rs25260cornel1. edu
Ziv Goldfeld Cornell University
nietertθcs. cornell. dietert@cs.correell.co edu
goldfeed@ccoreel..cd
Kengo Kato Cornell University kk976@cornel1..om
Abstract
Sliced Wasserstein distances preserve properties of classic Wasserstein distances while being more scalable for computation and estimation in high dimensions. The goal this work is to quantify this scalability from three key aspects: (i) empirical convergence rates; (ii) robustness data contamination; and (iii) efficient com- putational methods. For empirical convergence, we derive fast rates with explicit dependence of constants dimension, subject log-concavity of the population distributions. For robustness, we characterize minimax optimal, dimension ro- bust estimation risks, and show an equivalence between robust sliced I-Wasserstein estimation and robust mean estimation. This enables lifting statistical and al- gorithmic guarantees available for the latter the sliced J-Wasserstein setting. Moving on to computational aspects, we analyze the Monte Carlo estimator for the sverage-sliced distance, demonstrating that larger dimension can result faster convergence of the numerical integration error. For the max-sliced distance, we focus on subgradient- based local optimization algorithm that is frequently used practice, albeit without formal guarantees, and establish O -() computational complexity bound for it. Our theory is validated by numerical experiments, which altogether provide comprehensive quantitative account of the scalability question.
Introduction
Sliced Wasserstein distances consider the average or maximum of Wasserstein distances between one-dimensional projections of the distributions. Formally, for 1 S.p p < 20, they are defined
Wn(mvv= [L p())do)
1/p and Wp(p,v) max (p(pfHppp.) (1) 6EB4-1
where pf is the pushforward of under the projection pa 0Jr from Rd to lR and is the uniform distribution on the unit sphere gd-1 in Rdd, Sliced Wasserstein distances were introduced in 49 as a means to mitigate the computational burden of evaluating classic Wp- which rapidly becomes excessive as d grows. Indeed, sliced distances are readily computable using the closed-form expression for Wp between distributions I (as the LP norm between quantile functions). Further,
W, and W. are metrics on Pp (IR)) and generate the same topology as classic W, [10 44 42). As
such, the sliced distances have been applied to various statistical inference and machine learning tasks, including barycenter computation [49] 9) generative modeling [18] 17 KFl 58), autoencoders 29]
differential privacy [50), Bayesian computation
41 and topological data analysis [12].
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Statistical, Robustness, and Computational Aspects of Sliced Distances
In practice, the sliced Wasserstein distances in ( must be approximated from two aspects: (i) empiri- cally estimate the population measures fu and v, and (ii) employ numerical integration or optimization methods to compute the average- or max-sliced distances, respectively. While these approximations are implemented in all but every application of sliced distances, formal guarantees concerning their accuracy are partial or even missing. For the estimation error, the question boils down to quantifying the rate at which ((n, j4) and (,,, (4) decay to O, where fin the empirical distribution of independent observations from 1 These rates are known to adapt to the low-dimensionality of the projected distribution, but previously derived rates do not seem to be sharp [35 rely on high-level assumptions that may be hard to verify in practice [47] or hide dimension-dependent constants whose characterization is crucial for understanding the scalability of sliced distances (42) More
recently, (37] showed that near-parametric rates (i.e., up to polylogarithmic factors) are achievable for the wwerage-sliced p- Wasserstein distance in the two-sample case, under the alternative (μ & v/). Limit distributions for sliced Wasserstein distances were studied in [37 21 60 59]. but these results inherently neglect constants and dependence on dimension.
Concerning robust estimation, while these aspects were studied for classic Wasserstein distances 53 [66). they were not considered under sliced Wy. Improvement in robustness to outliers due to projection-averginng was demonstrated for the Cramér-von Mises statistic in the context of multivariate two-sample testing (27). It therefore stands to reason that similar gains would emerge for Wasserstein distances, which is especially appealing since robust estimation of classic Wp in high dimensions is hard. Indeed, [46] showed that when an e-fraction of data is
45 40 30
contaminated, W, admits worst-case estimation risk //e1/2 over distributions with bounded covariance. Consequently, obtaining accurate estimates of W, from contaminated data is infeasible in high dimensions when é = (2))), which further motivates exploring robustness under slicing.
From the computational standpoint, the average-slice distance W, is typically computed using Monte Carlo (MC) integration (28 The accuracy of this approach strongly depends on the variance of the function 0 + (P /4, p/u) when @ is uniformly distributed on gd which may scale badly with d. A bound on the MC integration error in terms of this variance was provided in 42] but without further analysis to control by basic properties of the population distribution or characterize its dependence on d. Accordingly, the accuracy of the MC-based approach for computing W, stands unresolved. Recently, 43 used the conditional central limit theorem [5I] to derive a Gaussian approximation of W2 that can be computed in closed form. The accuracy of this approximation may improve as d d 00, contingent on certain weak dependence assumptions on the data distribution. A popular approach for computing the max-sliced distance is the heuristic alternating optimization procedure from 28 which, however, lacks formal convergence guarantees. More recently, computational aspects of the so-called "projection-robust" Wasserstein distance, which considers projections to k-dimensional subspaces, were explored in [48,34]] 34 25 As maximization of projected distance is a non-convex and non-smooth optimization problems, these works considered convex relaxations [48
or entropic regularization 34 25 to prove approximate convergence to a stationary point.
1.2 Contributions
The goal of this paper is to close the aforementioned gaps by (i) deriving fast empirical convergence rates for sliced distances with explicit dimension dependence; (ii) characterizing minimax optimal robust estimation rates with improved dependence dimension; and (ii) providing formal guarantees for frequently used methods for computing both the average- and max-sliced Wp. Focusing on log- concave distributions, we show that both average- and max-sliced empirical distances converge as n - m). which is sharp as it matches lower bounds from 8 Furthermore, we characterize the constant in terms of d and elementary properties of the population distribution (e.g.. mean, moments, covariance matrix). Our derivation leverages the machinery of [8] for analyzing empirical convergence of Wasserstein distances between log- log-concave measures on R. To that end, we show that log-concavity is preserved under projections and derive lower bounds on the Cheeger constant of the projected distribution. Our results elucidate scaling rates of d with n for which sigh--dimessional) empirical convergence holds true, thereby addressing the scalability of empirical estimates question.
1 'The two-sample setting, which concerns the convergence W,, Pa) and Wp Dx) towards the corre- sponding distance between the population measures, is also of interest. Despite the name "iojecctionrrouus"" these works do not explore robust estimation.

---

For robustness guarantees, we formalize minimax risk for robust estimation under sliced Wp with total variation (TV) contamination and prove that Wp enjoys dimension-free risk of 2//-11/u when clean distributions have bounded qth moments for q > p and the corruption level is at most e. Wp admits a strictly smaller risk which scales at the same rate when q = O(1). contrast, the comparable risk for classic Wp in this setting acquires an extra v factor. Using the framework of generalized resilience [6]. extend these guarantees to the finite-sample setting with adversarial corruptions, obtaining matching rates up to an added empirical approximation term. Furthermore, when p = 1, we prove equivalence between standard mean resilience [53] and resilience w.r.t. W1, allowing one to lift statistical and algorithmic guarantees for robust mean estimation to the sliced W1 setting.
Lastly, we provide formal guarantees for popular methods for computing W and Wy. which were (p. until now lacking. Our analysis relies on showing that w, + W, (p, μ4, P2y) and its pth power
are Lipschitz continuous on gd-1 and deriving sharp bounds on their Lipschitz constants. Having that, we analyze the MC estimator for the average-sliced distance, and use concentration of Lipschitz functions on the unit sphere to bound the variance of w The obtained bound reveals that higher dimension can in fact shrink the MC error when the covariance matrices have bounded operator norms. We numerically verify this surprising observation on synthetic examples.
For the max-sliced distance, we analyze the heuristic algorithm from 17 28 which utilizes alternat- ing subgradient- based optimization. We observe that in addition to being Lipschitz. continuous, the optimization objective for p is weakly convex with easily computable gradients. This lets us cast the algorithm from [17 (28) under the proximal stochastic subgradient optimization framework of [14), from which we obtain local solutions for (2) with O(E +) computational complexity. An empirical comparison with the more advanced approaches of 33 25 for computing the projection-robust Wasserstein distance (with & 1 to match the sliced framework) based on Riemannian optimization reveals that our subgradient- based method is significantly faster in terms of iteration complexity and computation time. We also consider global optimization by showing that W, computation matches the framework of (36] for Lipschitz function optimization over convex domains. Adapting their LIPO algorithm to our problem, we obtain provably consistent algorithm for computing Wp. However, the number of function evaluations that LIPO requires grows exponentially with dimension, which renders the locally optimal subgradient method preferable when dimension is large.
2 Background and Preliminaries
Notation. We use || || for the Euclidean norm in Rd. The operator norm for matrices is || Ilop- The unit sphere in R2 denoted by sd-1, _ while IBd is the unit ball. Let ((R)) denote the space of Borel probability measures on Id equipped with the TV metric || - =llav = = - (RR)), and set (TR") == {u E P(R4): [=][Idd((x)) < oo) for 1 S < co. The support of E P(R))) denoted as sp)( and we write μ S / for setwise inequality. For for a measurable map f. the pushforward of under f is denoted as fiş = o f-1, i.e., if X ~ then f(X) ~ fEu. For two numbers a and 6, we use the notation A b = min(a, b) and a V 6 = max 6). The distance between a set S and a point x in a metric (X' d) space is defined as dist(xr, S) = inf d(z, y).
Some of our results assume log-concane concavity of the population distribution. A probability measure E P(Rd) is log concavee if for every nonempty compact sets A, B C Rd and X E [0, 1]. we have 2 ((A)) A probability density function f on IR is called concccee for every x, E Rd and E [o, 1]. it satisfies f(Az + (1 A)y) 2 f(x) 1-A Any non- degenerate distribution is log-concave if and only if it has log-coneave density [1I Theorem 1.1]. For 3 E 20, let vta = et - 1 for 2 O, and recall that the corresponding Orlicz (quasi-)norm of a real-valued random variable X is defined as || == inf > 0 ([vx((())e)) < 1}. A Borel probability measure μ E P(Rd)) is called sub-Gaussian if |||XX||| < for X n.
Classic and sliced Wasserstein distances. For 1 S co, the p- Wasserstein distance between 1 E (RR) is (n,,,, v) == inf [ || (|a-y// y/ dz //p, where [1u,, v/) the set of couplings of μ and v. Wp is a metric on ()R())) and metrizes weak convergence plus convergence of ythh moments. While for the definition of W, generally amounts to an infiniteddimensional optimization problem, the expression simplifies when distributions are supported in R. This motivates
3

---

the notion of the average- and max-sliced Wasserstein distances from I Both sliced distances are also metries on Pp (IE)) that induce the same topology as W IO 44
42
To present the simple one-dimensional formulae for Wy. for j P(R and e S let (t: inf R Fu 2 7), for (0, be the quantile function. The Wp between measures on I amounts the L.
p(fa E R &Tx I f)) be the distribution function of pf y. and ' 0)
distance between their quantile functions: (p pfv) = So (T; (r; l dr. For p= 1, the expression further simplifies to W1 (1 /4, pfv) SR. (t - (r; 0) dt.
Sliced Wasserstein distances between empirical distributions can be computed via order statistics. Let Hn n-1 Σx=1 ox; and i/, == n- Ex=1 ōy; be the empirical distributions of samples X1, X and Y1, ......: : ................................ For each 0 E gd-1, denote x; OT X,, and let ((1) - S (n) (0) be the order statisties; define (0)
- Y(n) (f) analogously. By Lemma 4.2 in B we have (p p. = EE= (0) - (0)) The sliced distances W, and Wp are computed
by integrating or maximizing the above over 0 E Sd-1
3 Empirical Convergence Rates
We study empirical convergence rates of sliced Wasserstein distances for log-concave distributions. The next result gives sharp oae-s rates with explicit dependence on the effective dimension.
Theorem 1 (Empirical convergence rates), Let 1 S p < 2o and n 2 2. Suppose that μ. E P(RR)) is log-concave with covariance matrix 2 and set k rank(2)). Then.
|>>|epp V(lgg) (logg)+(mm) (w-2)
Wp (fm, m)] Sp
(2a)
1//(2p))
lop log n n1//p
E
lop VElogn
| op v (log n) (==2)
E (p m)]
(2b)
(1/(2Vp)
1/2p2))))
The proof of Theorem in Appendix D.I employs the machinery of [8] for analyzing empirical convergence of log-concave distributions on IR based on their Cheeger constant (see Appendix For
(2 we show that concavity is preserved under projections and lower bound the Cheeger constant of the projected distribution by c/ c/||š]|ap. uniformly in 0 E $d-1 For (2b), concentration and covering arguments enables approximating the expected max-sliced distance by supsess (WW,(pB p,/"), for which the aforementioned (uniform in 0) bounds are applicable.
Remark 1 (Lower bounds). The rate in (a) is sharp up to log factors over the log-concave class. Corollary 6.14 in 18) implies that E.W, (pn, H)} 2 cp(tr(2)//d)/²² (n(log n)p/2) for j = E) E P(R") and any p > 2. For p = 2, a similar computation yields E,W, 1) R (tr(E)/d log log n/n, while for p E (1,2), E,W, (in, [4)] 2 TE[W, (pnz 10) Z VT(E) /n where (EE) = à Ei= (x)) the average of root eigenvalues of Since WplPn: 11) 2 Wp 1s), this also yields lower bound for Wp. while [47] gives vd/n lower bound under the T. inequality. Remark 2 (Comparison with [7 35)). In 47% empirical rates for W, were derived under high- level Tgp(0* assumption on μ. Our rate of decay from (2b) is faster, while replacing their entropy- transport inequality condition with bogcoocaaity. The bounds for Wp in (35) Theorem 3.6] assume the projection Poincaré inequality and M, == (u|l=r|19)2/ < for >> p, and matches (2a) as q + 2o in terms of the dependence on n. However, their dependence on d is implicit through M, which typically grows prohibitively with q and d. Our log- cognccicavvty assumption is strictly stronger than the Poincaré inequality, but yields a bound in terms of ||>]|op which, for example, is constant in d
when Σ- = = Finally, we note that the bound for W, in (bb adapts to the effective dimensionality l of the data, contrasting previously available bounds that depend on the ambient dimension d.
Remark (Concentration bounds). Combining the expectation bounds from Theorem I with [35 Theorem 3.8) yields concentration bounds for empirical sliced distances. These are presented in Appendix B and are later used to derive formal guarantees for computing Wp
'A recent preprint [5]. that was posted on arXiv after this paper was submitted, shows that an improved estimate holds with high probability (compared to the convergence in expectation studied herein) for isotropic log- log-concave random vectors; cf. Equation (1.13) therein.

---

When p > 2, the rates in Theorem @ are slower than parametric. Nevertheless, in the two-sample case with μ # v, parametric rates are attainable uniformly in p for compactly supported distributions.
Proposition 1 (Parametric rates under the alternative). Let 1 S p < oo, and suppose that p. have compact supports with diam (s)t()) V diam (spt(s)())) - R. Then,
E| [ P.,) Wp(H, w)]l Sp. n 1/2 and E (Pn Pn) (H,(H, Sp.n dn 1/2
If further μs F v, then the same (parametric) rate also holds for empirical Wp and Wp.
Proposition is proven in Appendix D.2 using a comparison incquality between Wp and W1 and elementary bounds for W1 using its integral representation and KR duality.
Remark 4 (Comparison to (37). Theorem of (37] establishes bound of (log n/n) the awo-sample average- Wasserstein distance, but under bounded moment assumptions instead of compact support.
4 Robust Estimation
We examine robustness of sliced Wasserstein distances to outliers, showing that slicing enables dimension-free risk bounds that avoid poly(d) factors present for classic Wp (cf. [46).. We consider TV corruptions, where an unknown "clean" distribution j is contaminated to obtain f with || TV S 6. Upon observing fi, the goal to return distribution ((ū) such that the error (TT()), 14) is small, where D E (Wp. Wp}. Without further assumptions, this error can be unbounded, so we require that μ belongs to family P(R") encoding standard moment bounds. We consider the minimax risk for robust estimation under D with TV contamination, defined by inf T:P TBP(B-)-P(MM ((. llvse
R(D,9,c)
sup
D(T()).
Fix q > p and let ( (I))): supaese-1 14 - p=)) S 0²) contain all distributions whose projections have bounded central qth moments. In particular, G2(a) = { E P2(RR) [x S o.. The next theorem characterizes minimax robust estimation risk over this class.
Theorem (Population-limit robust estimation). Fix S pp- < q, a 2 0, and 0 < S 0.49 We have R R(W,. (,) (1 (1 A p/d) 1// and R(Wp. (g(o), x //- T/o
Note that the / (1 v d/ q) p/d) prefactor in the first bound is always less than 1. The proof in D(u, v), a modulus of continuity that captures the sensitivity of D to small perturbations that preserve membership to the clean family. We employ techniques based on generalized resilience [61 (55) to relate this modulus to similar quantities arising in the robust estimation of pth moment tensors, giving the above rates. The procedure that achieves these rates projects the observed contaminated distribution onto the corresponding family of clean distributions in TV norm.
Appendix D.4 controls the risk via (e)).
Remark 5 (Comparison to [46)). A related framework [46] considers robust estimation of Wp under input measure contamination. They obtain a rate of o /e using similar methods under the weaker Huber t-contamination model when q = 2 (see Corollary therein). Evidently, slicing elimi- nates a v factor from the minimax estimation risk. In Appendix D.4 we interpolate between these regimes, proving that k-dimensional sliced distances admit risks bounded by a ovIV e/v-//111/u,
Theorem 2 characterizes population-limi robust estimation, i.e., when data is abundant. The next result, proven in Appendix D.3) extends to the finite-sample regime. For a radius R > 0, we write μR denote the distribution of X ~ conditioned on ||X par < R.
Proposition 2 (Finite-sample robust estimation). Fix 1 S P < 4, O. and 0 < S 0.49. and ler D E (W,, Wp). Then there exists a radius R x vd/c and a procedure which, given (RP + c (oo(d//)) samples with least (1 e)n drawn i.i.d. from any μ E Gy(a), returns E P(Rd) such that D(v, p) & R(D, (g), + E { (((n)) Un)] with probability at least 5
"The upper bound on of 0.49 can be substituted with an any constant bounded away from 1/2. precise high- brgbbbrobybllity bounds and extension to the strong contamination model.
SSee Appendix D.5 D.pendix(DSS
5

---

Evidently, the finite-sample error bound comprises the copulation-limin robust estimation risk (which necessary) plus the empirical estimation error associated with the truncated distribution μnn. The lower bounds on n. ensures that the empirical distribution (MR), satisfies the same generalized resilience property appearing in the population- analysis. The truncated empirical convergence term can typically be bounded by the corresponding untruncated version. For example, when (2) is log-concave and D Wi, we can bound this term by ( log + a / n//gn)/ which follows from Theorem and the fact that μR is also log-concave with | llop I 1 S for any R >
When = 1, we prove in Appendix D.6la precise connection to resilience, a sufficient condition for robust mean estimation, which may be of independent interest.
Proposition 3 (Connection to mean resilience). For 0 S L, μ E (I is (p, (pre)sreiilieet, i.e.
| S p for all VS -- if and only if
for all v VS
This suggests borrowing from the existing family of robust mean estimation algorithms, primarily developed for the bounded covariance setting (q = 2). Appendix [.7] we inspect an efficient spectral reweighting procedure and apply it for both W, and W, when 1 1 2
Proposition (Efficient computation via spectral reweighting). If S p < q = 2 and 0 < c 1/12, the guarantee of Proposition 2 is achieved by an )(nd)) )-ime spectral reweighting algorithm.
5 Formal Computational Guarantees
The computational tractability of empirical sliced Wasserstein distances relies on the simplified expressions for W, between distribution on R. However, even then, evaluating W,, and W, requires computing the average or the maximum of one-dimensional distances over projection directions E $d-1. This section provides formal guarantees for two such popular computational methods: MC integration for W, and alternating subgradient-bar based optimization for Wp- Our analysis relies on the observation that (f) := (p and its pth power are Lipschitz functions on g
Lemma (Lipschitz continuity). The functions Wp and wp are Lipschitz with constants bounded by TP A sup [[u
and MP = 3322 sup (//000 respectively. 8684
BES4
Lemma [] proven in Appendix D.8) sharpens the Lipschitz constants derived in [4 Lemma 2], which correspond to bounding [fTzl by ||>|| in the above expressions. The projected moments ((/fT=(())/> typically has a milder dependence on d than (P) which is crucial for the subsequent analysis.
5.1 Average-Slicing Monte Carlo Integration
The typical approach for computing the integral over the unit sphere in W, is MC averaging. Fix Jr, V E PP,((Re (TR)) and let fa, and in be the associated empirical measures. Take θ ~ Unif(Sū-1) and consider i.idd copies thereof θ 1, ..... Om. The MC based estimate of W is given by
m
m
Wh MC = m
(p 9 Pm. P: P
(
where (0) -... X (0) is the order statistics, which is readily evaluated using sorting algorithms with (n log average/worst-case complexity (e.g., quick_sort or berge_sort))
The next result bounds the effective error of W in approximating the population distance Wg(n, v).
Proposition (Monte Carlo error bound). Let 1 S p < oG, and assume μ.v E (P((R) are log-concave with covariance matrices yn and Σ,. respectively. The MC estimate above satisfies
Sn || wz P + 1t 1862 /2 +| 1o/2
p/2
E, 10%6 + +11 +152211863) (log n) (m==))
Wh MC (WD(WW v)
V Vmd
n(pa2)/2
where the hidden constant depends only p.

---

Algorithm 1 Projected subgradient method for v
Input: 0, E IB a sequence {ar)e20 C IR,,, and iteration count T
for t = .,..., , do
Calculate & E 0mm)(0)) Set Ø(+1 Projns (tt (
Sample t" E {o..... T according to the probability distribution P(t" =t) = Eizo
Return Tt-"
Proposition iis proven in Appendix D.9 by separately bounding the MC and the empirical approxima- tion errors. For the former, we use the Lipschitzness of wp on $d-1 show that it concentrates about its median. This enables controlling the variance of L Σn ( which, in turn, bounds the MC error. For the empirical approximation error, we reduce the analysis to one-sample empirical conver- gence under WE for measures on R and obtain explicit rates by drawing upon the results of (8)
Remark 6 (Comparison to 42)). Error bounds for the MC estimate WMC were also provided in (42).
but their results differ from ours in two key ways: they use implicil empirical approximation bounds and leave their MC error in terms of Var( (arlw](( (e)) without further analysis. Proposition 3 provides
an explicit convergence rates and bounds the said variance in terms of basic characteristies of the population distributions, providing precise rates in n, m, d, and p.
Remark 7 (Blessing of dimensionalityy. A cruder approximation of the Lipschitz constant that stems from (4 Lemma 2| would yield |||==|| + v||x:|| as the numerator of the first term. However, such a bound can have a significantly worse dimension dependence. Indeed, for instance, j and are both mean zero log-concave with identity covariance matrices, then =|p + v||=[|? is (2(p//2) while the numerator in our bound is Oa(1). For such μ and v, the bound decays to 0 as d -
5.2 Max-Slicing: Subgradient Methods and the LIPO Algorithm
Maximization of projected Wasserstein distance is a non-convex and non-smooth optimization problem. Therefore, past works that studied k-dimensional subspace projections relied on convex relaxations [48] or entropic regularization 34 25 to prove approximate convergence to a stationary point. We show that regularization is not needed the one-dimensional case of W, by proving an O(E=A) computational complexity bound for convergence stationarity of the simple subgradient- based optimization routine from [8 17]. We also note that global solutions are attainable via generic algorithms for optimizing Lipschitz functions, but with rates that deteriorate exponentially with d.
Local guarantees for subgradient methods. First note that we may relax the W, optimization domain from gd-1 the unit ball Bd without changing the value (indeed, for any 0 E Bdd, (0) [0/ [0])). Together with [8] Lemma 4.2], we express the empirical max-sliced distance as:
(_ Σ 10 (X(c))) 4=
W 0n) max 6 (E)T()n.0.)
min
E. [I0 - Y)
min max BE dES.
where S,, is the symmetric group. Here we used the fact that the optimal coupling is given by the order statistics, and hence it suffices optimize over permutations. Denote p(o, == Σi=1 1 (X, Yo())) and (0) == max p(a, 0). The subgradient of di has the closed form (0) = Conv ((Opp(a",0)
a* argmaaxess, Ó(a, 0))). We can compute optimal a² S, via order statistics and evaluate the corresponding subgradient vector in @ap(o*. 0). This gives direct access to subgradients of wy without approximation arguments or regularization.
A heuristic description of Algorithm [ was given in 28 17 but without formal guarantees. Proposi- tion below can be viewed as closing that gap by providing said guarantees. particular, for p = the objective function w is weakly convex 34 Lemma 2.2] and Lipschitz (Lemmal) 1 Together with the computable subgradients, this enables applying the proximal stochastic subgradient method from [14. Algorithm describes the adaptation of this method to our problem, after replacing the stochastic subgradient sampling step therein with the direct subgradient calculation described above. The following proposition provides convergence guarantees for Algorithm]
7

---

Projection complexity, 1000
Projection complexity.
1000
10-1
d=2
d=
MC lsstimatee error
MC estimatee error
102
d
d-50
d= 10
d= 100
d=2
5=5
d=
10-7
d=
== 100
10
10
10a
10a
10
10 projections (m)
10a
projections (m)
Sample complexity, m
1000
Sample complexity,
1000
10a
d-2
d-20
d
d-
MC esstimate error
d=5
d=50
MC estimate error
d=5
d=
10
d=10
d=100
d= 10
d=
10-2
10
10a
10a samples
10a
10a
10 samples
10a
(a) MMC
W (1, v)
under Model (I).
(b) WMC (2( v) under Model (2).
Figure 1: Projection and sample complexity for W2.
Proposition (Computational complexity of subgradient method). Fix any >> O and n, d E N such that d 2 [logn)² Let p. E P22 be log-concave with covariance matrices Σn and Ev, respectively, and consider M2,, defined in Lemmaa [ Then, there exist universal constants
C1, C2, C3, C1 such the following holds: Algorithm for the objective (p() w + ôgs, where
Sga = -oo with step size a4 X V2+1' outputs a point 0y. that is close to statissaay
point 0", in the sense that Ex- -110-~0--110 S for Pu.v = I| souu-vxl'' vx+12+ (IEElllop + ||Exllop): and dist (0, (w)((0)) S 6, within a number of computations N S Cp, In log n, where Cp,,v capj.u (M cs (I) [[p))) with probability at least
ca n
Proposition iis proven in Appendix D.10 via the complexity bound from [14 Corollary 2]. As the algorithm is tuned for the empirical objective (8), the bound depends on the random Lipschitz and weak convexity constants M, = 4 supeess- (P,, |0Tx|² +0T,00== and Pn. = 2 max,,==1..... I|X,- 1111a. We use concentration bounds for M, and p.. to obtain the deterministic bound above.
Remark 8 (Comparison to past works), Computation of projection- robust Wasserstein distances (i.e.,
when projections are k-dimensional) was studied [48] and (34 25 using a convex relaxations and entropic regularization, respectively. A similar O) convergence rate is proven in (34) for their regularized method. Proposition shoos that regularization not necessary to achieve this rate when projections one-dimensional. The result of (34) was improved to O(E-3) 3) in (25) using Riemannian block coordinate descent (still with entropic regularization) While this rate is faster than in P Proposition 6 our goal was to couple the simpler and abundantly used subgradient ascent approach with formal guarantees. In addition, the next section shows that empirically, our algorithm much faster than those of 34 25 for the Wa in terms of complexity and computation time.
Remark 9 (The nou-quadrttic case). For p 2, we still have Lipschitzness of the objective in 0 (Lemma Zy. Recent work on finding stationary points for non non-smooth, non-corvex, Lipschitz functions, such as [15%. provide convergence guarantees for these cases. These guarantees appear to be of the same c 1/4 order (cf. [SS] Theorem 3.2]), but we leave a full exploration for future work.
Remark 10 (Global guarantees via LIPO). We can attain global optimality, i.e., compute W (p Da) itself. via the LIPO algorithm (36]. LIPO performs global optimization of Lipschitz.uunctios functions over convex domains based on function evaluations, which are reudily accessible in our problem via sorting. In Appendix C adapt LIPO to the max-sliced distance, prove consistency, and derive its complexity. While this approach attains global optimality, the number of evaluation grows exponentially with dimension. Hence, the subgradien method described above is preferable when dimension is large.
8

---

Iteration Complexity for W; Algorithms
Computation Time for W; Algorithms
2.2-
subgredienn
12-
SU0g adlont ascent, d-50
2.0-
10
RANED d=20
aubgredien ascert, d=200
W5 aiment
RABCO d-50
b.bgrzdinn ascent, d-20
RADED, d=100
S. S.bgradeen ascent, d-50
RAGAS d=20
1.6-
subgradien: ascent, 1-000
Uime elepsed
6
RAGAS, C-50
RARED, d-20
RAGAS, 6-100
1.4
RABCD, d-50
RABLD, d0100
1.2
RAGAS, c::0
RAGKS,
2-
25
50
75
100
125
150
175
200
25
50
100
125
150
175
200
steps
aaccent stops
Figure 2: Errors and runtime versus step count for W2 computation algorithms.
Empirical Results
Projection and sample complexity for W We validate the convergence rates of the MC-based
estimate of W, predicted by Propositions 5 in the following two models: (1) μ = (0, Ia), v = 0.5. Ia) + 00, Ia + 0.51.11/dh d). and (2) μ (0, Ia), v/ (2 Ia), where 1a is vector with all coordinates equal to 1. For Model (1), Proposition predicts decreasing error with dimension, and inverse square root decay in number of projections and number of samples. For Model (2), on the other hand, the errors should increase with d for sufficiently large n. Plots of the projection and sample complexities for each model (averaged over 100 runs) are given in Figure at the top of the previous page, and are in line with the above discussion and our theoretical results. Additionally, confidence bands are plotted representing top and bottom 10% quantiles among 20 bootstrappped means from the same 100 runs An additional experimental setup, comparing 10 component normal mixtures with different means and variances, can be found in Appendix F
Comparison of W2 algorithms. We compare the performance of the subgradient- Algorithm and the Riemannian optimization methods of [34 25]. Consider the setup from [25] Section 6.1].
where = Uni, and v = Tap, with T(x) = I Σ sign(z;)) Jes, is the fragmented hypercube distribution with k'' 10. Figure 2 shows the errors and runtime by step count of
Algorithm D (with a constant step size) and the Riemannian algorithms from [4 25 (abbreviated
RAGAS and RABCD, respectively) for different ambient dimensions. For these algorithms, used the code from
com wtw.e/uw...oommmuungggg./// /PR__RBD with their default choice of parameters; we also tried optimizing these parameters but the observed trends remained the same. Sample size is fixed at = 500 and computation times are averaged over 10 trials. Evidently, the subgradient ascent algorithm converges significantly faster and within fewer iterations than the other two methods, for all considered values of d. Despite our O(c=4) iteration complexity bound, which slower than the best known rates (25). this favorable empirical performance may be attributed to the fact that Algorithm I relies on the cheap sorting operation, as opposed to the burdensome computation of regularization operations in [4 25 It may also the case that our bound can be improved, which we plan to explore in future work.
Robust estimation. To support Proposition 3] we perform robust estimation via a standard iterative filtering algorithm developed for mean estimation [19]. For d E {10, 20.... 200),. we take = 10de 2 samples, with (1 e)n drawn i.i.d. from (0, Ia) and from a product noise distribution used in 19 with 0.1. For each d, iterative filtering returns a candidate subset of clean samples, and Figure (left) compares these subsets to the true clean samples both in W1 (estimated via projected subgradient ascent) and in &, distance between means, Note that the error in the latter never exceeds that in the former by more than factor of 2 (Proposition Datiiionnimmpeeer implies that mean and W,, risk are equivalent up to constant factors). In Figure 3 (right), we set (1 - e)ōg + Unif( / d/e 1d-1) with null contamination, and take n, ranging as before. this case, since many samples are 0, we can efficiently compute a lower bound on classic W1 between the filtered and clean samples in high dimensions. As predicted by Theorem 2 we observe the vd separation in estimation error between Wi and W, In this case, only errors for the filtered samples are plotted, since the unfiltered samples have no contamination. See Appendix [F] for additional experiments on generative modeling with contaminated datascts, along with full details and code for all experiments.

---

Robust Estimation Error: W. vs. Difference byt Means
Robust Estimation Error: 17 vs. W/
crior (fite od)
crror
evcess error (F. (iahinn
2.5
crror (comusted)
excess error distata)))))
12-
W. urror (ower bound)
22 mean (comupted)
2.0-
10-
6-
1.0-
0.0
25
75
100
125
150
175
200
25
50
75
100
125
150
175
200
(d)
Figure 3: Robust estimation for the iterative filtering estimate in scenarios: (left) comparing W1 with difference between means and (right) comparing W to W Mean and W errors are hounded as - co, while W1 error scales like vd.
7 Summary and Concluding Remarks
This paper provided quantitative study of the scalability of sliced Wasserstein distances high dimensions. Three key aspects were covered:
Empirical convergence rates: We established sharp, dimension- free rates for W, and W,, with explicitly characterized dimensioo-ddependent constants. Our bounds reveal the interplay between the number of samples n, dimension d, and the order of the distance p.
Robust estimation: The minimax optimal robust estimation rate of W, and W under contami- nation level e, was characterized as O(aee 0/-1)/)))//) This rate is dimension- free and improves upon corresponding results for Wp by a /d factor. We showed that robust estimation of W, is equivalent to robust mean estimation, which enables lifting statistical/algorihmiic results from means to W1. Computational guarantees: The error of MC-based estimator for W, was derived, showing that it can improve - oo, depending on the growth-rate of the mean and the operator norm of the covariance matrix. For Wp. p, we analyzed the subgradient-basee based local optimization algorithm from and proved (A) complexity using Lipschitzness and weak convexity of the objective.
28
17
In all three aspects, the benefit of slicing in terms of dependence on dimension was clearly evident, thus providing rigorous justification the perceived scalability of sliced distance. Going forward, we plan to pursue improved complexity bounds for the subgradient ascent algorithm for computing W2. (6 as our empirical results suggest it converges faster than Proposition predicts. We are also interested in understanding conditions on /t, v under which faster global guarantees for W, can be provided, e.g., by precluding the existence of nontrivial local optima for (p i Ar, p..) on gd-1, or matching the conditions (36) Theorem 15], which results in polynomial and even exponential rates for LIPO. Extensions of our results to coojection-obbus" Wasserstein distance, which considers projections to k-dimensional subspaces, are interest, aiming to understand the effect of & on the results.
Acknowledgments and Disclosure of Funding
The authors thank Jason Gaitonde for helpful discussion high-dimensional probability. S. Nietert was supported by NSF Graduate Research Fellowship under Grant DGE-1650441. Z. Goldfeld is partially supported by NSF grants CCF-1947801 CCF-2046018, and DMS-2210368, and the 2020 IBM Academic Award. K. Kato is supported by NSF grants DMS-1952382 DMS-2014636 and DMS MMMS-22
10

---

References
[1] R. Adamezak, R. Latala, A. E. Litvak, A. Pajor, and N. Tomezak- Jannzaa--aegermann. Tail estimates for norms of sums of log-coneave random vectors. Proceedings of the London Mathematical Society, 108(3);600-63) 6370006-3,2260 2014.
[2] R. Adamezak, A. Litvak, A. Pajor, and N. Tomezak-Jaegermane Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles. Journal of the American Mathematical Society, 23(2):535-561 2010.
[3] M. Arjovsky, S. Chintala, and L.. Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning (ICML), 2017.
[4] Y. Balaji, R. Chellappa, and S. Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[5] D. Bartl and S. Mendelson. Structure preservation via the Wasserstein distance. arXiv preprint ar arXiv:2209.07058 2022.
[6] E. Bayraktar and G. Guo. Strong equivalence between metrics of Wasserstein type. Electronic Communications in Probubility, 26:1-13, 2021.
[7] S. G. Bobkov and C. Houdré. Isoperimetric constants for product probability measures. The Annals P Probubility, 25(1):184 205, 1997.
[8] G. Bobkov and M. Ledoux. One-dimensional empirical measures, order statistics, and Kantorovich transport distances. American Mathematical Society, 2019.
[9] N. Bonneel, J. Rabin, G. Peyré, and Pfister. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 1(51):22-45, 2015.
[10] N. Bonnotte. Unidimensional and evolution methods for optimal transportation. PhD thesis, Paris 11, 2013.
[11] C. Borell. Convex measures on locally convex spaces. Arkiv för Matematik, 12(1-2):239-252 1974.
[12] M. Carriere, M. Cuturi, and S. Oudot. Sliced Wasserstein kernel for persistence diagrams. In International Conference Machine Learning (ICML), 2017.
[13] Y. Chen. An almost constant lower bound of the isoperimetric coefficient the KLS conjecture. Geometric and Functional Analysis, 31(1):34 61, 2021.
[14] D. Davis and D. Drusvyatskiy. Stochastic subgradient method converges the rate O(k 0kk-1/4) on weakly convex functions. arXiv preprint arXiv:1802.02998. 2018.
[15] D. Davis and D. Drusvyatskiy. A gradient sampling method with complexity guarantees for general Lipschitz functions. arXiv preprint arXiv:21 /2.06969, 2021.
[16] L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2916):1111142, 2012.
[17] I. Deshpande, Y.-T. Hug, R. Sun, Pyrros, N. Siddiqui, S. Koyejo, Zhao, D. Forsyth, and A. G. Schwing. Max-sliced Wasserstein distance and its use for GANs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
[18) I. Deshpande, 7. Zhang, and A. G. Schwing. Generative modeling using the sliced Wasserstein distance. In Proceedings of the IEEF Conference Computer Vision and Pattern Recognition (CVPR), 2018.
[19] I. Diakonikolas, G. Kamath, D. M. Kane, Li, A. Moitra, and A. Stewart. Being robust (in high dimensions) can be practical. Proceedings of the International Conference on Machine Learning (ICML), 2017.

---

[20] D. L. Donoho and R. C. Liu. The "Automatic" Robustness of Minimum Distance Functionals. The Annals of Statistics, 16(2):552- 586, 1988.
[21] Z. Goldfeld, K. Kato, G. Rioux, and R. Sadhu. Statistical inference with regularized optimal transport. arXiv preprint arXiv:2205.04223 2022.
[22] Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training of Wasserstein GANs. In Advances in Neural Information Processing Systems (NeurlPS), 2017.
[23] A. K. Gupta and S. Nadarajah, editors. Handbook of beta distribution and its applications. volume 174 of Statistics: Texthooks and Monographs. Marcel Dekker, Inc., New York, 2004.
[24] S. B. Hopkins, J. Li, and F. Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS), 2020.
[25] M. Huang, S. Ma, and L. Lai. A Riemannian block coordinate descent method for computing the projection robust Wasserstein distance. In International Conference on Machine Learning, pages 4446 4455. PMLR, 2021.
[26] R. Kannan, Lovász, and M. Simonovits. Isoperimetric problems for convex bodies and localization lemma. Discrete & Computational Geometry, 13(3):541-55, 1995.
[27] I. Kim, S. Balakrishnan, and L. Wasserman. Robust multivariate nonparametric tests via projection averaging. The Annals of Statistics, 311-33344, 2020.
[28] S. Kolouri, K. Nadjahi, U. Simsekli, R. Badeau, and G. K. Rohde. Generalized sliced Wasser- stein distances. arXiv preprint arXiv: 00440,00444..... 2019.
[29] S. Kolouri, P. E. Pope, C. E. Martin, and G. K. Rohde. Sliced Wasserstein auto-encoders. In International Conference Learning Representations, 2018.
[30] K. Le, H. Nguyen, Q. Nguyen, N. Ho, T. Pham, and H. Bui. On robust optimal transport: Computational complexity, low-rank approximation, and barycenter computation. arXiv preprint arXiv:2102.06857, 2021.
[31] M. Ledoux. Concentration of measure and logarithmic Sobolev incqualities. In Seminaire de probabilites XXXIII, pages 120-216. Springer, 1999.
[32] M. Ledoux and M. Talagrand. Probability in Banach Spaces: isoperimetry and processes. volume 23. Springer Science & Business Media, 1991.
[33] Y. T. Lee and S. S. Vempala. The Kanan-LLvvaz--Smonovis conjecture. arXiv preprint arX.v:1807.03465. 2018.
[34] T. Lin, C. Fan, N. Ho, M. Cuturi, and M. Jordan. Projection robust Wasserstein distance and Riemannian optimization. Advances in neural information processing systems, 33:9383-9397, 2020.
[35] Lin, Z. Zheng, E. Chen, M. Cuturi, and M. Jordan. On projection robust optimal transport: Sample complexity and model misspecification. In International Conference on Artificial Intelligence and Statisties, pages 262-270. PMLR, 2021.
[36] C. Malherbe and N. Vayatis. Global optimization of Lipschitz functions. In International Conference on Machine Learning, pages 2314-2323, PMLR, 2017.
[37] T. Manole, S. Balakrishnan, and L. Wasserman. Minimax confidence intervals for the sliced Wasserstein distance. Electronic Journal of Statistics, 16(1):2252-2345. 2022.
[38] O. Marchal and Arbel. On the sub- caab-aaussinityy of the beta and Dirichlet distributions. Electron. Commun. Probab., 22:Paper No. 54, 14, 2017.
[39] E. Milman. On the role of convexity in isoperimetry, spectral gap and concentration. Inventiones mathematicae. 177(1):1-43, 2009.
12

---

[40] D. Mukkherjee, A. Guha, J. Solomon, Y. Sun, and M. Yurochkin. Outlier-robust optimal transport. In International Conference on Machine Learning (ICML), 2021.
[41] K. Nadjahi, V. De Bortoli, A. Durmus, R. Badeau, and U. Şimşekli. Approximate Bayesian computation with the sliced-Wasseree Wasserstein distance. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5470-5474, IEEE, 2020.
[42] K. Nadjahi, A. Durmus, L. Chizat, S. Kolouri, S. Shahrampour, and U. Simsekli. Statistical and topological properties of sliced probability divergences. Advances in Neural Information Processing Systems, 33:20802-2088 12, 2020.
[43] K. Nadjahi, A. Durmus, P. E. Jacob, R. Badcau, and U. Simsckli. Fast approximation of the sliced- Wasserstein distance using concentration of random projections. Advances in Neural Information Processing Systems, 34, 2021.
[44] K. Nadjahi, A. Durmus, U. Şimşekli, and R. Badeau. Asymptotic guarantees for learning generative models with the sliced-Wassersteen Wasserstein distance. arXiv preprint 19X6::990.0045//// 2019.
[45] J. S. Nath. Unbalanced optimal transport using integral probability metric regularization. arXiv preprint arXiv:2011.05001, 2020.
[46] S. Nietert, R. Cummings, and Z. Goldfeld. Outlier-robust optimal transport: duality, structure, and statistical analysis. In International Conference on Artificial Intelligence and Statisties, 2022.
[47] Niles- Weed and P. Rigollet. Estimation of Wasserstein distances in the spiked transport model. arXiv preprint 199.0:19,, 2019.
[48] F.PP. Paty and M. Cuturi. Subspace robust Wasserstein distances. In International Conference on Machine Learning, pages 5072-5081. PMLR, 2019.
[49] J. Rabin, G. Peyré, Delon, and M. Bernot, Wasserstein barycenter and its application to texture mixing, In International Conference Scale Space and Variational Methods in Computer Vision, pages 435-446. Springer, 2011.
[50] A. Rakotomamoniy and R. Liva. Differentially private sliced Wasserstein distance. In Interna- tional Conference on Machine Learning, pages 8810-8820. PMLR, 2021.
[51] G. Reeves. Conditional central limit theorems for gaussian projections. In 2017 IEEE Interna- tional Symposium on Information Theory (ISIT), pages 3045-3049 IEEE, 2017.
[52] M. C. Spruill. Asymptotic distribution of coordinates high dimensional spheres. Electron. Comm. Probab., 12:234-247,22 2007.
[53] G. Staerman, P. Laforgue, P. Mozharovskyi, and F. d' Alché-Bucc. When OT meets MoM: robust estimation of Wasserstein distance. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
[54] J. Steinhardt. Robust learning: Information theory and algorithms. Stanford University. 2018.
[55] Steinhardt, M. Charikar, and G. Valiant. Resilience: criterion for learning in the presence of arbitrary outliers. In A. R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge. MA, USA, volume 94, pages 45:1- 45:21, 2018
[56] A. W. van der Vaart and A. Wellner. Weak convergence. In Weak convergence and empirical processes, pages 16-28. Springer, 1996.
[57] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
13

---

[58] J. Wu, Z. Huang, D. Acharya, W. Li, Thoma, D. P. Paudel, and L. V. Gool. Sliced Wasserstein generative models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 3713-3722, 2019.
[59] J. Xi and J. Niles-Weed. Distributional convergence of the sliced Wasserstein process. arXiv preprint arXiv:2206.001166 2022.
[60] X. Xu and Z. Huang. Central limit theorem for the sliced I-Wasserstein distance and the max-sliced I-Wasserstein distance. arXiv preprint arXiv:2205.1400 2022.
[61] B. Zhu, J. Jiao, and Steinhardt. Generalized resilience and robust statistics. arXiv preprint arXiv: 099.99999900.... 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We state all assumptions needed
for our results and compare them to existing work in several remarks.
(c) Did you discuss any potential negative societal impacts of your work? [No] We provide
a statistical analysis of an existing framework; applications of sliced optimal transport
have societal implications but these are not addressed by this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The result of each statement includes all needed assumptions,
(b) Did you include complete proofs of all theoretical results? [Yes] Yes, see Appendixes
A-D for all proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL.)? [Yes] See Appendix for experimental details and code.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6 and Appendix for details.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Yes, for experiments with significant statistical variation.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix E for details.
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Section 6 and Appendix E.
(b) Did you mention the license of the assets? [No] The code which used was not accompanied by licenses.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We link to full code for experiments in Appendix F.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] Our experiments use only synthetic data.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Our experiments use only synthetic data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "w-KgCZpQHtj", "reviewer": "Reviewer_ULQb", "summary": "The Sliced-Wasserstein distance (SW) has been deployed in various machine learning applications over the past few years as a computationally efficient alternative metric to the Wasserstein distance. Due to its reported empirical success, recent work have studied the theoretical properties of SW to further motivate its use. For instance, SW has been shown to retain some important topological properties of the Wasserstein distance while yielding a dimension-free sample complexity, which justifies its efficiency on high-dimensional settings. On the other hand, a different line of work identified the limitations of SW and proposed solutions, including alternative metrics inspired by SW, such as the maximum Sliced-Wasserstein distance (max-SW). \n\nThis paper is a theoretical analysis of SW and max-SW, which refines existing guarantees for these metrics and explores unsolved questions. The contributions are described more precisely below.\n\n1) Convergence rates of empirical distributions to the \"true\" distributions under SW or max-SW are derived (Section 3), assuming the true distributions are log-concave (Theorem 1) or supported on compact domains (Theorem 2). Empirical convergence rates under SW or max-SW have already been established in the literature under different assumptions. The authors argue that, as compared to prior work, their rates are faster or reflect more explicitly the influence of the data dimension (Remarks 1 and 2).\n\n2) The robustness of SW/max-SW to outliers is also studied (Section 4): the minimax risk for robust estimation under SW/max-SW for a corrupted distribution (according to \"total variation contamination\") is characterized (Theorem 2, Corollary 1), under assumptions on the corruption level and on the moments of the projected distributions. The authors state their result is another confirmation that SW does not suffer from the curse of dimensionality, since the minimax risk does not contain a factor of $\\sqrt{d}$ as opposed to the Wasserstein distance (Remark 4). Additionally, the \"resilience\" condition (which bounds the difference between the means of $\\mu, \\nu$ for $\\nu \\leq \\frac{\\mu}{1-\\varepsilon}$) is shown to be equivalent to controlling max-SW$(\\mu,\\nu)$ (max-SW is of order 1) for $\\nu \\leq \\frac{\\mu}{1-\\varepsilon}$ (Proposition 2). This allows the authors to extend algorithmic guarantees for robsut mean estimation (under the resilience condition) to robust estimation with max-SW.\n\n3) Then, guarantees on the errors induced by the approximation of SW or max-SW are established (Section 5). First, the error associated to the Monte Carlo estimation of SW is bounded, assuming the distributions are log-concave -- which, similarly to Section 2, helps derive rates that are explicit in the parameters of the problems ($n, m, d, p$), as opposed to existing error bounds in related work (Remark 5). Then, convergence guarantees on a subgradient method used to approximate max-SW of order 2 (Algorithm 1) are derived (Proposition 4), provided $log(n) \\leq \\sqrt{d}$ and $\\mu, \\nu$ are log-concave. As discussed in Remark 7, some algorithms have been proposed in the literature and shown to be faster, but they are less used than the subgradient method and slower in practice (Figure 2). Note that these results rely on the fact that the Wasserstein distance between projections of distributions (as a function of the projection direction) is Lipschitz (Lemma 1).\n\n4) Finally, the authors conduct a set of experiments on synthetic data in order to illustrate their theoretical findings (Section 6).", "questions": "Besides adding a discussion to [*] \"Minimax Confidence Intervals for the Sliced Wasserstein Distance\" (Manole et al., 2019), I encourage the authors to clarify the following points. \n\nTheorem 1:\n- Equation (2a): according to the proof, if I am not mistaken, $log(n)$ should be $log(n)^{1/2}$.\n- Proof of Lemma 3(ii): For $p \\geq 2$, $n^{1/2}$ is missing when bounding the RHS, since $|| u - u' ||_1 \\leq n^{1/2} || u - u' ||_2$ (to verify).\n\nRemark 2: the case $\\Sigma = I_d$, whose norm indeed does not depend on $d$, is not realistic since components of a data point are more likely to depend on each other. Could the authors provide a more realistic example to illustrate the dependence on $d$ in their rates?\n\nProposition 1: \n- Such rates were already established in the literature (e.g., [Section 4, 34] or [*]). Could the authors precise what is new in Proposition 1 as compared to prior work?\n- Proof (end of Appendix D.2): it is unclear to me why the rates for SW$^p$ (or max-SW$^p$) can be applied to SW (or max-SW): how to get rid of $b^{1-p}$?\n\nRemark 4: \"slicing eliminates a $\\sqrt{d}$ factor\" This is true for max-SW, but not for SW whose minimax risk can contain such factor depending on the value of $d/q$ and $p/d$ (see Theorem 2). Could the authors clarify this aspect?\n\nProof of Lemma 1 (Appendix D.8): \"the last step uses the optimal transportation cost formulation of $W_p$\", this step is confusing to me. Could the authors explain why they can bound the sum of one-dimensional Wasserstein distances by the product of $||\\theta_1 - \\theta_2||$ and a sup over $\\theta$? \n\nProposition 3: Could the authors confirm if the second term in the RHS is in $n^{p/2}$ when $p > 2$? It seems like it should be in $n^{-1}$ according to the proof of Proposition 3 and Theorem 1.\n\nSection 6, \"Projection and sample complexity\": The increase of the errors with $d$ for Model (2) is not obvious on Figure 1(b). I think the authors should give more detailed explanations on why this behavior is expected (for both models) given Proposition 3: the provided explanations are quite vague (due to a lack of space, I guess).\n\nMinor comments:\n- Typos: l.114 \"For for\", l.122 \"nongenerate\", l.211 $\\mathcal{R}^d$, Algorithm 1: in the title, $\\tilde{\\omega_2}^2$ but in the loop, $\\tilde{\\omega}_p^p$, l.290 \"in not necessary\", l.383: \"providing rigorous justification the perceived scalability\"\n- l.91: the definition $\\omega_p^p$ should be precised here. Same for $\\omega_2(\\theta)$ (l.98)\n- The following operators should be defined: $\\lesssim_p$, $poly(d)$, $\\asymp$, $Conv$\n- l.187: $\\sigma$ is already used to denote the uniform distribution on the sphere.\n- l.219: Unclear definition for $\\delta_{\\mathbb{B}^d}$\n- The uncertainty of the empirical results is not reported and the authors say in Appendix E that error bars will be added in the final version of this paper. This aspect is important and should have been included in this version.\n- Appendix D.9: Add a reference for the dual form of $W_p^p$\n\n", "limitations": "The limitations of the theoretical results are adequately discussed throughout the paper. The potential negative societal impact is not addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work adequately addresses some important theoretical questions raised by the increasing use of Sliced-Wasserstein distance and its variants in machine learning applications. The contributions are mostly theoretical and have clear practical implications: they help quantify the efficiency and robustness of SW and max-SW according to the problem setting (i.e. in terms of data dimension and nature of distributions), or evaluate the quality of the traditional estimates of SW or max-SW. In that sense, I believe this work is significant and useful. \n\nI find the paper very well written and clear. I strongly appreciate that the authors put effort into providing interpretations on their theoretical findings as well as discussions on their advantages and limitations over prior related work. Overall, the contributions of this paper, namely the theoretical results, their proofs and their empirical illustration, look sound to me. The proof techniques do not seem particularly original (e.g., they are direct consequences of existing results on one-dimensional Wasserstein distances derived in [5] or consist in assuming a specific structure for the distributions, i.e. log-concavity, a common practice in statistics), but they provide answers to relevant questions on SW in a simple and elegant manner.\n\nThe main weakness of this paper is that it is too dense. I am quite familiar with the questions addressed in this work and related work, which strongly helped me understand the main conclusions of the contributions, but I could not thoroughly check all the proofs in the supplement document. Besides, some aspects of the paper are unclear to me: more details are given in the \"Questions\" section of my review.\n\nOn the other hand, one important related work is missing and should be discussed as compared to the contributions: \"Minimax Confidence Intervals for the Sliced Wasserstein Distance\", Manole et al., 2019.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "k-Ep5xL9mqr", "reviewer": "Reviewer_diVV", "summary": "This paper provides a comprehensive theoretical analysis on the scalability, convergence rates, and robustness of sliced Wasserstein distances and max-sliced Wasserstein distances. Specifically, the paper established sharp empirical convergence rate for sliced Wasserstein distances which is sharp up to log factors over the log-concave class. In addition, this work also investigated the robustness of (max) sliced Wasserstein distances to data contamination. For the computational guarantees, the Monte Carlo error bound of the sliced Wasserstein distance using finite slices was derived. Regarding the max sliced Wasserstein distances, although without formal computational guarantees, this paper analysed a subgradient-based local optimisation algorithm used in previous literature and proved a computational complexity bound for it. The experiment section validates the above theoretical analysis, including the projection and sample complexity, the computational cost of the subgradient max sliced Wasserstein distance, and the robustness of max sliced Wasserstein distance to data contamination.", "questions": "1. In Theorem 1, it is assumed that measure μ is log-concave, is this a common assumption in ML applications? What if this assumption does not hold?\n\n2. What are “one sample” and “two sample” the paper refers to? I guess they refer to the case where the compared distributions are the same and the compared distributions are different, respectively. The author would better explain it to avoid confusion.\n\n3. Is it possible to show the improved robustness of max sliced Wasserstein distances upon classic Wasserstein distances in a ML model?", "limitations": "Future work including improved complexity bounds for the subgradient methods for computing max-sliced Wasserstein distances are mentioned, although limitations of the work are barely mentioned.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. This paper is well-written and well-structured, provided an in-depth analysis of the statistical properties, robustness to data contamination, and computational guarantees for sliced Wasserstein distances and max sliced Wasserstein distances.\n\n2. The derivations are theoretically sound and provides a good reference for the community working on sliced Wasserstein distances.\n\nWeakness:\nAlthough not entirely a weakness due to the nature of theoretical work, the technical part of the paper, including notations and equations, are dense. It will be helpful if the paper can be made more accessible, so that researchers working on algorithmic work rather than theoretical work of SWDs can more easily extract conclusions from the theoretical results derived in the paper.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JTBdZrOIjf1", "reviewer": "Reviewer_DAJE", "summary": "The authors' contribution is threefold: computing empirical convergence rates, robustness to data contamination and improving computational methods of SW distances.", "questions": "No questions", "limitations": "no limitations or negative societal impact", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Multiple new theoretical results are given and rates seem to be sharp.\n\nWeaknesses:\n- Empirical results are sparse, more could have been expected, for more complicated distributions/datasets, to show the theory is robust.\n- I don't have the feeling that the authors compare Theorem 1 to other convergence rates (for instance Equation 7.120 of https://tel.archives-ouvertes.fr/tel-03533097/document ).\n- The authors should develop more on the log-concave assumption: what are the practical implications for ML practitioners? \n- I feel like the three parts of the papers do not have much in common and could each deserve a study on their own.\n- What about distributional SW? Is it possible to compute such theorems for this distance?\n\nI am willing to increase my score if I find the author's answer satisfying.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J4iF4gR_aOK", "reviewer": "Reviewer_tcaq", "summary": "The paper is focused on Sliced-Wasserstein (SW) and Max-Sliced-Wasserstein (Max-SW) distances and it provides important theoretical results on three fronts: 1)  empirical convergence rates, 2) robustness to data contamination, and 3) the error rates of Monte Carlo estimator for SW and the computational complexity bound for the subgradient-based local optimization that is often devised to calculate Max-SW distances. The results are well positioned with respect to existing work in the literature, and whether provide tighter bounds or looser assumptions. In particular, for log-concave distributions the authors show: 1) the sample complexity of SW and Max-SW are both $n^{-\\frac{1}{max(2,p)}}$, the rate is sharp, and that the constants depend on the dimensionality of the problem, 2) under $\\epsilon$ TV-contamination, the p-SW and p-Max-SW distances for the class of distributions with bounded q'th moment projections, and maximum covariance eigenvalue of $\\sigma$,  have minimax rates of $\\sigma\\epsilon^{-\\frac{1}{p}-\\frac{1}{q}}$, and finally 3) the convergence of the subgradient-based local optimization commonly used for Max-SW distance is $O(\\epsilon^{-4})$ and the results are obtained without the entropic regularization used previously in Lin et al. [NeurIPS 2020]. Lastly, all three contributions were numerically confirmed on simple problems.", "questions": "Minor editorial: \n\nLine 114 - \"For for a measurable map\" must be \"For a measurable map.\"\n\n", "limitations": "Given the more theoretical nature of the work, I do not foresee any potential negative societal impact of this work. \n\nIn addition, the authors have done a good job describing the limitations and future work (the room for improvement), and have been transparent about all assumptions used in their derivations. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n* The paper is well written, and well organized, and the authors have done a good job placing their work among the recent literature on this topic.\n\n* The contributions improve the existing bounds/rates with fewer/less-restricted assumptions. \n\n* The paper provides theoretical contributions on multiple fronts to a topic that is of interest to a broad audience.\n\nWeaknesses:\n\n* Not necessarily a weakness but the experimental section of the paper is on the lighter side, which makes sense given the heavy theoretical contributions. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept