Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For universe size of k and with n users, our epsLDP algorithm has communication cost ceil(log_2 k) and computation cost O(n + k\exp(eps) log k) for the server to approximately reconstruct the frequency histogram, while achieve optimal privacyutility tradeoff. In many practical settings this is a significant improvement over the O (n+k^2) computation cost that is achieved by the recent PIRAPPOR algorithm (Feldman and Talwar; 2021). Our empirical evaluation shows a speedup of over 50x over PIRAPPOR while using approximately 75x less memory. In addition, the running time of our algorithm is comparable to that of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. The error of our algorithm essentially matches that of the communication and timeinefficient but utilityoptimal SubsetSelection (SS) algorithm (Ye and Barg; 2017). Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction for the server.more » « less

Given a data set of size n in d'dimensional Euclidean space, the kmeans problem asks for a set of k points (called centers) such that the sum of the l_2^2distances between the data points and the set of centers is minimized. Previous work on this problem in the local differential privacy setting shows how to achieve multiplicative approximation factors arbitrarily close to optimal, but suffers high additive error. The additive error has also been seen to be an issue in implementations of differentially private kmeans clustering algorithms in both the central and local settings. In this work, we introduce a new locally private kmeans clustering algorithm that achieves nearoptimal additive error whilst retaining constant multiplicative approximation factors and round complexity. Concretely, given any c>sqrt(2), our algorithm achieves O(k^(1 + O(1/(2c^21))) * sqrt(d' n) * log d' * poly log n) additive error with an O(c^2) multiplicative approximation factor.more » « less

null (Ed.)We design differentially private algorithms for the bandit convex optimization problem in the projectionfree setting. This setting is important whenever the decision set has a complex geometry, and access to it is done efficiently only through a linear optimization oracle, hence Euclidean projections are unavailable (e.g. matroid polytope, submodular base polytope). This is the first differentiallyprivate algorithm for projectionfree bandit optimization, and in fact our bound matches the best known nonprivate projectionfree algorithm and the best known private algorithm, even for the weaker setting when projections are available.more » « less

We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contributions are two singlepass (semi)streaming algorithms that use $\tilde{O}(k)\cdot\mathrm{poly}(1/\varepsilon)$ memory, where $k$ is the size constraint. At the end of the stream, both our algorithms postprocess their data structures using any offline algorithm for submodular maximization, and obtain a solution whose approximation guarantee is $\frac{\alpha}{1+\alpha}\varepsilon$, where $\alpha$ is the approximation of the offline algorithm. If we use an exact (exponential time) postprocessing algorithm, this leads to $\frac{1}{2}\varepsilon$ approximation (which is nearly optimal). If we postprocess with the algorithm of BuchbinderFeldman '19, that achieves the stateoftheart offline approximation guarantee of $\alpha=0.385$, we obtain $0.2779$approximation in polynomial time, improving over the previously best polynomialtime approximation of $0.1715$ due to Feldman'18. One of our algorithms is combinatorial and enjoys fast update and overall running times. Our other algorithm is based on the multilinear extension, enjoys an improved space complexity, and can be made deterministic in some settings of interest.more » « less