Error Estimation for Sketched SVD via the Bootstrap
Jul 12, 2020
Speakers
Miles E. Lopes
Speaker · 0 followers
N. Benjamin Erichson
Speaker · 0 followers
Michael Mahoney
Speaker · 0 followers
About
In order to compute fast approximations to the singular value decompositions (SVD) of very large matrices, randomized sketching algorithms have become a leading approach. However, a key practical difficulty of sketching an SVD is that the user does not know how far the sketched singular vectors/values are from the exact ones. Indeed, the user may be forced to rely on analytical worst-case error bounds, which do not account for the unique structure of a given problem. As a result, the lack of tools for error estimation often leads to much more computation than is really necessary. To overcome these challenges, this paper develops a fully data-driven bootstrap method that numerically estimates the actual error of sketched singular vectors/values. In particular, this approach allows the user to inspect the quality of a rough initial SVD, and then adaptively predict how much extra work is needed to reach a given error tolerance. Meanwhile, from a computational standpoint, the proposed method incurs only minor cost, because it operates on the (small) output of a sketching algorithm, and it requires no passes over the (large) matrix being factored. Lastly, the proposed method is supported by theoretical guarantees and a very encouraging set of experimental results.In order to compute fast approximations to the singular value decompositions (SVD) of very large matrices, randomized sketching algorithms have become a leading approach. However, a key practical difficulty of sketching an SVD is that the user does not know how far the sketched singular vectors/values are from the exact ones. Indeed, the user may be forced to rely on analytical worst-case error bounds, which do not account for the unique structure of a given problem. As a result, the lack of too…
Categories
Mathematics
Category · 2.4k presentations
About ICML 2020
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Talk by Rachel Ward
Watch later
MoFlow: An Invertible Flow Model for Molecular Graph Generation
Watch later
Chengxi Zang, …
XAI and Strategy Extraction via Reward Redistribution
Watch later
Continuous Graph Neural Networks
Watch later
