Randomized Sketches of Convex Programs With Sharp Guarantees
From MaRDI portal
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.
Cited in
(37)- On principal components regression, random projections, and column subsampling
- Dimensionality reduction of SDPs through sketching
- Low-rank matrix completion using nuclear norm minimization and facial reduction
- Randomized sketches for kernel CCA
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Approximate nonparametric quantile regression in reproducing kernel Hilbert spaces via random projection
- Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections
- Functional principal subspace sampling for large scale functional data analysis
- Hierarchical inference for genome-wide association studies: a view on methodology with software
- Random projections for quadratic programs
- Reduced rank regression with matrix projections for high-dimensional multivariate linear regression model
- On nonparametric randomized sketches for kernels with further smoothness
- Generic error bounds for the generalized Lasso with sub-exponential data
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- On \(b\)-bit min-wise hashing for large-scale regression and classification with sparse data
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Second-order stochastic optimization for machine learning in linear time
- Sharper bounds for regularized data fitting
- Tensor-structured sketching for constrained least squares
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- Convexification with bounded gap for randomly projected quadratic optimization
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Structured random sketching for PDE inverse problems
- Sketching for principal component regression
- Redundancy techniques for straggler mitigation in distributed optimization and learning
- Randomized numerical linear algebra: Foundations and algorithms
- Distributed learning for sketched kernel regression
- M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
- Sketched approximation of regularized canonical correlation analysis
- Randomized estimation of functional covariance operator via subsampling
- Random projections for linear programming: an improved retrieval phase
- Random projections for semidefinite programming
- Practical operator sketching framework for accelerating iterative data-driven solutions in linear inverse problems
- Random matrices acting on sets: independent columns
- Equivariant test-time training with operator sketching for imaging inverse problems
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
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)
