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

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

Research output: Contribution to conferencePaper

Abstract

We provide a unified optimization view of iterative Hessian sketch (IHS) and iterative dual random projection (IDRP). We establish a primal-dual connection between the Hessian sketch and dual random projection, and show that their iterative extensions are optimization processes with preconditioning. We develop accelerated versions of IHS and IDRP based on this insight together with conjugate gradient descent, and propose a primal-dual sketch method that simultaneously reduces the sample size and dimensionality.

Original languageEnglish (US)
StatePublished - Jan 1 2017
Externally publishedYes
Event20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 - Fort Lauderdale, United States
Duration: Apr 20 2017Apr 22 2017

Conference

Conference20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017
CountryUnited States
CityFort Lauderdale
Period4/20/174/22/17

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Statistics and Probability

Fingerprint Dive into the research topics of 'Sketching meets random projection in the dual: A provable recovery algorithm for big and high-dimensional data'. Together they form a unique fingerprint.

  • Cite this

    Wang, J., Lee, J. D., Mahdavi, M., Kolar, M., & Srebro, N. (2017). Sketching meets random projection in the dual: A provable recovery algorithm for big and high-dimensional data. Paper presented at 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, Fort Lauderdale, United States.