Before revision:  The running time of both these algorithms, however, is d^{\Omega(1/\alpha^4)} and the error bounds on } \|\Pi-\Pi_*\|_F ^2 = \kappa^4 \log (r ) (\emph{  1/ \alpha^2), where hides polylogarithmic factors in 1/ \alpha .
After revision:  The running time of both these algorithms, however, is d^{\Omega(1/\alpha^4)} and the error bounds on } \|\Pi-\Pi_*\|_F ^2 = \kappa^4 \log (r ) (\emph{ error via a faster fixed-polynomial running time under less restrictive distributional assumptions. Specifically, we give a poly( 1/ \alpha^2), where hides polylogarithmic factors in 1/ \alpha .