Differentially Private Data Publishing and Analysis: A Survey <s> Adaptive Data Analysis <s> A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries, from the use of sophisticated validation techniques, to deep statistical methods for controlling the false discovery rate in multiple hypothesis testing. However, there is a fundamental disconnect between the theoretical results and the practice of data analysis: the theory of statistical inference assumes a fixed collection of hypotheses to be tested, or learning algorithms to be applied, selected non-adaptively before the data are gathered, whereas in practice data is shared and reused with hypotheses and new analyses being generated on the basis of data exploration and the outcomes of previous analyses. In this work we initiate a principled study of how to guarantee the validity of statistical inference in adaptive data analysis. As an instance of this problem, we propose and investigate the question of estimating the expectations of m adaptively chosen functions on an unknown distribution given n random samples. We show that, surprisingly, there is a way to estimate an exponential in n number of expectations accurately even if the functions are chosen adaptively. This gives an exponential improvement over standard empirical estimators that are limited to a linear number of estimates. Our result follows from a general technique that counter-intuitively involves actively perturbing and coordinating the estimates, using techniques developed for privacy preservation. We give additional applications of this technique to our question. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Adaptive Data Analysis <s> Overfitting is the bane of data analysts, even when data are plentiful. Formal approaches to understanding this problem focus on statistical inference and generalization of individual analysis procedures. Yet the practice of data analysis is an inherently interactive and adaptive process: new analyses and hypotheses are proposed after seeing the results of previous ones, parameters are tuned on the basis of obtained results, and datasets are shared and reused. An investigation of this gap has recently been initiated by the authors in [7], where we focused on the problem of estimating expectations of adaptively chosen functions. ::: ::: In this paper, we give a simple and practical method for reusing a holdout (or testing) set to validate the accuracy of hypotheses produced by a learning algorithm operating on a training set. Reusing a holdout set adaptively multiple times can easily lead to overfitting to the holdout set itself. We give an algorithm that enables the validation of a large number of adaptively chosen hypotheses, while provably avoiding overfitting. We illustrate the advantages of our algorithm over the standard use of the holdout set via a simple synthetic experiment. ::: ::: We also formalize and address the general problem of data reuse in adaptive data analysis. We show how the differential-privacy based approach given in [7] is applicable much more broadly to adaptive data analysis. We then show that a simple approach based on description length can also be used to give guarantees of statistical validity in adaptive settings. Finally, we demonstrate that these incomparable approaches can be unified via the notion of approximate max-information that we introduce. This, in particular, allows the preservation of statistical validity guarantees even when an analyst adaptively composes algorithms which have guarantees based on either of the two approaches. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Adaptive Data Analysis <s> A new line of work, started with Dwork et al., studies the task of answering statistical queries using a sample and relates the problem to the concept of differential privacy. By the Hoeffding bound, a sample of size $O(\log k/\alpha^2)$ suffices to answer $k$ non-adaptive queries within error $\alpha$, where the answers are computed by evaluating the statistical queries on the sample. This argument fails when the queries are chosen adaptively (and can hence depend on the sample). Dwork et al. showed that if the answers are computed with $(\epsilon,\delta)$-differential privacy then $O(\epsilon)$ accuracy is guaranteed with probability $1-O(\delta^\epsilon)$. Using the Private Multiplicative Weights mechanism, they concluded that the sample size can still grow polylogarithmically with the $k$. ::: Very recently, Bassily et al. presented an improved bound and showed that (a variant of) the private multiplicative weights algorithm can answer $k$ adaptively chosen statistical queries using sample complexity that grows logarithmically in $k$. However, their results no longer hold for every differentially private algorithm, and require modifying the private multiplicative weights algorithm in order to obtain their high probability bounds. ::: We greatly simplify the results of Dwork et al. and improve on the bound by showing that differential privacy guarantees $O(\epsilon)$ accuracy with probability $1-O(\delta\log(1/\epsilon)/\epsilon)$. It would be tempting to guess that an $(\epsilon,\delta)$-differentially private computation should guarantee $O(\epsilon)$ accuracy with probability $1-O(\delta)$. However, we show that this is not the case, and that our bound is tight (up to logarithmic factors). <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Adaptive Data Analysis <s> Adaptivity is an important feature of data analysis---typically the choice of questions asked about a dataset depends on previous interactions with the same dataset. However, generalization error is typically bounded in a non-adaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC '15) and Hardt and Ullman (FOCS '14) initiated the formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis. ::: Specifically, suppose there is an unknown distribution $\mathcal{P}$ and a set of $n$ independent samples $x$ is drawn from $\mathcal{P}$. We seek an algorithm that, given $x$ as input, "accurately" answers a sequence of adaptively chosen "queries" about the unknown distribution $\mathcal{P}$. How many samples $n$ must we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy? ::: In this work we make two new contributions towards resolving this question: ::: *We give upper bounds on the number of samples $n$ that are needed to answer statistical queries that improve over the bounds of Dwork et al. ::: *We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrary low-sensitivity queries and the important class of convex risk minimization queries. ::: As in Dwork et al., our algorithms are based on a connection between differential privacy and generalization error, but we feel that our analysis is simpler and more modular, which may be useful for studying these questions in the future. <s> BIB004
Adaptive data analysis creates a connection between differential privacy and machine learning. Machine learning theory is well developed, but is based on the assumption that a learning algorithm operates on a freshly sampled dataset. However, data samples are often reused, and the practice of learning is naturally adaptive. This adaptivity violates standard generalization guarantees. It is easy to over-fit the data when applying adaptive data analysis. Differential privacy can solve this adaptive problem. Dwork et al. BIB001 , BIB002 proposed a method that can perform arbitrary adaptive data with solid generalization guarantees. In this method, the algorithm's stability is assumed to prevent over-fitting and differential privacy is considered to be an algorithmic stability guarantee. Thus, a quantitative error bound is provided in terms of generality. This line of research proves that differential privacy has a generalization property that can be applied in statistical analysis and machine learning BIB003 , BIB004 . Although, at this early stage, many new possibilities for generalization need to be explored.