# Randomized Sketches of Convex Programs with Sharp Guarantees

arXiv: https://arxiv.org/abs/1404.7203 · HTML: https://mlsanity.com/paper/1404.7203/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2014.

## Built on by (most cited first, 25 of 25)

- [Provable Continual Learning via Sketched Jacobian Approximations](https://mlsanity.com/paper/2112.05095/) (2021)
- [Learning Augmentation Distributions using Transformed Risk Minimization](https://mlsanity.com/paper/2111.08190/) (2021)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [ControlBurn: Feature Selection by Sparse Forests](https://mlsanity.com/paper/2107.00219/) (2021)
- [Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds](https://mlsanity.com/paper/2203.09755/) (2022)
- [Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs](https://mlsanity.com/paper/2205.13163/) (2022)
- [Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs](https://mlsanity.com/paper/2206.10291/) (2022)
- [Feature Space Sketching for Logistic Regression](https://mlsanity.com/paper/2303.14284/) (2023)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [LoRA Provides Differential Privacy by Design via Random Sketching](https://mlsanity.com/paper/2409.17538/) (2024)
- [Accelerating Plug-and-Play Image Reconstruction via Multi-Stage Sketched Gradients](https://mlsanity.com/paper/2203.07308/) (2022)
- [The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches](https://mlsanity.com/paper/2505.24603/) (2025)
- [Learning-Augmented Sketches for Hessians](https://mlsanity.com/paper/2102.12317/) (2021)
- [Statistical optimality conditions for compressive ensembles](https://mlsanity.com/paper/2106.01092/) (2021)
- [Equivariance Regularization for Image Reconstruction](https://mlsanity.com/paper/2202.05062/) (2022)
- [Near-Optimal Private Linear Regression via Iterative Hessian Mixing](https://mlsanity.com/paper/2601.07545/) (2026)
- [Fast Multi-label Learning](https://mlsanity.com/paper/2108.13570/) (2021)
- [Learning Linear Models Using Distributed Iterative Hessian Sketching](https://mlsanity.com/paper/2112.04101/) (2021)
- [Distributed Sparse Multicategory Discriminant Analysis](https://mlsanity.com/paper/2202.10913/) (2022)
- [Statistical Analysis of Karcher Means for Random Restricted PSD Matrices](https://mlsanity.com/paper/2302.12426/) (2023)
- [On the Noise Sensitivity of the Randomized SVD](https://mlsanity.com/paper/2305.17435/) (2023)
- [Equivariant Test-Time Training with Operator Sketching for Imaging Inverse Problems](https://mlsanity.com/paper/2411.05771/) (2024)
- [A Scalable Approach for Safe and Robust Learning via Lipschitz-Constrained Networks](https://mlsanity.com/paper/2506.23977/) (2025)
- [The Fast Mixing Mechanism for Differential Privacy](https://mlsanity.com/paper/2605.30600/) (2026)
- [Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws](https://mlsanity.com/paper/2610.00101/) (2026)

## Abstract (arXiv)

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 ℓ1-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.