Timezone: »

 
Poster
Random Quadratic Forms with Dependence: Applications to Restricted Isometry and Beyond
Arindam Banerjee · Qilong Gu · Vidyashankar Sivakumar · Steven Wu

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #227
in Theory -- Large Deviations and Asymptotic Analysis »

Several important families of computational and statistical results in machine learning and randomized algorithms rely on uniform bounds on quadratic forms of random vectors or matrices. Such results include the Johnson-Lindenstrauss (J-L) Lemma, the Restricted Isometry Property (RIP), randomized sketching algorithms, and approximate linear algebra. The existing results critically depend on statistical independence, e.g., independent entries for random vectors, independent rows for random matrices, etc., which prevent their usage in dependent or adaptive modeling settings. In this paper, we show that such independence is in fact not needed for such results which continue to hold under fairly general dependence structures. In particular, we present uniform bounds on random quadratic forms of stochastic processes which are conditionally independent and sub-Gaussian given another (latent) process. Our setup allows general dependencies of the stochastic process on the history of the latent process and the latent process to be influenced by realizations of the stochastic process. The results are thus applicable to adaptive modeling settings and also allows for sequential design of random vectors and matrices. We also discuss stochastic process based forms of J-L, RIP, and sketching, to illustrate the generality of the results.

Keywords: Large Deviations and Asymptotic Analysis · Hardness of Learning and Approximations · Theory · Algorithms -> Sparsity and Compressed Sensing; Theory
[ Paper]  [ Slides] 

Author Information

Arindam Banerjee (University of Minnesota, Twin Cities)

Arindam Banerjee is a Professor at the Department of Computer & Engineering and a Resident Fellow at the Institute on the Environment at the University of Minnesota, Twin Cities. His research interests are in machine learning, data mining, and applications in complex real-world problems in different areas including climate science, ecology, recommendation systems, text analysis, and finance. He has won several awards, including the NSF CAREER award (2010), the IBM Faculty Award (2013), and six best paper awards in top-tier conferences.

Qilong Gu (University of Minnesota Twin Cities)
Vidyashankar Sivakumar (University of Minnesota)
Steven Wu (University of Minnesota)

zstevenwu.com

More from the Same Authors