acceptodds
Withdrawn from ICLR 2027

Coresets for Euclidean Clustering Problems with Concentrated Geo-Privacy

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Coresets are compact summaries of datasets such that models trained on a coreset can (provably) approximate those trained on the entire dataset. As such, they have been widely used to scale up clustering problems to massive data. In many real-world scenarios, clustering involves sensitive data, making the release of coresets subject to privacy concerns. Existing differentially private (DP) methods for coreset construction focus predominantly on the centralized model, while extending them to the local model of DP is still largely unexplored. In this paper, we study how to construct coresets for Euclidean clustering problems with concentrated geo-privacy (CGP), a local DP model that quantifies distinguishability based on the distance between data points as defined by a distance function (i.e., the Euclidean distance in our formulation). We first propose an algorithm to build coresets with CGP for the -center problem (a.k.a. minimum enclosing ball, MEB) with a relative approximation and an additive error. We then extend the scheme to the -center problem with any . Furthermore, we propose constructing approximate coresets with CGP for general -clustering (of which -median and -means are special cases when and , respectively). We implement our algorithms and conduct extensive experiments to demonstrate their effectiveness in practice.

Primary area:
learning theory
Keywords:
clustering, coresets, approximation algorithms, concentrated geo-privacy, metric differential privacy

Reviews

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

This paper studies private coreset construction for Euclidean clustering under concentrated geo-privacy (CGP). It develops algorithms for the minimum enclosing ball, k-center, and general (k,z)-clustering problems by incorporating noisy distance queries and private point releases into existing geometric coreset techniques. The paper provides privacy and approximation guarantees and evaluates the proposed methods on synthetic and real-world datasets.

Critical strengths

+. The paper addresses a meaningful problem. Constructing coresets under local privacy constraints is challenging because perturbations may disrupt the geometric structure required for clustering.

+. The framework covers several important clustering problems, including MEB, k-center, and general (k,z)-clustering. The combination of CGP mechanisms with geometric coreset constructions is reasonable, and the paper provides corresponding theoretical guarantees.

+. The experiments show consistent privacy–utility trends, and the supplementary material includes additional evaluations of coreset size and the number of clusters.

Critical weaknesses

-. In Algorithm 5 of the supplementary material, the correction weight assigned to a reference center is not guaranteed to be nonnegative. In particular, a sampled point with a small sampling probability may receive a sufficiently large importance weight to make the correction weight negative. This appears inconsistent with Definition 2.2, which requires nonnegative coreset weights, and may affect the validity of Theorem 4.3. The authors should clarify how this situation is prevented or handled.

-. The theoretical analysis of the general (k,z)-clustering construction needs further justification. In particular, the proof of Lemma 4.2 does not provide sufficient details on how the private residual estimates and assignments preserve the required sensitivity bound. Moreover, the k-center coreset size is stated as O(k/γ) in the introduction and Appendix B.2, but O(k/γ²) in Theorem 3.9. These issues should be clarified.

-. The practical significance of the theoretical guarantees is not sufficiently demonstrated. The privacy-induced additive errors may be substantial under certain parameter settings, but their impact is not systematically analyzed. The experiments also involve relatively small, low-dimensional datasets and do not directly evaluate the exhaustive k-center refinement or the k-median construction. Further evidence on scalability and computational costs would strengthen the results.

Questions for authors

Q1. How does Algorithm 5 ensure nonnegative coreset weights, and can the authors provide a more detailed justification of Lemma 4.2?

Q2. Which k-center coreset-size bound is intended, and how should the additive-error guarantees be interpreted relative to the standard coreset definitions?

Q3. How do the theoretical error bounds and computational costs behave under larger datasets and higher dimensions?

Reviewer_TbNJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies coreset construction for Euclidean clustering under concentrated geo-privacy (CGP), a local model in which the privacy guarantee between two inputs degrades with their Euclidean distance. The paper designs interactive protocols in which users report noisy distances to points chosen by the curator, and a few selected users release a noisy copy of their own point. Using this approach, they adapt the farthest-point method for MEB, Gonzalez's algorithm for kk-center, and sensitivity sampling for (k,z)(k,z)-clustering. In each case they obtain a multiplicative approximation together with an additive error caused by the privacy noise. Experiments on three small UCI datasets and one synthetic dataset per task show that the approximation improves as ρ\rho increases, and that the kk-means coreset outperforms the only baseline.

Critical strengths
  • The problem is of some theoretical interest, I would like to know these results.
  • The MEB analysis is clean, and as far as I checked it is correct; the privacy accounting is simple and easy to verify.
  • The same interactive framework covers MEB, kk-center, and (k,z)(k,z)-clustering.
  • Empirically, the kk-means coreset outperforms DKdP in cost ratio across all datasets.
Critical weaknesses

Major

  • The techniques are mostly direct adaptations: each algorithm replaces exact distances by Gaussian-noised distance reports and selected points by noisy proxies, and the analysis shows that the corresponding non-private algorithm tolerates the resulting additive error.
  • The (k,z)(k,z) result is not convincing. The additive error in Thm 4.3 is hidden in Nmax⁡N_{\max}, which is never bounded. In fact, for this construction the additive error grows linearly in nn: if all points sit at one location, the coreset weights must sum to about nn and every coreset point is a single user's noisy copy, so for d≳log⁡nd \gtrsim \log n the coreset cost at that location is Ω(n(d/ρ)z/2)\Omega(n (d/\rho)^{z/2}) while the true cost is 00. Moreover, Lemma 4.2 (lines 913–928) and Thm 4.3 (lines 930–939) are each proved in a few sentences, and the analysis treats the noisy DzD^z seeds as a constant-factor bicriteria solution (lines 341, 367), which is neither proved nor cited.
  • No lower bounds are given, so it is hard to judge how far the bounds are from optimal. Note that a local ρ\rho-CGP protocol also satisfies distance-based DP at every radius rr, so the Ω(kr2)\Omega(kr^2) lower bound of Epasto et al. for kk-means translates into Ω(k/ρ)\Omega(k/\rho) here. The paper only mentions Epasto et al. in Appendix A.
  • The experiments are weak. The datasets are small (n≤2000n \le 2000), and the paper does not say whether the features are normalized, so the chosen values of ρ\rho have no clear meaning. DKdP is the only baseline, and it is not explained how its privacy parameter is matched to ρ\rho. The trivial baseline above is missing.

Minor

  • Section 3.2 (lines 318–319) defers the kk-center refinement procedure to Appendix E, but Appendix E only contains Algorithms 3–5.
  • Some notions and notations should be better explained.
    • The proof of Thm 3.9 relies on "bucket updates" (line 898), which appear nowhere else.
    • The "branch-specific violation queries" (lines 313–314) are only described in the proof as distances to "a fixed union of balls" (lines 894–895), which is never specified.
    • αz\alpha_z (line 357) appears only once and is never defined; czc_z (lines 341, 1085) is never specified.
    • The baseline DKdP is never introduced (it first appears in Fig. 3, lines 449–454).
  • Figure 3 is never discussed in the text; I believe "Figure 4" in line 469 should be Figure 3.
Questions for authors

Please see weakness.

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

The paper aims to create private summaries called coresets for clustering when each user holds one point and does not trust the server therefore the privacy have to be achieved locally first.

The fundamentals of their proposed algorithms are the following. The server announces some public points and every user replies with a noisy distance to them. Using these noisy distances, the server picks a user or users sampled at random for the k-median and k-means case. The user sends a noisy copy of their point, the server updates the centers with these noisy points, and the collected noisy points form the summary. The paper also attempts to provide CGP guarantees for these algorithms.

Critical strengths

None

Critical weaknesses
  • [W1] The proofs of Lemma 4.2 and Thm. 4.3 are provided as a few sentences in a different file under supplementary material. As far as I understood the MEB analysis can be extended to k-center. However, (1+\gamma) k-center and other (k, z)-clustering analysis is written as sketches. Explicit derivations needed as a proof.
  • [W2] The motivation behind the algorithms and the necessity of them are not well explained. The privacy is achieved by adding noise at the local level however that release might even achieve privacy by itself and then using noisy points might achieve private mechanisms directly by the post processing guarentees.
  • [W3] The paper is really hard to follow, the connections between Lemmas, the main theorem and the contribution is not really clear.
Questions for authors
  • [Q1] Can you provide explicit proofs for each claim, even for the constants you have set? For example, τref=O~(Qref/ρ)\tau_{\mathrm{ref}} = \tilde{O}(\sqrt{Q_{\mathrm{ref}}/\rho}), the reason behind it and derivations is not existed but instead only calibrating over the complete search tree is mentioned.
  • [Q2] How do your methods compare with the trivial method I mentioned in the W2?
  • [Q3] Can you turn the algorithms to much easily understandable format by moduling some of the repetative behaviours and explain the intuition behind the approaches.

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

Related papers

Discussion (0)

Sign in to comment.