Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Computing the barycenter of a finite set of probability measures is an important task in various statistical and machine learning problems, and is usually done by comparing the measures with a specific divergence. This divergence plays a significant role as it affects the properties and practical performance of the resulting barycenter, and should then be carefully chosen. Motivated by the attractive theoretical properties of the Wasserstein distance, which emerges from optimal transport (OT) theory, the Wasserstein barycenter has been introduced and extensively studied from a theoretical and practical point a view.

This paper introduces a novel barycenter of measures that is closely related to the Wasserstein barycenter, since the comparisons are made by solving OT problems: the authors introduce the "weak barycenter" (Definition 1), which is based on the recently introduced "optimal weak transport" problem, and study its theoretical properties. Specifically, they prove the existence of a solution to the optimization problem that defines the weak barycenter (Proposition 1), and they provide a characterization of the solutions (Lemma 1, Proposition 2). They also bound the deviation between the weak and Wasserstein barycenters (Lemma 2), and show that the weak barycenter is linked to a specific latent variable (Theorem 3). 

Then, the authors introduce the "weak population barycenter" to average an infinite set of probability measures (Definition 2), which can be used for online settings. This barycenter correponds to an optimization problem, which is obtained by extending the definition of the weak barycenter and is well defined (Lemma 3, Proposition 3). 

The authors prove that the weak and weak population barycenters are necessarily fixed points of specific operators (Proposition 4, Lemma 4), and they develop two iterative procedures (Algorithms 1 and 2, supplementary document) that are guaranteed to converge to such fixed points (Proposition 5, Theorem 5). The computational requirements of the two algorithms are investigated in Section 6. Finally, several experiments are conducted to compare the empirical performance of the weak barycenter against the Wasserstein barycenter (Section 7).

main_review: This paper introduces a new methodology to average probability distributions, even if these are provided as a stream. Besides, it is based on optimal transport theory, which has received increased attention in recent years from the statistics, optimization and machine learning community. Therefore, this work is relevant for the NeurIPS community.

The contributions are obtained by adapting existing results from the literature on the Wasserstein barycenter (for example, the two algorithms and their properties are largely inspired by "A fixed-point approach to barycenters in Wasserstein space", Alvarez-Esteban et al.), and in that sense, they are not very original. This does not affect the quality of the work in my opinion: the theoretical findings are technically sound, and I appreciate that the authors provided some explanations on what they imply intuitively (e.g., Lemma 2 and Theorem 3). 

However, my main concern, which prevents me from giving a positive score for now, is that it is not clear enough why weak barycenters should be used in practice. Therefore, I strongly encourage the authors to emphasize more the significance of their contribution. 
One clear advantage is that the weak population barycenter (and Algorithm 2) can process streaming data. However, results in Section 7.1 and 7.2 only illustrate that the weak population barycenter is more concentrated than the "OT barycenter". On the other hand, the experiment on the cytometry dataset (Section E.3) seems more promising in illustrating the benefits of Algorithm 2, thus could be more discussed in the main document. 
Besides, I am not fully convinced by the superior performance of the weak barycenter (and Algorithm 1), since Section 7.3 only shows qualitative results for a single example from the MNIST dataset; the analysis should present more examples supporting this conclusion (e.g., similarly to Section 4 in "Continuous Regularized Wasserstein Barycenters", Li et al.).
 
While experiments in Section 7 also explore interesting properties that this paper do not study theoretically (the robustness to outliers and relation with OT Sinkhorn barycenters), I think it would be more relevant to illustrate more the consequences of the theoretical results established in Sections 3, for example Lemma 2 and Theorem 3 (the link between robustness to outliers and Theorem 3 is not trivial), as well as the computational aspects of the algorithms (as in Section 5 in "A fixed-point approach to barycenters in Wasserstein space", Alvarez-Esteban et al.). 

Regarding clarity, the paper is well written (some minor typos are listed at the end of my review), but quite dense. Besides, I suggest incorporating the following changes in the organization, for better readability:
- A subsection on the Wasserstein barycenter could be added in the background section (Section 2), to recall the definition (l.105-106) and contributions from the literature that are relevant for this work (including Section 6.1).
- Section 3 and 4 could be merged. Same suggestion for Section 5 and 6 (or 6 and 7).
- The explanation on the algorithms for computing the weak barycenters would be much clearer if Algorithms 1 and 2 (or only Algorithm 1) are given in the main document, rather than in the supplementary doc.

Typos:

l.121: missing parentheses for the expectations of $Y_i$

l.230: "an iterative procedure that converge" -> "an iterative procedure that converges"

l.278: "We first focused in Algorithm 2" -> "We first focused on Algorithm 2"

l.303: "$p \in (200, 225)$" -> "$r \in (200, 225)$"

limitations_and_societal_impact: The limitations of this work have been adequately addressed, but not the societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The present manuscript introduces the natural extension of the concept of the Wasserstein Barycenter to the barycenter based on optimal weak mass transport.  Some analytical, statistical and computational properties of this object (the barycenter based on optimal weak mass transport) are discussed and shown. Some numerical experiments are shown too.
main_review: Apart from some minor typos here and there ( e.g., eq. instead of Eq.) , the paper is well written, and I would say it is tailored for a rather advanced audience that is familiar with the problem of OT and its nuances. With that being said, the introduced concept of weak barycenter is a rather natural extension once once has the weak Wasserstein distance. 

I think this paper is very nice as it presents a number of properties for the studied object with some computational an statistical aspects of it. This is the strong part of the paper, and it provides a nice presentation of the problem. However, some of the weaknesses of the present form of  the manuscript need to be improved. Find them below in no particular order.

-  While the weak barycenter is a nice object, I could not find a good or convincing motivation (either computational, statistical, or in applications) for which one would like to compute the weak barycenter. 

- In a couple of instances where claims are made with little or no justification, for example in the experiments it is read " weak barycenter being the most 297 concentrated as expected." I have no reason to expect that the weak barycenter will be more concentrated.

- While the relation to the outliers is nice, this comes out of the blue and with no theoretical justification why. Outlier detection is a rather developed field with its own tools to quantify its properties, and I feel this is not developed in this manuscript and read as some experiment to run, with no justification on why robustness is induced. For example, we know that the median is "more robust" than the mean because we need more than 50% of outliers to drive the mean to an arbitrary position. How can we quantify the robustness of the weak barycenter?

- The numerical section is the reviewers opinion the weakest part of the paper. The plots are very nice and interesting, but little to no discussion is made to connect the numerical results to the theoretical properties of the weak barycenter. For example, what is the conclusion from the 8 plots in figure 4 and 5? It is very hard for me to really obtain any new information from them.  Some numerical experiments are needed that really highlight the statistical, computational, and analytical properties of the weak barycenter. I do no see that in the present numerical results. 

- Some minimal discussion about the computational complexity of the weak barycenter is needed. Traditional Wasserstein barycenter is know to be very computationally intensive to compute. is the weak barycenter easier or harder to compute? 

Minor

-The term "concentrated" is used a couple of times as a property of a probability distribution. Even if this is an intuitive concept, some formal definition would be greatly appreciated.


- 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces and study Fréchet means (aka barycenter) problem for optimal weak transport (OWT), a variant of the standard optimal transport problem which presents in particular the benefits of guaranteeing the existence of optimal transport *map* without needing regularity assumptions on the measures. They prove theoretical properties of these objects (existence, characterization) and, using a fixed-point equation that any (OWT) barycenter must satisfy, they design an interative algorithm that is guaranteed to converge toward such a fixed-point (which, however, may not be a OWT barycenter). 
main_review: Quality:
The paper introduces an interesting optimization problem and studies it properly. The theoretical content is solid, it comes with algorithms + guarantees, and numerical experiments - though not ground-breaking as restricted to dimension 2 - support the approach in an informative way.

Clarity: 
The paper is well-written and pleasant to read. 

Originality / Significance: 
OWT is a fairly new topic in the Optimal Transport field and this paper addresses a natural question when new OT models are proposed. As such, it may open the way for interesting theoretical and applied use of O(W)T in machine learning and other fields. Important questions remain open, in particular the existence (and perhaps the estimation) of a ''maximal'' OWT barycenter when $d \geq 2$. In particular, the discrepancy between the existence of a "trivial" OWT barycenter (Lemma 1) and the (interesting) output of the proposed Algorithms suggest that some gap should be filled in the understanding of fixed-points of the map $\mu \mapsto G(\mu)$. 


Minor comments and suggestions:
- As (for once!) we exactly know the objective value of a (true) OWT barycenter (Eq 7), it may be enlightening to show how does the output of the proposed Algorithms perform empirically in terms of energy. Perhaps does it avoid spurious local minima (if non-adversarialy initialized) and actually converges toward a true OWT barycenter "in practice". 
- Figure 9 (Pair of ellipses) may be worth including in the main paper as it feels quite convincing. 
- It may be nice to present an experiment (perhaps the Pair of ellipses?) in the formalism of Theorem 3, showing that (hopefully) one retrieves (some valid) $X$ given the $Y_i$. 

limitations_and_societal_impact: The paper mentions some of its limitations/questions left. I did not identify negative social impact that may be specific to this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies barycenters of probability distributions using the weak transport distance, and establishes a number of results which mirror the theory of standard optimal transport barycenters that has been established over the past 10 years. In particular, they investigate existence and uniqueness, the first order optimality criterion, as well as iterative methods to compute weak barycenters. They propose a proximal sub-routine for this iterative method, and evaluate the performance of weak barycenters on a number of examples, comparing with standard barycenters and Sinkhorn barycenters.
main_review: The paper is the first to study weak optimal transport barycenters, and establishes a number of desirable results for this new notion. In particular, the authors establish existence (in both finitely supported and non-finitely supported Q cases) and some optimality properties of weak barycenters, such as closure under the convex order. They also give a latent variable characterization of the weak barycenter and study first order methods for computing the weak barycenter. Finally, they provide convincing and clear empirical results that there is significant value in this weak barycenter notion.

Overall, I believe this is a quality, well-written submission. Although the technical results are largely based off porting over proofs from the standard case, I think the convincing empirics demonstrate that this is certainly a valuable notion, and the breadth of technical results is of substantial value for the literature.
limitations_and_societal_impact: The authors adequately discuss limitations (including references for the standard barycenter version of their proofs plus valid directions for extensions) and societal impact.
review_title: null

Meta-review: All the reviewers insisted on the quality of the exposition of the paper, which is able to import advanced notions from OT to the ML community. This being said, the paper only partially motivates (from both a theoretical and numerical perspective) the relevance of weak OT for ML. For this reason, and after discussing with the reviewers, I believe that the paper is borderline for acceptance. I nevertheless proposed acceptance. I strongly urge the authors to take into account some of the suggestions of the comments of the reviewers in the final version. 
Decision: Accept (Poster)