Locally Private k-Means in One Round
- URL: http://arxiv.org/abs/2104.09734v1
- Date: Tue, 20 Apr 2021 03:07:31 GMT
- Title: Locally Private k-Means in One Round
- Authors: Alisa Chang, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
- Abstract summary: We provide an approximation algorithm for k-means clustering in the one-round (aka non-interactive) local model of differential privacy (DP)
This algorithm achieves an approximation ratio arbitrarily close to the best non private approximation algorithm.
- Score: 44.00192304748844
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide an approximation algorithm for k-means clustering in the one-round
(aka non-interactive) local model of differential privacy (DP). This algorithm
achieves an approximation ratio arbitrarily close to the best non private
approximation algorithm, improving upon previously known algorithms that only
guarantee large (constant) approximation ratios. Furthermore, this is the first
constant-factor approximation algorithm for k-means that requires only one
round of communication in the local DP model, positively resolving an open
question of Stemmer (SODA 2020). Our algorithmic framework is quite flexible;
we demonstrate this by showing that it also yields a similar near-optimal
approximation algorithm in the (one-round) shuffle DP model.
Related papers
- Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation.
We obtain several improved algorithms for private optimization problems, including decomposable submodular and set algorithm cover.
arXiv Detail & Related papers (2024-05-28T19:02:30Z) - Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
This paper studies the design and analysis of approximation algorithms for aggregating preferences over Conditional Preference Networks (CP-nets)
Its focus is on aggregating preferences over so-called emphswaps, for which optimal solutions in general are already known to be of exponential size.
arXiv Detail & Related papers (2023-12-14T17:31:38Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
We study differentially private approximation algorithms for hierarchical clustering.
We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset.
We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
arXiv Detail & Related papers (2023-01-31T19:14:30Z) - Reinforcement Learning with Unbiased Policy Evaluation and Linear
Function Approximation [11.345796608258434]
We provide performance guarantees for a variant of simulation-based policy iteration for controlling Markov decision processes.
We analyze two algorithms; the first algorithm involves a least squares approach where a new set of weights associated with feature vectors is obtained via at least squares at each iteration.
The second algorithm involves a two-time-scale approximation algorithm taking several steps of gradient descent towards the least squares solution.
arXiv Detail & Related papers (2022-10-13T20:16:19Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
We consider off-policy policy evaluation with function approximation in average-reward MDPs.
bootstrapping is necessary and, along with off-policy learning and FA, results in the deadly triad.
We propose two novel algorithms, reproducing the celebrated success of Gradient TD algorithms in the average-reward setting.
arXiv Detail & Related papers (2021-01-08T00:43:04Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
We give efficient differentially private algorithms for basic clustering problems.
Our results imply an improved algorithm for the Sample and Aggregate privacy framework.
One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
arXiv Detail & Related papers (2020-08-18T16:22:06Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions.
A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples.
We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
arXiv Detail & Related papers (2020-05-10T19:52:03Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.