Computational and Statistical Tradeoffs via Convex Relaxation
arXiv:1211.1073 · doi:10.1073/pnas.1302293110
Abstract
In modern data analysis, one is frequently faced with statistical inference problems involving massive datasets. Processing such large datasets is usually viewed as a substantial computational challenge. However, if data are a statistician's main resource then access to more data should be viewed as an asset rather than as a burden. In this paper we describe a computational framework based on convex relaxation to reduce the computational complexity of an inference procedure when one has access to increasingly larger datasets. Convex relaxation techniques have been widely used in theoretical computer science as they give tractable approximation algorithms to many computationally intractable tasks. We demonstrate the efficacy of this methodology in statistical estimation in providing concrete time-data tradeoffs in a class of denoising problems. Thus, convex relaxation offers a principled approach to exploit the statistical gains from larger datasets to reduce the runtime of inference algorithms.
References in corpus (8)
- Lectures on 0/1-polytopes
- Regularized estimation of large covariance matrices
- The Convex Geometry of Linear Inverse Problems
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Theta Bodies for Polynomial Ideals
- Orbitopes
- Oracle inequalities for computationally adaptive model selection
- Using More Data to Speed-up Training Time
Cited by in corpus (45)
- Convex Optimization for Big Data
- Optimal detection of sparse principal components in high dimension
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Computational barriers in minimax submatrix detection
- On statistics, computation and scalability
- A new perspective on least squares under convex constraint
- -Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?
- Computational Lower Bounds for Sparse PCA
- Statistical and computational trade-offs in estimation of sparse principal components
- HoloClean: Holistic Data Repairs with Probabilistic Inference
- Compressed Sensing with Prior Information: Optimal Strategies, Geometry, and Bounds
- More data speeds up training time in learning halfspaces over sparse vectors
- Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
- Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
- Tight convex relaxations for sparse matrix factorization
- Reducibility and Statistical-Computational Gaps from Secret Leakage
- Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
- Sharp MSE Bounds for Proximal Denoising
- Tradeoffs for Space, Time, Data and Risk in Unsupervised Learning
- Bayesian computation: a perspective on the current state, and sampling backwards and forwards
- Measures of Correlation for Multiple Variables
- The Overlap Gap Property in Principal Submatrix Recovery
- Starting Small -- Learning with Adaptive Sample Sizes
- Compressed Super-Resolution of Positive Sources
- Collaborative Information Bottleneck
- Gordon's inequality and condition numbers in conic optimization
- Proximal Markov chain Monte Carlo algorithms
- Provable quantum state tomography via non-convex methods
- Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
- Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
- Optimal link prediction with matrix logistic regression
- A Scalable Semidefinite Relaxation Approach to Grid Scheduling
- Quantized Estimation of Gaussian Sequence Models in Euclidean Balls
- Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs
- Magging: maximin aggregation for inhomogeneous large-scale data
- Regularized Non-Gaussian Image Denoising
- A Geometric View on Constrained M-Estimators
- Compressive MRI quantification using convex spatiotemporal priors and deep auto-encoders
- Learning Machines Implemented on Non-Deterministic Hardware
- Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
- Statistical Limits of Convex Relaxations
- Analyzing statistical and computational tradeoffs of estimation procedures
- Statistical and Computational Tradeoff in Genetic Algorithm-Based Estimation
- Extended Formulations for Online Linear Bandit Optimization
- Accelerated Dual Learning by Homotopic Initialization