Adaptive Reduced Rank Regression
Qiong Wu, Felix MF Wong, Yanhua Li, Zhenming Liu, Varun Kanade
Abstract
We study the low rank regression problem y = Mx + ε, where x and y are d1 and d2 dimensional vectors respectively. We consider the extreme high-dimensional setting where the number of observations n is less than d1 + d2. Existing algorithms are designed for settings where n is typically as large as rank(M)(d1+d2). This work provides an efficient algorithm which only involves two SVD, and establishes statistical guarantees on its performance. The algorithm decouples the problem by first estimating the precision matrix of the features, and then solving the matrix denoising problem. To complement the upper bound, we introduce new techniques for establishing lower bounds on the performance of any algorithm for this problem. Our preliminary experiments confirm that our algorithm often out-performs existing baseline, and is always at least competitive.
BibTeX
@inproceedings{NEURIPS2020_2a27b814,
author = {Wu, Qiong and Wong, Felix MF and Li, Yanhua and Liu, Zhenming and Kanade, Varun},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {4103--4114},
publisher = {Curran Associates, Inc.},
title = {Adaptive Reduced Rank Regression},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/2a27b8144ac02f67687f76782a3b5d8f-Paper.pdf},
volume = {33},
year = {2020}
}