Randomized Sketches of Convex Programs With Sharp Guarantees
From MaRDI portal
Publication:2977306
DOI10.1109/TIT.2015.2450722zbMATH Open1359.90097arXiv1404.7203OpenAlexW2963459305MaRDI QIDQ2977306FDOQ2977306
Authors: Mert Pilanci, Martin J. Wainwright 
Publication date: 28 April 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: Random projection (RP) is a classical technique for reducing storage and computational costs. We analyze RP-based approximations of convex programs, in which the original optimization problem is approximated by the solution of a lower-dimensional problem. Such dimensionality reduction is essential in computation-limited settings, since the complexity of general convex programming can be quite high (e.g., cubic for quadratic programs, and substantially higher for semidefinite programs). In addition to computational savings, random projection is also useful for reducing memory usage, and has useful properties for privacy-sensitive optimization. We prove that the approximation ratio of this procedure can be bounded in terms of the geometry of constraint set. For a broad class of random projections, including those based on various sub-Gaussian distributions as well as randomized Hadamard and Fourier transforms, the data matrix defining the cost function can be projected down to the statistical dimension of the tangent cone of the constraints at the original solution, which is often substantially smaller than the original dimension. We illustrate consequences of our theory for various cases, including unconstrained and -constrained least squares, support vector machines, low-rank matrix estimation, and discuss implications on privacy-sensitive optimization and some connections with de-noising and compressed sensing.
Full work available at URL: https://arxiv.org/abs/1404.7203
Cited In (34)
- Randomized sketches for kernel CCA
- Hierarchical inference for genome-wide association studies: a view on methodology with software
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- On principal components regression, random projections, and column subsampling
- Randomized numerical linear algebra: Foundations and algorithms
- Second-order stochastic optimization for machine learning in linear time
- Random projections for linear programming: an improved retrieval phase
- On \(b\)-bit min-wise hashing for large-scale regression and classification with sparse data
- On nonparametric randomized sketches for kernels with further smoothness
- Reduced rank regression with matrix projections for high-dimensional multivariate linear regression model
- Sharper bounds for regularized data fitting
- Random projections for quadratic programs
- Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Functional principal subspace sampling for large scale functional data analysis
- Low-rank matrix completion using nuclear norm minimization and facial reduction
- Convexification with bounded gap for randomly projected quadratic optimization
- Sketching for principal component regression
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- Random projections for semidefinite programming
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Redundancy techniques for straggler mitigation in distributed optimization and learning
- Structured random sketching for PDE inverse problems
- M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
- Generic error bounds for the generalized Lasso with sub-exponential data
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Distributed learning for sketched kernel regression
- Approximate nonparametric quantile regression in reproducing kernel Hilbert spaces via random projection
- Sketched approximation of regularized canonical correlation analysis
- Randomized estimation of functional covariance operator via subsampling
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Tensor-structured sketching for constrained least squares
- Dimensionality reduction of SDPs through sketching
This page was built for publication: Randomized Sketches of Convex Programs With Sharp Guarantees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977306)
