Computational and statistical tradeoffs via convex relaxation

DOI10.1073/pnas.1302293110zbMath1292.62019arXiv1211.1073OpenAlexW2132001804WikidataQ30538182 ScholiaQ30538182MaRDI QIDQ5170958

Michael I. Jordan, Venkat Chandrasekaran

Publication date: 25 July 2014

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.1073

Mathematics Subject Classification ID

Linear inference, regression (62J99) Convex programming (90C25)

Related Items

Tensor clustering with planted structures: statistical optimality and computational limits, WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions, Proximal Markov chain Monte Carlo algorithms, Statistics for big data: a perspective, When small data beats big data, Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing, Sharp MSE bounds for proximal denoising, High-dimensional change-point estimation: combining filtering with convex optimization, \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?, On statistics, computation and scalability, Optimal detection of sparse principal components in high dimension, Manifold separation-based DOA estimation for nonlinear arrays via compressed super-resolution of positive sources, Unnamed Item, Kronecker-structured covariance models for multiway data, BOLT-SSI: A Statistical Approach to Screening Interaction Effects for Ultra-High Dimensional Data, A new perspective on least squares under convex constraint, Crawling subsampling for multivariate spatial autoregression model in large-scale networks, Unnamed Item, Sharp oracle inequalities for least squares estimators in shape restricted regression, Making sense of big data, Optimal testing for planted satisfiability problems, Unnamed Item, Bayesian computation: a summary of the current state, and samples backwards and forwards, Statistical and computational tradeoff in genetic algorithm-based estimation, The overlap gap property in principal submatrix recovery, Detection of Long Edges on a Computational Budget: A Sublinear Approach, Computational barriers in minimax submatrix detection

Cites Work

• Unnamed Item
• Computing the nearest correlation matrix--a problem from finance
• Nuclear norm minimization for the planted clique and biclique problems
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Semidefinite programming relaxations for semialgebraic problems
• Minimax estimation via wavelet shrinkage
• The convex geometry of linear inverse problems
• Hyperbolic programs, and their derivative relaxations
• Regularized estimation of large covariance matrices
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Global Optimization with Polynomials and the Problem of Moments
• Orthogonal Tensor Decompositions
• Theta Bodies for Polynomial Ideals
• ORBITOPES
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Odd Minimum Cut-Sets and b-Matchings
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• De-noising by soft-thresholding
• Finding and certifying a large hidden clique in a semirandom graph
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions
• Maximum matching and a polyhedron with 0,1-vertices
• Compressed sensing
• Computational sample complexity and attribute-efficient learning