4a1590df1d5968d41b855005bb8b67bf-Paper.pdf

For regression, we obtain a running time of O(nd+(nL/µ) p snL/µ) where µ > 0 is the smallest eigenvalue ofA>A. This running time improves upon the previous best unaccelerated running time of O(nd + nLd/µ). This result expands the regimes where regression can be solved in nearly linear time from whenL/µ= O(1)towhenL/µ= O(d2/3/(sn)1/3).