of representations and models that lead to good performance are well-known. In text classification, for example, unigram and bigram features together with linear classifiers are known to work well for a variety of related tasks [@halevy2009unreasonable]. For other problems, such as drug design, speech, and image recognition, far less is known about which combinations are effective. This has fueled interest in methods that can learn the appropriate representations directly from the raw signal, with techniques such as dictionary learning [@mairal2008supervised] and deep learning [@krizhevsky2012imagenet; @hinton2012deep] achieving state of the art performance in many important problems.

In this work, we explore conceptually and computationally simple ways to create discriminative features that can scale to a large number of examples, even when data is distributed across many machines. Our techniques are not a panacea. They are exploiting simple second order structure in the data and it is very easy to come up with sufficient conditions under which they will not give any advantage over learning using the raw signal. Nevertheless, they empirically work remarkably well.

Our setup is the usual multiclass setting where we are given labeled data $\{x_i,y_i\}_{i=1}^n$, sampled iid from a distribution ${\mathcal{D}}$ on ${\mathbb{R}}^d \times [k]$, and we need 