Before revision:  Two recent independent works (Raghavendra-Yau, Bakshi-Kothari ( 2020) ) gave algorithms for this problem that work whenever \mathcal{D , however, is d^{\Omega(1/\alpha^4) and the error bounds on \|\Pi}  ]  - \Pi_*\|_F grow with r (which can be \Omega(d) ) . In this work, we improve on these results on all three fronts: dimension-independent error via a faster fixed-polynomial running time under less restrictive distributional assumptions.
After revision:  Two recent independent works (Raghavendra-Yau, Bakshi-Kothari ( 2020) ) gave algorithms for this problem that work whenever \mathcal{D , however, is d^{\Omega(1/\alpha^4) and the error bounds on \|\Pi} ] and logarithmically in BK) at the cost of quasi-polynomial running time) and rely on - \Pi_*\|_F grow with r (which can be \Omega(d) ) . In this work, we improve on these results on all three fronts: dimension-independent error via a faster fixed-polynomial running time under less restrictive distributional assumptions.