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{dimension-independent 1/ \alpha^2), where hides polylogarithmic factors in 1/ \alpha .