Appendix 1 Interpretation using rank-1 Nyström approximation

The bound in Equation 5 of the main paper can be interpreted using a rank-1 Nyström approximation for f(xt,xt). By holding w fixed and maximizing for q in the right hand side of Equation 5, we get q = f(w,w) P t ytf(xt,w) where f(w,w) indicates the pseudo-inverse.1 Typically the weight vector w, often called a "landmark", used in the Nyström approximation is set either by setting it to a random input or by more sophisticated schemes like setting it with KMeans. In our case, we are directly optimizing the landmarks via Equation 6 in the main paper. To our knowledge the only other work to do this was performed in Fu [2014]. The code used in the main training loop of our algorithm is shown in Figure 1.