Computational and Statistical Tradeoffs via Convex Relaxation

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 (4)

• Regularized estimation of large covariance matrices
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Oracle inequalities for computationally adaptive model selection
• Using More Data to Speed-up Training Time

Cited by in corpus (44)

• Convex Optimization for Big Data
• 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
• ${\ell }^1$-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
• Proximal Markov chain Monte Carlo algorithms
• Gordon's inequality and condition numbers in conic optimization
• 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
• A Scalable Semidefinite Relaxation Approach to Grid Scheduling
• Optimal link prediction with matrix logistic regression
• Quantized Estimation of Gaussian Sequence Models in Euclidean Balls
• Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs
• Regularized Non-Gaussian Image Denoising
• Magging: maximin aggregation for inhomogeneous large-scale data
• 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