Related papers: Faster Privacy Accounting via Evolving Discretization

Faster Privacy Accounting via Evolving Discretization

URL: http://arxiv.org/abs/2207.04381v1
Date: Sun, 10 Jul 2022 04:25:37 GMT
Title: Faster Privacy Accounting via Evolving Discretization
Authors: Badih Ghazi and Pritish Kamath and Ravi Kumar and Pasin Manurangsi
Abstract summary: We introduce a new algorithm for numerical composition of privacy random variables. Our algorithm achieves a running time and memory usage of $mathrmpolylog(k)$ for the task of self-composing a mechanism.
Score: 54.32252900997422
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for composition of mechanisms. Our algorithm achieves a running time and memory usage of $\mathrm{polylog}(k)$ for the task of self-composing a mechanism, from a broad class of mechanisms, $k$ times; this class, e.g., includes the sub-sampled Gaussian mechanism, that appears in the analysis of differentially private stochastic gradient descent. By comparison, recent work by Gopi et al. (NeurIPS 2021) has obtained a running time of $\widetilde{O}(\sqrt{k})$ for the same task. Our approach extends to the case of composing $k$ different mechanisms in the same class, improving upon their running time and memory usage from $\widetilde{O}(k^{1.5})$ to $\widetilde{O}(k)$.

Related papers

Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning [2.2083091880368855]
We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of $d,Theta(k)$ possible length-$k$ sequences. We present an improved algorithm with time and space complexity $O(d + k2 / epsilon cdot ln d)$, where $epsilon$ denotes the privacy
arXiv Detail & Related papers (2024-11-14T16:06:13Z)
Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
We introduce edgedifferentially private algorithms for the multiway cut and the minimum $k$cut. For the minimum $k$-cut problem we use a different approach, combining the exponential mechanism with bounds on the number of approximate $k$-cuts.
arXiv Detail & Related papers (2024-07-09T14:46:33Z)
User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
We consider the example-scarce regime, where each user has only a few examples, and obtain the following results. For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. We present a simple technique for adapting the exponential mechanism [McSherry, Talwar FOCS 2007] to the user-level setting.
arXiv Detail & Related papers (2023-09-21T21:51:55Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z)
A Smooth Binary Mechanism for Efficient Private Continual Observation [13.846839500730873]
We show how to release differentially private estimates based on a dataset that evolves over time. A simple Python implementation of our approach outperforms the running time of the approach of Henzinger et al.
arXiv Detail & Related papers (2023-06-16T07:45:32Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
arXiv Detail & Related papers (2023-01-11T09:12:28Z)
Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
arXiv Detail & Related papers (2022-06-17T09:24:41Z)
On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
We find that mechanism K achieves a smaller social cost than mechanism P on every input. We also find that the average-case approximation ratio of mechanism P converges to the same constant.
arXiv Detail & Related papers (2022-04-14T20:57:50Z)
Private Frequency Estimation via Projective Geometry [47.112770141205864]
We propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of $k$ and with $n$ users, our $varepsilon$-LDP algorithm has communication cost $lceillogkrceil bits in the private coin setting and $varepsilonlog e + O(1)$ in the public coin setting. In many parameter settings used in practice this is a significant improvement over the O(n+k2)$optimal cost that is achieved by the recent PI-
arXiv Detail & Related papers (2022-03-01T02:49:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.