which the Gaussian kernel is approximated in the primal by a randomized cosine map; we used logistic regression for the primal learning algorithm. We treated the bandwidth and number of cosines as hyperparameters to be optimized.

The relatively poor classification performance of RFF on Covertype has been noted before [@rahimi2007random], a result we reproduce here. Instead of using the randomized feature map directly, however, we can apply Algorithm \[alg:gem\] to the representation induced by RFF, which we denote GEM + RFF. This improves the classification error with only modest increase in computation cost, e.g., in MATLAB it takes 8 seconds to compute the randomized Fourier features, 58 seconds to (sequentially) solve the generalized eigenvalue problems and compute the GEM feature representation, and 372 seconds to optimize the logistic regression. The final error rate of 8.4% is a new record for this task.

         Method         Test Error Rate
  -------------------- -----------------
          GEM                12.9%
          RFF                12.7%
        deep GEM             9.8%
       GEM + RFF             8.4%
   RBF kernel (exact)        8.8%

  : Test error rates on Covertype. The RBF kernel result is from [@manik] where they also use a 90%-10% (but different) train-test split.[]{data-label="tab:covertyperes"}

TIMIT
-----

TIMIT is a corpus of phonemically and lexically annotated speech of English 