Sketching meets random projection in the dual: a provable recovery algorithm for big and high-dimensional data

DOI10.1214/17-EJS1334SIzbMATH Open1470.62068arXiv1610.03045OpenAlexW2773306503MaRDI QIDQ1688973FDOQ1688973

Authors: Jialei Wang, Jason D. Lee, Mehrdad Mahdavi, Mladen Kolar, Nathan Srebro 

Publication date: 12 January 2018

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1610.03045

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

zbMATH Keywords

conjugate gradientpreconditioningaccelerationdual random projectioniterative Hessian sketchprimal-dual conversionprimal-dual sketch

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Estimation in multivariate analysis (62H12) Large-scale problems in mathematical programming (90C06)

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
• An investigation of Newton-sketch and subsampled Newton methods
• Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
• Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
• On nonparametric randomized sketches for kernels with further smoothness
• Convexification with bounded gap for randomly projected quadratic optimization
• Random projections of linear and semidefinite problems with linear inequalities
• 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)