acceptodds
Under review as a conference paper at ICLR 2027

A New Framework for Fair -Median: Static and Dynamic

Abstract

Concerns over bias in AI-driven decision-making have made fairness a prominent issue in machine learning. In this work, we study fair clustering under the -median objective, following a popular notion of fairness suggested by Chierichetti et al., which requires each cluster to maintain a balanced representation of input classes. Building on the reduction of Chierichetti et al., which transforms fair -median into its vanilla counterpart via fairlet decompositions, we give a general framework that converts any polynomial-time fairlet decomposition into almost-linear time algorithm with only a constant-factor loss in approximation. Through the extension of our framework, we obtain the first efficient dynamic algorithm for maintaining a fair decomposition under point insertions and deletions. We validate our algorithms on real-world datasets, demonstrating competitive performance against existing baselines.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
clustering, fair $k$-median, fairlet decomposition

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_S2ugOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies fair clustering under the k-median objective, following the fairness notion suggested in [CKLV17] (balanced representation of classes in the clusters). The authors propose a framework that converts any polynomial-time fairlet decomposition into an almost-linear time algorithm with a constant-factor loss in approximation, for points in low-dimensional Euclidean spaces (Theorem 1.1). This framework uses nested grids, where the points of each cell are represented by the centers of their sub-cells. The fairlets spanning sub-cells are finalized immediately on real points, and the rest are pushed down and handled recursively. Using this with a weighted version of [CKLV17]'s flow-based algorithm gives a constant-factor fair k-median static algorithm in almost-linear time (Corollary 1.3). Then, they extend it to the dynamic setting, and they obtain a fair k-median dynamic algorithm with sublinear update time (Corollary 1.3). Experiments show ~10x speedup over static baselines recomputed after each update, at comparable cost.

Critical strengths
  • The paper's originality lies in being the first attempt to tackle the fair-median problem under the dynamic setting.

  • Some technical contributions of the paper are strong. The central technical idea behind the dynamic result (one-sided monotonicity idea), introducing a small metric perturbation so that a single update deletes only fairlets when propagating downward, is an elegant and non-obvious idea. So is the acceleration framework that proves collapsing points to sub-cell centers incurs only a constant-factor approximation loss per level.

Critical weaknesses
  • The high-dimensional limitation is not properly discussed. Theorems 3.1 and 4.1 state that the running time is O~(n1+dϵ)\tilde O(n^{1+d\epsilon}) and the approximation is (αd(r+b))O(1/ϵ)(\alpha d(r+b))^{O(1/\epsilon)}. However, these two bounds are coupled through ϵ\epsilon. For the running time to be almost-linear, dϵd\epsilon needs to be small, i.e. ϵ∼1/d\epsilon \sim 1/d, which makes the approximation (αd(r+b))O(d)(\alpha d(r+b))^{O(d)}, i.e. exponential in dd. Similar for the dynamic result (Theorem 4.1). This is something that needs to be clearly stated in the paper.
    • Moreover, Theorems 1.1, 1.2 and Corollary 1.3 are stated only for d=2d=2, without a pointer to the general versions.
    • I understand that for the specific application (tabular) and the datasets used, constant dd is a fully justifiable assumption. However, if dd is dependent on nn or just very large (e.g. in graph clustering), then it falls out of paper's reach - something that can be handled by the Backurs et al. baseline.
Questions for authors
  • A proper conclusion section is missing, and there is no place where the limitations of the work are discussed, especially the restriction to constant dd (as discussed in the weaknesses). I suggest adding a short conclusion that also clearly mentiones the limiations of the work. Space could be freed by making Figure 1 more compact.
2 comments
AuthorsOpenReview ↗

Response to Comments

We thank the reviewer for insightful comments.

The high-dimensional limitation is not properly discussed...

I understand that for the specific application (tabular) and the datasets used, constant dd is a fully justifiable assumption. However, if dd is dependent on nn or just very large (e.g. in graph clustering), then it falls out of paper's reach - something that can be handled by the Backurs et al. baseline.

Our main focus is on low (constant) dimensional spaces. Even in this restricted setting, no dynamic algorithm was previously known in the literature. As for the static setting, our aim was designing a fast, almost-linear constant-approximate algorithm. For this reason, we chose to present the main result in two dimensions for clarity, while providing the generalization to arbitrary dimension dd in the technical sections for completeness.

Designing static and dynamic algorithms for high-dimensional spaces was not the goal of this paper, but we believe it is a natural and interesting direction for future research.

Moreover, Theorems 1.1, 1.2 and Corollary 1.3 are stated only for d=2d=2, without a pointer to the general versions.

We will add the corresponding pointers to the general versions of the theorems.

A proper conclusion section is missing, and there is no place where the limitations of the work are discussed, especially the restriction to constant dd (as discussed in the weaknesses). I suggest adding a short conclusion that also clearly mentiones the limiations of the work.

We thank the reviewer for this suggestion. We will add a Conclusion section discussing the limitations of our approach, in particular the algorithms' exponential dependence on dd, and outlining possible directions for future research in this area.

I would like to thank the authors for their response. The restriction to constant dimension is ineed reasonable given that no dynamic algorithm was previously known even in this setting, and I appreciate the planned pointers to the general theorems and the new conclusion discussing limitations. However, I think that the trade-off between ϵ\epsilon and dd should be explicitly stated next to the main theorems or in the introduction - not only in the conclusion. I will keep my positive score.

Reviewer_ALRnOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper examines the fair k-median problem, a variant on the well-studied k-median optimization problem wherein data can be colored one of two colors and clusters must be "balanced" in their representation of each. Specifically, the authors design such algorithms in the dynamic setting where the dataset is subject to controlled changes over time (thus, the data structure must be updated carefully to handle these changes with low cost). The overall result is a dynamic (1,t)-fair decomposition algorithm with O~ndϵtO(1/ϵ\tilde{O}n^{d\epsilon}t^{O(1/\epsilon} amortized update time and (dt)O(1/ϵ)(dt)^{O(1/\epsilon)} expected approximation ratio. Theoretical results are supplemented with experiments on three tabular datasets.

Critical strengths

While dynamic kk-median has been extensively studied in recent years, this is seemingly the first procedure for maintaining fair decompositions dynamically under insertions and deletion. The edge-cost perturbation trick is a nice technical innovation that could have utility for related problems.

Critical weaknesses

The main weaknesses are in the presentation, interpretation of the approximation guarantees, misleading experiments, and restricted fairness setting.

Presentation

  • The introductory sections present the results in the restricted d=2d=2 setting which hides the real exponential dependence on this dimension which, even for small dd can become impractical on real-world datasets (see experiment discussion).
  • Many technical details are insufficiently defined and need to be inferred by reading the proofs. For example, the norm used is assumed to be Euclidean (fine) but this is never stated. Moroever, the problem can take on an entirely different nature if we consider different norms so this needs to be formalized (the proofs rely heavily on ℓ2\ell_2 bounding box diameters of dΔ\sqrt{d} \Delta). Similarly, the dynamic model is not formally defined in the main text and subtle issues like the expected approximation ratio never being defined (especially, over what we are taking expectations) and make the paper not of sufficient quality.
  • The related work section is remarkably sparse and does not well situate this work within the vast literature on fair coresets, streaming/sliding window fair clustering, or dynamic clustering. There is seemingly no discussion of the expanding literature on dynamic k-median algorithms.

Approximation Guarantees

  • As noted above, in RdR^d the approximation ratios (static and dynamic) scale with dd and, most importantly, the update time has an exponential dependence on dd. Even for moderate values, like ϵ=0.1,d=6,t=3\epsilon = 0.1, d=6,t=3 like in the experiments, the theoretical approximation factor is massive. For higher dimensions of real-world data (say d≥20d \ge 20), the quad-tree approach becomes impractical.
  • Theorem 3.1 assumes that WeightedFairlet runs in O~(poly(n)+W)\tilde{O}(poly(n) + W). In each cell, we have ndϵn^{d\epsilon} sub-cells so it would seem that invoking WeightedFairlet on these takes O~(ncdϵ+∣P∩C∣)\tilde{O}(n^{cd\epsilon} + |P \cap C|) for some cc which is not the same as ndϵn^{d\epsilon} claimed. Is this just a typo? If not, line 1 of algorithm 3 with baseline threshold ∣P∣<n2dϵ|P| < n^{2d\epsilon} would take O~((n2dϵ)c)\tilde{O}((n^{2d\epsilon})^c).

Misleading Experiments

  • The paper claims a 10x speedup over baselines but Figure 3 seems to show that the fairlet decomposition time is only 1.25 to 1.8x faster than recomputation from scratch. Seemingly, the speed up comes enitirely from the downstream dynamic kk-median algorithm. Since static tree-fairlet is re-run from scratch each step the downstream subprocess is flooded. What if you instead run a fast static kk-median algorithm on top of tree-fairlet or maintain tree-fairlet in the same quad-tree? The baseline comparisons here seem unfair.
  • The paper cites "fair clustering in the sliding window model" but does not compare against it or any coreset-based dynamic baseline.
  • Only 3-6 features are extracted for the given datasets, which avoids the scaling with dd noted above.

Restricted Fairness Setting

The results are restricted to the two color setting and (1,t)(1,t)-balance, which are largely outdated notions of fairness. The fair clustering literature has largely moved toward multiple protected groups, general fractional balance constraints, etc.

Questions for authors
  • Can you clarify the questions on approximation guarantees and their presentation in the paper?
  • Can you clarify the runtime speedups and why you selected the given baseline over a potentially more natural one?
4 comments
AuthorsOpenReview ↗

Response to Comments (1/3)

We thank the reviewer for insightful comments.

The introductory sections present the results in the restricted d=2d=2 setting which hides the real exponential dependence on this dimension which, even for small dd can become impractical on real-world datasets (see experiment discussion).

As noted above, in Rd\mathbb{R}^d the approximation ratios (static and dynamic) scale with dd and, most importantly, the update time has an exponential dependence on dd...

Our main focus is on low (constant) dimensional spaces. Even in this restricted setting, no dynamic algorithm was previously known in the literature. As for the static setting, our aim was designing a fast, almost-linear algorithm. For this reason, we chose to present the main result in two dimensions for clarity, while providing the generalization to arbitrary dimension dd in the technical sections for completeness.

Hence, designing static and dynamic algorithms for high-dimensional spaces was not the goal of this paper, and the goal is to initiate the study of efficient/dynamic fair clustering, with a starting point in low dimension. We believe it is a natural and interesting direction to resolve the high dimensional case for future research.

Many technical details are insufficiently defined and need to be inferred by reading the proofs...

We will make presentation of the paper more self-contained by adding the description of the metric space, formally defining the expected approximation ratio, and giving a precise description of the dynamic setting.

The related work section is remarkably sparse and does not well situate this work within the vast literature on fair coresets, streaming/sliding window fair clustering, or dynamic clustering...

We will expand the Related Work section to include relevant literature on the kk-median problem in various related settings.

Theorem 3.1 assumes that WeightedFairlet runs in O~(polyn+W)\tilde{O}(poly n + W). In each cell, we have ndϵn^{d\epsilon} sub-cells so it would seem that invoking WeightedFairlet on these takes O~(ncdϵ+∣P∩C∣)\tilde{O}(n^{cd\epsilon} + |P\cap C|) for some cc which is not the same as ndϵn^{d\epsilon} claimed. Is this just a typo? If not, line 1 of algorithm 3 with baseline threshold ∣P∣≤n2dϵ|P|\leq n^{2d\epsilon} would take O~(n2cdϵ)\tilde{O}(n^{2cd\epsilon}).

We thank the reviewer for pointing this out. Invoking WeightedFairlet on all subcells indeed takes O~(ncdϵ+∣P∩C∣)\tilde{O}(n^{cd\epsilon} + |P \cap C|) time. However, this issue can be resolved by simply using a rescaled parameter η=ϵ/(2c)\eta = \epsilon/(2c) instead of ϵ\epsilon, both in this step and in the baseline threshold. We will make this rescaling explicit throughout the algorithm.

AuthorsOpenReview ↗

Response to Comments (2/3)

The paper claims a 10x speedup over baselines but Figure 3 seems to show that the fairlet decomposition time is only 1.25 to 1.8x faster than recomputation from scratch. Seemingly, the speed up comes enitirely from the downstream dynamic kk-median algorithm. Since static tree-fairlet is re-run from scratch each step the downstream subprocess is flooded. What if you instead run a fast static kk-median algorithm on top of tree-fairlet or maintain tree-fairlet in the same quad-tree? The baseline comparisons here seem unfair.

Can you clarify the runtime speedups

The paper cites "fair clustering in the sliding window model" but does not compare against it or any coreset-based dynamic baseline.

Our description is inaccurate, and we clarify that the “10×” claim actually refers to total runtime that includes both the decomposition step and the downstream dynamic k-median step. You are right that the speedup mostly comes from the second k-median step. However, this speedup is due to a better first decomposition step which generates less update to the downstream k-median step, and that is why we attribute the cause of the speedup to the decomposition step. We will clarify how the time/speedup is measured in the next version of the paper.

Following the suggestion, we add a new baseline called Tree-Fairlet + static k-median\text{Tree-Fairlet + static } k\text{-median}, which implements the Tree-Fairlet followed by static FasterPAM [1], provided by the Python kmedoids package (v0.5.5) [2]. We also add the coreset method from Fair Clustering in the Sliding Window Model (ICLR 2025) as a new baseline which we call SW-Coreset\text{SW-Coreset}.

We run the experiments with these new baselines under the same experiment setup as in our paper, and we report the result in Table 1 below. We can conlude that our method still has a clear advantage even considering the new baselines. Specifically, again measured by both the decomposition and k-median step combined, our method achieves a speedup of 1.081.08–4.19×4.19\times over Tree-Fairlet + static k-median\text{Tree-Fairlet + static } k\text{-median}, and 10.3710.37–35.20×35.20\times over SW-Coreset\text{SW-Coreset} across the three datasets, with comparable or lower average cost.

We note that the runtime numbers of our algorithm is different from what we reported in Fig 3 as in our paper. This is because we slightly improved the implementation of the dynamic k-median solver during the rebuttal, and re-run all baselines with respect to this new version (so Table 1 is still a fair comparison).

Table 1. Average cost per window and runtimes over all windows. The runtime includes both the decomposition and downstream k-median step.

\text{Dataset} & \text{Method} & \text{Average cost} & \text{Runtime over all windows (s)} \\\\ \hline \text{Bank} & \begin{array}{l} \text{Ours} \\\\ \text{Tree-Fairlet} \\\\ \text{CKLV-Fairlet} \\\\ \text{Tree-Fairlet + static } k\text{-median} \\\\ \text{SW-Coreset} \end{array} & \begin{array}{r} 1.008\times10^{6} \\\\ 2.124\times10^{6} \\\\ 4.164\times10^{5} \\\\ 2.088\times10^{6} \\\\ 2.547\times10^{6} \end{array} & \begin{array}{c} 19.59 \\\\ 211.97 \\\\ 1{,}261.00 \\\\ 57.43 \\\\ 590.19 \end{array} \\\\ \hline \text{Adult} & \begin{array}{l} \text{Ours} \\\\ \text{Tree-Fairlet} \\\\ \text{CKLV-Fairlet} \\\\ \text{Tree-Fairlet + static } k\text{-median} \\\\ \text{SW-Coreset} \end{array} & \begin{array}{r} 7.319\times10^{7} \\\\ 1.826\times10^{8} \\\\ 2.361\times10^{7} \\\\ 1.821\times10^{8} \\\\ 1.904\times10^{8} \end{array} & \begin{array}{c} 488.17 \\\\ 3{,}702.23 \\\\ 13{,}093.20 \\\\ 525.32 \\\\ 5{,}062.78 \end{array} \\\\ \hline \text{Diabetes} & \begin{array}{l} \text{Ours} \\\\ \text{Tree-Fairlet} \\\\ \text{CKLV-Fairlet} \\\\ \text{Tree-Fairlet + static } k\text{-median} \\\\ \text{SW-Coreset} \end{array} & \begin{array}{r} 6.792\times10^{4} \\\\ 5.726\times10^{4} \\\\ 3.796\times10^{4} \\\\ 5.474\times10^{4} \\\\ 5.828\times10^{4} \end{array} & \begin{array}{c} 319.63 \\\\ 4{,}314.51 \\\\ 30{,}848.32 \\\\ 1{,}338.11 \\\\ 11{,}250.10 \end{array} \end{array}$$ [1] E. Schubert and P. J. Rousseeuw. Fast and Eager k-Medoids Clustering: O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms. Information Systems, 101:101804, 2021. [2] E. Schubert and L. Lenssen. Fast k-Medoids Clustering in Rust and Python. Journal of Open Source Software, 7(75):4183, 2022.
AuthorsOpenReview ↗

Response to Comments (3/3)

why you selected the given baseline over a potentially more natural one?

We selected the original baselines with a purpose to measure the effectiveness of deomposition methods. Hence, this requires to use the same downstream k-median solver, and only the decomposition steps vary. However, what you suggested also makes sense and is complementary, in the sense that those are general algorithms for solving fair k-median in sliding window, not restricted to our framework.

Only 3-6 features are extracted for the given datasets, which avoids the scaling with dd noted above.

Our experiments focus on low-dimensional space, which is also the regime our method is designed for. We will make this explicit in the paper.

The results are restricted to the two color setting and (1,t)(1, t)-balance, which are largely outdated notions of fairness. The fair clustering literature has largely moved toward multiple protected groups, general fractional balance constraints, etc.

We are aware that several definitions and generalizations of fairness have been studied in the literature. However, even in the most restricted setting of two protected groups with a (1/t)(1/t)-balance constraint, no previous dynamic algorithm was known. In the static setting, even for two protected groups with a general fractional (r/b)(r/b)-balance constraint, obtaining a constant-approximation algorithm with subquadratic running time remains an open problem.

Finally, we believe that extending our results to more general fairness constraints and multiple protected groups is a natural and interesting direction for future research.

Dear Reviewer ALRn,

Thank you for your review.

The authors have responded to your concerns and added new baseline comparisons. As the discussion ends, could you please check whether their response addresses your main concerns?

Your feedback would be appreciated.

Regards, AC

Reviewer_txhrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the fair clustering problem under the kk-median objective where no almost-linear time algorithm existed. Each point to be clustered belongs to one of two groups. A clustering is considered fair if, for every cluster, the ratio between the numbers of points from the two groups is at least a predefined ratio. Building on the fairlet decomposition framework of Chierichetti et al. (2017), the authors propose a wrapper algorithm that accelerates any polynomial-time fairlet decomposition into an almost-linear time algorithm "O~(n1+dϵ)\tilde{O}(n^{1+d\epsilon})". Furthermore, the paper introduces the first dynamic algorithm for maintaining a fairlet decomposition under point insertions and deletions. Empirical evaluations show that the dynamic algorithm achieves a speedup compared to recomputing static baselines from scratch, while maintaining competitive clustering cost.

Critical strengths

Extanding fairlet decompositions to the dynamic setting is a very interesting extansion. The analysis is technically novel and, from what I read, seems sound.

Critical weaknesses
  • No AI use statement.
  • The abstract claims an "almost-linear time" algorithm. However, Theorem 3.1 reveals the runtime is O~(n1+dϵ)\tilde{\mathcal{O}}(n^{1+d\epsilon}). Because the dimension dd is in the exponent, the runtime scales with dimensionality, which might be slower than the stated baseline O(n2)\mathcal{O}(n^2). Especially when considering the theoretical approximation ratio is (αd(r+b))O(1/ϵ)(\alpha d(r+b))^{\mathcal{O}(1/\epsilon)}. To achieve nearly-linear O~(n1+dϵ)\tilde{\mathcal{O}}(n^{1+d\epsilon}) runtime, ϵ\epsilon must be chosen to be very small (e.g., ϵ≤1/d\epsilon \leq 1/d), yielding an approximation ratio scaling exponentially with the dimension.
  • The authors claim a speedup over baselines. However, it is unclear when analyzing Figure 3. The proposed "Decomp." step is not that faster than the Tree-Fairlet baseline. The speedup comes almost entirely from the downstream kk-median step. While the proposed dynamic fairlet method provides a more stable input to the kk-median solver, attributing the speedup to the efficiency of the fairlet decomposition algorithm itself does not follow the empirical data.
  • The presentation would gain from a major rewriting.

Overall, I find difficult to follow the authors presentation due to notion not defined when discussed (see below for some example). The manuscript would benefit from defining notion formally instead of in prose, or alternate. Moreover, in Section 3 and 4, the theorems are not analyzed: it would be helpful that the authors explain why and when these bounds improve upon prior work, analyze all the dependencies, specifically discuss the dimension dependence and the constants not shown in the main text.

Below, some intance of where the authors should be clearer.

  • To understand the theorems stated in introduction, it is important to define what is an "α\alpha-approximate (r,b)(r, b)-fairlet decomposition" and a "(r,b)(r, b)-fairlet decomposition with expected approximation ratio". Also, how α\alpha is not present in the running time? Why hiding the dimension dependence from the abstract and introduction?
  • Writing a "Technical Overview" is interesting. Though, at this stage of the paper, I stuggle to understand the section. It would be preferable to keep this smaller, adressing the main novelty / idea keeping the techniqualities for when the theorems are instanciated. Then, when the theorems are stated, provide a more formal proof sketch so that we can follow the technicalities in-depth.
  • In Section 2, the bounding box and aspect ratio assumptions are written as inline prose. Please format these as formal Assumptions, discuss their limitations and add it in theorem assumptions.
  • In Definition 2.3, please formally define the "kk-median cost" for the decomposition in the main text, rather than deferring it to Definition A.5.
  • Please formally define the O~\tilde{\mathcal{O}} notation in the preliminaries.
Questions for authors
  1. In Theorem 3.1, The theoretical approximation ratio is (αd(r+b))O(1/ϵ)(\alpha d (r+b))^{\mathcal{O}(1/\epsilon)} for a time O~(n1+dε)\tilde{\mathcal{O}}(n^{1+d\varepsilon}). Hence, to achieve the claimed runtime speeds, ϵ\epsilon should be smaller than 1/d1/d, rendering the approximation ratio exponential in the dimension. This renders the theoretical upper bound quite high, even for small datasets. Could the authors elaborate on these dependencies (constants, dd, ϵ\epsilon, α\alpha)?
    • How do you justify calling the approximation ratio a "constant-factor loss" when it is (αd(r+b))O(1/ϵ)(\alpha d(r+b))^{\mathcal{O}(1/\epsilon)}?
    • Given that the runtime is O~(n1+dϵ)\tilde{\mathcal{O}}(n^{1+d\epsilon}), how does this framework scale to high-dimensional datasets? At what dimension dd does your accelerated framework become slower than running the O(n2)\mathcal{O}(n^2) Chierichetti baseline? Does the Chierichetti baseline also suffer from the dimension?
  2. In Corollary 1.3, shouldn't it be formally stated that kk is constrained by the maximum possible number of fairlets (e.g., k≤n/(r+b)k \le n / (r+b))? If kk exceeds the number of viable fairlets, the problem is infeasible right?
  3. In the experiments (Figure 3), the runtime for the "Decomp." phase of your algorithm is comparable to the Tree-Fairlet baseline, while the claim of the authors is a speedup of this phase. The majority of the speedup occurs in the subsequent kk-median step. Can you elaborate more on this unexpected result? Could you explicitly quantify the speedup of your fairlet decomposition component compared to the baselines?

If clearly answered, and upon a strong willingness of the authors to significantly improve the clarity of the exposition (see Weaknesses) I would be willing to increase my score; otherwise I would instead be willing to decrease my score.

3 comments
AuthorsOpenReview ↗

Response to Comments (1/2)

We thank the reviewer for insightful comments.

No AI use statement.

We will add an AI use statement at the end of the main body. All main theoretical and experimental results were developed by us (we obtained these results earlier this year). The analysis in the appendix was streamlined with the help of AI. AI was also used to verify and polish the paper.

The abstract claims an "almost-linear time" algorithm. However, Theorem 3.1 reveals the runtime is n1+dϵn^{1+d\epsilon}...

The paper considers the setting where the dimension dd is fixed and constant. Hence, for sufficiently small ϵ\epsilon (i.e. 0<ϵ<1/d0<\epsilon < 1/d), the the static algorithm indeed runs in almost-linear time.

The authors claim a speedup over baselines. However, it is unclear when analyzing Figure 3. The proposed "Decomp." step is not that faster than the Tree-Fairlet baseline. The speedup comes almost entirely from the downstream kk-median step...

In the experiments (Figure 3), the runtime for the "Decomp." phase of your algorithm is comparable to the Tree-Fairlet baseline, while the claim of the authors is a speedup of this phase. The majority of the speedup occurs in the subsequent kk-median step. Can you elaborate more on this unexpected result? Could you explicitly quantify the speedup of your fairlet decomposition component compared to the baselines?

We agree that our description that the speedup comes from the "Decomp." step is not accurate. The accurate statement is that, the improvement is not directly the running time of the "Decomp." step, but due to a better "Decomp." step that generates more stable/low-recourse input to the downstream k-median, the total runtime, especially the k-median step, is improved.

This also explains why we claim the speedup is roughly 10x, since we measure the total runtime which includes both the "Decomp." and the k-median step. In the next version, we will clarify that the claimed speedup is the total speedup and report the decomposition speedup separately.

The presentation would gain from a major rewriting... To understand the theorems stated in introduction, it is important to define what is an "α\alpha-approximate (r,b)(r, b)-fairlet decomposition" and a "(r,b)(r, b)-fairlet decomposition with expected approximation ratio".

We will add the corresponding definitions to the Preliminaries section to make the paper easier to follow.

Moreover, in Section 3 and 4, the theorems are not analyzed...

Given the limited space in the main body, we decided to present the algorithms there and defer the detailed analysis of Theorems 3 and 4 to the Appendix. Additionally, the main ideas behind the proofs are already outlined in the Technical Overview subsection of the Introduction.

How is α\alpha not present in the running time?

Intuitively, since α\alpha denotes the approximation ratio of the oracle, this factor appears in the approximation ratio of the algorithm, and not in its running time. On the other hand, ϵ\epsilon is the parameter that controls the tradeoff between the running time and the approximation ratio of the algorithm.

Why hiding the dimension dependence from the abstract and introduction?

Our main results are for R2\mathbb{R}^2. We also show that our results extend to arbitrary dimension dd, albeit with weaker guarantees. However, the high-dimensional setting is not the main focus of our work. For this reason, we defer this generalization to the technical sections rather than presenting it in the abstract and Introduction. We will clarify this in the Introduction in the next revision of the paper.

Writing a "Technical Overview" is interesting. Though, at this stage of the paper, I stuggle to understand the section...

Our intent in the Technical Overview was to provide a high-level overview of the results and highlight the main technical ideas behind them. In the next revision of the paper, we will make the exposition more self-contained and accessible, so that readers can develop a better intuition for the techniques.

In Section 2, the bounding box and aspect ratio assumptions are written as inline prose. Please format these as formal Assumptions, discuss their limitations and add it in theorem assumptions.

We will state the two assumptions explicitly in the theorem statements.

In Definition 2.3, please formally define the "kk-median cost" for the decomposition in the main text, rather than deferring it to Definition A.5. Please formally define the O~\tilde{O} notation in the preliminaries.

We will move both definitions to the Preliminaries section to make the main body more self-contained and easier to follow.

AuthorsOpenReview ↗

Response to Comments (2/2)

How do you justify calling the approximation ratio a "constant-factor loss" when it is (αd(r+b))1/ϵ(\alpha d (r+b))^{1/\epsilon}?

We work in the setting where dimension dd, as well as parameters r,br, b are constant and fixed. Since α\alpha is also a constant in our applications (Lemma 3.2), we refer to the (αd(r+b))1/ϵ(\alpha d (r+b))^{1/\epsilon} factor as "constant-factor loss". We will clarify this in the abstract by stating that "...we give a general framework that converts any polynomial-time constant-approximate fairlet decomposition into almost-linear time algorithm with only a constant-factor loss in approximation."

Given that the runtime is O~(n1+dϵ)\tilde{O}(n^{1+d\epsilon}), how does this framework scale to high-dimensional datasets? At what dimension dd does your accelerated framework become slower than running the O(n2)O(n^2) Chierichetti baseline? Does the Chierichetti baseline also suffer from the dimension?

Our algorithm also scales to high dimensional spaces and, by choosing ϵ<1/d\epsilon < 1/d, achieves a better running time than the O(n2)O(n^2) Chierichetti baseline, at the cost of a worse approximation ratio. The Chierichetti baseline applies to general metric spaces and is therefore independent of the dimension dd. However, we once again emphasise that our results primarly target low-dimensional spaces, while we also show that our framework extends to general dimension dd, albeit with weaker guarantees.

To answer the question about for what dd ours is slower than Chierichetti baseline, we did a new initial experiment on a small dynamic test on Census II (window 3,000, step 15, k=150k=150), and we found that when d=25d = 25, our runtime (measured by both the decomposition and k-median step) is about 1.68 times that of CKLV-Fairlet, meaning that our method is competitive up to around 25 dimensions in this dataset compared with CKLV.

In Corollary 1.3, shouldn't it be formally stated that kk is constrained by the maximum possible number of fairlets (e.g., k≤n/(r+b)k\leq n/(r+b))? If kk exceeds the number of viable fairlets, the problem is infeasible right?

This is correct and we thank the reviewer for pointing this out. One way to address this is to define kk-clustering as allowing at most kk clusters, which ensures that the problem is always feasible. We will modify the definition of kk-clustering accordingly.

Thank you for your answers. While several clarifications are helpful, three main concerns remain regarding the presentation and framing of the paper:

  • I do not understand why the authors keeps a dense "Technical Overview" in the Introduction rather than properly discussing the main theorems in Sections 3 and 4. As currently written, the Technical Overview is difficult to follow before seeing the formal definitions, while Sections 3 and 4 state the main theorems with almost no accompanying intuition or discussion. Moving the proof intuition and parameter trade-off discussions directly alongside the theorems in Sections 3 and 4 would make the paper far clearer.

  • Although the authors state in the rebuttal that the high-dimensional setting is not their main focus, this does not match the current framing of the paper. The abstract and introduction advertise an "almost-linear time" algorithm with "constant-factor loss" without clearly scoping these claims to constant dimension upfront.

  • In the experimental section, claiming a ~10$\times$ speedup by attributing it to the decomposition phase is not faithful to the numbers in Figure 3, where Decomp. takes roughly the same time as Tree-Fairlet and almost the entire speedup comes from the downstream kk-median step. While the authors rebuttal clarifies that this gain stems from lower recourse rather than faster decomposition runtime, the current text overstates what is actually happening in the plot and weakens the credibility of the experimental claims.

Because resolving these issues requires substantial revisions to the current manuscript, I cannot support accepting the paper in its current form.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to Common Concerns

We noticed that all three reviewers pointed out the exponential dependence on the dimension dd in the running time of our algorithms. We would like to emphasize that our results primarily target low-dimensional spaces (in particular, the two-dimensional setting). Nevertheless, we include an extension of these results to arbitrary dimension dd in the technical sections to demonstrate that our framework also applies in higher dimensions, albeit with weaker guarantees. We will make sure to better highlight our primary contributions in the next revision of the paper, particularly in the Introduction and Abstract.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.