Fair Clustering via Alignment

Weaknesses

W1: The FCA algorithm's optimality is not clear. It seems that the algorithm does not find the optimal fair clustering. I suggest including a detailed comparison of the notion of optimality and the commonly used optimal solution.

Answer

As Lloyd's $K$-means algorithm has the descent property (i.e., the cost decreases with each iteration; Lloyd (1982); Selim & Ismail (1984)), FCA inherits this property as well and thus converges to an optimum. The solution would be a local optimum, because FCA depends on the initial cluster centers (as well as Lloyd's algorithm) and involves optimizing the joint distribution.

To clarify this point, we modify the abstract and introduction by adding the term `(local) optimum' where appropriate.

Experimentally, we observe that using Lloyd's algorithm with $K$-means++ initialization in FCA results in more effective performance compared to baseline methods (FCA tends to find a good local optimum). Moreover, in Table 7 in Section C.3.4 of Appendix, we compare three algorithms: $K$-means (Lloyd's) algorithm with $K$-means++ initialization and random initialization (added newly in the revised paper), and a gradient-based optimization. The results show that $K$-means++ initialization provides superior performance.

W2: Sec 3 mainly discusses the case of perfect fair clustering, in which we can construct mappings between different groups. However, it is more common that there is a group-wise lower and upper bound for the ratio of each group in a cluster. How do we handle this case?

Answer

While FCA (in Section 4.1) finds the perfectly fair optimal clustering, FCA-C (in Section 4.2) is specifically designed to handle such non-perfect fairness cases. FCA-C controls (non-perfect) fairness level by applying fairness constraint only to a subset of the aligned space, as formulated in eq. (5) and (6). The fairness level is controlled by controlling the size of this subset.

Moreover, we would like to emphasize that FCA-C can find the optimal clustering that minimizes cost for a given (non-perfect) fairness level, as shown in Theorem 4.1. This optimality is achieved by optimizing the selection of members in the subset.

Questions

Q1: Could you give examples of what settings FCA can actually find an optimal fair clustering and what settings it does not?

Answer

FCA would find a local optimum, since Lloyd's algorithm for $K$-means clustering is used. Even though the solution of FCA would be a local optimum, we experimentally confirm that the solution of FCA is consistently better than that of baseline algorithms, in terms of the trade-off between cost and fairness level. Please also see our response to W1.

Q2: Instead of perfect fair clustering, e.g., we only require the balance to be at least 0.8, is there any theoretical result?

Answer

In fact, Theorem 4.1 is the theoretical result showing that FCA-C can optimally control the trade-off between cost and (non-perfect, Balance $< 1$) fairness level. Please also see our response to W2.

Dear reviewer C9w4:

Once again, thank you very much for your review, which has been greatly helpful for our work. We hope this post doesn't cause any inconvenience, but we have about 5-6 hours left to make revisions to the paper's PDF (although discussions can continue for a few more days).

We would like to ask whether our responses have addressed your concerns or if there are any remaining discussion points that require further revisions to the paper (minor points can still be discussed over the next few days!).

Thank you.

Questions

Q1: Your problem requires the input of a distribution of input. In many other fair clustering papers, the input is simply a point set and the optimization is done only on one input. How are the two settings related? Notice that in your experiments you do a comparison to those algorithms, then how do you set the input accordingly?

• Answer

  We would like to clarify that there is no difference between FCA and existing methods in terms of input: FCA also takes a given dataset as input. The term `distribution' defined in this paper simply refers to the empirical distribution defined over the given dataset.

  The distribution is defined in this paper to discuss (i) probabilistic matching, which is similar to the optimal transport problem (defined over two probability measures), and (ii) subsequent probabilistic assignments for the case of unequal sample sizes.

  To avoid such confusion, we newly add the following statement in Section 2: We specifically define these distributions to discuss the (probabilistic) matching between two protected groups of different sizes, and subsequent probabilistic assignments for fair clustering.

Q2: For your phase 2, you mentioned that one could use k-means++ to update $\mu$. However, is there a formal treatment of this? In particular, does the $O(\log k)$ approximation ratio carries on to your case?

• Answer

  As FCA alternately updates the joint distribution and cluster centers, we would not guarantee the approximation ratio of $K$-means++. However, as Lloyd's $K$-means algorithm has the descent property (i.e., the cost decreases with each iteration; Lloyd (1982); Selim & Ismail (1984)), FCA inherits this property as well and thus converges to an optimum. The solution would be a local optimum, because FCA depends on the initial cluster centers (as well as Lloyd's algorithm) and involves optimizing the joint distribution. To clarify this point, we modify the abstract and introduction by adding the term `(local) optimum' where appropriate.

  Experimentally, we observe that using Lloyd's algorithm with $K$-means++ initialization in FCA results in more effective performance compared to baseline methods (FCA tends to find a good local optimum). Moreover, in Table 7 in Section C.3.4 of Appendix, we compare three algorithms: $K$-means (Lloyd's) algorithm with $K$-means++ initialization and random initialization (added newly in the revised paper), and a gradient-based optimization. The results show that $K$-means++ initialization provides superior performance.

  Developing an algorithm with a low approximation error or the capability to find a global optimum, building upon FCA, would be an interesting topic for future work.

Q3: The FCA-C algorithm seems to use many more steps than FCA. How efficient can we implement this?

• Answer

  Compared to FCA, FCA-C technically performs only one additional step: constructing $\mathcal{W},$ the set of data points to which the non-fair cost (i.e., $K$-means cost) is applied. The construction of $\mathcal{W}$ involves just the calculation of FCA cost (i.e., $\eta$ in line 322) followed by a single sorting operation, which is straightforward.

  We also experimentally confirm that, FCA-C does not require significantly more computational cost compared to FCA: Table 9 in Section C.3.7 of Appendix shows that the computation time of FCA-C is higher than FCA by at most 3.8%.

Q4: How do you measure the balance of the baselines in the experiments? I don’t think they work with a distributional input.

Answer

The calculation of the balance is done once the clusters (i.e., the assignments for each data point) are given, regardless of algorithm used or data distributions. Please also see our response to Q1.

Weaknesses

W1: The relation to the widely considered proportional fairness is not formally addressed.

• Answer

  We acknowledge that there are various fairness notions in clustering, such as group fairness, proportional fairness, and individual fairness. Among these, this paper focuses on the group fairness notion (fairness with respect to the ratio of protected groups within each cluster).

  While our proposed framework would not be directly extended to other notions, our core idea of alignment could potentially be adapted for them. We believe exploring such extensions or relationships would be a very promising topic for future research.

  Instead, in the revised paper, we add a new section (Section A.5 of Appendix) introducing other fairness notions in clustering, including proportional fairness and individual fairness. Due to the page limit, this section is included in Appendix, rather than the main body.

W2: It seems the method can only deal with a binary sensitive attribute, whereas many previous works can systematically solve arbitrary groups and sensitive attributes

• Answer

In fact, we can extend FCA to handle multiple (more than two) protected groups. Note that this paper mainly focuses on the case of two protected groups, for ease of discussion. The main idea is similar: matching multiple individuals from different protected groups.

Let $G$ be the number of protected groups, and denote $s\^{\*} \\in \\{0, \ldots, G-1\\}$ as a fixed (reference) sensitive attribute. For the case of equal sample sizes that $n\_{0} = \ldots = n\_{G-1},$ we can similarly decompose the objective function in terms of matching map as follows, which we prove in Section A.3 of Appendix:

where $\mathbf{T}\_{s’}$ is the one-to-one matching map from $\mathcal{X}\_{s\^{\*}}$ to $\mathcal{X}\_{s’}$ for $s' \\in \\{0, \ldots, G-1\\}.$ Note that this result holds for any $s\^{\*} \\in \\{0, \ldots, G-1 \\}.$

For the case of unequal sample sizes, we expect that a similar decomposition (i.e., eq (A) below) would be valid. We first define the alignment map as: $\mathbf{T}\^{\textup{A}} (\mathbf{x}\_{0}, \ldots, \mathbf{x}\_{G-1}) := \pi\_{0} \mathbf{x}\_{0} + \ldots + \pi\_{G-1} \mathbf{x}\_{G-1}.$ Then, we find the joint distribution and cluster centers by minimizing the following objective (A): $\mathbb{E}\_{ (\mathbf{X}\_{0}, \ldots, \mathbf{X}\_{G-1}) \sim \mathbb{Q}} \left( \sum\_{s = 0}\^{G-1} G \pi\^{G} \bigg\Vert \sum_{s' \neq s} \left( \mathbf{X}\_{s} - \mathbf{X}\_{s’} \right) \bigg\Vert\^{2} + \min\_{k} \Vert \mathbf{T}\^{\textup{A}} ( \mathbf{X}\_{0}, \ldots, \mathbf{X}\_{G-1} ) - \mu\_{k} \Vert^{2} \right),$ where $\pi\^{G} := \prod\_{s=0}\^{G-1} \pi\_{s}.$
Furthermore, since finding the joint distribution for multiple protected groups is technically similar to the case of two protected groups, the optimization of the objective in eq. (A) can be solved using a linear program. Unfortunately, we have not succeeded in proving (A), which we are trying now.

We newly add this feasible extension of FCA, with details in Section A.3 of Appendix.

W3: The case of general “balance” seems to be weak (Corollary 4.2), and no worst-case bound that only depends on the magnitude of input is given.

• Answer

  In fact, the Balance defined in Definition 2.1 explicitly captures the worst-case with respect to clusters $\times$ protected groups. That is, Balance is defined by $\min_{s} \min_{k}$ of (the probability of assigning to the $k$th cluster for group $s$ $\div$ the probability of assigning to the $k$th cluster for the entire dataset).

  Moreover, as we mentioned in Section 2, this definition is widely used in the fair clustering literature for group fairness (Chierichetti et al., 2017; Bera et al., 2019; Backurs et al., 2019; Esmaeili et al., 2021; Ziko et al., 2021; Zeng et al., 2023), so we believe this measure is appropriate for evaluating group fairness.

(Approximation guarantee)

We establish the approximation guarantee of our proposed algorithm: The cost of our fair clustering solution is at most $\tau + 2$ times of the cost of the global optimal fair clustering solution (where $\tau$ is the approximation error of the algorithm used for $K$-means clustering). In other words, FCA-C has an approximation error of $\tau + 2$ for any fairness level.

• Theorem A below shows that finding fair clustering (assignments) using FCA-C with fixed cluster centers (found by an approximation algorithm for $K$-means clustering) has a guaranteed approximation error.

• Proposition B below subsequently presents a straightforward result that updating cluster centers also guarantees at least the same approximation error.

The formal mathematical statements are as follows.

• (Definitions) Recall the $K$-means clustering cost $C(\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1}) := \mathbb{E} \sum\_{k=1}\^{K} \mathcal{A}\_{S}(\mathbf{X})\_{k} \Vert \mathbf{X} - \mu\_{k} \Vert\^{2},$ where $\mu = \\{ \mu\_{k} \\}\_{k=1}\^{K}.$ Note that this is equivalently written as $\sum\_{i=1}\^{n} \sum\_{k=1}\^{K} \mathcal{A}\_{s\_{i}}(\mathbf{x}\_{i})\_{k} \Vert \mathbf{x}\_{i} - \mu\_{k} \Vert\^{2}.$

  For a given $\epsilon,$ let $\tilde{\mu}, \tilde{\mathcal{A}}\_{0}, \tilde{\mathcal{A}}\_{1}$ be the optimal solution of $min\_{\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1}} C(\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1})$ subject to $(\mathcal{A}\_{0}, \mathcal{A}\_{1}) \in \mathbf{A}\_{\epsilon},$ i.e., optimal fair clustering solution for fairness level $\epsilon.$

  Let $C^{*} = min_{\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1}} C(\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1})$ be the global optimal clustering cost without fairness constraint.

• (Theorem A) Given a $\tau$-approximation algorithm for (standard) $K$-means clustering, let $\mu\^{\diamond}, \mathcal{A}\_{0}\^{\diamond}, \mathcal{A}\_{1}\^{\diamond}$ be the (approximated) solution of $min\_{\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1}} C(\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1}),$ found by the $\tau$-approximation algorithm. For fixed $\mu\^{\diamond},$ we have that $C( \mu\^{\diamond}, \mathcal{A}\_{0}', \mathcal{A}\_{1}' ) \le (\tau + 2) C(\tilde{\mu}, \tilde{\mathcal{A}}\_{0}, \tilde{\mathcal{A}}\_{1}),$ where $\mathcal{A}\_{0}', \mathcal{A}\_{1}'$ are the assignment functions corresponding to $\mathbb{Q}', \mathcal{W}' = argmin\_{\mathbb{Q}, \mathcal{W}} \tilde{C}(\mathbb{Q}, \mathcal{W}, \mu\^{\diamond}),$ i.e., the solution of FCA-C under fixed $\mu^{\diamond}.$

  • (Sketch of proof) We show that there exist $\mathcal{A}\_{0}\^{+}$ and $\mathcal{A}\_{1}\^{+}$ such that (i) $(\mathcal{A}\_{0}\^{+}, \mathcal{A}\_{1}\^{+}) \in \mathbf{A}\_{\epsilon}$, (ii) $C( \mu\^{\diamond}, \mathcal{A}\_{0}\^{+}, \mathcal{A}\_{1}\^{+} ) \le (\tau + 2) C(\tilde{\mu}, \tilde{\mathcal{A}}\_{0}, \tilde{\mathcal{A}}\_{1}),$ and (iii) $C( \mu\^{\diamond}, \mathcal{A}\_{0}', \mathcal{A}\_{1}' ) \le C( \mu\^{\diamond}, \mathcal{A}\_{0}\^{+}, \mathcal{A}\_{1}\^{+} ).$ Full proof is provided in the following response (= Proof of Theorem A #1 and #2) as well as Section B.5 of Appendix.

• (Proposition B) For given $\mathcal{A}\_{0}', \mathcal{A}\_{1}',$ there exists $\mu'$ such that $C(\mu', \mathcal{A}\_{0}', \mathcal{A}\_{1}') \le C(\mu^{\diamond}, \mathcal{A}\_{0}', \mathcal{A}\_{1}').$

  • (Sketch of proof) Letting $\mu\_{k}' := \sum\_{i=1}\^{n} \mathcal{A}\_{s}(\mathbf{x}\_{i})\_{k} \mathbf{x}\_{i} / \sum\_{i=1}\^{n} \mathcal{A}\_{s}(\mathbf{x}\_{i})\_{k},$ which solves $min\_{\mu} C(\mu, \mathcal{A}\_{0}', \mathcal{A}\_{1}'),$ concludes the proof.

• (Implication)

  For the fair assignment functions $\mathcal{A}\_{0}'$ and $\mathcal{A}\_{1}'$ obtained by FCA-C, it is guaranteed that cost of fair clustering obtained by FCA-C (for fixed cluster centers) $\le (\tau + 2) \times$ cost of the optimal fair clustering (shown in Theorem A).

  Next, once the cluster centers are updated by minimizing the clustering cost given the assignment functions, it follows that: cost of fair clustering obtained by FCA-C (after one cluster center update) $\le$ cost of fair clustering obtained by FCA-C (for fixed cluster centers) (shown in Proposition B). This implies that the fair clustering obtained by FCA-C with updated cluster centers also has the $(\tau + 2)$-approximation guarantee.

Dear reviewer 7dQE:

We sincerely appreciate your valuable feedback and this important discussion! Thanks to your comment, we were able to derive an approximation guarantee of our proposed algorithm. We believe these results enhance the theoretical validity of FCA, particularly regarding its worst-case guarantee, and we hope this addresses your remaining concern. The following discussion has been also added to Section B.5 of Appendix.

Specifically, while Bera et al., (2019) finds a fair assignment under fixed cluster centers and controls fairness level using $\alpha$ and $\beta,$ we were able to obtain a similar approximation result for FCA-C, which controls fairness level using $\epsilon$ (in 2nd follow-up response #2). After that, we discuss several points comparing between FCA and Bera et al., (2019) (in 2nd follow-up response #3).

Please see our follow-up responses below.

(Comparison between our approach and Bera et al., (2019))

The fair assignment functions in our framework, obtained by the matching (transport) map, can be viewed as an alternative and efficient approach to the fair assignment algorithm of Bera et al., (2019). Specifically, we translate the linear programming (LP) in Bera et al., (2019) for directly finding the fair assignments into finding a matching map between different protected groups.

In our framework, any matching map between different protected groups guarantees fairness of the resulting clustering, as discussed in Theorem 3.1. This is because fairness is implicitly satisfied through the use of matching. FCA focuses on finding the optimal matching (as well as cluster centers) that minimizes the clustering cost while ensuring fairness. On the other hand, Bera et al., (2019) requires solving a constrained LP to directly obtain a fair assignment.

Several advantages of our framework (using the matching map for fair clustering) are as follows.

1. (Descent property of cost) FCA alternately updates cluster centers and fair assignments (via alignment) until convergence. This iterative process enables the final solution to numerically converge to a local optimum, achieving a better trade-off between cost and fairness. In contrast, Bera et al., (2019) finds fair assignments under fixed cluster centers.

2. (Numerical performance) As mentioned in lines 1333-1335 in Section C.2.2 of Appendix and supported by the VFC paper (Ziko et al., 2021), VFC outperforms Bera et al., (2019) in terms of cost-fairness trade-off on the datasets used in our experiments. Consequently, FCA, which shows improved trade-offs compared to VFC, is expected to outperform Bera et al. (2019).

3. (Possible fast computation) By leveraging regularization algorithms such as the Sinkhorn algorithm, we can reduce the computational complexity to $\mathcal{O}(n^{2})$ when finding the matching in FCA. Furthermore, using the partitioning technique introduced in Section 4.3, the complexity can be further reduced to $\mathcal{O}(n m),$ where $m$ is the partition size. Importantly, fairness on the entire dataset is still guaranteed in FCA when using this technique.

   In contrast, the computational complexity of Bera et al., (2019) could be high, since the computational complexity of LP is approximately $\mathcal{O}(n^{3}),$ in general. As noted in their paper, `solver fails to find a solution in under an hour even with 40K points'. Additionally, even with our partitioning technique for the LP in Bera et al. (2019), the computational complexity would be reduced to $\mathcal{O}(n m^{2}),$ but we cannot guarantee fairness for the entire dataset. It is because partition-wise LP may not ensure fairness on the entire dataset.

Dear reviewer 7dQE: Thank you very much for the additional feedback. In this response, we provide a clearer result regarding the approximation error.

1. Does your assignment violate the fairness constraint? And I don’t see where $\epsilon$ appears in your followup discussion and the meaning of the this notation.

• Answer: First, $\epsilon$ represents the fairness level of a given fairness constraint (defined in line 337). The smaller the value of $\epsilon,$ the fairer the clustering. Additionally, our assignment function satisfies the fairness constraint, as its corresponding fairness level is below $\epsilon$, according to the definition in eq. (6).

2. I’m not sure about this claim. This claim seems to assume the cluster centers are fixed/given, and I suppose the said assignment is found for this given center set. Then how can its cost be comparable to he optimal fair clustering? I think it makes more sense to relate to the cost of the given center set. Anyway, it’s more conclusive if you can give a more direct approximation bound, such that there’s no assumption about “fixed center set”.

• Answer:

  In fact, the fixed cluster centers we described in the previous response can be understood as the initial cluster centers, obtained using an approximation algorithm for $K$-means clustering. Please note that in Bera et al., (2019), they also provide an approximation bound result for their fair clustering approach (via assignment) under the fixed cluster centers.

  However, we agree that presenting a result without the term "fixed cluster centers" would be more conclusive. In response, we present the following Theorem A', which guarantees that the cost of fair clustering obtained by FCA-C is at most $(\tau + 2)$ times the cost of the optimal fair clustering. This result is based on the previous results and the mechanism of FCA-C, which iteratively updates fair assignments and cluster centers to minimize the cost.

  • Definitions: For a given fairness level $\epsilon$, let $\tilde{\mu}, \tilde{\mathcal{A}}\_{0}, \tilde{\mathcal{A}}\_{1}$ be the optimal solution of $\min_{\mu, \mathcal{A}\_{0}, \mathcal{A}_{1}} C(\mu, \mathcal{A}\_{0}, \mathcal{A}\_{1})$ subject to $(\mathcal{A}\_{0}, \mathcal{A}\_{1}) \in \mathbf{A}\_{\epsilon},$ i.e., optimal fair clustering solution for fairness level $\epsilon.$

           Let $\mu\^{\triangle}, \mathcal{A}\_{0}\^{\triangle}, \mathcal{A}\_{1}\^{\triangle}$ be the solution of FCA-C given a fairness level $\epsilon,$ given initial cluster centers obtained by a $\tau$-approximation algorithm for $K$-means clustering.
    

  • Theorem A': Given initial cluster centers obtained by a $\tau$-approximation algorithm for $K$-means clustering, FCA-C returns a $(\tau + 2)$-approximate solution for fair clustering, i.e., $C( \mu\^{\triangle}, \mathcal{A}\_{0}\^{\triangle}, \mathcal{A}\_{1}\^{\triangle} ) \le (\tau + 2) C(\tilde{\mu}, \tilde{\mathcal{A}}\_{0}, \tilde{\mathcal{A}}\_{1}).$

  Note that if we use Lloyd's algorithm with the $K$-means++ initialization, we have $\tau = \mathcal{O}(\log K).$

  As a result, we will make slight revisions to Section B.5 of Appendix in the final version, by updating this result and its proof accordingly. The proof is provided in the responses below.

Given a $\tau$-approximation algorithm for (standard) $K$-means clustering, let $\mu\^{\diamond}, \mathcal{A}\_{0}\^{\diamond}, \mathcal{A}\_{1}\^{\diamond}$ be the (approximated) solution. We also recall that $\mathbb{Q}', \mathcal{W}' := argmin_{\mathbb{Q}, \mathcal{W}} \tilde{C}(\mathbb{Q}, \mathcal{W}, \mu\^{\diamond}),$ and $\mathcal{A}\_{0}', \mathcal{A}\_{1}'$ are the assignment functions corresponding to $\mathbb{Q}'$ and $\mathcal{W}'.$

It suffices to show (Claim A): there exist $\mathcal{Q}\^{init}, \mathcal{W}\^{init}$ such that $C(\mu\^{\diamond}, \mathcal{A}\_{0}\^{init}, \mathcal{A}\_{1}\^{init}) \le C(\mu\^{\diamond}, \mathcal{A}\_{0}', \mathcal{A}\_{1}') + 3 R \epsilon,$ where $\mathcal{A}\_{0}\^{init}$ and $\mathcal{A}\_{1}\^{init}$ are the fair assignment functions corresponding to $\mathcal{Q}\^{init}$ and $\mathcal{W}\^{init}.$

Then, by combining with the proof of the theorem in the previous response (approximation error under given cluster centers), we can get the same approximation error for $(\mu^{\triangle}, \mathcal{A}\_{0}\^{\triangle}, \mathcal{A}\_{1}\^{\triangle}),$ which completes the proof.

Proof of Claim A: Note that we can rewrite

$\le \mathbb{E}\_{\mathbf{X}\_{0}, \mathbf{X}\_{1} \sim \mathbb{Q}'} (\textup{FCA-cost}(\mathbf{X}\_{0}, \mathbf{X}\_{1}, \mu\^{\diamond})) - \mathbb{E}\_{\mathbf{X}\_{0}, \mathbf{X}\_{1} \sim \mathbb{Q}'}$ $\big( \textup{FCA cost} (\mathbf{X}\_{0}, \mathbf{X}\_{1}, \mu) - \textup{K-means cost} (\mathbf{X}\_{0}, \mathbf{X}\_{1}, \mu) \big) \mathbb{1} \left((\mathbf{X}\_{0}, \mathbf{X}\_{1}) \in \mathcal{W}' \right)$ $+ sup_{\mathbb{Q}, \mathcal{W} : \mathbb{Q}(\mathcal{W}) \le \epsilon} \mathbb{E}\_{\mathbf{X}\_{0}, \mathbf{X}\_{1} \sim \mathbb{Q}} \big( \textup{FCA cost} (\mathbf{X}\_{0}, \mathbf{X}\_{1}, \mu) - \textup{K-means cost} (\mathbf{X}\_{0}, \mathbf{X}\_{1}, \mu) \big) \mathbb{1}\left((\mathbf{X}\_{0}, \mathbf{X}\_{1}) \in \mathcal{W} \right)$

$= \tilde{C}(\mathbb{Q}', \mathcal{W}', \mu\^{\diamond}) + sup_{\mathbb{Q}, \mathcal{W} : \mathbb{Q}(\mathcal{W}) \le \epsilon} \mathbb{E}\_{\mathbf{X}\_{0}, \mathbf{X}\_{1} \sim \mathbb{Q}}$ $\big( \textup{FCA cost} (\mathbf{X}\_{0}, \mathbf{X}\_{1}, \mu) - \textup{K-means cost} (\mathbf{X}\_{0}, \mathbf{X}\_{1}, \mu) \big) \mathbb{1}\left((\mathbf{X}\_{0}, \mathbf{X}\_{1}) \in \mathcal{W} \right).$

(iii): The last term of the right-hand-side can be bounded as follows: First, let $\mu\^{\diamond}(\mathbf{x}) := argmin_{\mu\^{\diamond}\_{k} \in \mu\^{\diamond}} \Vert \mathbf{x} - \mu\^{\diamond}\_{k} \Vert^{2}$ for $\mathbf{x} \in \mathcal{X}$ and $\mu\^{\diamond}(\mathbf{x}\_{0}, \mathbf{x}\_{1}) := argmin_{\mu\^{\diamond}\_{k} \in \mu\^{\diamond}} \Vert \mathbf{T}\^{\textup{A}}(\mathbf{x}\_{0}, \mathbf{x}\_{1}) - \mu\^{\diamond}\_{k} \Vert^{2}$ for $(\mathbf{x}\_{0}, \mathbf{x}\_{1}) \in \mathcal{X}\_{0} \times \mathcal{X}\_{1}.$ Then, $\forall (\mathbf{x}\_{0}, \mathbf{x}\_{1}) \in \mathcal{X}\_{0} \times \mathcal{X}\_{1},$ it holds that $\textup{FCA cost}(\mathbf{x}\_{0}, \mathbf{x}\_{1}, \mu\^{\diamond}) - \textup{K-means cost}(\mathbf{x}\_{0}, \mathbf{x}\_{1}, \mu\^{\diamond}) = 2 \pi_{0} \pi_{1} \Vert \mathbf{x}\_{0} - \mathbf{x}\_{1} \Vert^{2} + \Vert \mathbf{T}\^{\textup{A}}(\mathbf{x}\_{0}, \mathbf{x}\_{1}) - \mu\^{\diamond}(\mathbf{x}\_{0}, \mathbf{x}\_{1}) \Vert^{2} - \left( \pi_{0} \Vert \mathbf{x}\_{0} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2} \right) - \left( \pi_{1} \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{1}) \Vert^{2} \right)$ $\le 2 \pi_{0} \pi_{1} \Vert \mathbf{x}\_{0} - \mathbf{x}\_{1} \Vert^{2} + \Vert \mathbf{T}\^{\textup{A}}(\mathbf{x}\_{0}, \mathbf{x}\_{1}) - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2}- \left( \pi_{0} \Vert \mathbf{x}\_{0} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2} \right) - \left( \pi_{1} \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{1}) \Vert^{2} \right)$ $\le 2 \pi_{0} \pi_{1} \Vert \mathbf{x}\_{0} - \mathbf{x}\_{1} \Vert^{2} + \pi_{0} \Vert \mathbf{x}\_{0} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2} + \pi_{1} \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2} - \left( \pi_{0} \Vert \mathbf{x}\_{0} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2} \right) - \left( \pi_{1} \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{1}) \Vert^{2} \right)$ $= 2 \pi_{0} \pi_{1} \Vert \mathbf{x}\_{0} - \mathbf{x}\_{1} \Vert^{2} + \pi_{1} ( \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2} - \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{1}) \Vert^{2} ) \le 2 \pi_{0} \pi_{1} \Vert \mathbf{x}\_{0} - \mathbf{x}\_{1} \Vert^{2} + \pi\_{1} \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2}$ $\le \frac{1}{2} \Vert \mathbf{x}\_{0} - \mathbf{x}\_{1} \Vert\^{2} + \Vert \mathbf{x}\_{1} - \mu\^{\diamond}(\mathbf{x}\_{0}) \Vert^{2} \le \frac{1}{2} 2 R + 2R = 3R.$