Efficient Discrete Multi Marginal Optimal Transport Regularization
Authors: Ronak Mehta
Jeffery Kline
Vishnu Suresh Lokhande
Glenn Fung
Vikas Singh
Venue: ICLR 2023 notable top 25% (2023)
Keywords: optimal transport
multi-marginal
earth mover's distance
fairness

Abstract: Optimal transport has emerged as a powerful tool for a variety of problems in machine learning, and it is frequently used to enforce distributional constraints. In this context, existing methods often use either a Wasserstein metric, or else they apply concurrent barycenter approaches when more than two distributions are considered. In this paper, we  leverage multi-marginal optimal transport (MMOT), where we take advantage of a procedure that computes a generalized earth mover's distance as a sub-routine. We show that not only is our algorithm computationally more efficient compared to other barycentric-based distance methods, but it has the additional advantage that gradients used for backpropagation can be efficiently computed during the forward pass computation itself, which leads to substantially faster model training. We provide technical details about this new regularization term and its properties, and we present experimental demonstrations of faster runtimes when compared to standard Wasserstein-style methods. Finally, on a range of experiments designed to assess effectiveness at enforcing fairness, we demonstrate our method compares well with alternatives.

Published as a conference paper at ICLR 2023
EFFICIENT DISCRETE MULTI-MARGINAL OPTIMAL TRANSPORT REGULARIZATION
Ronak Mehta* Jeffery Kline
Vishnu Suresh Lokhande WW-Madison
Glenn Fung Liberty Mutual
Vikas Singh WW-Madison
UW-Madison Affimm
ABSTRACT
Optimal transport has emerged as a powerful tool for variety of problems in machine learning, and is frequently used to enforce distributional constraints. In this context, existing methods often use either Wasserstein metric, clse they apply concurrent barycenter approaches when more than two distributions are considered. In this paper, we leverage marti-marginal optimal transport (MMOT), where we take advantage of a procedure that computes a generalized earth mover's s distance sub-routine. We show that not only is our algorithm computationally more efficient compared to other barycentric-basee the additional advantage that gradients used for backpropagation can be efficiently computed during the forward pass computation itself, which leads to substantially faster model training. We provide technical details about this new regularization term and its properties, and we present experimental demonstrations of faster runtimes when compared to standard Wasserstein-style methods. Finally, on a range of experiments designed to assess effectiveness at enforcing fairness, we demonstrate our method compares well with alternatives.
distance methods, but it has
INTRODUCTION
The use of Optimal transport (OT) is now prevalent in many problem settings including information retrieval (Balikas al.) 2018 Yurochkin al.] 2019), image processing (Bonneel et al., (014)). statistical machine learning, and more recently, for ethics and fairness rescarch AgegyyrrAAggey
ctt al. 2021 Lokhande et al.) 2020a). OT well-suited for tasks where dissimilarity between two or more probability distributions must be quantified; its success was made possible through dramatic improvements in algorithms (Cuturi 2013) /Solomon et al. (2015) that allow one to efficiently optimize commonly used functionals. In practice, OT often used estimate and minimize the distance between certain (data-derived) distributions, using an appropriately defined loss functional. When one seeks to operate on more than two distributions, however, newer constructions are necessary to effectively estimate distances and transports. To this end, well studied idea in the literature is the "barycenter," identified by minimizing the pairwise distance between itself and all other distributions given. The d-dimensional proxy distance is then defined as the sum of the distances to the barycenter.
Computing barycenters. Assuming that a suitably regularized form of the optimal transport loss is utilized, the pairwise distance calculation, by itself, can be efficient - in fact, in some cases, Sinkhorn iterations can used (Cuturi 2013). On the other hand, to minimize distances to mean, most algorithms typically operate by repeatedly estimating the barycenter and those pairwise distances, and using a "coupling" strategy to push points toward the barycenter, or in other cases, summing over all pairwise distances. As the number of distributions grows, robustness issues exacerbate (Alvarez-Hsteban et al. 2008) and the procedure is expensive (e.g., for 50 distributions, 50 bins).
A potential alternative. Multi- marti-marginal optimal transport (MMOT) is a related problem to the aforementioned task but to some extent, the literature has developed in parallel. In particular, MMOT focuses on identifying joint distribution such that the marginals defined by the input distributions over which we wish to measure the dissimilarity. The definition naturally extends the two-dimensional formulation, and recent work has explored number of applications (Pass) 2015). But the MMOT computation can be quite difficult, and only very recently have practical algorithms been identified
"Corresponding Author, ronakrmocs. sc.edu.

---

Published as a conference paper at ICLR 2023
Itoration
Ittraton 100
Iteratio 200
Itbratton 500
Itoration 1000
Figure 1:
Starting and ending state of minimizing multi-marginal OT distance. Each iteration minimizes the generalized Earth Mover's objective, and then updates each histogram in the direction provided by the gradient.
(Lin et al. 2022). Additionally, even if a suitable method for computing an analogous measure of distance were available, minimizing this distance to reduce dissimilarity (push distributions closer to each other) is practically hard standard interior point solvers are needed just to compute the distance itself.
Why and where is dissimilarity important? Enforcing distributions to be similar a generic goal whenever one wishes some outcome of interest to be agnostic about particular groups within the input data. In applications where training deep neural network models needed, it is often a goal to enforce distribution similarity on model outputs. For example, in Jiang et al. (2020), the authors define fairness measures over the probability of the prediction, given ground truth labels. However, these methods are rarely extended continuous measures among internal neural network activations, mainly due to the strong distributional assumptions needed (product of Gaussians) and the added algorithmic complexity of estimating the barycenter. These issues limit application of these ideas to only the final outputs of neural network models, where the distribution is typically binomial or multinomial. MMOT solutions might be employed here, but suffer similar computational limitations.
Contributions. (1) We identify a particular form of the discrete multi-marginal optimal transport problem which admits an extremely fast and numerically robust solution. Exploiting a recent extension of the classical Earth Movers Distance (EMD) to a higher-dimensional Earth Mover's 's objective, we show that such construction is equivalent to the discrete MMOT problem with Monge costs. (2) We show that minimization of this global distributional measure leads to the harmonization of input distributions very similar in spirit to the minimization of distributions to barycenters (see Figure [ (3) We prove theoretical properties of our scheme, and show that the gradient can be read directly off from a primal/dual algorithm, alleviating the need for computationally intense pairwise couplings needed for barycenter approaches. (4) The direct availability of the gradient enables specific neural network instantiation, and with a particular scaffolding provided by diffcrentiable histograms, we can operate directly network activations (anywhere in the network) to compute/minimize the d-MMOT. We establish via experiments that computing gradients used backpropagation is fast, due to rapid access solutions of the dual linear program. We compare with barycenter-like approaches in several settings, including common fairness applications.
2 RELATED WORK
Despite originating with (Monge 1781), optimal transport continues to be an active area of research (Villani 2009). The literature is vast, but we list few key developments.
Early applications. Starting in (Peleg et al. 1989), the idea of shifting "mass" around within an image was used for comparing images to each other and applied to image retrieval (Rubner et al.) 2000), where the term "Earth Mover's s Distance" (EMD) was introduced. EMD has since been widely used in computer vision: e.g., for image warping (Zhang al. 201T). in supervised settings (Wang
& Guibas 2012). matching point sets (Cabello et al. 2008) and in scenarios involving histogram
comparisons (Ling& & Okadal 2007 Wang & Guibas 2012 Haker et al.) 2004).
Modern machine learning. The continuous optimal transport problem MMngeeKKntooroo prob- lem), was originally presented in (Kantorovich) 1942 Kantorovitch] 1958). While the continuous
problem has been studied intensively ( (Villani 2021). uses of optimal transport within machine learning were possible due to (Cuturi 2013), which showed that entropic regularization enables fast algorithms for EMD (two distributions with discrete support), and contributed to the success of Wasserstein distances in applications. Consequently, problems including autoencoders (Tolstikhin al. 2018), GANs (Arjovsky et al. 2017). domain adaptation (Courty et al. 2016), word embeddings (Hang et al. 2016) and classification tasks (Frogner et al. 2015) have benefited via the use of optimal transport.
2

---

Published as a conference paper at ICLR 2023
Multi-marginal optimal transport. Extending optimal transport theory to an arbitrary number of distributions has been studied on the theoretical side (Pass 2015). and practical extensions have been proposed (Lin et al. 20222. But implementations that integrate directly into machine learning pipelines rely on either heuristics or modifications that result in an approximation of the original
MMOT problem (Cao et al. 2019).
Wasserstein barycenters. One use case of our algorithms will be in formulations that involve Wasser- stein barycenters. Given of probability distributions, the Wasserstein barycenter minimizes the mean of Wasserstein distances to each probability distribution in the set: a practical definition of the mean under the transportation distance (Luise et al., 2019, Cuturi & Doucet 2014] Agueh & Carlier
2011: Janati et al. 2020). Applications of Wasserstein barycenter include texture analysis (Rabin
et al. 2011), sensor data fusion (Elvander et al. 2020), shape interpolation (Solomon al. 2015).
coupling problems (Rüschendorf & Uckelmann 2002) and others (Ho et al. (207)). Very recently, polynomial time algorithms have been derived (Altschuler Boix-Adsera| (021))
Fairness. Proposals such (Jiang et al. 2020; Chzhen et al. 2020 Gordaliza et al. 2019 Lokhande ct al. 2022b) have all regularized models towards outcomes which have equal predictive power over subgroups within a population, measured using optimal transport distance. Informally, the idea is to operate on distributions that are supported on disparate groups, and ask that the distributions get "pushed" towards a common central distribution. This requires solving optimal transport problem. Keegyir-Aggrey et al. (2021)
Greedy algorithms and extensions. Hoffman et al. (1963) observed that there exists family of linear-time greedy algorithms that solve the classical two-dimensional transportation problem. Later. Bein al. (1995) extended the relevant definitions and the greedy algorithm to d-dimensional transportation problems. More recently, the results in Kline (2019), which we will use here, further extended this result to the dual program, and several theoretical properties of the generalized Earth Mover's 's problem were shown. A slightly different generalized d-dimensional Earth Mover's problem explored in Eriicksnn (2020) with focus on statistical generalization properties.
BACKGROUND
Denote by [n] == {1,.... n), the set of positive integers no larger than n. For elements x E R", we denote the ith entry of x as z(i), e.g., for any æ E R", x = (x(i) : E [rz]). The positive orthant of Rn is denoted IR4 := (x R" x(1) 2 0, E [n]]. We denote by e == (I,...,1) 1) I2 the constant
vector. For q 1, we define the q-norm as ||>||, (Ere(n) |x(())) 1/9
and if q is suppressed, then ||ж||| = | A discrete probability distribution is a point RT with e'p |lpl| = 1.
Given a pair of discrete probability distributions P1 P2 E RT, we may want to quantify similarity. Often, we do this by selecting from many measures, including the g-norm, KL--dieegeence or the Farth Mover's Distance (EMD). The EMD for pair of distributions has several equivalent interpretations. First, let Pl be source of mass, and p2 be a sink for mass, and r),, where E gax*, represent the flow of mass from P1 (i) to P2 (i). Denote by j(i,j) the cost of moving one unit of mass from Pr (i) to Pz(i). The EMD between P1 and p2 is the minimal cost to transform p1 into p2, written as linear program (LP):
E((i)))(i s.t. = Pi(;; x (Vi,j E [n])- min ZEREXX
(I)
The source-sink interpretation asymmetric in P1 and P2. but the LP is symmetric in P1 and p2. It be shown that the objective value of this LP defines metric (Kantorovich) 1960), and the optimal value of the objective function can be interpreted as a distance between P1 and P2, and useful to quantify dissimilarity between pairs of distributions. In particular, P1 P2 if and only if the optimal objective value of the Earth Mover's problem vanishes. The LP in ① has an equivalent dual LP,
max 2, P1 + 2 P2 s.t. 21 (1) + 22 S c(t,)), (Vi.j 21.22ER=
E [n]).
By strong duality, the optimal value of the primal program equals the optimal value of the dual program (2). Many practical relaxations have been proposed for (1) including entropic regularization (Cuturi 2013). Computation of the EMD is readily available, as in the Python Optimal Transport
(POT) library (Flamary al. 2021)
3

---

Published as a conference paper at ICLR 2023
3.1 DISCRETE MULTI-MARGIIN OPTIMAL TRANSPORT
The foregoing approach applies only to d = 2 distributions, namely and p2. We briefly review the extension to distributions; the literature calls this multi-marginal optimal transport (MMOT).
Definition 3.1 (Discrete Multi-Marginal Optimal Transport (d-MMOT)). Let p1,...,Pd E I be
discrete probability distributions. Let Ca R" R+. The discrete multi-margine marginal optimal transport problem (d-MMOT) can be written as
min
Ca(X) s.t. x;= Pi, (Vi E [d),
X
where X, E R is the i-th marginal of X E 2 R"
Following the original formulation (Kantorovich: 1942, we will restrict the cost function Ca(-) to the is nonnegative. Here, the d-MMOT is the LP,
linear map, (x == (c, X) where c E Rax x
min Σ cii................... ia) 2id......................... ................................ ,.) ia) s.t. Σ
x(i id) pi (1.), (Vi, [n]]
#ER foondd
(3)
Σ
r(c. = pa(fa): (Via E [n]).
This linear program (LP) central to the regularization schemes that are discussed below.
4 EFFICIENT D-MMOT COMPUTATION
The linear d-MMOT problem (3) suffers from the curse of dimensionality: the L.P has nd variables, and even modest choices of and d can result in a LP with billions of variables, making standard LP solvers inapplicable. Alternatively, specific algorithms have been proposed (Benamou al. 2013), and relaxations via entropic regularization have become more widespread, with very recent
extensions to the d-MMOT setting (Tupitsa et al. 2020 Lin al. 2022).
In practice, the cost in typically takes one of two forms. In the case where the distributions PI.....P Pa are over categorical variables, the cost is typically defined as c(i,...., i2) when - ..... ia and 1 otherwise. However, and importantly, if the distributions p; are histograms over some ordinal or discretized space, the cost typically has a structure closer to that of a "tensorized" distance, characterized by the Monge property.
Definition 4.1 (Monge Property). A tensor is Monge if for all valid i,,... ia and j1. ji...., .......... ja.
( 82) + c(t1)....4) & c(i1....ig)) ig) c(Ji....;jd)
where 8; min(is.jss) and ls max((e.ja).
Our focus on a specific cost, which is known to Monge: c(11, 12, .., (4)) = max (ix k E [d] - min (ix k E [d)). When d = 2, this cost reduces to c(i1, i2) = ii - i2). which agrees with the classical EMD cost. This choice of è called the generalized EMD cost.
Remark 4.2. Limiting our attention to this cost is not as restrictive as it may appear. Indeed, Bein al. (1995) shows that the optimal solution the LP 33 independent of the cost, as long as is Monge. Additionally, when is the generalized EMD cost, Kline (2019) describes greedy algorithm that solves both (3) and dual (5) in linear time. is also shown that the optimal objective value is continuous nonnegative function of each probability distribution p5 (i.e., small changes in one distribution cause small changes in the objective value). Continuity is critical for numerical stability. Next, when is the generalized Earth Mover's array, the optimal objective value vanishes if and only P: Pj for all é.j E [n]. This separability property is useful in applications where we wish to iteratively "step towards" the barycenter of set of distributions, see Fig. In order step towards (red arrows) a barycenter, we require a descent direction. We observe that the following result gives us this functionality.
4

---

Published as a conference paper at ICLR 2023
Barycenter
d- A-Dimensional Earth Mover's Distance (DEMD) Iterations
STEP
STEP
STEP
STEP
m
Seatert
Figure 2: (Left) Barycenter methods identify center (red circle) and transport all distributions (blue circles) toward that center along the coupling path (yellow). (Right) Our DEMD approach identifies "support" distri- butions that lie on the convex hull (outlined cireles), and only those distributions are moved in direction that decreases the Generalized EMD objective.
Theorem 4.3. The dual linear program of the d-MMOT problem
3
maximize 2j EBCh jE(d]
Σn'rgs
subject to
21
za(la) S ia),
(5)
where the indices in the constraints include all iz E [n], j E [d]. Denote by (pi..... pa). the optimal objective value of the L. in (3) Let =" be optimal solution the dual program
Then,
Volpi.... .a) = = and for any t E R. 6(p1, P............ .P.......... = Ers(2}+ + +tm).
where 1) == (=ī(n) (m)) (z)())
Ferris & Mangasarian 1991) of LPs to assert that, under mild uniqueness conditions, small changes to a LP's input data does not change its optimal solution. The full proof is in Appendix 7.1
Proof. The main observation invokes perturbation analysis (Mangasarian & Meyer 1979
Remark 4.4. The first part of this result provides what we require: a direction of descent. Thus, we can solve the d-MMOT problem and also find the optimal solution to its dual, then we can step (or move) our distributions in the opposite direction of the dual variables to push them together, see The second claim is somewhat technical, and reconciles particular affine shifts that result in equivalent objective values.
Fig. 2
4.1 OPTIMIZATION OF D-MMOT
Setup. We now instantiate d-MMOT add-on term in standard machine learning formula- tion. Concretely, it can be positioned alongside typical learning losses L(f(x), y, 0) to encourage minimizing distances among different distributions gi E G, E [d], d-MMOT( gr 0), i.e., (2),y1 y: 0) + d-MMOT(f (f())) 0). Within a deep neural network (DNN) architecture, as in some of our experiments, several properties of the d-MMOT module are useful: our results above naturally provide clean operations for computing both the required objective in the "forward" pass and gradients in the "backward" pass.
ming ((f(z),
Using the primal and dual variables. If the optimal objective value of (3) serves in regularizing deep neural network, then we can train the network as follows. During the forward pass, i.e.. computing the d-MMOT objective, we can employ version of the aforementioned primal/dual algorithm that solely computes the function á and stores the dual variables z. As backpropagation incoming gradient, it is simply multiplied by the
proceeds, when the EMD module encounters stored dual variables (see Theorem 4.3 and Algorithm T]. We call our procedure the d ddimensional Earth Mover's Distance, in short, the DEMD algorithm.
Complexity. Computing the DEMD distance in the forward pass is exactly ((nd): linear in the number of distributions and number of bins. This property follows directly from the algorithm, needing only a single pass through all of the data. Bei et al. (1995) provides this result for greedy algorithms that solve OT programs in Def. 3.1 In contrast methods that derive gradients
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 Our proposed method: d' Dimensional Earch Mover's Distance (DEMD)
function FORWARD(PI,.....
Compute Σ 52.4 and (Z1,..., za) via the primal/dual algorithm in Kline 2019
save (21...... zd).
return Σx Sytz
function BACKWARD(gradCuppu)
load (21....,zd) 2d)
return (21,..., za) gradOutput
via entropic regularization schemes, i.c., relaxations of the optimal transport problem (uise et al. 2018 Xie et al. 2020 Cuturi et al.) 22020), this approach solves the distance computation exactly in linear time. This linear time analysis is not only provided by the theory in prior work, but is also explicit in the number of iterations defining our algorithm (see Appendix 7.4 for more details). For minimizing the DEMD (computing the updates, i.c., red arrows in Fig. 2 a convergence analysis would follow from the properties of the optimization scheme chosen. Our tool can be dropped in exactly as any other module in modern learning applications (using the observation that gradients are easily computed, i.e., (1) time to read stored dual variables).
A few practical adjustments. It often happens during training that the optimal solutions may, through updates by stepping the direction of the gradient, acquire entries that are negative. This violates an assumption that entries must be nonnegative. However, Thm. 2.2 in Kline (019) shows that the optimal objective value, Φ possesses type of translation invariance. Leveraging this alongside the second part of Thm 4.3 we ensure that, in the event that point escapes the nonnegative orthant of R",, an appropriately constructed constant vector may be added to the current iterate so that it again lies in the nonnegative orthant, without changing the objective value. Further, with relatively small learning rate, by the continuity of o, normalization is a small perturbation of the original point and can be applied as necessary to enforce that updates result in valid distributions.
Remark 4.5. Another useful property is that if the convex hull of (pi...., ,aa) is contained in the convex hull of (f):..... .a). Pa). is strict. A direct consequence of this property is that points within the interior of the convex hull of the data fed the optimization model have vanishing gradients. Practically, this leads sparse gradients w.r.t. the distributions, and nonzero gradients correspond to points on the hull, i.c., distributions which are maximally different from the rest. Minimization proceeds by iteratively moving mass such that these maximally different distributions are pushed toward each other. Fig. 2 showow the convex hull during minimization of the generalized EMD objective via our DEMD algorithm.
then opp),...,PP' Pa) S -(......7 .P)). with strict inequality if containment
Need for Histogramming. Note that outputs fxr) and intermediate activations are continuous values (layer shape by batch size). So, we must transform activations into normalized histograms (i.e., discrete distributions). While libraries such as PyTorch and Tensorflow typically provide histogram functions, they are not differentiable. The discontinuous operation of bin assignment does not allow for end-to-end pipeline where can push upstream parameters in the direction of minimizing the EMD objective over histograms. To address this, we use a simple relaxed/differenttabbl histogram- ming operation. First, all outputs are mapped to j0, 1] using a Sigmoid activation. Then, for each bin location, the "count" in that bin is determined by ReLU function applied to the difference between the gap between the activation and the distance to the bin boundary. In other words, if activation falls in a bin, the count of that bin increases based on the distance to the bin boundary, otherwise the count remains the same. The full procedure is detailed in Appendix 7.2 The ReLU activations defining bin boundaries allow for gradients to move samples towards neighboring bins as needed.
5 EXPERIMENTS
We evaluate our construction in number of settings. First, we demonstrate the computational speedup associated with evaluating d-MMOT using our algorithm, along with speedups associated with directly computing the gradient. Next, compute the construction in series of neural network tasks associated with ensuring distributional similarity: fairness, invariant representations, and multi-domain matching. We provide a complete PyTorch Network Module that packages the above

---

Published as a conference paper at ICLR 2023
Time Per Epoch [seconds]
Feature Extraction
Layer
000.00
Inputs
Predictions
O
1,000
Preactivation
0.000
Group Labels
g
DEMD
20 Number Distriutions
DEMD
Figure 3: (Left) DEMD is positioned after the final layer. prior to the activation, Activations are sorted into distributions utilizing group labels provided alongside the input data. Computed distributions then brought together using our algorithm. (Right) Computation times for direct distance evaluation of EMD-like distances. Existing methods take much more time (y-axis exponential) as the number distributions grow.
differentiable DEMD objective and histogram functions, and serves as a plug-and-play regularization module. Code available at https://github. www.ronaww.////ooooococcoaaaaact demd
5.1 PERFORMANCE BENCHMARKS
Figure 4 presents NumPy and Torch instantiations of both forward and backward passes using automatic differentiation and the gradients computed using the dual in $4.1 As expected, the forward (distance computation) times are comparable, but the backwards computation scales poorly with the number of distributions to be updated using automatic differentiation. Our dual setting allows the gradients to simply be read off (based on the forward pass), leading to no additional computation overhead during backpropagation.
Farword Time (5)
Backward Time (s)
Forward Time
Backward Time (s)
100
130
100
Kumberel Dierttteee AdtZoied TTechh-Dull
Mumberel
-call
A.ALOG Toch-DDa
Figure 4: Forward/Backward Pass Times for 10 Bins with varying number of distributions, averaged 10 runs. Forward wall-clock times are comparable, regardless backend (left pair: NumPy+SciPy: right pair: Cforch+AutoGran Direct reading of the gradient via the dual leads to significant gains in backward pass times, where automatic differentiation scales poorly with the number of distributions.
We compare our DEMD computation to what one may given existing Optimal Transport methods in Figure (right). Using standard off-the-shelf methods as a baseline, when the cost is Monge our algorithm provides significant speedups in computation time, the scale of orders of magnitude! Further, the number of distributions and bins increases, the time-cost for existing methods using more generic LP solvers
become significant, and may become infeasible with generic solutions via CVXPY (Diamond & Boyd 2016). We compare our approach to two off-the-shelf implementations of barycenters via the Python Optimal Transport (POT) Library (Flamary al., (02I), along with directly solving the Earth Mover's problem via CVXPY. Even for 10 distributions over 10 bins, CVXPY is unable to allocate the necessary memory using a direct instantiation.
5.2 GENERALIZED EM FAIRNESS ON FAIRNESS DATASETS
With viable tool in hand, we move to practical applications in machine learning fairness, which naturally requires enforcing closeness in model outputs. Here, construct networks with our DEMD regularizer, where we discretize the final activation output prior to classification, and push the distributions of this activation to be similar among sensitive attributes.
Data. We identify common faimess datasets often used to benchmark fair machine learning
algorithms: (1) the German Credit Dataset (Hofmann 1994). (2) the Adult Income Dataset (Dua & Graff (017), (3) the Communities and Crime Dataset (Redmond) 2009). and (4) The ACS Income
dataset, recently made available large, population- demographic dataset (Ding al. 2021
7

---

Published as a conference paper at ICLR 2023
Table 1: Fairness Experiments. Measures evaluated using standard metrics: maximum Demographic Parity Gap (DP), maximum Equalized Odds Gap (EO), and (DEMD). For all measures, lower values are preferred. With comparable accuracy, DEMD regularization leads to fairer representations as measured by common metrics. DP and EO measures scaled by 100 for case of presentation. Best results shown in bold.
German
Adult
Crime
ACS Incomee
DP
RO
DEMD
DP
RO
DEMD
DP
EO
DEMD
DP
DEMD
Nome
17(b) 11(2) 1.6)()332)
18(1)
13(0) 1.69().07)
38(6)
45(3)
2.86(0.38)
37(1)
25(0)
4.78(0.32)
DP-Reg.
16(8)
10(3) 1.3
17(1) 13(3) 1.6
38(6)
15(3)
0.83(
18(4)
28(0)
5.02 31)
BO-Reg.
17(6)
11(2) 1.69(0.32)
14(1) 12(1)
1.43
38(5)
44(3)
2.83(0.39)
38(1)
26(0)
4.82(0.32)
Bary- POT
27()))
17(1) 1.5
180)
13(0) 1.64
36(5)
44(1)
(..)(
57(37)
50(4s)
4.38 16)
DEMD (ours)
14(7)
9(4)
(.41
150)
1200 1.44(0.08)
36.0)
2.69(0.44)
33(0)
24:03
36(00.9) 29)
containing many as nine sensitive attributes. We set up simple three-layer neural network for classification tasks with the addition of a faimess-type regularizer. We compare our construction (1) No regularization, (2) Demographic Parity (DP), (3) Equalized Odds (HO), and (4) a histogrammed barycenter construction. DP and EO regularizers were computed using a PyTorch version of FairLearn (Bird et al. 2020), and the barycenter version was implemented using POT library (with GPU backend). Because the scale of the regularization term is not directly comparable, we sweep regularization weights and select the best over all measures for a each dataset/regularizer pair. We use 10 bins and replicate all experiments over three random seeds.
with 4 off-the-shelff plug-in regularizers:
Models. We set up two model settings with a standard logistic regressor and a 2-layer neural network. We compare three types of plug-in regularizers: (1) Demographic Parity (DP), (2) Equalized Odds (EO), and (3) the Generalized EMD. DP and BO regularizers were computed using Py PyTorch implementation of FairLeam (Bird et al. 2020).
Results. In the summary in Table 1 models were selected with the largest regularization weight before accuracy dropped significantly. When accuracies are comparable, we see good performance (when minimizing DEMD regularizer) against baseline methods. Notably, when accuracies are similar across methods, minimizing DEMD tends to give better (lower) faireess measures across all datasets. Summary: DEMD on the final network layer helps control multiple fairness measures.
5.3 HARMONIZATION FOR INVARIANT REPRESENTATIONS
Having evaluated the use of the DEMD layer to constrain the neural network for fairness measures, we will now move to a more general problem of deriving invariant representations from the datasets. Here, invariance is sought w.r.t. the sensitive attributes. Recent works (Lokhande al.) [022a] Akash eet al. ( on invariant representation learning propose leveraging an encoder-decode architectures to map the dataset features to latent space representations. The latent space representations are penalized to match or harmonize the distributions across several groups in the dataset. In contrast to the previous section, the goal here is to identify a good mapping in the latent space that is devoid of any group-related information in the dataset. Consequently, our evaluation metrics test if the latent representations have a lower value of (i) ADV, adversarial measure and (ii) MMD, maximum mean discrepancy measure. The measure ADV tests what extent separate neural network predict the group information from the latent features. Alternatively, the MMD scores measure the distance between the probability distributions across groups. Prior works such Li et al. (2014) and Xie et al. (2017) optimize each of these measures separately. Our experiments (Table 2) show the DEMD layer performs competitively with the baselines when applied on the latent space. Interestingly, these performance gains come despite not directly optimizing the harmonization measures, in contrast to baselines, which require several practical adjustments (batch variants and secondary neural networks). Summary: DEMD as an intermediate layer can be used to derive invariant representations efficiently.
5.4 MULTI-DOMAIN IMAGE TRANSLATION
We apply our construction to a recent multi multi-marginal GAN framing of multi-domain image translation. With the goal of learning mapping for source image to multiple target domains, focal point of recent literature has been to reduce the computational requirements of training individual models for each target, and learn concurrent matching problem over number of shared parameters or networks. MWGAN (Cao et al. 2019) set up a Multiple Marginal Matching problem in this context. Extending upon their key observation that inter-domain constraints can be measured via the gradients
8

---

Published as a conference paper at ICLR 2023
Table Harmonization Experiments. Evaluations conducted along three metries, Accuracy (ACC), Adver- sarial measure (ADV) and Maximum Mean Discrepancy (MMD). lower value & of ADV and MMD indicate successful harmonization across the different groups. A higher ACC with small drop from baseline is preferred.
German
Crime
ACC
ADV
MMD 1 ACC1 ADV J. MMD 4 ACC
ADV 4 MMD
ACC
ADV 4 MMD 1
None
74:0.0 9) 93(1.3) 7.7(0.8) 84
83
9.8(0.3) 86 77.0.5 14;0.1)
78(0.1) 98(0.7) 160(2)
Li al. 20144
73(1.6) 92(1.3) 1.5(0.3)
81
83:0.1) 3.1(0.5)
85(0.6)
76.1.) 12:10)
78(0.1) 97(0.6) 17(1.2)
Aze el ai 2017
76(1.3)
93(0.6)
2.
8400.04)
81 4.2(2.4)
85
76 15
78(0.1) 94(6.6) 99(2.9)
(burs)
74
93(0-4) 2.1.0.4) 84(0.03) 82(0.2) 5.3(.4) 83(0.3) 72(1.0) 7.10..))
77(0.4) 96(0.5) 26(3.9)
Original
Blond Hair
Glasses
Moustache
Skin
Original
Blond
Glasses
Moustache
Pale Skin
KCH
KCH
KcH
KCH
H
Figure 5: Six MWGAN+DEMD CelebA image translation results. Fach row corresponds to a random sample in
the validation set. The leftmost image is the original source image, and soquential columns represent translations (I) Blonde Hair, (2) Glasses, (3) Moustache, and (4) Pale Skin. Using DEMD relaxation the Multiple Marginal Matching problem facilitates high quality images translation. more results see Appendix 7.3.4
for each domain, we instantiate our DEMD layer over the gradient norms computed for each sample in batch per group. Specifically, DEMD minimizes the differences between the distributions over the gradient norms across all target domains. Using a weight of 100 for both regularizers, we observe similar performance when compared to the original MWGAN construction. In Figure [5] we show a few samples generated over an image translation task on the CelebA dataset. Here, we aim to translate original dataset images to ones with specific target attributes. Summary: Multi-domain image translation can be conducted by adding a DEMD layer in the native GAN construction.
DISCUSSION
presented an efficient solution for solving common practical multi-marginal optimal trans- port problems. Significantly cheaper to compute compared to similar methods, it allows for large numbers of distributions to be matched common DNN pipelines. Our implementation allows imposing fairness constraints for variety of applications, without the need for pair- wise measures. As such, subgroup fairness (Kearns et al., 2018) is an interesting problem set- ting that we believe can benefit. Other properties such as Minkowski additivity that have not been explicitly leveraged in our experiments may also be worthwhile direction to explore.
In its current form, DEMD cannot be directly applied distributions over multi-dimensional discrete spaces, such as images or latent spaces in generative models. Slicing is heuristic that has been shown to work well. To evaluate feasibility, we embed distributions over multi- dimensional continuous spaces, take random projections over 1-D spaces, and recompute our DEMD measure. Over a 64-dimensional latent space embedding of CelebA, can efficiently compute DEMD measure over all 40 attribute subgroups, and observe convergent behavior w.r.t. the number of projections.
0424
3.000
1000
Figure 6: Sliced DEMD across projections.

---

Published as a conference paper at ICLR 2023
REFERENCES
Martial Agueh and Guillaume Carlier. Barycenters in the wasserstein space. SIAM Journal on Mathematical Analysis, 43(2):904-92 924, 2011.
Aditya Kumar Akash, Vishnu Suresh Lokhande, Sathya Ravi, and Vikas Singh. Learning invariant repre- sentations using inverse contrastive loss. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6582-6591, 2021.
Jason M Altschuler and Enric Bosx-a Wasserstein barycenters can be computed in polynomial time in fixed dimension. J. Mach. Learn. Res., 22:44-1, 2021.
Pedro César Alvarez-Esteban. Eustasio Del Barrio, Juan Antonio Cuesta- and Carlos Matran. Trimmed comparison of distributions. Journal of the American Statistical Association, 103(482):677-744, 2008
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Sanjeev Arora, Rong Ge. Yingyu Liang. Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs), In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pp. 224 232. PMLR, 06-11 Aug 2017. htt.:httts//poceeeeeeeeee igs. ml wwtppp/se/aaarrrr//eeeepppe
html
Georgios Balikas, Charlotte Laclau, levgen Redko, and Massih-Reza Amini. Cross-lingual document retrieval using regularized wasserstein distance. In European Conference on Information Retrieval, pp. 398-410. Springer, 2018
Wolfgang W. Bein, Peter Brucker, James K. Park, and Pramod K. Pathak. dimensional transportation problem. Discrete Applied Mathematics, 58(2):97-099 1995. ISSN 0166-218X. doi: http:///.....////.0.0.006666662/
monge property for
URL htthttt:: : /www. scienced rect. com/ Workshop on Discrete Algoritms.
bcciencc/arricclee////116611 (10.:6226x33900000
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Tterative bregman projections for regularized transportation prohlems. SIAM Journal on Scientific Computing, A7(2)A1111- A1138, 2015.
Sarah Bird, Miro Dudík, Richard Edgar, Brandon Horn, Roman Lutz, Vanessa Milan, Mehrnoosh Sameki, Hanna Wallach, and Kathleen Walker. Fairlearn: A toolkit for assessing and improving faimess in ai. Microsoft, Tech. Rep. MSR- FER-TR-2E 772-2020-33 32, 2020.
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51, 01 2014. doi:
Sergio Cabello, Panos Giannopoulos, Christian Knauer, and Günter Rote. Matching point sets with respect to the earth mover's 's distance. Computational Geometry, 39(2): 2008 ISSN 0925-7721. doi: https://ooi.rr// 10.1006/).cmmeeo.2M00 10.001, URL | http:///wwwweeeeeccerrree..ccc com/ wwtp://ccccccccccccccceceaaeataa p21/5052577210500102
Jiczhang Cao, Langyuan Mo, Yifan Zhang, Kui Jia, Chunhua Shen, and Mingkui Tan. Multi-marginal wasserstein gan. Advances in Neural Information Processing Systems, 32, 2019.
Casey Chu, Kentaro Minami, and Kenji Fukumizu. Smoothness and stability in gans. In Internationaal Conference Ho-.ouueme..HHHHeeeHeeee
on Learning Representations, 2020. WRLLLtttps:://peeeeviiie
Evgeni Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil, Fair re- gression with wasserstein barycenters. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balean, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 7321-7331. Cur- ran Associates, Inc., 2020. URL httpss://proceeednggg
700-88008887777070 Beb 701e6777736--2 Paper.
Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakntomamonjy. Optimal transport for domain adaptation.
IEEE transactions on pattern analysis and machine intelligence, 1853))1853-1888 2016.
Marco Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 06:2292-2302 2013.
Marco Cuturi and Arnadd Doucet. Fast computation of wasserstein barycenters. In International conference on machine leorning, pp. 685-693. PMLRR 2014.
10

---

Published as a conference paper at ICLR 2023
Marco Cuturi, Olivier Teboul, Jonathan Niles-Weeks and Jean-Philippe Vert. Supervised quantile normaliza- tion for low-rank matrix factorization. In Proceedings of the 37th International Conference on Machine Vienna, Austria, 2020. URL http:://proceeddnggg mir htt.://dd............re//ss//ssa
Learning, pp. cutur 100a..220... html
Brian d' Alessandro, Cathy O' O'Neil, and Tom LaGatta. Conscientious classification: A data scientist's guide to discrimination-avee aware classification. Big data, 5(2):120-136) 2017.
Daniel De Wolf and Yves Smeers. Generalized derivatives of the optimal value of linear program with respect to matrix coefficients. European Journal of Operational Research, 291, 11 2019. doi: 10.1016/j.ejor20199.1 020.
Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):900-22113, 2016.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Dheeru Dua and Casey Graff. UCT machine learning repository, 2017. URL http:://acchieee ics. .us. @dd/mm]
Filip Elvander, Isabel Haasler, Andreas Jakobsson, and Johan Karlsson. Multi-marginal optimal transport using partial information with applications in robust localization and sensor fusion. Signal Processing, 171:107474, 2020.
William Q Erickson. A generalization for the expected value of the carth mover's distance. arXiv preprint arXiv:2009. 12723, 2020.
Michael C. Ferris and Olvi L Mangasarian. Finite perturbation of convex programs. Applied Mathematics and Optimization, (3(1):263-275 1991.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalic T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy. Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021. URL jmlr pttp:o/paapp////////22.22
html
Robert Freund. Postoptimal analysis a linear program under simultaneous changes matrix coefficients. In Mathematical Programming Exsays in Honor of George B. Danizig Part I. pp. 1-13. Springer, 1985.
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya- Polo, and Tomaso Poggio. Learning with a wasserstein loss. In Neural Information Processing Systems, 2015.
Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Jean-Michel Loubes. Obtaining faimess using optimal transport theory. In International Conference on Machine Learning, pp. 2357-2365. PMLR, 2019.
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. A kernel method for the two-sample- pro-smppl-ppollm.. Advances in neural information processing systems, 19, 2006.
Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent. Optimal mass transport for registration and warping. International Journal of computer vision, 60(3):225-22 2200, 2004.
Nhat Ho, XuanLong Nguyen, Mikhail Yurochkin, Hung Hai Bui, Viet Huynh, and Dinh Phung. Multilevel clustering wasserstein means. In International Conference on Machine Learning, pp. 1501-1509, PMLR. 2017.
Alan J Hoffman et al. On simple linear programming problems. In Proceedings of Symposia in Pure Mathematics, volume 7, pp. 317-327, 1963.
Hans Hofmann. Statlog (German Credit Data). UCT Machine Learning Repository, 1994.
Gao Huang, Chuan Quo, Matt Kusner, Yu Sun, Kilian Q Weinberger, and Fei Sha. Supervised word mover's distance. In Proceedings of the 30th International Conference Neural Information Processing Systems, pp. 4869 4877, 2016.
Hicham Janati, Marco Cuturi, and Alexandre Gramfort. Debiased sinkhom barycenters. In International Conference on Machine Learning, pp. 4692-4701. PMI.R, 2020.
11

---

Published as a conference paper at ICLR 2023
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang. and Silvia Chiappa. Wasserstein fair classification. In Uncertainty Artificial Intelligence, pp. 862-872. PMLR, 2020.
Leonid Kantorovich. On translocation of masses. Dokl. Akad. Nauk SSSR, 37:227-229, 1942.
Lconid Kantorovich, Mathematical methods organizing and planning production. Management science, (4):366442,, 1960.
Leonid Kantorovitch. On the translocation of masses. Management science, 5(1);144, 1958.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference Machine Learning, pp. 2564-2572 PMLR, 2018.
Jeffery Kline. Properties the d-dimensional earth mover's problem. Discrete Applied Mathematics, 265: 128-141,2019,
Kweku Kwegyir-Aggrey, Rehecca Santorella, and Sarah M. Brown. Everything is relative: Understanding fairness with optimal transport, 2021.
Susan Leavy, Gender bias in artificial intelligence: The need for diversity and gender theory in machine lcarning. In Proceedings of the 1st international workshop on gender equality software engineering, pp. 14-16, 2018.
Yujia Li, Kevin Swersky, and Richard Zemel. Learning unbiased features, 2014. URL https: 5244
Tianyi Lin, Nhat Ho, Marco Cuturi, and Michael I. Jordan. On the complexity of approximating multimarginal optimal transport. Journal of Machine Learning Research, 23(65): 1-13, 2022, Utt/ttpp:// org/
papers/v23/19-B22 html
Haibin Ling and Kazunori Okada. efficient earth mover's distance algorithm for robust histogram comparison. IEEE transactions on pattern analysis and machine intelligence, 29(5):840- 8853, 2007.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Vishnu Suresh Lokhande, Aditya Kumar Akash, Sathya N Ravi, and Vikas Singh. Fairalm: Augmented lagrangian method for training fair models with little regret. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings. Part XII, pp. 365-381. Springer, 2020a.
Vishnu Suresh Lokhande, Songwong Tasneeyspant, Abhay Venkatesh, Sathya N Ravi, and Vikas Singh. Gener- ating accurate pseudo-labels in semi-supervised learning and avoiding overconfident predictions via hermite polynomial activations. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 11435-11443, 2020b.
Vishnu Suresh Lokhande, Rudrasis Chakraborty, Sathya N. Ravi, and Vikas Singh. Equivariance allows handling multiple nuisance variables when analyzing pooled neuroimaging datasets, 2022a. URL [RLp
//arxiv. wwwp/vvoor/ooooooooo abs/ 2203. 1 15234
Vishnu Suresh Lokhande, Kihyuk Sohn, Jinsung Yoon, Madeleine Udell, Chen-Ye Yu Lee, and Tomas Pfister, Towards group robustness in the presenec of partial group labels. arXiv preprint arXiv:2201.03666 2022b.
Giulia Luise, Alessandro Rudi, Massimiliano Pontil, and Carlo Ciliberto. Differential propertics of sinkhom Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL ht ups: /twpeee/////eee/////oo
approximation for learning with wasserstein distance.
www..nn....nnnnnneeeeeeeee. neur cz/ paper /01.p//////////111/
33f2260b57822F66 F76bce 99239222222222 Paperrrr-a-paprr.... Paper. pdf
Giulia Luise, Saverio Salzo, Massimiliano Pontil, and Carlo Ciliberto. Sinkhorn barycenters with free support via frank-wolfe algorithm.
Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc E. Fox, and R. Gareett (eds.), Advances in Neural Information Processing Systems, volume 32, Cur- ran Associates, Inc., 2019. URL
BE96f36b7aaee 3b1 1884 222 6ac Papere .pff
Olvi I. Mangasarian and RR Meyer. Nonlinear perturhation of linear programs. SIAM Journal on Control and Optimization, 17(6)745-772,, 1979.
12

---

Published as a conference paper at ICLR 2023
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. survey bias and fairness machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
Harlan D. Mills. Marginal values of matrix games and linear programs. Linear Inequalities and Related Systems, 38, 1957.
Gaspard Monge. Memoire sur theorie des deblais et des remblais. Mem. Math. Phys. Acad. Royale Sci., pp. 666-704, 1781. (tRl:ttts:://et httpa////...iiiaaccmmm...
Cathy O' neil. Weapons of math destruction: How big data increases inequality and threatens democracy. Broadway Books, 2016.
Brendan Pass. Multi-marginal optimal transport: theory and applications. ESAIM: Mathematical Modelling and Numerical Analysis, 17161:77 2015.
Shmuel Peleg, Michael Werman, and Hillel Rom. A unified approach to the change of resolution: Space and gray-level. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(7):739-742 1989.
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Berntt. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision, pp. 435-446. Springer, 2011.
Bogdana Rakova, Jingying Yang, Henriette Cramer, and Rumman Chowdhury. Where responsible meets reality: Practitioner perspectives on enablers for shifting organizational practices. Proceedings of the ACM on Human-Come Computer Interaction, S(CSCWI):1 1):1-23, 2021.
Sathya N Ravi, Tuan Dinh, Vishnu Suresh Lokhande, and Vikas Singh. Explicitly imposing constraints in deep networks via conditional gradients gives improved generalization and faster convergence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4772-4779, 2019.
Michael Redmond. Communities and Crime. UCI Machine Learning Repository. 2009.
Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. The earth mover's distance metric for image retrieval. International journal of computer vision, 40(2):99- 121, 2000.
Ludger Rüschendorf and Ludger Uckelmann. On the n-coupling problem. Journal of multivariate analysis, 81 (2):242-258, 2002.
Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, and Leonidas Guibas. Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics (TOG), 14(4):1-11,201 2015.
Ilya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein auto-encoders. In Inter- national Conference on Learning Representations, 2018. URL httpps:://opeeeeevieww...s http:/eerrreeee...ee//oooroo
id=HkL7n1 Cb
Nazarii Tupitsa, Pavel Dvurechensky, Alexander Gasnikov. and César A. Uribe. Multimarginal optimal transport by accelerated alternating minimization. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 6132-6137, 2020. doi: 10. 00.1099/DDC4223402200000000 9300000010.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009,
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Fan Wang and Leonidas Guibas. Supervised earth mover's distance learning and its computer vision applications.
In European Conference on Computer Vision, pp. 442-48 455. Springer, 2012.
Qizhe Xie, Zihang Dai, Yulun Du, Eduard Hovy, and Graham Neuhig. Controllahle invariance through adversarial feature learning. In I. Guyon, U. Von Luxhurg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Cur- Associates, Inc., 2017. URL http:pp::ppooeeeeeeeesss www.ddiinnnnnnniiiineeeemm www.neurrrs.e.. see.rrpps.cc/ppppe///////1
Yujia Xie, Hanjun Dai, Minshuo Chen, Dai, Tuo Zhao Hongyuan Zha, Wei Wei, Tomas Pfister. Differentiable top-k with optimal transport. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.). Advances in Neural Information Processing Systems, volume 33, pp. 20520 20531. Curran Associates, Inc., 2020. URL pp: /ptp///eooccccccccccc wgs..ninggg... ngs. neur ips. cw/paper 2020/fi1221 640 8-
13

---

Published as a conference paper at ICLR 2023
Mikhail Yurochkin, Sebastian Claici, Edward Chien, Farzanch Mirzazadeh, and Justin Solomon. Hierarchical optimal transport for document representation, 2019.
Weiyu Zhang, Praveen Srinivasan, and Jianbo Shi. Discriminative image warping with attribute flow. In Computer Vision and Pattern Recognition 2011. pp. 2393-2400 2400. JEEE, 2011.
14

---

Published as a conference paper at ICLR 2023
7 APPENDIX
7.1 PROOF OF THEOREM 4.2
Here, we present the proof of Theorem 4.2. The main observation in the proof invokes perturbation analysis Mangasarian & Meyer Ferris & Mangasarian (1991) of linear programs to assert that, under mild uniqueness conditions, small changes to a linear program's 's data does not change the linear program's 's optimal solution. The informal reason why such a result is possible can be explained using a short, geometric argument follows.
Ferris
The feasible set of a nontrivial linear program is polytope, and, as a rule, an optimal solution to a linear program lives the point where hyperplane defined by the objective functional intersects vertex of the polytope. A small perturbation of the hyperplane does not alter the intersecting vertex. The derivative of a linear program's 's optimal objective value, treated function of the data fed to the LP, has been described several times in prior work, and under variety of conditions De Wolf & Freund (1855;; Agueh & Carlier (011)); Mills (957).
Smeers 2019)
The second claim of Theorem 4.2 is useful because dual solutions to the generalized EMD linear program are not unique. The claim explains how one can modify a given solution (found by direct gradient computation or else from an interior point solver, for example) so that it agrees with the solution yielded by the primal/dual greedy algorithm.
Proof of Theorem 4.2. Let 27, for [d], denote optimal solution to the dual linear program of equation equation 3 in the main paper. Standard sensitivity analysis of linear programs implies that 2z IR" (j E [d) is also optimal for the perturbed linear program,
maximize 2yERd
E(e + sh,)
subject
(11 - + za(ia) S i(i,)...,aa)
where the indices in the constraints include all E [m]. j E [d]. >> 0 is sufficiently small and hy E I2" are held fixed.
If ó( +eh,..... Za + +haa) represents the optimal objective value of this program, then by linearity,
Φ<21 ehi....., Fa + Eha) 6(.1.....,.. .... Σ h1z3.
Thus, we can form the directional derivative of á as
Φ( + ehi,........................ + sha) (( 6(I1....,
E, K3z3
lim 50+
E ||AA||
||A|||
where [|A]| = E, 11 From this, follows that
Vo(oi,..., = (zi ,., =z)
This shows the first claim of the theorem.
To see the second claim, have from Theorem 3.1 item of Kline (2019) that
Σ (1)
for all E [m]. Consequently, if one defines
(z) 2 (,)),,,.,,((()))) (z)e)),
then since we assume that e' e'z, for all j E [d].
Σ 5 + tn) = Σ 25zz +
Edje +1 Σ (n)
djg...
where the last equality holds by equation 66 This shows the second claim.
15

---

Published as a conference paper at ICLR 2023
7.2 DIFFERENTIABLE HISTOGRAMMING
Algorithm 2 Differentiable Histograms
function INIT(A)
I/ bins, (discretization) II bin size
2: r. = 1/n
3: locs == arange 1,
I/ bin boundaries
4: function FORWARD(acts)
5: edfss o(acts)
II compute CDFs
6: counts =
7:
for loc in locs do
8:
dist = edf's 8 loc
11 dist. to boundary I/ soft bucket count
9:
ct = Σ (r distli)
RE [
10:
counts. (ounts.pppend(ct)
11:
out = (counts))
12:
out out sumn(out) (out)
13:
return out
While gradients are now readily available, typical ML pipelines do not have distributions histograms predefined at outputs which can be fed directly into our EMD loss. Applying existing binning procedures over the batch to estimate histograms will break the ability to autodifferentiate: soft thresholds are necessary at bin boundaries such that samples within a bin may move smoothly as needed. prarithh@@provvidee
differentiable histogram implementation. Using a rectified linear relaxation allows for samples to have continuous gradient towards neighboring bins.
7.3 EXPERIMENTAL DETAILS
Results reported in tables in the main paper are of the form (sD), where M is the mean and SD is the standard deviation calculated over replications.
Setup details. Experiments were conducted using NumPy and PyTorch on Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz with an Nvidia Titan Xp GPU. Particular parameter settings and experimental runs can be found below in the scripts included with the code provided at litttps //github. caam/ronaemm/ demd
7.3.1 DATA AND LICENSES
The datasets Adult, Communities and Crime, and German datasets are all available under Cre- ative Commons Attribution 4.0 International (CC BY 4.0) licenses via the UCI Machine Learn- ing Dataset Repository https: /ttchi///rriieeee http:///tttt://mmll ab. ie cuhk edu. wtt.:ed.......oeeeeeeeeeeo wttpproojcts//eeeebbbbee.eeeeeee commercial purposes. See the website for more details.
ics uci wwt..eedddmmeeeeeeeeeee php The CelebA html available for non-
ACS Data. The American Census Survey (ACS) has recently made available a large set of de- mographic data. The original UCI Adult dataset Dua & Graff] (2017) was curated from this data, however recent work by Ding et al. (202)) has identified temporal shifts in demographic data, and recommends using more recent collection a baseline when evaluating biases and adjusting for fairness. Part of their contribution includes APIs to directly interface with the data provided by the ACS, and the ability to identify and construct similar problems associated with the original UCI-provided dataset, albeit with updated data. Data for the income predic- tion task was downloaded from 2018, localized Louisiana. Race is the provided group label, which we wish to be agnostic towards, over some measure of our output. Data was accessed using the folktables codebase https: /ettps:/ggithie //tptttbtttbb/t/// cwm zyk 1 / fo 1 llklalleeee with MIT Li- cense. The US Census data accessed is available for use so long as it is not used in combination with other data "to identify any particular respondent to a Census Bureau survey." See https | -feees--o-ee-eeeeeeeeeeeeeeeee html for more
wwwww.cnnsu.c. httpa///..cooeeeeceeeeeeeeeeeeee
details.
German Data. The German dataset classifies people good or bad credit risks. There about 20 features (7 numerical and 13 categorical). These features represent the economic status of the person, such as, credit history, savings account, year of present employment, property and others.
16

---

Published as a conference paper at ICLR 2023
Adult Data. The Adult dataset is comprised of demographic characteristics from the UCI repository Dua & Graff (2017). The protected attribute here is gender. It contains 44, 842 samples. The features that were used in the experiments include "age", "workclass", "fnlwgt", "education", "education- num", "marital-status., "occupation", "relationship", "race", "sex", "capital-gain" ""capital-loss" "hours-per-weet" "native-country", "income". A positve target label in this dataset is indicated by the attribute "income-bracket" being above S50K.
Communities and Crime Data. The Communities and Crime dataset consists of summary statisties of per-capita measures from a wide variety of communities across the United States, measured from a number of US census and surveys from the 1990's. The original goal of the dataset was predict crime rates in communities as a function of various demographic, socioeconomic, and other features. The dataset has widely become known as the prototypical example in which using racial population distributions can be extremely harmful in perpetuating stereotypes and lead to models that continue to exacerbate inequity that may exist within the data. As such, the dataset has become a de facto tool in evaluating fairness metrics and methods that attempt to account for these incquities and biases. The preprocessed data contains 1994 samples, and we attempt to predict the violent crime rate (binarized at 0.3 after normalization between 0 and 1), and the sensitive attribute is similarly binarized version of the percentage black population variable.
CelebA Data. CelebA (Liu et al., 2015) consists of 200K celebrity face images from the internet annotated by a group of paid adult participants. There are up to 40 labels available in the dataset, each of which is binary-valued.
7.3.2 FAIRNESS EXPERIMENT DETAILS
All experiments related to fairness use a three-layer fully-connected neural network classifier with a hidden layer size of 100. Numbers reported in Table I in the main paper are means and stan- dard deviations over three replicate runs with different seeds. Hyperparameters were selected as described in the main paper, by taking the best result for each dataset over the parameter range E [1.0, 0.1, 10, 0.01, 100, 0.001]. The full results of this sweep are presented in Table and Table 4
The |DP] and [FO] measures are the gap between the corresponding conditional probability dis- tributions when there is single binary group attribute, and the largest gap (maz min) when there are more than 2 groups. The DEMD loss is computed as described in the main paper with a discretization/Din level of 10.
7.3.3 HARMONIZATION EXPERIMENT DETAILS
For all our experiments related to harmonization, we an encoder-decoder framework comprising of fully-connected layers. The hidden layers comprised of 64 nodes and the latent space was of dimension 30. We report the mean and standard deviation on unseen test datasets for three random runs. The hyper-parameter selection has been done on a validation split obtained from the training dataset. The model that achieves the best ADV (the adversarial evaluation measure), with the test set accuracy remains within 5% of the vanilla (titled "None" in the paper) model, is chosen.
Recall that the harmonization experiments aimed minimizing the distributional differences of the latent features across the groups. Below, we will provide details on the evaluation metrics, ADV and MMD measures, that aptly assess distributional differences of the latent features.
Evaluation Metric: Adversarial Measure (ADV) The ADV measure corresponds to the accuracy obtained by training separate neural network predict groups from the latent features. This step conducted post harmonization. A lower value of the ADV accuracy denotes that the latent features are free of any group related information. This implies successful harmonization and suggests minimal distributional differences of the latent features across groups We follow (Xic al. 2017) for training the adversary used for reporting ADV measure. We use a three-layered fully- fully-connected network with batch normalization and train it with Adam optimizer for 200 epochs. The learning rate for the adversary is decreased multiplicatively by a factor of 0.65 every 10 epochs for convergence.
Evaluation Metric: Maximum Mean Diserepancy (MMD) We simply use the following MMD criterion as described in (Gretton et al. 2006) and evaluate the metric on the latent features obtained from the test set. Each group is considered as different distribution and lower value of this metric
17

---

Published as a conference paper at ICLR 2023
Table 3: Fairness Experiments. Mcasures evaluated using standard metrics: maximum Demographic Parity Gap (-DP-), maximum Equalized Odds Gap (-EO-,, and (DEMD). For all measures, lower values are preferred. With comparable accuracy, DEMD regularization leads to fairer representations as measured by common metrics. DP and EO measures scaled by 100 for of presentation. Best results shown in bold.
German
Adult
Reg. Type
A
DP
EO
DEMD
DP
E0
DEMD
None
0
0.17ro.06)
0.11(0.02)
1.69(0.92)
0.18(0.01)
0.13(o.01)
1.69(o.07)
DP-Reg.
0.001
0.19r0.08)
0.12(0.0)
1.79().27) 27)
0.18(0.01)
0.13ço. o3
1. (.....07))
0.01
0,2710.06)
0.17:0.01)
1.5r0.21)
0.13(0.01)
0.14().01)
0.99)).09)
0.1
0.23(0.2)
0.12(0.1)
(.99
0.02().03)
0. 0.15(0.02)
0,28((.09)
1.0
0.0g0
0.19)o.17)
0.Oro-o)
0.0
0.2(0.0)
0.0(p.0)
10.0
0.0:0.0)
(.1(0.17)
0.0ro.0)
0.0go.0)
0.2(0.0)
0.0(0.0)
100.0
0.0g0.00 0)
0.0(0.0)
0.0(o-0)
0.0ço.0)
0.2(0.0)
0.0(p.0)
EO- Reg.
0.001
0.17(o.0s)
(.1(0.02)
1.51(0.34)
0.18(0.01)
0. 0.13)).01)
1.67(0.07)
0.01
0.14(0.07)
0.09(0.04)
(o.3
0.15(0.01)
0.12(0-01)
1.44(0.08)
0.1
0.0:0.0)
0.0(0.0)
0.47(o.21)
0.03
0. 0.06ço.01)
0. 0.29((.u0 02)
1.0
0.0:0.0)
0.0ro.0)
0.08(..14)
0.0:0.0)
0.0ga.0)
0.0ro.0)
10.0
0.0ça.0)
0.19(0.17)
0.D(o.a)
0.0ça.0)
0.0(a.0)
0.0(o.0)
100.0
0.0g0.0 0)
0.0(0.0)
0.0(o.0)
0.0ço.0)
0.2(0.0)
0.0(p.0)
Bary
0.001
0.17ro.05]
0.11co.02)
1.69
0.18(0.01)
0,13(0.01)
1. 1.69(0.07)
0.01
0.17(0.05)
0.11(o.02)
1.68(0.31)
0.18(0.01)
0.13(0.01)
1.69(0.07)
0.1
0.17(0.05)
0.1(0.02)
1.51(0.a5)
0.18(0.01)
0.13(0.01)
1.68(0.07)
1.0
0.16r0.06)
1.5(0.28)
0.17(0.01)
0.13(0.01)
1.6(0.07)
10.0
0.06(0.07)
0.04(0.05)
0.58
0.09
0.09(o.01)
1.02:o
100.0
0.06(0.11)
0.03ro.00 06)
0.06((.13)
0.0ço.0)
0.04co.01 03
0.39(0.06)
DEMD
0.001
0.1 0.17:0005)
0.1 ((0
1.69
0.18(0.01)
0. 0.13
..60(o.77
0.01
0.17(0.05)
0.11 02)
1.69(0.32)
0.18((.01)
0.13(o.01)
1,69 07)
0.1
0.19(c.06)
0.11(0.02)
1.32(0.18)
0,18(0.01)
0.13(0.01)
1.66(0.07)
1.0
0.2(0.00)
0.11(0.08)
1.59(0.4e) 46)
0.14(0.01)
0.12(0.01)
1.43(0.07)
10.0
0,16(0.18)
0.09(0.07)
0.5(0.12)
0.07(0.02)
0.08(o.01)
0.91(0.17)
100.0
0,06(0.08)
0.18(o. 183
0.06ça.08)
0.01(..01)
(.01(0.01)
0.41(0.05)
Table Fairness Experiments. Mcasures evaluated using standard metrics: maximum Demographic Parity Gap (DD-)), maximum Equalized Odds Gap (-EO-), and (DEMD). For all measures, lower values are preferred. With comparable accuracy, DEMD regularization leads to fairer representations as measured by common metrics. DP and EO measures scaled 100 for of presentation. Best results shown in bold.
Crime
ACS Income
Reg. Type
>
DP
E0
DEMD
DP
-B0
DEMD
None
0
0.38r0.06)
0.45co.om 08)
2.86ço.38)
0.37(0.01)
0,25(o.0)
1. 1.700..32)
DP-Reg.
0.001
0.36
0.44co 04)
2.81
0.57(0.37)
0.5co 44)
4.38 16)
0.01
0.35(0.02)
0.11(o.0a)
2.61(0.17)
(.81(
0.76(0.42)
3,45(0.71) 71)
0.1
0,22(0.0m)
0.29(o. 12)
1.58(0.28)
(.62(0.53)
(.51(
2.67(0.03)
1.0
0.0g0.0)
(.41(o.03))
0.D(o.0)
0.0ç0.0)
(0.7(
0.0(p.0)
10.0
0.0:o.0)
0.26(0.23)
0.D(o..)
0.0ço.0)
(88
0.0(c.0)
100.0
0.0g0.03
0.26(0.25)
0.D(o.0)
0.0ço.0)
0.33(0.58)
0.0(0.0)
EO-Reg.
0.001
0.38(0.06)
0.45ço.03)
2.85 2.8500.
0.36
0.25(0.0)
(.77().32)
0.01
0.36ro.o8)
0.44(0.03)
2.69().44)
0.33
0.24(0.0)
3.6(0.29)
0.1
0.1 (p.077
0.39 03)
0.
(.03
0.03(o.0) 0)
0.53
1.0
0.0:0.0 o)
0.41
0.0ço.0)
0.0:0.0)
0.0ç0.0
0.0ro.0)
10.0
0.0:0.0)
0.41(0.03)
0.D(o.0)
0.0ço.0)
0.33(o.58)
0.0(c.0)
100.0
0.06(o.1)
0.09(o.15 18)
0.5(0.87)
0.0ça.0)
0.33(0.58)
0.0(o.0)
Bary
0.001
0.38co.06)
0.15co.08
2.86 2.8600.35)
0.37(0.01)
0.25(o.0)
1.78(0.32)
0.01
0.38(p.06)
0.45ço
2.80 39)
(.37().01)
0.25ço.0)
4.8(0.32)
0.1
0.38(c.06)
0.15co.03)
2. 2.83))
0.48(0.04)
0.28(o.01)
5.02(0.31)
1.0
0.37(0.00)
0.44co.o8 03)
2.65(0.45)
1.0ç0.0)
1.0ça.0)
5.66iç0.3)
10.0
(.21(
0.41(0.04)
1.36(0.32)
1.0ça.0)
1.0(0.0)
4.5(0.57)
100.0
0.01
0.4 03)
0. 0.19(0.)) 1)
0.0ç0.0 0)
(.33(o.58)
0.0(0.0)
DEMD
0.001
0.38(0.05)
0.44(0.04)
2.85ç0.39)
(g37
0.25(o.0)
4.78(0.32)
0.01
0.38
0.45co
2.85 38)
0.38
0.26((.0)
4.82(0.32)
0.1
0.38(6.05
0.14co. 03)
2, 2.83))339)
1.0
1.0g0.0)
4.33(0.42)
1.0
0.35(o.o5)
0.43ro 03)
2.54(0 39)
0.93(g.12)
1.0
2.67(0.17) 17))
10.0
0.26(0.05)
0.39(o.02)
1.35
0.68(0.28)
1.0(0.0)
0.9:0.47)
100.0
0.0:0.0)
0.41(0.08)
0.26;0.02)
0.0g0.0)
1.0(0.0)
0.0(0.0)
18

---

Published as a conference paper at ICLR 2023
Total MWGAN Discriminator Loss
Total MWGAN Generator Loss
0.0
2.5
-5.0
40
25000
50000
75000
100000
25000
50000
75000
100000
Batch (Step)
Batch (Step)
Total DEMD Discriminator Loss
Total DEMD Generator Loss
2.5
70-
-2.5
-500
.7.5
50000
75000
100000
50000
75000
Batch (Step)
Batch (Step)
Figure 7: Convergence Plots for MWGAN and DEMD on CelebA Multi-Domain Image Translation.
suggests minimal distributional differences across the groups. For latent feature vector & and groups i/j. we have
MMD = Zi (()) goos,
E
K(Z,,))
KC )l
(g))(
The criterion is defined using a Reproducing Kernel Hilbert Space with norm || II and kernel K.
7.3.4 MWGAN DETAILS AND ADDITIONAL RESULTS
The MWGAN code bttpss:/gitee com/ deepeeee/m/eeeeeeeeeeee /M/G0 license extended from the original StarGAN codebase ht pttpp:/// stargan
was used under the MIT
The original paper constructs an inter-domain penalty added to the multi-domain GAN discriminator loss follows:
2
RMWGAN = A
Σ [ g00 EEgo IV [V](((()
L
8
The sampling for expectation in practice done by interpolating randomly between real data and generated data for each domain. In contrast to this, we directly push the gradient norms computed over samples from each domain be close using our DEMD regularizer:
RDEMD(f) X DEMD ((II(([[IVV] ([IV)((())] (tl).
where indicates the domain associated with the fake samples generated in the same manner for each domain.
Convergence comparison. Interestingly we observe that our construction tends to lead more stable training. In Figure we can see that the variance of the total discriminator and generator loss fluctuate much less. We suspect that this can be directly attributed to the boundedness of the gradients of the DEMD regularizer, specific to the method where compute the gradients via the dual of the LP: the dual variables are bounded by definition and in this particular LP, are bounded exactly by the number of bins used for discretization. While additional investigation is needed, smoothness has been identified as a desirable property GAN training (Arora et al. 2017 Chu et al., 20200 Lokhande al. 2020b Ravi et al. 2019).
19

---

Published as a conference paper at ICLR 2023
Model
Blond Hair
Eyeglasses
Mustache
Pale Skin
MWGAN Cao et al. (0019)
49.91
45.74 34.43
45.49
38.67
DEMD
47.29
50.69
39.60
Table 5: Train FID Scores for CelebA Multi-Domain Image Translation! !
Quantitative Results. Using the Frechet Inception Distance we quantitatively measure the resulting generative samples. Following the description in Cao al. (2019), present the FID scores of our model and theirs in T Our metric as drop-in replacement performs comparably.
7.4 D-DIMENSIONAL EARTH MOVER'S S DISTANCE BACKGROUND AND ALGORITHM
Algorithm 3 describes the greedy algorithm that solves both primal and dual generalized Earth mover's programs, also see [Kline, 2019). The algorithm accepts distributions (i.c., histograms) Pl..... Pd E 12 with e'p; for j E [d]. Although the algorithm states that all histograms have the same number of bins, the algorithm can be easily adapted to accept inputs E R with n, # nz.
Algorithm 3 EMD Primal/Dual Algorithm
input Pj E R. with e'p, = 1. (Vj E [d] /ftteaation index, active indices, primal variables, dual variables
= 0 Z, = 0 E Zd x 0 RT" 2j = O E (Vj (d] while [(j) S n. (Vj E id) do
s4 == minseld (1)))
I1 the mass move II update the EMD solution // shrink the data
ax() t 8k
(,(( + (I()) - Sk. (Aj E d)
jr < argmin Pj (T())
(10")
k-
to cT)
I/ cost of this step
I(J*) & n then
2/. (I("))
4-11 + 2z. (((() 1)
Il update the dual solution
return x, (..,..., za), and the objective value Ex sk4k-
The algorithm has explicit terminal conditions for the main while loop. In the worst case the number of iterations can be rdd.
7.5 EXTENDED ETHICS DISCUSSION
As discussed in the main paper discussion, the primary application of our proposed construction is reduce invariance over particular of features. practice, with respect typical machine learning models and pipelines, this corresponds to minimizing performance difference as measured across subgroups within the data corresponding to a minority protected subsets of samples or individuals. While the construction can be applied to any existing ML pipeline, we do not claim to provide catch-all solution for group disparity that may be inherent the data exacerbated by the choice of the MI. model that is being used. As always, care needs to be taken when working with sensitive data or models which may have disparate impacts on different groups. We point interested readers to the following extensive surveys and references therein regarding various methods and procedures for addressing and dealing with bias and unfairness in ML problems, and the potential
danger associated with using models without care: (Mehrabi al. 2021
Leavy 2018
O neil 2016
Aleesanddr et al. 2017 Rakova et al. 2021).
Results presented here computed using the pytorch- tid package with code from the MWGAN repository here: ttttts:///itttt com tttp///sttttt////et ter /pyt htpppptorrree orch-fidi We were unable to replicate the FID scores provided in the original paper, but expect trends to he relatively similar when compared across different scoring methods.
20

---

Published as a conference paper at ICLR 2023
25
1
NO1
Figure More qualitative results from the multi-domain image translation problem with (Left) Cao et al.] (2019). (Right) DEMD (ours). On attributes such as "Blond Hair" and "Eyeglasses", the generated images through our DEMD procedure appear more realistic. On other attributes, the generated images are comparable.
21

---

Published as a conference paper at ICLR 2023
G
Gu
RS
CL
RS
WAS
WAS
WAS
Figure More qualitative results from the multi-doman image translaton problem with (Left) Cao et al.] (2019). (Right) DEMD (ours). On attributes such "Blond Hair" and "Eyeglasses", the generated images through our DEMD procedure appear more realistic. On other attributes the generated images are comparable.
22

---

Published as a conference paper at ICLR 2023
We also note that the final multi-marginal GAN image translation application could be used to generate so-called "deepfakes." While the results of our algorithm are comparable to existing works, believe that existing methods of identifying deepfakes would work well, and that the methods provided here and in the original paper Cao et al. (2019) would require significant effort to be made practical for much larger scale images.
ACKNOWLEDGMENTS
This work supported in part NIH grants RF1 AG059312,, RFIAG062336, RFIA9059869, and NSF award CCF 1918211. The work presented here was partially developed while Ronak Mehta, Jeffery Kline, and Glenn Fung were the Machine Learning Group at American Family Insurance. The authors thank Sathya N. Ravi (UIC) for time reading the paper and providing suggestions.
23


Reviews:
[{"review_id": "bhlvadmA--r", "reviewer": "Reviewer_7jEQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new algorithm to compute MMOT. It narrows down the ground cost to deal with a specific form of MMOT. That results in fast computation while still maintains its generalization to normal use cases. Simplification is supported with theoretical proof. Authors also insert a few tricks to speed up and differentiate the iterations. Empirical results show improvement over different tasks after applying the proposed algorithm in network training. ", "summary_of_the_review": "I'm leaning toward acceptance.\nThe paper is well written, theoretically solid, and it offers new insights in accelerating the computation of MMOT.\nExperiments also show several use cases of the new algorithm.", "strength_and_weaknesses": "Strength:\nEfficient algorithms for solving MMOT is an open field, especially a general one. This paper finds a sweep spot in the ground metric where the problem can be solved in linear time and differentiable to transportation map.\n\nWeaknesses:\nI haven't found major weakness of the paper. The theoretical contribution to MMOT seems marginal though.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aACfCqYn4J", "reviewer": "Reviewer_Gjfe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors of this work propose a fast algorithm for the computation of the discrete multi-marginal optimal transport problem (MMOT). The algorithm is derived from the dual form of the problem and has an explicit form for the gradient w.r.t. the objective. This makes it much faster than automatic differentiation. The algorithm is applied to fairness problems and image translation, demonstrating its effectiveness in both domains.", "summary_of_the_review": "Although the proposed method can be useful for some applications, I do not think this work has enough novelty to be accepted. \n\nI would encourage the authors to theoretically or empirically explore the complexity of the so-called “outer loop” under some simplified setting. This would make the work more solid and complete. ", "strength_and_weaknesses": "The authors should improve the writing of the paper. The overall logic is not smooth. In section 4.1, by using terminologies like “forward”, “backward”, “inner loop”, “outer loop”, the authors already assumed the readers know how the proposed tool is combined with NN, which can actually have many different forms. The definition of this combination is instead introduced in Section 4.2. In Section 4.2, the authors failed to clearly explain why the histograms are needed (although this can be vaguely inferred from some other literature). There are also some minor issues, such as the misusage of \\citep and \\citet in line 15 of introduction and line 5 of page 3.\n\nI am confused about the contribution of the work. Please correct me if I misunderstand anything: On the theoretical side, the authors prove the second half of Theorem 4.3, i.e., derive the gradient of the objective, which is essentially just the gradient of an LP problem. On the methodology side, the authors apply the derived gradient directly to the backward pass, which is a well-known trick to speed up the computation for problems where there are optimization problems in the forward pass. On the application side, the authors apply the proposed method to fairness, invariant representations, and image translation, where none of the applications are newly set-up. Furthermore, the performance of the proposed method is not as good as Li (2014) and Xie (2017). \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1iHz7xh4tvO", "reviewer": "Reviewer_RRc2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a novel, efficient method for computing multimarginal optimal transport plans. The approach applies to cases with Monge cost, which while a special case, the authors argue is relatively general. A generalized earth-mover distance is introduced, which is linear in the dimensions and bins in theory, and show that in practice can lead to orders of magnitude speed up relative to existing methods. Empirical results are demonstrated in fairness cases as well as image translation. ", "summary_of_the_review": "The paper introduces generalized earth mover distance which enables efficient computation of MMOT plans. The approach represents a significant advance over existing methods for computing MMOT plans, and efficiency gains are clear theoretically and practically. The approach is demonstrated on domains of interest. This is a nice contribution. ", "strength_and_weaknesses": "Strengths: \n- OT is a method of increasing importance in the machine learning literature. \n- Multi marginal OT is potentially important but hampered by significant computational costs that scale poorly with additional dimensions. \n- The theory clearly demonstrates the computational opportunity, which is nicely confirmed experimentally. \n- The empirical demonstrations show that the approach can be deployed on interesting problems. \n\nWeaknesses: \n- I did not find any particularly notable weaknesses of the paper. While the setting is clearly a restriction of the broader MMOT problem, the authors convincingly argue that it is not as much a restriction as one might think, and the computational gains are significant and worthy of the compromise. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%