We propose truncated concentrated differential privacy (tCDP), a refinement of and privacy. This new definition provides robust efficient composition guarantees, supports powerful algorithmic techniques such as amplification via sub-sampling, enables more accurate statistical analyses. In particular, we show central task for which the exponential accuracy improvement.

Differential privacy is a formal mathematical framework for quantifying and managing risks. It provides provable protection against wide range of potential attacks, including those currently unforeseen. primarily studied in the context collection, analysis, release aggregate statistics. These from simple statistical estimations, such as averages, to machine learning. Tools differentially private analysis are now early stages implementation use across variety academic, industry, government...

We prove new upper and lower bounds on the sample complexity of (ε, δ) differentially private algorithms for releasing approximate answers to threshold functions. A function c over a totally ordered domain X evaluates <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">z</sub> (y) = 1 if y ≤ x, 0 otherwise. give first nontrivial bound thresholds with differential privacy, showing that task is impossible an infinite X, moreover requires n ≥ Ω(log*...

We show new lower bounds on the sample complexity of (ε, δ)-differentially private algorithms that accurately answer large sets counting queries. A query a database D ∈ ({0, 1}d)n has form "What fraction individual records in satisfy property q?" order to an arbitrary set Q » nd queries within error ±α it is necessary

We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as function of all standardly considered parameters. Prior work obtained rates depend optimally on number users, size domain, and privacy parameter, but sub-optimally failure probability. strengthen existing lower bounds to incorporate probability, show that our upper bound is tight with respect this parameter well. Our based understanding structure protocols....

We present a new locally differentially private algorithm for the heavy hitters problem that achieves optimal worst-case error as function of all standardly considered parameters. Prior work obtained rates depend optimally on number users, size domain, and privacy parameter but sub-optimally failure probability. strengthen existing lower bounds to incorporate probability show our upper bound is tight with respect this well. Our based understanding structure protocols. further develop these...

We investigate the {\em direct-sum} problem in context of differentially private PAC learning: What is sample complexity solving k learning tasks simultaneously under differential privacy, and how does this cost compare to that without privacy? In our setting, an individual example consists a domain element x labeled by unknown concepts (c1,...,ck). The goal multi-learner output hypotheses (h1,...,hk) generalize input examples.

We show new information-theoretic lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately answer large sets counting queries. A query a database $D \in (\{0,1\}^d)^n$ has form "What fraction individual records in satisfy property $q$?" order to an arbitrary set $\mathcal{Q}$ $\gg d/\alpha^2$ queries $D$ within error $\pm \alpha$ it is necessary $ n \geq \tilde{\Omega}({\sqrt{d} \log |\mathcal{Q}|}/{\alpha^2 \varepsilon}). This bound...

The approximate degree of a Boolean function f is the least real polynomial that approximates pointwise to error at most 1/3. Approximate known be lower bound on quantum query complexity. We resolve or nearly and complexities following basic functions: $\bullet$ $k$-distinctness: For any constant $k$, complexity $k$-distinctness $\Omega(n^{3/4-1/(2k)})$. This tight for large $k$ (Belovs, FOCS 2012). Image size testing: testing image $[n] \to [n]$ $\tilde{\Omega}(n^{1/2})$. proves conjecture...

We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. This answers open question of Alon et al. (STOC 2019) who proved the converse statement (this was also asked Neel (FOCS 2019)). Together these two results yield equivalence between online learnability and private PAC learnability. introduce a new notion algorithmic stability called "global stability" which is essential to our proof may independent interest....

The technical literature about data privacy largely consists of two complementary approaches: formal definitions conditions sufficient for preservation and attacks that demonstrate breaches. Differential is an accepted standard in the former sphere. However, differential privacy's powerful adversarial model worst-case guarantees may make it too stringent some situations, especially when achieving comes at a significant cost to utility. Meanwhile, aim expose real worrying risks associated...

We provide a differentially private algorithm for hypothesis selection. Given samples from an unknown probability distribution $P$ and set of $m$ distributions $\mathcal{H}$, the goal is to output, in $\varepsilon$-differentially manner, $\mathcal{H}$ whose total variation distance comparable that best such (which we denote by $\alpha$). The sample complexity our basic $O\left(\frac{\log m}{\alpha^2} + \frac{\log m}{\alpha \varepsilon}\right)$, representing minimal cost privacy when compared...

Modern machine learning models are complex and frequently encode surprising amounts of information about individual inputs. In extreme cases, appear to memorize entire input examples, including seemingly irrelevant (social security numbers from text, for example). this paper, we aim understand whether sort memorization is necessary accurate learning. We describe natural prediction problems in which every sufficiently training algorithm must encode, the model, essentially all a large subset...

The simplest and most widely applied method for guaranteeing differential privacy is to add instance-independent noise a statistic of interest that scaled its global sensitivity. However, sensitivity worst-case notion often too conservative realized dataset instances. We provide methods scaling in an instance-dependent way demonstrate they greater accuracy under average-case distributional assumptions. Specifically, we consider the basic problem privately estimating mean real distribution...

The approximate degree of a Boolean function f : {-1, 1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> → is the least real polynomial that approximates pointwise to error at most 1/3. We introduce generic method for increasing given function, while preserving its computability by constant-depth circuits. Specifically, we show how transform any with d into F on O(n · polylog(n)) variables D = Ω(n...

The sign-rank of a matrix A with entries in {-1, +1} is the least rank real B A_{ij}*B_{ij} > 0 for all i, j. Razborov and Sherstov (2008) gave first exponential lower bounds on function AC^0, answering an old question Babai, Frankl, Simon (1986). Specifically, they exhibited = [F(x,y)]_{x,y} specific F:{-1,1}^n*{-1,1}^n -> {-1,1} such that has exp(Omega(n^{1/3}). We prove generalization Sherstov’s result, yielding non-trivial class functions (that includes used by Sherstov). As corollary...