Approximate Birkhoff-von-Neumann decomposition: a differentiable approach
Authors: Andrés Hoyos-Idrobo
Venue:  (2021)
Keywords: Birkhoff-von-Neumann decomposition
doubly stochastic matrices
Riemannian optimization
Fairness exposure in ranking

Abstract: The Birkhoff-von-Neumann (BvN) decomposition is a standard tool used to draw permutation matrices from a doubly stochastic (DS) matrix. The BvN decomposition represents such a DS matrix as a convex combination of several permutation matrices. Currently, most algorithms to compute the BvN decomposition employ either greedy strategies or custom-made heuristics. In this paper, we present a novel differentiable approach to approximate the BvN decomposition. Our algorithm builds upon recent advances in Riemannian optimization on Birkhoff polytopes. We offer an empirical evaluation of this approach in the fairness of exposure in rankings, where we show that the outcome of our method behaves similarly to greedy algorithms. Our approach is an excellent addition to existing methods for sampling from DS matrices, such as sampling from a Gumbel-Sinkhorn distribution. However, our approach is better suited for applications where the latency in prediction time is a constraint. Indeed, we can generally precompute an approximated BvN decomposition offline. Then, we select a permutation matrix at random with probability proportional to its coefficient. Finally, we provide an implementation of our method.

Under review as a conference paper at ICLR 2021
APPROXIMATE BIRKHOPF-VON-NEUMMAN
DECOMPOSITION: A DIFFERENTIABLE APPROACH
Anonymous authors Paper under double-blind review
A ABSTRACT
The Birkhoff- Birkhoff-vonNeemmin von-Neumann (BvN) decomposition is a standard tool used draw permutation matrices from a doubly stochastic (DS) matrix. The ByN decomposition represents such DS matrix a convex combination of several permutation matrices. Currently, most algorithms to compute the BvN decomposition employ either greedy strategies or custom-made heuristics, In this paper, we present a novel differentiable cost function to approximate the BvN decomposition. Our algorithm builds upon recent advances in Riemannian optimization on Birkhoff polytopes. We offer an empirical evaluation of this approach in the fairness of exposure in rankings, where we show that the outcome of our method behaves similarly to greedy hmss. Our approach is an excellent addition to existing methods for sampling from DS matrices, such as sampling from Grumbel-Sindhee distribution. However, our approach is better suited for applications where the latency in prediction time is constraint. Indeed, we can generally precompute an approximated BvN decomposition offline. Then, we select a permutation matrix at random with probability proportional to its coefficient. Finally, we provide an implementation of our method.
INTRODUCTION & RELATED WORK
Sampling from doubly stochastic (DS) matrix a significant problem that recently caught the attention of the machine learning community, with applications such exposure fairness ranking algorithms (Kahng et al. 2018 Singh & Joachims 2018), strategies to reduce bribery (Keller et al. 2018 2019). and learning latent representations (Mena et al.
2018: Grover et al. 2018: Linderman et al. 2018). We consider the
decomposition [BvND) (Brkhoof 1946), which is deterministic and represents a DS matrix as the convex combination of permutations matrices (or permutation sub-matrices). In general, the BvND of a particular DS matrix is not unique. Sampling from BvND boils down to selecting a sub-permutation matrix with a probability proportional to its coelficient.
Current BvND algorithms rely greedy heuristics (Dufossé Uçar 2016), mixed-integer
linear programming (Dufossé et al. 2018), or quantization (Liu et al. 2018). Hence, these methods are not differentiable.
We rely on reparametrization techniques to use gradient-based algorithms (Grover et al. 2018: Linderman al., 2018). Recently, MMna et al. (2018) introduced reparametrization trick to draw samples from a Gumbel-Sinkhorn distribution. However, these methods can un- derperform in applications where there is constraint the prediction, as reparametrization methods require to solve a perturbed Sinkhorn matrix scaling problem.
In this work, we propose an alternative to Gumbol-matchigg-elaree approaches, which well-suited for applications where we do not need to sample permutations online. Thus, our method fast during prediction time by saving all components in memory. We call our algorithm: differentiable approximate Birkhoff-von-Neumaee continuous relaxation of the BvND. We rely on the recently proposed Riemannian gradient descent on Birkhoff polytopes. The main parameter is the number of components of the decomposition. We enforce an approximate orthogonality constraint on each component of the BvND. To our knowledge, this is the first gradient-based approximation of the BvND
decomposition, and it is

---

Under review as a conference paper at ICLR 2021
2 PRELIMINARIES
We first present some background on the BvND and comment on recent advances on Riemannian optimization in Birkhoff polytopes.
Notations. We write column vectors using bold lower-case, e.g., X. X; denotes the i-th component of We write matrices using bold capital letters, e-g.; X. X; denotes the element in the i-row and j-column of X. [n] (1,...,n} Letters in calligraphic, e-g. P denotes sets. II denotes the Frobenius norm matrix. Ip is the p x p identity matrix, and 1, 1 vector of size n. We use the superscript of matrix X to indicate an element of a set. Thus, {X*]_ be short for the set {X*,... x*). However, we denote X matrix X iteration An denotes the probability simplex, and @ is the Hadamard product.
Ji=1
2.1 TECHNICAL BACKGROUND.
Definition (Doubly stochastic matrix (DS)) A DS matrix is non-negative, square matrir whose rows and columns sums The set of DS matrices is defined as:
:= = (XE X1, = In 1 =
(1)
Definition (Birkhoff polytope) The multinomial mandfold of DS matrices is equivalent
to the conver object called the Birkhoff Polytope (Birkhoff] 1946), an (n 1) dimensional conver submanifold of the ambient Raxa with n! verlices. We use DP, refer to the Birkhoff Polylope.
Theorem 1 (Birkhoff-von Neumann Theorem) The convez hull of the set of all per- mutation matrices is the set of doubly-stochastic matrices and there ezists a potentially non-unique such that any DS matria be expressed linear combination of l permu- totion matrices (Birkhoff
1946
c: Hurlbert 2008)
(2) While finding the minimam le shown be NP-hard (Dufossé al. 2018). by Marcus- Ree theorem, know that there exists constructible decomposition where k < (n 1)² + 1. Fig. shows an illsttation of the BuND.
X = = + O.P*. 0, >
0, 1 11
E
+
=.4
+ +31
+ .29
Figure Illustration of the a doubly stochastic matrix as a convex combination of permutation matrices.
decomposition (BvND): One can represent
Definition 3 (Permutation Matrix) A permutation matriz is defined sparse, square binary matrix, where each column and each row contains only a single true. (1) value:
Pn = {P 1)*x)">" P1, = 1n, 1 =
33)
In particular, we have that the set of permutation matrices P,, the intersoction of the of DS matrices and the orthogonal group O, = (xxx X E B=xn]. P, DP, no,
GGeemans) 2015).
Riemannian gradient descent on DP,, The base Riemannian gradient methods use the following update rule x(++1) = Rxw (-y H (x())) (Absil et al. 2009b, where H (x(1) is the Riemannian gradient of the loss L DP.. l at X 7 the learning rate,
2

---

Under review as a conference paper at ICLR 2021
and Rxin DP - DP, is retraction that maps the tangent space at X(() to
the manifold. Douik & Hassibi (2019) defined H (x(0) = xxx [ 7. (X(1) @ x
where 11 x is the projection onto the langent space of DS matrices at X The total complexity of an iteration of the Riemannian gradient descent method on the DS manifold
(16/3)n² + 7n2 + log(n) / (Douik & Hassibi 2019 See Appendix B for the closed-form computation of ( and Rx
APPROXIMATE BIRKHOFT-VON-NEUME
DECOMPOSITION
We propose a differentiable loss function to approximate the BvND of DS matrix. This approach valuable when one can save the resulting decomposition in memory.
3.1 FORMULATION
Plis al. 2011] showed that on DPn, all permutations are located on an hypersphere 8(n-1) of radius vn T,, g(n-1)² x (m(-1)) ||x|| vn 1n centered at the center of mass C, = 1 Therefore, we can rely on the hypersphere-basse relax- ations Plis et al. 2011 Zanfir & Sminchisoscu 2018 to learn the sub-permutation matricos.
However, we have two main reasons avoid the hypersphere relaxations in our sctting: i) Birdal & Simsekli (2019) showed that the gap as a ratio between DP,, and both S(n-1)²-1 grows. ūï While there exist polynomial-time projections of the n!-element permutation space onto the continuous hypersphere representation and back, these algorithms are prohibitive in iterative algorithms, as each operation displays a time complexity of Onn)).
and On grows to infinity
Another possible direction to build a convex combination of sub- aub-permutation matrices that is an e-close matrix of M E DP,, A n x matrix M' is an e-close matrix of M E DP,, if M, - M, I c, (i. [n|?. Barman (2015) showed that it is possible build an c-close representation using at most ((lo"(n)/<*) matrices. Kulkarni et al. (017)) further improve this result to using at most 1/c matrices. Therefore,
can build matrix M' that satisfies ||M | S 6, where M' = Σ === Vn ' and X E Pa for I [k]. However, it is not currently practical to operate directly on Pn. as have to solve combinatorial optimization problem. Additionally, Pn. lacks a manifold structure. Thus, we relax the domain of the absolute permutations by assuming that cach X' DP, for E [k] (Linderman ct al., 2018 Birdal & Simsckli 2019 Lyzinski et al.) 2015 Yan et al. 2016). We add an orthogonal regularization to ensure that each matrix X is approximately orthogonal. We can use Riemannian gradient descent-based methods on the manifold of DS matrices to minimize the total loss, which has time complexity of Onn²) per iteration.
3.2 OPTIMIZATION PROBLEM
We want to solve the following optimization problem:
min MEA*
M
X
s.L. DD, for l E [k],
(4)
where & is (11/e) (by Theorem 9 in Kulkarni et al. (0177) for an e-close matrix approximation. Now, recast Eq. 4 in its Lagrangian form and include additional penaltics to leverage the Riemannian gradient descent on DP,,-
Reconstruction loss. candidate DS matrices,
This loss measures the reconstruction error for given set of k Ji=ı and weight vector 77 E A as follows:
d M
Trecons (x.('')/_)
Σ
m X
(5)
1=1
F
3

---

Under review as a conference paper at ICLR 2021
Orthogonal regularization. This loss encourages DS matrix X to be approximately orthogonal by pushing them towards the nearest orthogonal manifold (Brock et al. 2017). We compute it follows:
Tortho () =
E -x
(6)
(1J)
Eq. 0 corresponds to entrywise matrix norm that promotes sparsity. Nevertheless, we can
also use other orthogonality promoting losses like Zavlanos & Pappas (2008) or Bansal
et al. (2018). e.g., soft orthogonality regularization, Lortho XX F.. We note that
Lortho DP,, + R+ and is zero iff X E On. However, Eq. is not convex in X and we are guaranteed only to converge to saddle points.
Optimization objective. We compute the total loss by adding the reconstruction loss and an orthogonal regularization for each X for 1 E [k], as follows:
min (X'EDP P ( (x' iiii (, = Lrecous (x:1)/))))
(1m1
Σ 1=1
M Lortho (x') w (t(),,
(7)
where 22()) is a regularization function, w > 0 and 14 > 0 for 1 E [b] are regularization hyper-parameters that control the trade-off between reconstruction and orthogonality. For simplicity, we assume the same value of for all E [k]. Algorithm displays a summary of our proposed solution. This algorithm has a complexity per iteration of Okk")). Thus, are interested in the h < regime.
Diversity. The regularization function 92(-) is necessary to avoid trivial solutions and force using various reconstruction components. For some 7 E [k:], the model sets X to M do not regularize 17. However, biasing the contribution of each component {x1} problem-dependent. We set (?-)) = -11-18.. We remark that this regularization does not impose fining different sub-permutation matrices. However, repcated sub-permutation matrices are not an issue for the BvND (sce Fig. 3).
J is
Orthogonalization cost annealing (optional). We can use variable regularization y(() at training time to improve fining suitable solutions (Bowman et al. 2015). At the start of training, we set (L = 0, so that the model learns to represent with various components. Then, as training progresses, we gradually increase this parameter, forcing the model to impose the orthogonality constraint. This process boils down to computing y = min (1. max (o, (,11, μu, were t, and to denote the initial and final iteration of the annealing, respectively. However, also need tune and 4i
Refinement. The primary use of the BvND to sample (binary) permutations matrices from DS matrix. However, the solution of Eq. 7 yields approximately orthogonal matrices. Thus, we still need to round/refine the solution to return a permutation matrix. We can use two different approaches: deterministic rounding rounding by stochastic sampling. The deterministic rounding finds a feasible permulation of a given DS matrix via the Hungarian algorithm (optimal transport problem) (Peyré al. 2019 Birdal & Simsekli 2019). where we set the (transport) cost for each | [k] to K = -I-X X. Thus, we solve K where X denotes the nonzero column of the ith row of the X - minx 1 Σ >",,',
matrix X However, the matching is not differentiable. In that case, can also the Sinkhorn algorithm (Cuuuri 2013), which solves an entropie-regularized optimal transport problem with cost K'S We set small entropic regularization (temperature) parameter. Our experiment showed similar performance for the matching and Sinkhorn, which suggests that approximation can result in practical end-to-end applications.
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Approximate BvND with differentiable cost function
Require: DS matrix M, number & of sub-permutation matrices, learning rate 7 regulariza- lion paramelers μ and w
Ensure: (n', (,',(**']
/ that minimizes Eq.
1: while not converge do
2: for E [k] do
3: Update using Riemannian gradient descent:
xi((+1) t Rx(1)) - X L softmax(1)1)), fx: sim1 :n(0 @ x:
4: end for
5: Update using gradient descent:
((++1) t- 11()) Nenc (1)l {x:(0)) s==1 11;10000,
6: end while
4 APPLICATION: FAIRNESS OF EXPOSURE IN RANKINGS
One recent application of the BvND in machine learning is the reduction of presentation bias in ranking systems Singh & Joachims (2018). The aim is to find a DS matrix representing probabilistic ranking system that satisfies fairness constraint in expectation. Then, sample a ranking from this fair DS matrix for each user. Thus, sampling for each user with ShunbelShhikhorn becomes prohibitive as it solves a Sinkhorn matrix scaling problem for each sample. Therefore, we precompute the BvND and propose rankings at random for each user. Here, . denotes the cardinality of a set.
Learning to rank algorithms tends to display top-ranked results more often given the user feedback (usually clicks), which leads to ignoring other potentially relevant results. In brief, the method finds probabilistic re-ranking system which satisfies specific presentation bias constraints We encode this probabilistic re-ranking in DS matrix. We decompose this DS matrix using the BvN algorithm. Then, one can select sub- mub-permutation matrix at random using a probability proportional to the decomposition coefficient. Thus, this re-ranking approach will satisfy group fairness constraints in expectation.
For simplicity, we assume a single query and consider that we want to present a ranking of set of documents/iten /itemms D = {d, ) We denote by U the set of all users u that lead to identical q. We represent rel(d, q) the mcasure relevances for a given query We assume full information setting. Thus relevances are known. We use the relevances to compute the utility, c.g., discounted cumulative gain (DCG), or the Normalized DCG (NDCG, the DCG normalized by the DCG of the optimal ranking) (Järvelin & Kekäläinen) 2002).
4.1 STATIC CASE
We can write a utility function U in terms of probabilistic ranking M for a query q as
U(M q) ΣΣM, M, u(d v))(),
d=E
where M E DP,, is the probabilistic ranking. Thus M,; represents the probability of replacing document d; (indexed al position i) at rank j. u(d/ = Eneu Pr|u| q) [rrel(d, q)), is the expected utility of document for query q, where f(-) maps the relevance of the document for a user to its utility. v(j) is the examination propensity; it models how much attention an item d position j. We use a logarithmic discount in the position v, = v(j) log2(1+))
Wee can extend this definition include user preferences, rel(d, q, u).
5

---

Under review as a conference paper at ICLR 2021
and frrel(d, q)) 2 T.uus, the utility function Eq. corresponds to the expected DCG.
We include fairness constraint by solving: M arg maXMeDP. U (M q) subject to M fair. Singh & Joachims (2018) define several fairness constraints that are linear in M, and this problem boils down to solving lincar program. However, in prediction time, one needs to sample from M. Thus, we use the BvN algorithm to decompose M into the convex combination of k permutation matrices p One chooses permutation at random with a probability proportional to the coefficient. The resulting model satisfies the fairness constraint in expectation.
To set our fairness constraints, we need first to define the merit, impact, and exposure of an item d. The merit of item its expected average relevance. The exposure of item is the probability P(d) that the user will see d and thus can read that article, buy that product, etc. We note that estimating the position bias not part of our study. We assume full knowledge of these position-based probabilities. We use the feedback C, e.g., clicks, as measure of impact. We extend these definitions to group G C D by aggregating over the group. Then, we have for a protected group G
1 Σ u(d))), Imp(g) 1 Ec(d), and Expo(g) G
1 P(d). (9) [
Merit(g)=
| dEg
dEg
Setting the constraints functions of the probabilistic ranking M. [xpood;/MM] Ej=1 Mij Vj. Assuming the Position-Based Model (PBM) click model, the estimated probability of a click the exposure x conditional relevancy. Thus, the estimated probability of click on a document d, is C(d) = Expo(d) M) u(d]q) Therefore, we can estimate the average impact and exposure on the items in group G for the rankings defined by M
Imp(O) M) =
Σ q) d.EG
Σ M and Expo(g M)
1
M
Vy.
|
|9]
d:EG j=l
(10)
Here, we only disparate exposure and impact constraints fairness constraints. The disparity constraints D(G,,g) is the difference of the fairness metric between protected groups G, and Gj, divided by their respective merit. We denote (G, and D' (9, 9j) to be the Disparity Exposure Constraint and Disparity Impact Constraint, respectively. Let D(G,, 9j) be the difference in cstimations.
4.2 FAIRNESS IN DYNAMIC LEARNING-TO-RANC
Morik al. (2020) present an exlension of the fairness of exposure (see Section 4 to dynamic setting. They propose a fairness coller algorithm that ensures notions group fairness amortized through time. This algorithm dynamically adapts both utility function and fairness more data becomes available.
Here, we assume that both the exposure and the impact vary through time, Imp, and Expo, Then, use the cumulative fairness constraint over time steps, c.g., EE=,Imm (g), We extend it to their estimations too.
The optimization problem is
M aig max U(M q) - -> Si Me:
max
(11)
s.t. Vg. 9y: D. 9,) + D7-1 9,) S Gúg
where À controls the trade-off between ranking score and fairness.

---

Under review as a conference paper at ICLR 2021
5 EXPERIMENTS
We explore our differentiable approximate BvND's behavior synthetic data and validate its usefulness the fairness of exposure in ranking problems. We aim to check its performance compared to the greedy combinatorial construction.
Optimization. We build DS Random matrices naively to initialize each component X'. For I E [k), we sample each element of matrix M v(i.j) E [n]] from a half-normal distribution, Le., the absolute value of an i..d. sample drawn from Gaussian. Then, we project onto DS using the Sinkhorn algorithm. We set the maximum number of iterations to 10 10000, the learming 7 10-3 3, and relative tolerance of 10 After greedy parameter Lunning, use w 1 and 10
Technical aspects. We give Pytorch (Paszke et al. 2019) implementation in Appendix A We use AlMM implemented in the geoopt library (Kochurov et al., 2222 We run all the experiments on single desktop machine with a 4-core Intel Core i7 2.4 GHz.
SYNTHETIC DATA
computation time (min)
Setup. We build set of ten DS Random matrices (DPn)u=) where [4, 6, 10). To add sparsity, we mask each matrix by Uhresholding at 0.5,, 0.9] divided n, respectively. Then, we project the masking result using the Sinkhorn algorithm. We explore the performance of the differentiable BvND as a function of the number of l components. We measure the computation time, the reconstruction crror, and the orthogonalization error.
k
4.43 + 1.28
6 30
8.68 + 2.18
40
15.13 + 5.49
Table 1: Computation time
Matrix size nm6
Matrix size nmb
Matrix size n=10
Results. We observe in Fig. 2 the re- construction error is monotonically de- creasing. However, the approximate orthogonalization constraint becomes more challenging to satisfy when in- creasing the DS input matrix's dimen- sionality. Table shows the the compu- tation time for each parameter.
3.0
3.5
0.5
20
Nambber components
Number of comporent
Number companents
Count
30t-
12
10'
5.2 STATIC FAIRNESS OF EXPOSURE
10
8.5 Orthogonalzzation enter
300
Orthogonalization
Orthogonalization erfor
Setup. We use the toy example pre- sented in Singh & Joachims (2018). These data represent a web-service that connects employers (users) to potential employees (items). The set contains three males and three females. The male applicants have relevance for the employers of 0.80, 0.79, 0.78, respectively, while the female applicants have the relevance of 0.77, 0.76, 0.75, respectively Here we follow the standard probabilistic. definition of relevance, where 0.77 means that 77% of all employers issuing the query find that applicant relevant.. The Probability Ranking Principle suggests ranking these applicants in the decreasing order of relevance, Le., the three males at the top positions, followed by the females. The task is to re-rank them so that the system satisfies equal opportunity of exposure across groups. Thus, solve linear program to maximize Eq such that FG
Figure 2: Performance of the approximate BvND on synthetic data: for different. matrix sizes. (lop) Reconstruction error function of the number of components. (bottom) Histogram of the orthogo- nalization error of each component.
FFemate) < 60
shows toy example of the fairness of exposure. Fig. 3a presents the original biased ranking, whereas Fig. 3b shows a fair probabilistic ranking, which has a negligible loss in performance. Note that solving this problem does not imply that each
Results.
Fig.

---

Under review as a conference paper at ICLR 2021
Position
Document id
8
= =334
+ .32
+ .4
(a) DCG: 2.37
(b) DCG: 2.36
Figure 3: Static fairness exposure on toy data: a) Unfair ranking; b) Ranking satisfies the disparate exposure constraint. We decompose fair probabilistic ranking using the approximate and differentiable BvND using three components.
sub-permutation matrix is unique. In practice, we often find a decomposition with repeated sub-permutations.
5.3 DYNAMIC FAIRNESS OF EXPOSURE
Setup. We rely on Morik et al. 2020) to simulate an enviromment based on articles in the Ad Fontes Media Bias dalaset, which generales a dynamic ranking on a set of news articles belonging two groups left-leaning and right-leaning news articles, Gien and Fright respectively. See Appendix C for a full description of this simulation. We use dynamic learning rank settings minimize amortized fairness disparities. We solve Eq. [T] using linear programming. We evaluate the effectiveness of our differentiable approximate BvND (Diff-ByN) algorithm compared to the standard implementation of the BvND (BvN). We explore the difference between both models over various trade-offs between ranking score and fairness A. Then, we measure their performance for a fixed X.
Baseline. We use as baseline the greedy heuristic of BvN (Dufossé & Uçar 2016 Dufossé
et al. 2018). For the Dift-BvN, we set the number of components to k 10. We refine the matrix using the Hungarian algorithm (Kuhn) 1955) to ensure returning permutation matrix. However, also tried the stabilized Sinkhorn used in Cuturi et al. 2019 with the same performance.
Results. Fig. 4 presents the performance of BvN and Diff-BvN over various values of the fairness regularization parameter X. Fig. 4a shows the NDCG of both methods, whereas Fig. [c] shows their unfairness of impact. Regarding the NDCG, ByN and Biff-BrN display the same performance across different values of X. We observe the same patlern in the unfairness of exposure and impact, Fig and Fig 4c. respectively.
We set the fairness regularization parameter to X 10-2 We see in Fig. 5 that the performance of the re-ranked system is the same for BvN and Diff-BvN. However, the similar performance between these methods implies that only components 10 represent most of the information, which might not hold in other sconarios. Nevertheless, fewer components improve the performance in some applications (Porter et al. 2013 Liu et al. 2015
DISCUSSION AND CONCLUSION
In this paper, we proposed differentiable cost function to approximate the Birkhoff- von- Neumann decomposition (Diff-Bvel BvN). Our algorithm approximates DS matrix by a convex combination of matrices on the Birkhoff polytope, where each matrix in the decomposition is approximately orthogonal. We can minimize the final loss function using Riemannian gradient descent. Our algorithm is easy to implement on standard auto-diff-base based libraries. Experiments the fairness of exposure in ranking problems show that our algorithm yields similar results to the Warkhoff-von-Nemmen
decomposition algorithm with a greedy hcuristic. Our algorithm provides an alternative to existing approaches to sample permutation matrices from DS matrix. In particular, it offers the option to balance the trade-off between memory and time in prediction settings. Fewer assignments lead to improved performance in some
8

---

Under review as a conference paper at ICLR 2021
6405
Unlaimeess of Exposure
BvN Diff-BvN
Unfeimees of immect
BuN
NOCG
BvN DIE--BN
18
020
(a) Averaged cumulative
(b) Group-difference of exposure (c) Group-difference of clicks per per true relevance
NDCG
true relevance
Figure Performance of the fairness controller as a function the parameter A: Both meth- ods, ByN and Diff-BvN display almost the same behavior across values of the regularization parameter. These values correspond to ten trials the simulated news data 3000 users.
Unfaimess Expesure
Unfairmess Impact
BvN
BvN
DifT-vwN
Dift BvN
0.4
NDCG
0.7
0.4
0.2
100
1000
10
100
1000
10
100
1000
Users
Users
Users
(a) Average cumulative NDCG
(b) Group-difference of exposure (c) Group-difference of clicks per per true relevance
true relevance
Figure 5: Performance of the fairness controller (A= 0.01) a function of the number of users: Both methods, BvN and Diff-BvN display the same convergence behavior on various metrics computed on ten trials of the simulated news data (3000 users).
applications (Porter el al. 2013 Liu et al. 2015). Thus, our algorithm can display better performance that greedy approaches as one sets the number of assignments priory.
Potential improvements. In practice, our algorithm is sensitive to the orthogonal con- straints. Therefore, we need to explore setting the parameters of the cost scheduler annnallin for the orthogonal regularization parameter, c.g., how fast do we have to increase the orthog- onal regularization parameter?. Additionally, we note that the current implementation of our algorithm is still limited to small matrices. Thus, we need to explore different possible directions to make scalable, e.g,, randomization or quadrature methods (Altschuler et al. 2019h.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Pierre-Antoine Absil, Robert Mahony, and Rodolphe Sepulchre. Optimizalion algorithmms on matriz manifolds. Princeton University Press, 2009.
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Niles Weed. Massively scalable sinkhorn distances via the nyström method. In NewrIIPS, pp. 4427-4437 2019.
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regularizations in training deep networks? In NewrlPS, pp. 4261-4271, 2018.
Siddharth Barman. Approximating nash equilibria and dense bipartite subgraphs via approximate version of caratheodory's ' theorem. In STOC, pp. 361-369, 2015.
Tolga Birdal and Umut Simsekli. Probabilistic permutation synchronization using the riemannian structure of the birkhoff polytope. CVPR, pp. 11105 11116, 2019.
Garrett Birkhoff. Three observations on linear algebra. Univ. Nac. Tacuman, Rev. Ser. A, 5: 147 151, 1946.
Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions Automatic Control, 58:2217-2222 2013.
Samuel R Bowman, Luke Vilnis, Oriol Vinyals, Andrew M Dai, Rafal Jozefowicz, and Samy Bengio. Generating sentences from contimuuus space. arXiv preprint Xrx::1511..00 2015.
Andrew Brock, Theodore Lim, James Millar Ritchie, and Nicholas J Weston. Neural photo editing with introspective adversarial networks. In ICLR, 2017.
Aleksandr Chuklin, Ilya Markov, and Maarten de Rijke. Click models for web search. Morgan & Claypool, 2015.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurIPS, pp. 2292-2300 2013.
Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranking and sorting using optimal transport. In NewrIPS, pp. 6861-6871, 2019.
Ahmed Douik and Babak Hassibi. Manifold optimization over the set of doubly stochastic matrices: second-order geometry. IEEE Transactions on Signal Processing, 67:5761 5774, 2019.
Fanny Dufossé and Bora Uçar. Notes on birkhoff von neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, 497:108-115, 2016.
Fanny Dufossé, Kamer Kaya, loannis Panagiotas, and Bora Uçar. Further notes on birkhoff von ncumann decomposition of doubly stochastic matrices. Linear Algebra and its Appli- cations, 554:68-78, 2018.
Michel X Goemans. Smallest compact formulation for the permutahcdron. Mathematical Programming, 153:5 11, 2015.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In ICLR, 2018.
Glenn Hurlbert. A short proof of the birkhoff-von neumann theorem. preprint (umpublished), 2008.
Kalervo Järvelin and Jaana Kekäläinen. Cumulated gain- evaluation of ir techniques. ACM TOTS, 00:422-446, 2002.
Anson Kahng, Yasmine Kotturi, Chinmay Kulkarni, David Kurokawa, and Ariel D Procaccia. Ranking wily people who rank each other. AAAT, pp- 1087-1094, 2018.
10

---

Under review as a conference paper at ICLR 2021
Orgad Keller, Avinatan Hassidim, and Noam Hazon. Approximating bribery in scoring rules. In AAAI, pp. 1121-1129, 2018.
Orgad Keller, Avinatan Hassidim, and Noam Hazon. Approximating weighted and priced bribery in scoring rulcs. JAIR, 66:1057-1098, 2019.
Max Kochurov, Rasul Karimov, and Serge Kozlukov. Geoopt Riemannian optimization in pytorch, 2020.
Harold Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2:83 97, 1955.
Janardhan Kulkarni, Euiwoong Lee, and Mohit Singh. Minimum birkhoff-voo neumann decomposition. In IPCO, pp. 343 354, 2017.
Scott Linderman, Gonzalo Mena, Hal Cooper, Liam Paninski, and John Cunningham. Reparameterizing the birkhoff polytope for variational permutation inference. In AISTATS, pp. 1618 1627, 2018.
He Liu, Matthew K Mukerjee, Conglong Li, Nicolas Feltman, George Papen, Stefan Savage, Srinivasan Seshan, Geoffrey M Voelker, David G Andersen, Michael Kaminsky, et al. Scheduling techniques for hybrid circuit/packet networks. In ACM CoNEXT, pp. 1-13, 2015.
Liang Liu, Jun Xu, and Lance Fortnow. Quantized bvnd: A better solution for optical and hybrid switching in data center networks. In JEEE/ACM UCC, pp. 237-246, 2018.
Vince Lyzinski, Donniell Fishkind, Marcelo Fiori, Joshua T Vogelstein, Carey Priebe, and Guillermo Sapiro. Graph matching: Relax at your own risk. IEEE TPAMI, 38:60-73, 2013.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbol-sinkhorn networks. In ICLR, 2018.
Marco Morik, Ashudeep Singh, Jessica Hong, and Thorsten Joachims. Controlling fairness In ACM SIGIR, pp. 429-438, 2020.
to-rank. teannnng-to-rank. and bias in dynamic learning-
Adamn Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, An- dreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NewrIPS, pp. 8024-8035 2019.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundalions and Trends0 in Machine Learning, 11(566):355 607, 2019.
Sergey Plis, Stephen McCracken, Terran Lane, and Vince Calhoun. Directional statistics permutations. In AISTATS, pp. 600-608, 2011.
George Porter, Richard Strong, Nathan Farrington, Alex Forencich, Pang Chen-Sun, Tajana Rosing, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Integrating microsecond circuit switching into the data center. ACM SIGCOMM, 43:447-458, 2013.
Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In ACM SIGKDD, pp. 2219 2228, 2018.
Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematios, 21:343-344 3444--48,11 1967.
Steven T Smith. Optimization techniques on riemannian manifolds. Fields Institute Com- munications, 1994.
Stefan Sommer, Tom Fletcher, and Xavier Pennec. Introduction to differential and riemannian geometry. In Riemannion Geometric Statistics in Medical Image Analysis, pp. 3-37. Elsevier, 2020.
11

---

Under review as a conference paper at ICLR 2021
Junchi Yan, Xu- Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, and Xiaokang Yang. A short survey of recent advances in graph matching. In ACM ICMR, pp. 167-174, 2016.
Andrei Zanfir and Cristian Sminchiscscu. Deep learning of graph matching. In CVPR, pp. 2684-2693, 2018.
Michael Zavlanos and George Pappas. dynamical systems approach to weighted graph matching. Automatica, 44:2817-2824, 2008.
A PYTORCH IMPLEMENIATION
import torch
import geoopt
from torch import nn
from geoopt import ManifoldParameter
from geoopt. manifolds import BirkhoffPolytope
class BirkhoffVon Verrbootoou (un. Module):
.** Approximate differentiable Sorkhoff-von-Neumme decompsition of a doubly-stochastic matrix.
Parameters
int, size of the matrix.
components int (optional), the number of coefficients in the approximation.
Attributes
manifold RirkhoffPolytope
Matrices: Parameter Matrix on the Birkhoff Polytope. Used to compute compute RiemannaaAADAM
weight Parameter, Tensor of coefficients.
def init (self, n, n components=2):
super
self). init ()
self.n
self. tt_n_commn ___componentss
components self. manifold_ Birkhofffolytope ()
self. Matrices mn. P ParameterDict
str (ind): ManifolPParameter
data=self mwnifoldd_dd.....o random ((n, n)),
manifold=self. manifold
for ind in range (u_eomponents)
} self. weight = nn. Parameter (data=torch. (anettrrcc.....II.... (1, 1, n components)) )
def forward input=None):
torch. softmax torch.softmax self. weight, dim=-1)
= torch.
self. Matrices [ [str (choice)) unsqueeze (2) for choice in range (self. components)
1. dim=2)
return (Ms sum
Listing 1: Approximate
docomposition (ApproxBvND)
12

---

Under review as a conference paper at ICLR 2021
import torch
import numpy as up
def ortho error (X):
n_ s_samples len (X)
return (X.T @
torch eee (n_samples) abs () .sum ()
def reconstruction error (A, A approx):
return torch. norm (A A __approx, p= fro pow (2)
def train (model,
A: torch. Tensor,
Ir: float=le-2
max iter: int 5500, reg weights: float=1., reg ortho: float=.01,
stop thr: float=le-4): "*"rranning function.
A Tensor, is the doubly stochasic matrix to approximate.
Ir : float (optional), learning rate of the NiemamianADDM.
iter int (optional), maximum number of iterations.
reg_ weights : float (optional), regularization parameter for the weigths.
reg ortho float (optional), regularization parameter for the orthogonal constraints.
thr float (optional), stopping threshold.
optimizer RiemannianAdam list (model, parameters ()), 1r=lr) vloss = [stop_toe thr]
loop = 1 if max iter > 0 else 0
it
while loop:
+=1
optimizer, zero zero_ grad
with torch enable_ ():
orth loss torch. zeros (1)
for param model. parameters ()
if isinstance eeetanceeparaee (param, geoopt. tensor. tensor ManifoldParameter)
orth loss + ortho_error error (param)
else:
weight_ reg = model. weight. pow pow(p) .2).sum ()
A. recons model()
reconstruction loss reconstruction__orro
A, recons)
loss =
reconstruction _loss reg_ortho orth loss
+ reg weights weight_reg
vloss. append (loss item ())
13

---

Under review as a conference paper at ICLR 2021
relative error
a avsoss [-]] vloss 1-21) / abs(vvos)) (-2))
if vloss -2] != else 0.)
if ((it >= max iter) or (np. isnan (vloss| [1]] (relative_ error < stop stop_thr)) _
loop =
loss backward
optimizer step return model
Listing Training utils
B RIEMANNIAN OPTIMIZATION
A Riemannian manifold is smooth manifold M of dimension d that can be locally approx- imated by an Euclidean space Rd. At each point M one can define a d-dimensional vector space, the tangent space T.M. We characterize the structure of this manifold by a Riemannian metric, which is a collection of scalar products p {p(. +)x]xMM where p(: : T TxM + R on the langent space T varying smoothly with x. The Riemannian manifold is pair (M,p) (Sommer et al. 2020).
The tangent space linearizes the manifold point x M,, making it suitable for practical applications as it leverages the implementation of algorithms in the Euclidean space. We use the Riemannian exponential and logarithmic maps to project samples onto the manifold and back to tangent space, respectively. The Riemannian exponential map, when well-defined, Expx T + .M realizes a local diffeomorphism from a sufficiently small neighborhood in T&M into a neighborhood of the point x E M.
Riemannian gradient descent. The base Riemannian gradient methods (Bonnabel 2013; Smmth 1994) use the following update rule Wr+1 Expw, (-:+HH(w:)), where (ww) Is the Ricmannian gradient of the loss L MM - R at We, and ") is the learning rate. However, the exponential map is not casy compute in many cases, calculus of variations problem or know the Christoffel symbols (Bonnabel] 2013). Thus, it is much easier and faster Lo use a first-order approximation of the exponential map, called relraction. A retraction (v) : Tw.M - M maps the langent space at w to the manifold such that d(Rw(tv) (tv) = Ot?), this imposes a local rigidity condition that preserves gradients. Therefore, one can rely on the retraction to compute the alternative update Wt+1 Rw, (-7; Hw:)) (Absil al. 2009).
needs to solve
Douik & Hassibi (219)) introduced the following computation of the retraction mapping and the projection onto the tangent space of DS matrices. The proofs can be found in (Douik &
Hassibi 2019).
Theorem 2 The projection operator Ix( maps Y E DP, onto the tangent space at DP,,, TxDP, is wrillen as
Tx = - Y + +13 ox.
(12)
where C is the Hadomard product, a = (1- (XxXx] (Y- - 3 - XJa, a, and (.)+ denotes the pseudo-inverse
Theorem 3 (Retraction) For a vector (x E TxDP,, lying on the tangent space at X e DP,, the first order retraction map Rx is given by
Rx(Gx)= = 1I O exp ((x X)),
(13)
where Ø is the Hadamard division, the operator II denotes the projection onto DP,,, efficiently computed using the Sinkhorn algorithm [Sinkhorn & Knopp. 1967).
14

---

Under review as a conference paper at ICLR 2021
C SIMULATIONS
News data. Morik et al. (020) contain the description of this dataset. Nevertheless, we added it for completeness. In each trial, we sample set of 30 news articles D. For each article d, the dataset contains a polarity value pa that we rescale to the interval between -1 and 1. We simulate the user polarities. We draw the polarity for each user from mixture of two nor- mal distributions clipped to [-1,1], pdr ~ clipj-1,1| (P 22 + (1 - Pnog) P. (..,, where Pneg is the probability of the user to be left-learning (mean -0.5). We use Pueg = 0.5. Besides, each user has an openness parameter Ute ~ M((05, .55, indicating the breadth of interest outside their polarity.
We draw the Berrnoulli p exp
relevance from the Bernoulli distribution re(d) (=1"" - ]. We the Position-based click model (PBM (Chuklin
2(00))²
et al. 2015 to model user behavior, where the marginal probability that user u, examines an article depends only on its position. The remainder of the simulation follows the
dynamic ranking setup. At each time step t user u, arrives at the system, the algorithm presents an unpersonalized ranking and the user provides leedback c, according to p. and re- The algorithm only observes O₂ and not rt.
15


Reviews:
[{"review_id": "yZJpW-ET_fV", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors propose an optimization formulation for the decomposition of doubly stochastic matrices in terms of permutation matrices, where the cost function is differentiable. The optimization is carried out in the optimization over manifolds setting, using a recent result that gives a Riemannian structure to the set of doubly stochastic matrices.\n\nThe writing of the paper is correct in general, although there are some points commented below.\n\nThe term \"differentiable\" in this setting is somehow confusing. I would add \"differentiable cost function\" or something that leaves no room for misunderstandings. I was reading the paper thinking that I would find something different regarding the differentiable part.\n\nThe proposed formulation and optimization method seem correct, and to me it is a promising starting point. From here, I would expect to see some theoretical results regarding convergence (at least partially, in the spirit of [Z]), or applications where its full potential can be seen.\n\nSection 4, which is an application of the proposed method, constitutes a great part of the paper (maybe more than half of it). Of course, the application of a given method is extremely important, but in this case it shifts the focus of the paper. Besides that, the writing of this large section seems to be quite different from the previous parts. While the first part was relatively well written and easy to follow, this half is rough. \n\nTo me, the interesting part of the paper is the method, and it falls short, given the comments above.\n\nI would usually write this under \"minor comments\", but in this case it shows a lack of care and attention.\nI appreciate the notation paragraph, but it seems to correspond to another paper. The notation for cardinality is never used as such, but the same notation is used for the absolute value several times. The upper index in $X^i$ is never defined (it could index a set of matrices, or indicate rows/columns). The Hadamard operations and pseudo-inverse are never used. On the other hand, in Algorithm 1 there are undefined operators, such as $\\Pi$ and $R_X$ (which I assume are projection and retraction).\n\nMinor comments:\n - Please add punctuation to the equations, since they are part of the text (in Definition 1 for instance)\n - The last sentence in page 2 is weird. \n - In the last sentence of the first paragraph, Section 3.1, there is an extra \"f\" (of f O(n^4) )\n - typo: geootp -> geoopt\n - The bibliography is not consistent. Some authors with full name, some with initials, some in all caps\n\n\n[Z] Zavlanos, M. M., & Pappas, G. J. (2008). A dynamical systems approach to weighted graph matching. Automatica, 44(11), 2817-2824.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fYueEHP8h2L", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper deals with the problem of finding an (approximate) Birkhoff von Neumann decomposition of a doubly stochastic matrix DS, i.e., given a matrix DS find a convex combination of permutation matrices that sum to the given matrix DS.\n\nThe main innovation of the paper is a novel algorithm, based on Riemannian optimization, to find such a decomposition.\nThis algorithm leads to a set of approximately orthogonal matrices, based on which a set of permutation matrices can be constructed in a second step, e.g., via rounding or using a Sinkhorn algorithm.\n\nWhile the paper contains a few interesting aspects, I think there are a number of problems with it.\n\n## Presentation\nThe structure of the overall presentation is somewhat difficult to follow. \nFor instance, the paper lacks a clear mathematical problem statement that gives a precise definition of what the problem is that is to be solved here; and this only becomes partially clear as the paper unfolds.\n\nA few questions I found myself having when reading the paper initially were:\nDo the authors want to find 1 BvN decomposition? Sample from (create multiple feasible) BvN decompositions for a particular doubly stochastic matrix? \nWhat is the relation to the fairness in ranking problems and how does their algorithm help in this context?\nWhy do other methods \"underperform\" when there is a \"constraint in the prediction\" and their approach does not?\nWhen and why would we not need to \"sample permutations online\" -- which is presumably the scenario when their algorithm is advantageous?\n\nIn addition there are a number of typos and mistakes which impede a smooth reading of the paper. Some examples:\np.2 \"DS matrices is incident\" -> should be \"equivalent\"? if not what does incident mean in this context?\np.2. the last paragraph on the page is somewhat confusing the way it is written (cf. the clarification question by one reviewer). The orthogonal group should presumably have the same symbol twice (\\mathcal{O}_m).\nWhy introduce the Stiefel manifold, if it is never used afterwards? It would be enough to simply introduce the orthogonal group as the set of square matrices with orthonormal columns (X^T X = I_n)??\n\nRe: section 3 and 4. I found these sections difficult to follow. \nFor instance, how is a hypersphere relaxation defined? Why is it relevant here, if it is not used?\nAs another example, it seems the Barman (2018) comes after Kulkarni (2017), so how does the (chronologically) earlier paper improve upon a later paper??\nHow should we set the parameters in the optimization problem? How do we actually construct the permutation matrices from the outputs of the optimization. \nThe authors simply list a few high level alternatives but no precise description is given. \n\nWhere does it save computation/memory as advertised in the introduction? \nPersonally, I think the application is quite interesting, but based on the presentation I simply cannot see the connection based on what the authors wrote.\nI don't think the connection of section 4 to the BvN decomposition problem is understandable from the presentations of the authors. Why is the result the authors present relevant? \n\n## Theoretical contribution\nI think the strongest potential contribution here is theoretical, in that a new algorithm is introduced for a relevant problem.\nHowever, the paper does deliver a more detailed analysis of the algorithm but mainly states an optimization problem.\nFor instance, issues such as time / memory complexity are not discussed in more detail. \nAs mentioned above the procedure to actually construct permutation matrices is not described at all. In particular a rounding procedure would break the differentiability, which presumably is one of the advantages of the new method?\nAs the algorithm is approximate: what about the approximation error?\nWhat is the sensitivity of the algorithm w.r.t. to the hyperparameters and how do we set them? \nHow does it effect the diversity of the permutation matrices one obtains (as the authors hint, there might be an issue here -- at least some more detailed discussion could be given).\n\n## Application\nI found the descriptions of the application to be not detailed enough to understand how the results of the authors come into play here.\nNeglecting this aspect, it also remains unclear to me why the algorithm of the authors provides an advantage here as it does not seem to perform better in the applications shown compared to the baseline?\nI think this would have potentially ok, if the paper would have provided a stronger theoretical analysis. However, as it stands I think both the \"theory\" as well as the \"application\" part of the paper fall below acceptance standards.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NLVsp1M8jgh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary \n**Objective:** decompose doubly stochastic matrix into convex combination of permutation matrices. \n\n**Approach:** recast problem as an optimization problem by using a reconstruction loss and an orthogonality loss. Optimize \"permutation matrices\"-part by using Riemannian gradient descent and optimize coefficients using normal gradient descent. Refine final solution by either deterministic rounding or rounding by stochastic sampling. \n\n### Strengths\n**[+]** Idea is easy to understand, and the explanation is fairly straight-forward to read. \n\n**[+]** The math seems correct. \n\n### Weaknesses\n\n**[-]** While the BvN decomposition might be of interest to the ICLR community, I am concerned the suggested differentiable approach to attaining the BvN decomposition is not. \n\n**[-]** It seems fairly straight-forward to recast the matrix decomposition problem as an optimization problem and use RGD and GD. It is possible I am being to harsh on this account, and I'll be happy to revise my conviction if the other reviewers disagree. \n\n**[-]** There is no time complexity analysis of Algorithm 1. \n\n**[-]** The method is only tested for $n\\le 30$, I am concerned the algorithm would not scale to even $n=100$. It is not clear to me whether this method will have any practical impact for $n=30$, however, it is definitely possible I am wrong on this account. \n\n### Recommendation: Rejection 4, but with low confidence. \n\n**[-]** While the BvN decomposition might be of interest to the ICLR community, I am concerned the suggested differentiable approach to attaining the BvN decomposition is not. \n\n**[-]** It seems fairly straight-forward to recast the matrix decomposition problem as an optimization problem and use RGD and GD. It is possible I am being to harsh on this account, and I'll be happy to revise my conviction if the other reviewers disagree. \n\nI am not very confident in this review and open to changing my recommendation, in particular, I'll re-evaluate my opinion based on the comments from the other reviews.\n\n### Questions and Concerns\nPlease note the questions below were posted before this review and the authors already responded to these questions. \n\n---\n\nThanks for submitting your work to ICLR. I hope you can help me clarify a few potential misunderstandings on my behalf. \n\nQuestion 1. Is it correct that you named the approach 'differentiable' because it approximates the BvND by minimizing a differentiable loss? \nI ask because I thought, after reading the title, that you compute BvND while supporting gradient computations, similar to how PyTorch supports gradient computations through eigendecomposition. \n\nAnswer: Yes. \n\nQuestion 2. On the bottom of page 2 I was confused by  *\"... the discrete set of permutation matrices $P_n$ is the intersection of the convex set of doubly stochastic matrices *and the* $DP_n\\cap O_n$, ... \"*. \nDo you mean that $P_n = DP_n \\cap O_n$? \n\nAnswer: Yes.\n\nQuestion 3. Is it correct that experiment 5.1 and 5.2 use matrices of size at most $10$? You mention that finding the smallest $k$ is NP-Hard. But if $n=10$ I am not sure why it wouldn't just be possible to brute-force the solution. One can usually brute-force 3SAT or TSP problems of size $n=10$. Am I am misunderstanding something? Are the constants too big or something?\n\nAnswer: See the posted answer for details. \n\nQuestion 4. It is not clear how big the matrices are in experiment 5.3. I get that you attempt to compute a decomposition with $k=10$ permutation matrices, but I am not sure how big the matrices are. In the appendix you state that you sample $30$ news articles and the article states there are $3000$ users. How big are the matrices?\n\nAnswer: The largest matrices are of size $(30, 30)$. \n\nI apologize for any misunderstandings and look forward to reading your clarification. \n\n---\n\n### Additional Feedback\n\nComment 1. In the Preliminaries section, you introduce a lot of notation. The ICLR style template attempts to standardize notation, and I believe most of your notation is the same as the ICLR style template. \n\nComment 2. I was confused by the last sentence on page 2, I think you can revise/clarify this sentence. \n\nComment 3. In section 4 you write \".. bias constraints We encode this ...\", you are missing a period before \"We\". \n\n### Ethics Disclaimer\nI have no training in ethics and thus have no basis to review the ethical implications of \"{static, dynamic} fairness of exposure\". I can read and understand the mathematical formulation of the problem, but for all I know, the problem formulation could be non-sensual from an ethical perspective. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper explores the Birkhoff-von-Neumann decomposition in order to propagate gradients through a bi-partite matching. The task is very relevant to the community but the reviewers raised concerns both about the theory and the practice of the work. Unfortunately the work is not ready for publication at ICLR.  
Decision: Reject