Anru Zhang (Wisconsin-Madison)

Dec 11, 2020

Title and Abstract

Importance Sketching for Fast Low-rank Matrix/Tensor Learning: Algorithm and High-order Convergence

In this talk, we propose a new recursive importance sketching algorithm for rank constrained least-squares optimization (RISRO). As its name suggests, the algorithm is based on a new sketching framework, recursive importance sketching. Several existing algorithms in the literature can be reinterpreted under the new sketching framework and RISRO offers clear advantages over them. RISRO is easy to implement and computationally efficient, where the core procedure in each iteration is only solving a dimension reduced least-squares problem. Different from numerous existing algorithms with a locally geometric convergence rate, we establish the local quadratic-linear and quadratic rate of convergence for RISRO under some mild conditions. In addition, we discover a deep connection of RISRO to Riemannian manifold optimization. The effectiveness of RISRO is demonstrated in applications in machine learning and statistics.

Bio

Anru Zhang is currently an assistant professor at the Department of Statistics, University of Wisconsin-Madison. He obtained the PhD degree from University of Pennsylvania (2015). He is the recipient of the NSF CAREER Award (2020) and Bernoulli New Researcher Award (2020-2021). His current research interests include high-dimensional statistics, statistical learning theory, tensor learning