A Smooth Binary Mechanism for Efficient Private Continual Observation
- URL: http://arxiv.org/abs/2306.09666v2
- Date: Mon, 15 Jan 2024 12:54:05 GMT
- Title: A Smooth Binary Mechanism for Efficient Private Continual Observation
- Authors: Joel Daniel Andersson, Rasmus Pagh
- Abstract summary: 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.
- Score: 13.846839500730873
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In privacy under continual observation we study how to release differentially
private estimates based on a dataset that evolves over time. The problem of
releasing private prefix sums of $x_1,x_2,x_3,\dots \in\{0,1\}$ (where the
value of each $x_i$ is to be private) is particularly well-studied, and a
generalized form is used in state-of-the-art methods for private stochastic
gradient descent (SGD). The seminal binary mechanism privately releases the
first $t$ prefix sums with noise of variance polylogarithmic in $t$. Recently,
Henzinger et al. and Denisov et al. showed that it is possible to improve on
the binary mechanism in two ways: The variance of the noise can be reduced by a
(large) constant factor, and also made more even across time steps. However,
their algorithms for generating the noise distribution are not as efficient as
one would like in terms of computation time and (in particular) space. We
address the efficiency problem by presenting a simple alternative to the binary
mechanism in which 1) generating the noise takes constant average time per
value, 2) the variance is reduced by a factor about 4 compared to the binary
mechanism, and 3) the noise distribution at each step is identical.
Empirically, a simple Python implementation of our approach outperforms the
running time of the approach of Henzinger et al., as well as an attempt to
improve their algorithm using high-performance algorithms for multiplication
with Toeplitz matrices.
Related papers
- SGD with memory: fundamental properties and stochastic acceleration [15.25021403154845]
In non-stochastic setting, the optimal exponent $xi$ in the loss convergence $L_tsim C_Lt-xi is double that in plain GD.
We show that in memory-1 algorithms we can make $C_L$ arbitrarily small while maintaining stability.
arXiv Detail & Related papers (2024-10-05T16:57:40Z) - Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy [24.138484222651346]
We present two approaches to differentially private continual counting.
Our first approach is based on a space-efficient streaming matrix multiplication algorithm for a class of Toeplitz matrices.
We derive efficient closed-forms for the objective function for arbitrarily many steps, and show direct numerical optimization yields a highly practical solution to the problem.
arXiv Detail & Related papers (2024-04-25T16:11:46Z) - Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
We show that two evolutionary algorithms can tolerate constant noise probabilities without increasing the runtime on the OneMax benchmark.
Our results are based on a novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring.
arXiv Detail & Related papers (2024-04-02T16:35:52Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
We propose a first-order algorithm named $B$-sample dual averaging with the logarithmic barrier.
For the Poisson inverse problem, our algorithm attains an $varepsilon$ solution in $smashtildeO(d3/varepsilon2)$ time.
When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an $varepsilon$-optimal solution in $smashtildeO(d3/varepsilon2)$ time.
arXiv Detail & Related papers (2023-11-05T03:33:44Z) - 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) - Efficient Mean Estimation with Pure Differential Privacy via a
Sum-of-Squares Exponential Mechanism [16.996435043565594]
We give the first-time algorithm to estimate the mean of a $d$-positive probability distribution with covariance from $tildeO(d)$ independent samples subject to pure differential privacy.
Our main technique is a new approach to use the powerful Sum of Squares method (SoS) to design differentially private algorithms.
arXiv Detail & Related papers (2021-11-25T09:31:15Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
We propose two single-timescale single-loop algorithms that require only one data point each step.
Our results are expressed in a form of simultaneous primal and dual side convergence.
arXiv Detail & Related papers (2020-08-23T20:36:49Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
We study the learnability of halfspaces in the presence of Tsybakov noise.
We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
arXiv Detail & Related papers (2020-06-11T14:25:02Z) - 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.