acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Sampling for Weighted k-Median and Row Subset Selection

Abstract

A common approach to differentially private weighted optimization is to add noise to the private weights before running the optimization algorithm. Once the noisy weights are released, every computation based on them is post-processing, but randomized algorithms must then sample using perturbed rather than original weights. We study whether the private weights can remain inside the algorithm and be used directly for sampling. Direct sampling is difficult for zero and small weights because one record can change a sampling probability from zero to positive. The problem becomes more severe when sampling is repeated, since the privacy costs accumulate across steps and a fixed privacy budget requires larger minimum sampling weights. A private threshold provides this minimum weight, but a higher threshold can leave substantial total weight outside the sampling distribution. We address this issue by keeping the selected weights at their original locations and summing the other weights within public groups, so their total weight can still affect sampling through public representatives. Lower-bounding each group sampling weight by gives per-step privacy cost , which composes over adaptive sampling steps and also applies to joint weighted volume sampling. We bound the optimization error from replacing locations by their representatives and from adding weight to groups below . On the same family of -median instances, algorithms using only the selected weights incur cost on some input, while one sample from the grouped weights has expected cost on every input. We apply these results to metric -median and row subset selection. Experiments show that grouping the low-frequency weights improves solution quality over using only the selected weights and reduces running time on the tested instances.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
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_e64XOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the problem of differentially private weighted optimization. It incorporates the idea of differential clustering to handle zero or small weights. The authors present the theoretical privacy bound and the optimization error. They also provide numerical experiments to validate the effectiveness of the proposed methods.

Critical strengths
  1. The author did provide the theoretical guarantee of privacy bound and the optimization error.

  2. The author performed extensive empirical experiments to demonstrate the effectiveness of their methods.

Critical weaknesses
  1. The writing is very confusing and hard to follow:
  • Most notations are used without introduced first; such as λ\lambda in line 24, wxw_x in line 53, ΔM\Delta M in line 27, Ju(⋅)J_u(\cdot) in line 100, to name a few.
  • The whole structure of this paper is messy. For example, the introduction should be structured like: problem formulation (may include some motivating examples)-> current related work weakness -> the main contributions of the work. The current introduction spends most paragraphs introducing abstract failures and potential fixes (lines 53 - 87). It is really hard to follow even though the core idea of using clustering is simple.
  • The main text in section 4 and 5 are overloaded with symbols without proper notation section to summarize them.
  • In line 11 - 15 of the abstract, the discussion of differentially private weight sampling is not the contribution of this paper. But the current framing is like this is from the author's contribution.
  1. The core idea is a straightforward incorporation of differential clustering into the problem of differential weight clustering. It lacks insight of the problem.

  2. In experiments, Table 8 and 12, the proposed method seems to incur a higher cost than baseline methods.

Questions for authors

See the weakness.

2 comments
AuthorsOpenReview ↗

Response to Reviewer e64X

We thank the reviewer for the careful reading and constructive feedback. Below, we address the three concerns.


Weakness 1. The writing is very confusing and hard to follow:

  • Most notations are used without introduced first; such as λ in line 24, wx​ in line 53, ΔM in line 27, Ju​(⋅) in line 100, to name a few.
  • The whole structure of this paper is messy. For example, the introduction should be structured like: problem formulation (may include some motivating examples) -> current related work weakness -> the main contributions of the work. The current introduction spends most paragraphs introducing abstract failures and potential fixes (lines 53 - 87). It is really hard to follow even though the core idea of using clustering is simple.
  • The main text in section 4 and 5 are overloaded with symbols without proper notation section to summarize them.
  • In line 11 - 15 of the abstract, the discussion of differentially private weight sampling is not the contribution of this paper. But the current framing is like this is from the author's contribution.

Response.

Thank you for pointing out these presentation issues. In the revised version, we have clarified our contributions in the Abstract and reorganized the Introduction to better explain the problem setting, motivation, and main contributions. We have also added a notation table in Section 3, a numerical example illustrating group totals in Section 4.1, and explicit definitions of the grouped objective and its optimum in Section 4.3.


Weakness 2. The core idea is a straightforward incorporation of differential clustering into the problem of differential weight clustering. It lacks insight into the problem.

Response.

Thank you for raising this concern. While grouping itself is a familiar technique, our contribution is to preserve small counts in private adaptive sampling. Positive sampling weights and single-coordinate stability provide pure DP guarantees (Theorem 4.3), while Theorem 4.4 bounds the approximation error under the original weights. Theorem 5.3 further provides an example where grouping small counts achieves substantially lower expected cost than using only threshold-selected weights.


Weakness 3. In experiments, Table 8 and 12, the proposed method seems to incur a higher cost than baseline methods.

Response.

Thank you for pointing this out. We acknowledge that GW has higher clustering costs in the cited comparisons. This is partly because GW incurs privacy costs for sampling and private swap decisions, while histogram methods perform optimization as post-processing. However, GW can achieve lower costs when small group weights are important for sampling. In a targeted low-count RSS experiment on USPS, GW achieved 2.99% lower cost than same-HH HIST-GROUP (Appendix D.18.2).

Thanks for your reply! After reading the rebuttal, I still believe this paper cannot be accepted in its current state, so I will maintain my score.

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

The paper studies DP weighted optimization where the weights are private information and the location loss functions are public. Instead of releasing a noisy histogram, the paper keeps the weight inside the algorithm and samples from them directly. On technical side, the proposed method first release a set HH of locations with large weights. The remaining locations are grouped based on a public partition and assigned to public representative. They provide both the per-step privacy cost and the optimization error for their methods. Finally, the demonstrate the effectiveness of their method via extensive experiments with prior works.

Critical strengths
  1. The privacy argument for direct sampling is simple and general. Thus, the derived privacy cost can be applied to any mechanism accepting the sampling protocol, which is widely used.
  2. Grouping the low-count weights into a public representative can effectively reduct the support, which gives a large speedup on the running time.
  3. The experimental study is extensive and comprehensive with clearly statement on the limitation of their methods.
Critical weaknesses
  1. A private histogram is the obvious solution to this weighted DP optimization problem. A histogram is much simpler. It has sensitivity one, so the privacy budget is paid only once, with no composition over sampling rounds and no private swap decisions. Once the noisy histogram is released, everything else is post-processing. The paper's own experiments show that the histogram-based method HIST-GROUP achieves both lower cost and shorter running time than GW in a wide range of settings. The paper needs to argue more convincingly why sampling directly from the unperturbed weights is necessary, and what benefits it brings.

  2. The theoretical results are not compared with prior bounds. Private k-median has been widely studied. The paper compares with prior methods in its experiments, but it does not compare its theoretical results, in particular Theorem 5.2, with prior bounds. I would like the authors to add this comparison and to highlight where their results improve on prior work.

  3. The paper is not well motivated. The introduction motivates the method by the unbounded likelihood ratio when a weight changes from 0 to 1 (l. 53–56). However, the objective Jw(θ)J_w(\theta) (l. 151) has sensitivity at most BlossB_{\mathrm{loss}}, regardless of the weight values. The unbounded ratio is a property of sampling proportionally to the weights, not of the optimization objective itself. Mechanisms that work with JwJ_w directly, such as a noisy histogram or the exponential mechanism (which the paper itself uses for the swap step), do not face this problem.

  4. The experiments mainly demonstrate efficiency, which is not how the paper is motivated. The experiments focus mostly on the efficiency of the proposed method. This is understandable, since grouping the low-weight locations reduces the support. However, efficiency is not part of the paper's motivation: the introduction motivates the method by accuracy, and the abstract mentions running time only in its last sentence. Furthermore, the main text reports the quality comparison only qualitatively and in bar charts of total cost. The numbers are deferred to the appendix, where GW has higher cost than the k-median baselines. ​

Questions for authors
  1. How does the plain floor ux=max⁡(wx,κ)u_x = \max (w_x, \kappa) for all xx, with no threshold or groups, compare with the proposed method, both in theory and in experiments?
  2. Please give the analogue of Theorems 4.4 and 5.2 for HIST-GROUP (same HH, partition and support), and identify a regime where the proposed method is provably or empirically better.
  3. How does Theorem 5.2 compare with the bounds of Gupta et al. (2010) and Fan et al. (2023)?
  4. How should the partition and KK be chosen without seeing the data?
3 comments
AuthorsOpenReview ↗

Response to Reviewer gpez

We thank the reviewer for the thoughtful comments and constructive feedback. We address the four questions below.


Weakness 1. A private histogram is the obvious solution to this weighted DP optimization problem. A histogram is much simpler. It has sensitivity one, so the privacy budget is paid only once, with no composition over sampling rounds and no private swap decisions. Once the noisy histogram is released, everything else is post-processing. The paper's own experiments show that the histogram-based method HIST-GROUP achieves both lower cost and shorter running time than GW in a wide range of settings. The paper needs to argue more convincingly why sampling directly from the unperturbed weights is necessary, and what benefits it brings.

Response.

Thank you for raising this concern. We acknowledge that HIST-GROUP is simpler and achieves lower costs and running times in many settings. However, our method allows locations with small individual counts to influence sampling through their combined group weights, without adding histogram noise. This can be beneficial when low-count groups are important. In a targeted low-count RSS experiment on USPS, GW achieved 2.99% lower original-weight cost than same-HH HIST-GROUP (Appendix D.18.2).


Weakness 2. The theoretical results are not compared with prior bounds. Private k-median has been widely studied. The paper compares with prior methods in its experiments, but it does not compare its theoretical results, in particular Theorem 5.2, with prior bounds. I would like the authors to add this comparison and to highlight where their results improve on prior work.

Response.

Thank you for pointing out this missing comparison. We have added Appendix E to compare Theorem 5.2 with Gupta et al. (2010) and Fan et al. (2023). Although our approximation factor is weaker (16 versus 6), GW evaluates only kk possible swaps per round instead of k(m−k)k(m-k).


Weakness 3. The paper is not well motivated. The introduction motivates the method by the unbounded likelihood ratio when a weight changes from 0 to 1 (l. 53–56). However, the objective Jw​(θ) (l. 151) has sensitivity at most Bloss​, regardless of the weight values. The unbounded ratio is a property of sampling proportionally to the weights, not of the optimization objective itself. Mechanisms that work with Jw​ directly, such as a noisy histogram or the exponential mechanism (which the paper itself uses for the swap step), do not face this problem.

Response.

Thank you for pointing out this distinction. We agree that Jw(θ)J_w(\theta) has sensitivity at most BlossB_{\mathrm{loss}} for fixed θ\theta, while the unbounded likelihood ratio arises from sampling probabilities when a private weight changes from zero to positive. In the revised version, Section 3 explicitly distinguishes objective sensitivity from the privacy requirements of sampling. Our focus is on protecting adaptive sampling decisions made using internal private weights.


Weakness 4. The experiments mainly demonstrate efficiency, which is not how the paper is motivated. The experiments focus mostly on the efficiency of the proposed method. This is understandable, since grouping the low-weight locations reduces the support. However, efficiency is not part of the paper's motivation: the introduction motivates the method by accuracy, and the abstract mentions running time only in its last sentence. Furthermore, the main text reports the quality comparison only qualitatively and in bar charts of total cost. The numbers are deferred to the appendix, where GW has higher cost than the k-median baselines.

Thank you for raising this concern. In the revised Introduction, we clarify that our motivation is to preserve small counts that threshold-only sampling would discard. For example, on Colon with uniform counts, GW reduces RSS cost from 0.755 to 0.397 compared with threshold-only sampling (Appendix D.4).


Question 1. How does the plain floor ux​=max(wx​,κ) for all x, with no threshold or groups, compare with the proposed method, both in theory and in experiments?

Response.

Thank you for suggesting this comparison. In theory, uniform flooring retains all mm locations, whereas GW combines counts outside HH into at most KK public groups. This reduces the sampling support to at most ∣H∣+K|H|+K locations and can reduce the additional weight introduced by flooring.

In experiments, GW is 2.78–23.37 times faster per call. Under Zipf-1 counts, its mean objective costs differ from uniform flooring by −0.29% to +2.54%, while under uniform counts they are 1.27–23.18% higher (Appendix D.16.1).

AuthorsOpenReview ↗

Response to Reviewer gpez

Question 2. Please give the analogue of Theorems 4.4 and 5.2 for HIST-GROUP (same H, partition and support), and identify a regime where the proposed method is provably or empirically better.

Response.

Thank you for this suggestion. Using the same HH, partition, and support before clipping, let NHN_H denote the ℓ1\ell_1 error of HIST-GROUP's clipped noisy weights relative to the exact grouped weights before flooring. For an (α,E)(\alpha,E)-approximate solver, the analogue of Theorem 4.4 is Jw(θ^)≤αOPT(w)+E+(α+1)DH(w)+(α+1)BlossNHJ_w(\hat\theta)\leq\alpha\mathrm{OPT}(w)+E+(\alpha+1)D_H(w)+(\alpha+1)B_{\mathrm{loss}}N_H. With a factor-16 kk-median solver, the analogue of Theorem 5.2 is Φw(CHG)≤16OPTk(w)+17TH(w)+17ΔNH\Phi_w(C^{HG})\leq16\mathrm{OPT}_k(w)+17T_H(w)+17\Delta N_H.

GW can have a tighter bound when group totals exceed the sampling floor and the private-swap error is dominated by the optimal cost. Empirically, in a targeted low-count RSS experiment on USPS (q=1q=1), GW achieved 2.99% lower original-weight cost than same-HH HIST-GROUP (Appendix D.18.2).


Question 3. How does Theorem 5.2 compare with the bounds of Gupta et al. (2010) and Fan et al. (2023)?

Response.

Thank you for this question. Under binary counts on a public universe of size mm, Gupta et al. (2010) achieve 6OPTk+O(Δk2log⁡2m/ϵ)6\mathrm{OPT}_k+O(\Delta k^2\log^2 m/\epsilon), while Fan et al. (2023) improve the additive term to O(Δk2log⁡mlog⁡log⁡m/ϵ)O(\Delta k^2\log m\log\log m/\epsilon). Our Theorem 5.2 gives Φw(CT)≤max⁡{16OPTk(w),16kbsw}+17TH(w)+16ΔPH(w)\Phi_{w}(C_{T}) \leq \max\lbrace 16\mathrm{OPT}_{k}(w), 16kb_{\mathrm{sw}}\rbrace + 17T_{H}(w) + 16\Delta P_{H}(w). Although our approximation factor is weaker (16 versus 6), GW considers only kk possible swaps per round instead of k(m−k)k(m-k) (Appendix E).


Question 4. How should the partition and K be chosen without seeing the data?

Response.

Thank you for raising this practical question. We construct the partition using public geometry, with farthest-point grouping as our default and public kk-means as an alternative. We set K=128K=128 before accessing private counts and evaluate K∈8,32,128,512K\in\\{8,32,128,512\\} in Appendix D.3.

Thank you to the authors for the detailed rebuttal. However, my concerns regarding the motivation and the weaker guarantee remain, and addressing them requires more than a simple revision to meet the acceptance threshold. Accordingly, I maintain my recommendation of weak rejection.

Reviewer_Mk9vOpenReview ↗
Rating
2(−1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper addresses a common problem in DP optimization: they require computing private weights and sampling from them. Typical methods first compute DP estimates of the weights, sample those, and do the optimization as post-processing. This paper instead presents a general method for sampling the weights privately without releasing them, leading to higher end utility. They achieve pure DP rather than approx for their sampling algorithm.

The basic idea is to first identify locations that are "heavy" using the laplace mechanism and thresholding. The exact weights of these locations are preserved (clipped below at a floor). All locations below the threshold are grouped together using a public grid. Their counts are summed and they're assigned a public representative. The exact grouped count is preserved, rounded up to some public value. During private optimization if sampling is required, the sample is drawn from this resulting grouped distribution. They bound the error that's introduced in the final optimization output due to this sampling method.

In section 5 they apply the sampling method to two optimization problems: k-median and row subset selection, and in section 6 they report empirical results showing that their method is superior to existing DP methods in both cost (accuracy) and compute time.

Critical strengths

Thanks for submitting this work, overall I enjoyed learning about your method for privately sampling weights, and this technique seems useful in general for DP optimization problems.

Specific strengths: S1. The idea to do private sampling in this manner seems to be novel and a clever way to reduce error due to sparsity.

S2. The applications to k-median and row selection demonstrate why this technique is useful for a variety of optimization problems.

S3. The experiments section validates the claim that this method reduces error (cost) and compute time.

Critical weaknesses

W1. The exposition in this paper was dense and confusing. It was hard for me to even understand the problem setting and how privately sampling weights relates to clustering and row selection. The paper would benefit substantially from improved exposition and motivation. For example even your first algorithm in section 4.1 was quite hard to parse and understand even though it's not conceptually very complex.

W2. The algorithm assumes a public grid to use for grouping, but if the public grid isn't aligned with where the points actually are, then the error will be quite high. Prior works use adaptive grouping methods to reduce error due to sparsity.

Questions for authors

Q1. For your fixed public grid, have you measured what happens for skewed/misaligned data compared to existing methods, or considered adaptive methods for choosing the grid?

Q2. Have you thought about applying your sampling method to DP clustering methods that use adaptive trees rather than public ones to group points? This would get rid of the potential error blowup if the public grid isn't well aligned with where points are, but I'm not sure if it's possible.

Q3. Are there DP problems besides optimization that this sampling method could be useful for? It seems like a general purpose tool beyond DP optimization specifically

Q4. This work reminds me a lot of "Instance-Optimal Private Density Estimation in the Wasserstein Distance" by Feldman, McMillan, Sivakumar, and Talwar. They use an adaptive hierarchical grid for privately estimating density in sparse spaces, and they achieve an instance optimal algorithm (whereas your error guarantee depends on your public grid). Have you compared your method to running optimization as post-processing on their adaptive density estimate? (you'd get unlimited optimization steps for free after the initial DP density estimate). At some number of steps their method should outperform yours, but the question is when.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Mk9v

We thank the reviewer for the thoughtful comments and constructive feedback. We address the four questions below.


Weakness 1. The exposition in this paper was dense and confusing. It was hard for me to even understand the problem setting and how privately sampling weights relates to clustering and row selection. The paper would benefit substantially from improved exposition and motivation. For example even your first algorithm in section 4.1 was quite hard to parse and understand even though it's not conceptually very complex.

Response.

We thank the reviewer for pointing out these presentation issues. In the revised version, we have reorganized the Introduction to clarify the problem setting and motivation, and explain how weighted sampling is used in kk-median and row subset selection. We have also added a notation table in Section 3 and a numerical example in Section 4.1 showing how 100 locations with count two contribute a group weight of 200. Section 4.3 now explicitly defines the grouped objective and its optimum before analyzing the approximation error introduced by grouping.


Weakness 2. The algorithm assumes a public grid to use for grouping, but if the public grid isn't aligned with where the points actually are, then the error will be quite high. Prior works use adaptive grouping methods to reduce error due to sparsity.

Response.

We appreciate this concern. We construct groups using public geometry to avoid additional privacy costs and limit distances to group representatives. We acknowledge that a fixed partition may be misaligned with private counts, and Theorem 4.4 bounds the resulting approximation error through weighted distances to representatives.


Question 1. For your fixed public grid, have you measured what happens for skewed/misaligned data compared to existing methods, or considered adaptive methods for choosing the grid?

Response.

Thank you for raising this concern. Theorem 4.4 bounds the error caused by partition misalignment using the weighted distances to public group representatives. We tested skewed/misaligned data by moving counts from locations near representatives to more distant ones within fixed public groups. GW's excess mean cost over HIST-CLIP increased from 2.77% to 26.66% on Skin and from 3.62% to 17.45% on Census (Appendix D.16.2).Using adaptive methods to choose the grid based on private data would require an additional DP mechanism and privacy budget. We therefore use a public partition.


Question 2. Have you thought about applying your sampling method to DP clustering methods that use adaptive trees rather than public ones to group points? This would get rid of the potential error blowup if the public grid isn't well aligned with where points are, but I'm not sure if it's possible.

Response.

Thank you for this suggestion. Adaptive trees may reduce partition misalignment, but constructing them from private data requires additional privacy budget. We therefore use public geometry to construct groups without this cost, while Theorem 4.4 explicitly bounds the resulting approximation error.


Question 3. Are there DP problems besides optimization that this sampling method could be useful for? It seems like a general purpose tool beyond DP optimization specifically.

Response.

Thank you for this problem. Beyond optimization, our framework might be applicable for private frequency-weighted sampling in statistical estimation (Cohen et al., 2021), adaptive exploratory data analysis, and sampling-based summaries of categorical or spatial data. Simliar to our problem, these tasks involve sampling from public locations or categories with private counts, such that all these problems have potential to be solved using our methods, which deserves further study.

AuthorsOpenReview ↗

Response to Reviewer Mk9v

Question 4. This work reminds me a lot of "Instance-Optimal Private Density Estimation in the Wasserstein Distance" by Feldman, McMillan, Sivakumar, and Talwar. They use an adaptive hierarchical grid for privately estimating density in sparse spaces, and they achieve an instance optimal algorithm (whereas your error guarantee depends on your public grid). Have you compared your method to running optimization as post-processing on their adaptive density estimate? (you'd get unlimited optimization steps for free after the initial DP density estimate). At some number of steps their method should outperform yours, but the question is when.

Response.

Thank you for highlighting this connection. We evaluated an adaptive density-estimation method based on Instance-Optimal Private Density Estimation in the Wasserstein Distance (Feldman et al., 2024), adapting its tree construction and density reconstruction to our setting. The method releases a private distribution once, after which optimization is post-processing.

Under fixed-size replacement adjacency with ϵ=1\epsilon=1 and k=8k=8, we compared mean original-weight costs over 30 runs per setting. On Census, GW has lower costs at T∈T\in{8,16,32,64,1288,16,32,64,128}, while the density-estimation method has lower costs at T=256,512T=256,512. One reason for this pattern is that GW incurs privacy costs for sampling and swap decisions in each round, whereas the density-estimation method requires only a one-time private release.

Thank you for your responses, but they didn't address my concerns. For example, the response that using an adaptive grid would require additional privacy budget is true but doesn't address my question in any meaningful way.

I read the revisions, and I don't feel the paper can be accepted in its current state. I will be lowering my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.