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

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

Computer Science and Engineering

Research output: Contribution to conference › Paper › peer-review

7 Scopus citations

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 language	English (US)
State	Published - 2017
Event	20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 - Fort Lauderdale, United States Duration: Apr 20 2017 → Apr 22 2017

Conference

Conference	20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017
Country/Territory	United States
City	Fort Lauderdale
Period	4/20/17 → 4/22/17

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Statistics and Probability

Cite this

@conference{82b5850d3cfa4636886861754f3a1241,

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

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.",

author = "Jialei Wang and Lee, {Jason D.} and Mehrdad Mahdavi and Mladen Kolar and Nathan Srebro",

year = "2017",

language = "English (US)",

}

Sketching meets random projection in the dual: A provable recovery algorithm for big and high-dimensional data. / Wang, Jialei; Lee, Jason D.; Mahdavi, Mehrdad et al.
2017. Paper presented at 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, Fort Lauderdale, United States.

Research output: Contribution to conference › Paper › peer-review

TY - CONF

T1 - Sketching meets random projection in the dual

T2 - 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017

AU - Wang, Jialei

AU - Lee, Jason D.

AU - Mahdavi, Mehrdad

AU - Kolar, Mladen

AU - Srebro, Nathan

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85083938656&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083938656&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85083938656

Y2 - 20 April 2017 through 22 April 2017

ER -

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

Abstract

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this