Timezone: »
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.
Author Information
Qiong Wu (College of William and Mary)
Felix MF Wong (Google)
Yanhua Li ("Worcester Polytechnic Institute, USA")
Zhenming Liu (William and Mary)
Varun Kanade (University of Oxford)
More from the Same Authors
-
2021 Poster: SBO-RNN: Reformulating Recurrent Neural Networks via Stochastic Bilevel Optimization »
Ziming Zhang · Yun Yue · Guojun Wu · Yanhua Li · Haichong Zhang -
2020 Poster: f-GAIL: Learning f-Divergence for Generative Adversarial Imitation Learning »
Xin Zhang · Yanhua Li · Ziming Zhang · Zhi-Li Zhang -
2019 Poster: Implicit Regularization for Optimal Sparse Recovery »
Tomas Vaskevicius · Varun Kanade · Patrick Rebeschini -
2019 Poster: Decentralized Cooperative Stochastic Bandits »
David Martínez-Rubio · Varun Kanade · Patrick Rebeschini -
2019 Poster: On the Hardness of Robust Classification »
Pascale Gourdeau · Varun Kanade · Marta Kwiatkowska · James Worrell -
2019 Spotlight: On the Hardness of Robust Classification »
Pascale Gourdeau · Varun Kanade · Marta Kwiatkowska · James Worrell -
2017 Poster: From which world is your graph »
Cheng Li · Felix MF Wong · Zhenming Liu · Varun Kanade