← Back to papers
2007 NIPS NeurIPS 2007

Compressed Regression

Abstract

Recent research has studied the role of sparsity in high dimensional regression and signal reconstruction, establishing theoretical limits for recovering sparse models from sparse data. In this paper we study a variant of this problem where the original $n$ input variables are compressed by a random linear transformation to $m \ll n$ examples in $p$ dimensions, and establish conditions under which a sparse linear model can be successfully recovered from the compressed data. A primary motivation for this compression procedure is to anonymize the data and preserve privacy by revealing little information about the original data. We characterize the number of random projections that are required for $\ell_1$-regularized compressed regression to identify the nonzero coefficients in the true model with probability approaching one, a property called ``sparsistence.'' In addition, we show that $\ell_1$-regularized compressed regression asymptotically predicts as well as an oracle linear model, a property called ``persistence.'' Finally, we characterize the privacy properties of the compression procedure in information-theoretic terms, establishing upper bounds on the rate of information communicated between the compressed and uncompressed data that decay to zero.

🌉 Interdisciplinary Bridge — Machine Learning and Security & Privacy
📈 Trend Setter — Privacy
🧭 Keyword Pioneer — privacy preservation
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Security & Privacy, Speech & Audio
🌱 Topic Pioneer — Sparse Optimization
🐣 Hot Topic Early Bird — dimensionality reduction

Authors

Shuheng Zhou , Larry Wasserman , John D. Lafferty

Topics

Machine Learning > Core Methods > Regression Machine Learning > Optimization & Theory > Optimization Machine Learning > Application Areas > Privacy Machine Learning > Learning Types > Supervised Learning Security & Privacy > Privacy Mathematics & Optimization > Optimization > Sparse Optimization Machine Learning > Core Methods > Sparse Optimization Machine Learning > Optimization & Theory > Sparse Optimization Mathematics & Optimization > Optimization > Compressed Sensing

Keywords

dimensionality reduction privacy preservation l1 regularization privacy preserving compressed regression sparse regression sparse optimization ℓ1 regularization random projection sparse model sparse linear model
Download PDF

Related papers

Exponential Family Predictive Representations of State 2007
Privacy-Preserving Belief Propagation and Sampling 2007
Efficient Principled Learning of Thin Junction Trees 2007
How SVMs can estimate quantiles and the median 2007
Rapid Inference on a Novel AND/OR graph for Object Detection, Segmentation and Parsing 2007