Before revision:  We give a simple task-agnostic method for retaining the worst-case guarantees of randomized sketching, which yields time-optimal algorithms for LRA and least-squares regression . Also, for k-means clustering , we give a faster alternative for retaining worst-case guarantees.
After revision:  We give a simple task-agnostic method for retaining the worst-case guarantees of randomized sketching, which yields time-optimal algorithms for LRA and least-squares regression (LS), and k-means clustering , we give a faster alternative for retaining worst-case guarantees.