Sketching meets random projection in the dual: a provable recovery algorithm for big and high-dimensional data
From MaRDI portal
(Redirected from Publication:1688973)
Abstract: Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this paper, we study sketching from an optimization point of view: we first show that the iterative Hessian sketch is an optimization process with preconditioning, and develop accelerated iterative Hessian sketch via the searching the conjugate direction; we then establish primal-dual connections between the Hessian sketch and dual random projection, and apply the preconditioned conjugate gradient approach on the dual problem, which leads to the accelerated iterative dual random projection methods. Finally to tackle the challenges from both large sample size and high-dimensionality, we propose the primal-dual sketch, which iteratively sketches the primal and dual formulations. We show that using a logarithmic number of calls to solvers of small scale problem, primal-dual sketch is able to recover the optimum of the original problem up to arbitrary precision. The proposed algorithms are validated via extensive experiments on synthetic and real data sets which complements our theoretical results.
Recommendations
- An investigation of Newton-sketch and subsampled Newton methods
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Adaptive iterative Hessian sketch via A-optimal subsampling
- A statistical perspective on randomized sketching for ordinary least-squares
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
Cited in
(21)- Randomized sketches for kernel CCA
- Regularized Linear Inversion with Randomized Singular Value Decomposition
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- An investigation of Newton-sketch and subsampled Newton methods
- On nonparametric randomized sketches for kernels with further smoothness
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- Random projections of linear and semidefinite problems with linear inequalities
- Convexification with bounded gap for randomly projected quadratic optimization
- The COR criterion for optimal subset selection in distributed estimation
- An asymptotic analysis of distributed nonparametric methods
- Sketch-based empirical natural gradient methods for deep learning
- M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
- Statistical inference for sketching algorithms
- Sketching for Big Data Recommender Systems Using Fast Pseudo-random Fingerprints
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Approximate nonparametric quantile regression in reproducing kernel Hilbert spaces via random projection
- SketchySGD: reliable stochastic optimization via randomized curvature estimates
- Adaptive iterative Hessian sketch via A-optimal subsampling
- Sketching for large-scale learning of mixture models
- RidgeSketch: a fast sketching based solver for large scale ridge regression
This page was built for publication: Sketching meets random projection in the dual: a provable recovery algorithm for big and high-dimensional data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688973)
