Finding Wasserstein Ball Center: Efficient Algorithm and The Applications in Fairness

Q1 On the missing part of the vector $\boldsymbol{b}$.

We sincerely appreciate the reviewer’s meticulous reading. Yes, there is a missing $\boldsymbol{0}_N$ as the last $N$ terms of vector $\boldsymbol{b}$. We will correct this typo in the final version. Notebly, since the design of our algorithm focuses on the constraint matrix $A$, this typo does not affect any other part of the paper.

Q2 About the experiments on the running times (experiment 1): How did you form the distributions? What are the dimensions of the distributions? Are they all supported on the same support? How did you choose the support of the WBC?

For the first three question, see Line 403-405 in paper: "we generate random datasets in $\mathbb{R}$, and the weights of $(q_1^{(t)}, ..., q_m^{(t)})$ in each distribution $P^{(t)}$ are generated uniformly at random."

The support points of the WBC is generated in the same way, and we will clarify this in the final draft. Thank you for pointing out this ambiguity.

Q3 About the fairness metric in paper

We sincerely appreciate your valuable suggestion, which highlights the need for a more comprehensive discussion of fairness in the context of WBC.

One of the inspirations of this paper is the social fairness concept as mentioned in the last paragraph of Introduction and Appendix A. Apart from that, Minimax fairness is gaining increasing attention within the machine learning community [1-3], where fairness is achieved by minimizing the maximum error across groups—as opposed to minimizing the average error (i.e., replacing $\min\sum$ with $\min\max$ in the objective). This aligns precisely with our formulation.

We acknowledge that there are other fairness notions—such as demographic parity [4], equalized odds/opportunity [5-6], and individual fairness [7]. Extending these frameworks to probability-measure spaces (e.g., via Wasserstein metrics) presents a compelling direction for future research, and we will include a brief discussion of this in the revised manuscript.

Q4 How can one derive this support set, and it is not the same as the support of the distributions?

Due to space limitations, please refer to our response to Q2 of Reviewer f8bo to view block coordinate descent method. As for our point-cloud experiment (see Appendix I.3), we proceeds as follows:

1. Initialization: Compute the fixed-support WBC using the vertices of a dense grid as the initial support set.
2. Support Update:
   • Augmentation: Sample new points from Gaussian distributions centered at high-weight support points.
   • Pruning: Remove support points with negligible weights (below a threshold).
3. Iteration: Recompute the fixed-support WBC on the updated support and repeat until convergence.

This design is motivated by two key observations:

• The WB admits a sparse support representation, with a theoretical upper bound of $N\max\limits_{i\in [N]}m_i$ [8].
• Adaptive refinement balances computational efficiency with solution accuracy by dynamically focusing on high-density regions, which avoid too many iterations.

From the theoretical perspective, "free-support WBC'' is indeed a much more challenging problem than the fixed-support case, especially when the dimensionality is high. We further note that even the ``fixed-support WB'' problem is also very hard and the polynomial-time algorithm with high precision is only for fixed-dimension [8]. We appreciate the reviewer for raising this question, and will spend more effort to investigate this problem as the future work.

[1] Martinez, Natalia, Martin Bertran, and Guillermo Sapiro. "Minimax pareto fairness: A multi objective perspective." International conference on machine learning. PMLR, 2020.

[2] Abernethy, Jacob D., et al. "Active Sampling for Min-Max Fairness." International Conference on Machine Learning. PMLR, 2022.

[3] Singh, Harvineet, et al. "When do minimax-fair learning and empirical risk minimization coincide?." International Conference on Machine Learning. PMLR, 2023.

[4] Zemel, Rich, et al. "Learning fair representations." International conference on machine learning. PMLR, 2013.

[5] Hardt, Moritz, Eric Price, and Nati Srebro. "Equality of opportunity in supervised learning." Advances in neural information processing systems 29 (2016).

[6] Woodworth, B., Gunasekar, S., Ohannessian, M., and Srebro, N. (2017). Learning non-discriminatory predictors. In Proceedings of the 2017 Conference on Learning Theory, pages 1920–1953.

[7] Dwork, Cynthia, et al. "Fairness through awareness." Proceedings of the 3rd innovations in theoretical computer science conference. 2012.

[8] Altschuler, Jason M., and Enric Boix-Adsera. "Wasserstein barycenters can be computed in polynomial time in fixed dimension." Journal of Machine Learning Research 22.44 (2021): 1-19.

Q1: Missing references

Thank you for your valuable suggestions on the references, and we will add them to the revised version.

Q2: Algorithm for free-support Wasserstein ball center (WBC)

For the free support Wasserstein barycenter, many previous researches [1-3] apply block coordinate descent. For our WBC, we can also utilize this approach, where the objective becomes:
$

\begin{array}{cl} & \min\limits_{\boldsymbol{w}, X, \left\{ \Pi^{(t)} \right\}} \max\limits_{t\in [N]} \left\langle D(X,Q^{(t)}), \Pi^{(t)} \right\rangle \\ \text{s.t.} & \Pi^{(t)} \boldsymbol{1}_{m_t} = \boldsymbol{w}, \left( \Pi^{(t)} \right)^{\top} \boldsymbol{1}_m = \boldsymbol{a}^{(t)}, \Pi^{(t)} \geq 0, \forall t = 1, \cdots, N \\ & \boldsymbol{1}_m^{\top} \boldsymbol{w} = 1, \boldsymbol{w} \geq 0 \end{array}
$

where $\boldsymbol{w} := (w_1, \cdots, w_m)^{\top} \in \mathbb{R}_+^m$, $X:= [\boldsymbol{x}\_1, \cdots, \boldsymbol{x}\_m] \in \mathbb{R}^{d \times m\_t}$, $\Pi^{(t)} \in \mathbb{R}\_+^{m\times m\_t}$ and $D(X, Q^{(t)}):= [ \\| \boldsymbol{x}_i - \boldsymbol{q}^{(t)}_j \\|^p ]\in \mathbb{R}^{m \times m_t}$ for $t=1,\cdots, N$.

Free support WBC is nonconvex. By block coordinate descent, one optimizes the support set $X$, and then the fixed support WBC to obtain the weight $\boldsymbol{w}$ of WBC and coupling matrices $\Pi^{(t)}$ alternately. The algorithm will converge to a local minima. For instance, in $l_2$ space, the minimization of $X$ is $\min\limits\_{X}\max\limits\_{t\in [N]}\sum\_{k=1}^m\sum\_{j=1}^{m\_t}||\boldsymbol{x}\_k-\boldsymbol{q}\_j^{(t)}||^2\pi\_{kj}^{(t)}$. This is a quadratically constrained quadratic program (QCQP) in that it can be reformulated as the following problem:

$

\begin{aligned} &\min\limits_{X,\zeta} \zeta \\ \text{s.t.} \ \ &\sum_{k=1}^m\sum_{j=1}^{m_t}||\boldsymbol{x}_k-\boldsymbol{q}_j^{(t)}||^2\pi_{kj}^{(t)}\leq \zeta \end{aligned}
$

Since the quadratic forms of $X$ in the constraints is positive semidefinite, the problem is convex [4], thus can be efficiently solved with convex programming, such as interior point method. Note that the size of variable $X, \zeta$ is $m+1$, the number of constraints is $N$, the scale of solving $X$ is much smaller than solving the fixed support WBC.

Due to space limitations, please refer to our response to Q4 of Reviewer YCD8 for our approach in the point-cloud experiment (see also Appendix I.3).

From the theoretical perspective, "free-support WBC'' is indeed a much more challenging problem than the fixed-support case, especially when the dimensionality is high. We further note that even the ``fixed-support WB'' problem is also very hard and the polynomial-time algorithm with high precision is only for fixed-dimension [5-6]. We appreciate the reviewer for raising this question, and will spend more effort to investigate this problem as the future work.

Q3: Provide more guidance on choosing between WB and WBC for different applications - when is the fairness benefit of WBC worth potential increases in average Wasserstein distance?

Thanks for this question, and we will include a discussion on it. In general, the trade-off between fairness (WBC) and average performance (WB) depends on the application:

• WBC is preferable when minimizing worst-case deviation is critical (e.g., equitable resource allocation).
• WB is better for applications where average accuracy dominates (e.g., density estimation).

Q4: How does the proposed WBC approach handle noisy distributions or outliers that might not represent meaningful minorities but rather data corruption?

Thank you for raising this interesting question. Please see the answer to Q2 in response to Reviewer Xncv.

[1] Cuturi, Marco, and Arnaud Doucet. "Fast computation of Wasserstein barycenters." International conference on machine learning. PMLR, 2014.

[2] Ge, Dongdong, et al. "Interior-point methods strike back: Solving the wasserstein barycenter problem." Advances in neural information processing systems 32 (2019).

[3] Huang, Minhui, Shiqian Ma, and Lifeng Lai. "Projection robust Wasserstein barycenters." International Conference on Machine Learning. PMLR, 2021.

[4] Floudas, Christodoulos A., and Viswanathan Visweswaran. "Quadratic optimization." Handbook of global optimization (1995): 217-269.

[5] Altschuler, Jason M., and Enric Boix-Adsera. "Wasserstein barycenters can be computed in polynomial time in fixed dimension." Journal of Machine Learning Research 22.44 (2021): 1-19.

[6] Lin, Tianyi, et al. "Fixed-support Wasserstein barycenters: Computational hardness and fast algorithm." Advances in neural information processing systems 33 (2020): 5368-5380.

Q1: Comparison between our work and 1-center problem for arbitrary metric space.

Thanks for the question regarding the connection between our WBC problem and the 1-center problem in arbitrary metric spaces. We will add more references and explanations in our paper. In Euclidean space, 1-center problem is often called “minimum enclosing ball problem'' or ”minmax location problem''. Their numerical or approximate algorithms has been extensively studied, see [1-5]. However, the 1-center problem under Wasserstein metric remains unexplored—precisely the gap our work aims to address. Due to the inherent nature and complexity of Wasserstein metric, those previous 1-center algorithms cannot be directly applied to handle our proposed WBC problem (to our best knowledge).

Q2: How to deal with outlier distributions?

Thank you for raising this interesting question. Actually, we think it is hard to precisely distinguish between "outlier'' and "minority'', if there is no any prior knowledge/assumption. For example, a minority distribution could be far away from other distributions, and thus performs quite similarly as an outlier. So we believe an efficient way should take some prior knowledge on inliers and outliers into account.

When no prior information is available, we can also utilize the following iterative strategy to extract "outlier'' distributions and construct the WBC for the remaining distributions (which is similar with the "trim'' idea in statistics): initially, we compute the WBC of the input distributions; perform the following two steps in each iteration, until stable:

1. Recognize the set of distributions farthest from the current WBC as outliers;
2. Update the WBC as the WBC of the remaining distributions.

Nevertheless, since we do not have any prior knowledge, the above strategy could bring some error (e.g., mistaken a minority distribution as an outlier). So we believe it deserves more further study on how to distinguish between "outlier'' and "minority'', and which kinds of prior knowledge can be utilized.

[1] Bâdoiu, Mihai, and Kenneth L. Clarkson. "Smaller core-sets for balls." Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. 2003.

[2] Tansel, B.Ç. (2011). Discrete Center Problems. In: Eiselt, H., Marianov, V. (eds) Foundations of Location Analysis. International Series in Operations Research & Management Science, vol 155. Springer, New York.

[3] Abboud, Amir, et al. "On Complexity of 1-Center in Various Metrics." Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2023).

[4] Yildirim, E. Alper. "Two algorithms for the minimum enclosing ball problem." SIAM Journal on Optimization 19.3 (2008): 1368-1391.

[5] Kumar, Piyush, Joseph SB Mitchell, and E. Alper Yildirim. "Approximate minimum enclosing balls in high dimensions using core-sets." Journal of Experimental Algorithmics (JEA) 8 (2003): 1-1.