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

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 $\kappa$ gives per-step privacy cost $\max \{\log (1+1/\lambda ),\log (1+1/\kappa )\}$, 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 $\kappa$. On the same family of $1$-median instances, algorithms using only the selected weights incur $\Omega (\Delta M)$ cost on some input, while one sample from the grouped weights has expected cost $o(\Delta M)$ on every input. We apply these results to metric $k$-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.