- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper considers the partial p-Wasserstein Barycenter problem for general/Euclidean metrics. Here we are given a given k sets of points in a metric space and a distributions over each. (Informally) The p-Wasserstein barycenter problem asks us to a measure over a set of points as well as mappings from each input point set/distribution pairs to minimizing the cost of the (average) of these maps. The -partial variant of the problem expects the measure to have mass , that is for each map to transport an fraction of the mass of the respective to . The paper considers -approximate algorithms, where stands for multiplicative slack and we expect to have at least mass.
The main contribution of the paper is in presenting a -approximate -partial p-Wasserstein barycenter for a fix support in time (n is the total number of inputs points, k is the number of input sets, m is the size of the fixed support, is the spread of the input points).
The authors also show, assuming the support is not fixed, for d-dimensional Eucledian spaces 1) a -approximation in time, -approximation in time for ; a 2) -approximation in time. They also show that an exact solution can be computed in time.
The first approximate algorithm works through completing a binary search for the cost of the optimal solution. The decision problem in each step of the binary search can be formulated as a linear program, which is then approximately solved using multiplicative weight updates. The approximate results restricted to Euclidean metrics simmiliarly complete a binary search. The algorithm chooses a support of points and represents each input distribution with a single point through clustering, accelerating the LP-solver. The exact algorithm relies on the ellipsoid algorithm. Overall, the algorithms are natural in terms of the overall approach, but the details are technically involved.
Critical strengths
While the Wasserstein barycenter problem has received significant attention and is widely applied in practice, the particular relaxation (-partial) was only known to admit efficient algorithms for additive approximation (multiplicative approximation required time). The -partial notion is introduced to handle outlier solutions. While there are further variations of the problem designed to handle such cases, the authors make a compelling case of the usefullnes of this definition.
Critical weaknesses
Previous results for the -partial setting appear to not rely on the -relaxation. It is unclear if additive slack would not be preferable to relaxation in the objective.
Compared to how standard MWU is for solving LP-s its quite challenging to parse what modification compared to say the well known Arora et al. experts setting are needed to obtain the results. I would advise the authors to aim to make the LP solving part as black-box based on standard approaches as possible, improving readability.
Questions for authors
No questions.
2 comments
I thank the authors for the detailed response. I maintain my review of leaning towards acceptance. I understand that the LP solving part (as its the case in many applications) doesn't follow from the black-box. I suggest to the authors to present that part based on the standard LP formulation and then what modifications are required. This might come down to personal taste, but i think since LP solving via MWU is well known, most readers would likely be convinced by just seeing what needs to be done on top of standard solvers (such as described in the rebuttal response but more in-depth).
Response to Reviewer NvsC
We thank the reviewer for their thoughtful feedback and address their main concerns below.
Accuracy of approximation algorithms: We clarify the definitions of different approximations discussed in the paper.
Relative vs. Relaxed: A (1+ϵ)-relative approximate solution f satisfies wp(f)≤(1+ϵ)wp(f∗). Greedily removing the most expensive ϵ fraction of mass from f yields a δ-relaxed solution (transporting α−δ mass at cost ≤wp(f∗)). Thus, the relative guarantee is stronger than the relaxed guarantee.
Relaxed vs. Additive: A δ-relaxed solution transports α−δ mass at cost ≤wp(f∗). Arbitrarily adding the unrouted mass incurs at most a δ-additive error (assuming p=1 for simplicity), yielding a δ-additive approximation. Thus, the relaxed guarantee is stronger than the ϵ-additive approximation.
While standard ML optimal transport papers (e.g., Sinkhorn-based) typically guarantee additive approximation, we use (1+ϵ)-relative and δ-relaxed solutions because their guarantees are stronger. We agree that mixing approximation types can be confusing, and we will clarify this distinction more explicitly in the revised text (building on lines 108–114).
Comparison with experts MWU algorithm: Our algorithm is similar to the multicommodity flow approach from Section 3.3 of Arora et al. [1], rather than the classical experts MWU. Directly applying the experts MWU algorithm to Wasserstein barycenters causes two issues: (a) updating every weight every iteration is computationally expensive, and (b) overcommitting mass to fixed centroids requires many iterations, constrained by the LP width. Our algorithm circumvents these issues for the partial Wasserstein barycenter problem with three new ideas over the multicommodity flow algorithm, which are some of the main contributions:
Reformulating the problem as binary search over a collection of packing-like LPs, as partial Wasserstein barycenters do not form a standard packing LP. The LP we solve is not a packing LP, but since the equality ("non-packing") constraints are always satisfied by construction of the oracle, we prove that it behaves like one from the perspective of MWU.
Designing an efficient oracle for low weighted-cost k-tuples using lazy weight updates (where weight updates affect the oracle only after accumulating sufficiently).
Developing a two-level MWU structure in Section 3, featuring distinct inner and outer MWU algorithms tailored to solve the oracle efficiently.
This is the reason why we cannot present the MWU algorithm as an LP black box. In view of the reviewer's comments, we will emphasize this point and say why we cannot use the LP algorithm as a black box.
[1] The multiplicative weights update method: a meta-algorithm and applications, Arora, Hazan, Kale