The analysis of Big Data involves often the selection of a few promising finding out of extremely large number of potential ones. Such selection may affect our inferences about the significance, the size, and the uncertainty of the selected findings. In this tutorial I shall motivate our interest in this 'selective inference' problem, present the false discovery rate (FDR) as an effective approach to assess the significance of the selected discoveries in large scale problems, and review the available methodologies to address its control (and some open problems). I shall then carry the insight gained from FDR into selective estimation and confidence intervals, as well as model selection. I shall end by describing the currently active area of post model selection confidence intervals and estimators.

Real-time aggregate statistics of data collected from individuals can be shared to enable many applications such as disease surveillance and traffic monitoring. However, it must be ensured that the privacy of individuals is not compromised. While differential privacy has emerged as a de facto standard for private data analysis, directly applying the differential privacy mechanisms on time-series has limited utility due to high correlations between data values. In this talk, I will present FAST, a novel Filtering and Adaptive Sampling based framework for monitoring aggregate Time-series under differential privacy. FAST adaptively samples long time-series according to detected data dynamics and simultaneously uses filtering techniques to dynamically predict and correct released data values. I will present experimental studies using real datasets demonstrating the feasibility and benefit of FAST and conclude with open questions.

We describe a framework for designing efficient active learning algorithms that are tolerant to random classification noise and differentially-private. The framework is based on active learning algorithms that are statistical in the sense that they rely on estimates of expectations of functions of filtered random examples.

We show that any efficient active statistical learning algorithm can be automatically converted to an efficient active learning algorithm which is tolerant to random classification noise. We show that commonly studied concept classes including thresholds, rectangles, and linear separators can be efficiently actively learned in our framework. These results combined with our generic conversion lead to the first computationally-efficient algorithms for actively learning some of these concept classes in the presence of random classification noise that provide exponential improvement in the dependence on the error parameter over their passive counterparts. In addition, we show that our algorithms can be automatically converted to efficient active differentially-private algorithms. This leads to the first differentially-private active learning algorithms with exponential label savings over the passive case.

Differential privacy is a cryptographically motivated definition of privacy which has gained considerable attention in the algorithms, machine-learning and data-mining communities. While there has been an explosion of work on differentially private machine learning algorithms, an important barrier to achieving end-to-end differential privacy in practical machine learning applications is the lack of an effective procedure for differentially private parameter tuning, or, determining the parameter value (such as a regularization parameter for SVMs or bin size for histograms) that is suitable for a particular application.

In this paper, we introduce a generic validation procedure for differentially private machine learning algorithms that apply when a certain stability condition holds on the training algorithm and the validation performance metric. The training data size and the privacy budget used for training in our procedure is independent of the number of parameter values searched over. We apply our generic procedure to two fundamental tasks in statistics and machine-learning—training a regularized linear classifier and building a histogram density estimator that result in end-to-end differentially private solutions for these problems.

Based on joint work with Staal Vinterbo.

Principal components analysis is a popular dimension reduction method with wide applications. In high dimensional data analysis, sparse PCA offers simultaneous dimension reduction and variable selection. This talk will report some recent development in sparse PCA with a special focus on subspace estimation. The results include minimax rates of estimation, a new convex relaxation, and some statistical properties of this new method such as matrix norm convergence and variable selection consistency. Some possible future research topics related to differential privacy will also be mentioned.

We review models and algorithms for private analysis of massive dynamic data. We first consider algorithms that satisfy the combined constraints of the streaming model and differential privacy: they make a constant number of passes over the data, keep sublinear space, and output a differentially private statistic. Then we consider a natural further requirement for dynamic data: that the algorithm continuously updates a statistic as new data arrives, while keeping the entire sequence of updates private. Finally, we explore the connections between streaming algorithms and pan-private algorithms, i.e. algorithms whose memory state is private, so that their guarantees hold even in the face of a security breach. While the strong pan-privacy requirement forbids explicitly storing sketches of the data, we show we can store sufficient statistics on a sketch in order to estimate interesting quantities, such as the number of distinct elements or the number of heavy hitters.

Empirical risk minimization (ERM) is a canonical learning algorithm for learning a hypothesis with small generalization error. Moreover, there exists several generic results that characterize the generalization error in terms of hypotheses space and other problem specific characteristics.

However, most of these results focus on non-private learning where the learned hypothesis might reveal significant information about individual points. In this talk, we will survey some of the recent results for privacy-preserving ERM. In particular, we will discuss privacy and generalization error guarantees of these methods and also discuss their pros/cons in terms of theoretical bounds as well as empirical results.

The talk is based on joint works with Abhradeep Guha Thakurta and Pravesh Kothari.

In this talk, I will survey some fruitful connections between convex geometry and differential privacy for linear queries. The connection is established through a polytope that captures the sensitivity of a set of queries. I will describe several techniques on using the geometry of sensitivity polytope to bound (both upper and lower) the noise level needed to achieve DP. This leads to nearly optimal mechanisms for linear queries, under both pure and approximate privacy  definition.