Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares

Abstract

We study randomized sketching methods for approximately solving least-squares problem with a general convex constraint. The quality of a least-squares approximation can be assessed in different ways: either in terms of the value of the quadratic objective function (cost approximation), or in terms of some distance measure between the approximate minimizer and the true minimizer (solution approximation). Focusing on the latter criterion, our first main result provides a general lower bound on any randomized method that sketches both the data matrix and vector in a least-squares problem; as a surprising consequence, the most widely used least-squares sketch is sub-optimal for solution approximation. We then present a new method known as the iterative Hessian sketch, and show that it can be used to obtain approximations to the original least-squares problem using a projection dimension proportional to the statistical complexity of the least-squares minimizer, and a logarithmic number of iterations. We illustrate our general theory with simulations for both unconstrained and constrained versions of least-squares, including ${\ell }_1$-regularization and nuclear norm constraints. We also numerically demonstrate the practicality of our approach in a real face expression classification experiment.

References in corpus (7)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Consistency of trace norm minimization
• Randomized algorithms for matrices and data
• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving

Cited by in corpus (46)

• Online Censoring for Large-Scale Regressions with Application to Streaming Big Data
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
• Communication-Efficient Distributed Statistical Inference
• Stochastic Subsampling for Factorizing Huge Matrices
• Communication-Efficient Edge AI: Algorithms and Systems
• Testing and non-linear preconditioning of the proximal point method
• A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares
• Randomized sketches for kernels: Fast and optimal non-parametric regression
• Faster Least Squares Optimization
• Lifted Neural Networks
• Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Primal-dual block-proximal splitting for a class of non-convex problems
• Randomized spectral co-clustering for large-scale directed networks
• How to reduce dimension with PCA and random projections?
• Distributed Sketching Methods for Privacy Preserving Regression
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• A Sketched Finite Element Method for Elliptic Models
• Randomized Iterative Algorithms for Fisher Discriminant Analysis
• Random mesh projectors for inverse problems
• Optimized Auxiliary Particle Filters: adapting mixture proposals via convex optimization
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
• Compressed and Penalized Linear Regression
• Structured random sketching for PDE inverse problems
• Efficient First-Order Algorithms for Adaptive Signal Denoising
• RSN: Randomized Subspace Newton
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Sparse sketches with small inversion bias
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners
• Learning Augmentation Distributions using Transformed Risk Minimization
• A row-sampling-based randomised finite element method for elliptic partial differential equations
• Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes
• Regularized Linear Inversion with Randomized Singular Value Decomposition
• Subsampled Optimization: Statistical Guarantees, Mean Squared Error Approximation, and Sampling Method
• Statistical and Algorithmic Perspectives on Randomized Sketching for Ordinary Least-Squares -- ICML
• Adaptive Iterative Hessian Sketch via A-Optimal Subsampling
• Improved SVRG for quadratic functions
• Precise expressions for random projections: Low-rank approximation and randomized Newton
• Model-specific Data Subsampling with Influence Functions
• Learning-Augmented Sketches for Hessians