Search

The growth of data sharing initiatives for neuroimaging and genomics represents an exciting opportunity to confront the "small N" problem that plagues contemporary neuroimaging studies while further understanding the role genetic markers play in the function of the brain. When it is possible, open data sharing provides the most benefits. However, some data cannot be shared at all due to privacy concerns and/or risk of re-identification. Sharing other data sets is hampered by the proliferation of complex data use agreements (DUAs) which preclude truly automated data mining. These DUAs arise because of concerns about the privacy and confidentiality for subjects; though many do permit direct access to data, they often require a cumbersome approval process that can take months. An alternative approach is to only share data derivatives such as statistical summaries—the challenges here are to reformulate computational methods to quantify the privacy risks associated with sharing the results of those computations. For example, a derived map of gray matter is often as identifiable as a fingerprint. Thus alternative approaches to accessing data are needed. This paper reviews the relevant literature on differential privacy, a framework for measuring and tracking privacy loss in these settings, and demonstrates the feasibility of using this framework to calculate statistics on data distributed at many sites while still providing privacy. [ABSTRACT FROM AUTHOR]

The principal components analysis (PCA) algorithm is a standard tool for identifying good low-dimensional approximations to high-dimensional data. Many data sets of interest contain private or sensitive information about individuals. Algorithms which operate on such data should be sensitive to the privacy risks in publishing their outputs. Differential privacy is a framework for developing tradeoffs between privacy and the utility of these outputs. In this paper we investigate the theory and empirical performance of differentially private approximations to PCA and propose a new method which explicitly optimizes the utility of the output. We show that the sample complexity of the proposed method differs from the existing procedure in the scaling with the data dimension, and that our method is nearly optimal in terms of this scaling. We furthermore illustrate our results, showing that on real data there is a large performance gap between the existing method and our method. [ABSTRACT FROM AUTHOR]

Private companies, government entities, and institutions such as hospitals routinely gather vast amounts of digitized personal information about the individuals who are their customers, clients, or patients. Much of this information is private or sensitive, and a key technological challenge for the future is how to design systems and processing techniques for drawing inferences from this large-scale data while maintaining the privacy and security of the data and individual identities. Individuals are often willing to share data, especially for purposes such as public health, but they expect that their identity or the fact of their participation will not be disclosed. In recent years, there have been a number of privacy models and privacy-preserving data analysis algorithms to answer these challenges. In this article, we will describe the progress made on differentially private machine learning and signal processing. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword \bf x=(x1, \dots, xn) bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bits xi one at a time and can change up to a p-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit xi, the jammer's decision on whether to corrupt it or not must depend only on xj for j \leq i. This is in contrast to the “classical” adversarial jamming situations in which the jammer has no knowledge of \bf x, or knows \bf x completely. In this study, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes. [ABSTRACT FROM PUBLISHER]

List-decoding for arbitrarily varying channels (AVCs) under state constraints is investigated. It is shown that rates within \epsilon of the randomized coding capacity of AVCs with input-dependent state can be achieved under maximal error with list-decoding using lists of size O(1/\epsilon). Under the average error criterion, an achievable rate and converse bound are given for lists of size L. These bounds are based on two different notions of symmetrizability and do not coincide in general. An example is given which shows that for list size L, the capacity may be positive but strictly smaller than the randomized coding capacity, in contrast to the situation without constraints. [ABSTRACT FROM AUTHOR]

The arbitrarily varying channel (AVC) is a channel model whose state is selected maliciously by an adversary. Fixed-blocklength coding assumes a worst-case bound on the adversary's capabilities, which leads to pessimistic results. This paper defines a variable-length perspective on this problem, for which achievable rates are shown that depend on the realized actions of the adversary. Specifically, rateless codes are constructed which require a limited amount of common randomness. These codes are constructed for two kinds of AVC models. In the first the channel state cannot depend on the channel input, and in the second it can. As a by-product, the randomized coding capacity of the AVC with state depending on the transmitted codeword is found and shown to be achievable with a small amount of common randomness. The results for this model are proved using a randomized strategy based on list decoding. [ABSTRACT FROM AUTHOR]

We provide high-probability sample complexity guarantees for exact structure recovery and accurate predictive learning using noise-corrupted samples from an acyclic (tree-shaped) graphical model. The hidden variables follow a tree-structured Ising model distribution, whereas the observable variables are generated by a binary symmetric channel taking the hidden variables as its input (flipping each bit independently with some constant probability q 2 [0; 1=2)). In the absence of noise, predictive learning on Ising models was recently studied by Bresler and Karzand (2020); this paper quantifies how noise in the hidden model impacts the tasks of structure recovery and marginal distribution estimation by proving upper and lower bounds on the sample complexity. Our results generalize state-of-the-art bounds reported in prior work, and they exactly recover the noiseless case (q = 0). In fact, for any tree with p vertices and probability of incorrect recovery ffi > 0, the sufficient number of samples remains logarithmic as in the noiseless case, i.e., O(log(p=)), while the dependence on q is O 1=(1 2q)4, for both aforementioned tasks. We also present a new equivalent of Isserlis' Theorem for sign-valued tree-structured distributions, yielding a new low-complexity algorithm for higher-order moment estimation. [ABSTRACT FROM AUTHOR]

Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the e-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance. [ABSTRACT FROM AUTHOR]