Sketching and stochastic gradient methods are arguably the most common tech- niques to derive efficient large-scale learning algorithms. In this paper, we investigate their application in the context of nonparametric st