Correlated random features for fast semi-supervised learning
This paper presents Correlated Nyström Views (XNV), a fast semi-supervised algorithm for regression and classification. The algorithm draws on two main ideas. First, it generates two views consisting of computationally inexpensive random features. Second, multiview regression, using Canonical Correlation Analysis (CCA) on unlabeled data, biases the regression towards useful features. It has been shown that CCA regression can substantially reduce variance with a minimal increase in bias if the views contains accurate estimators. Recent theoretical and empirical work shows that regression with random features closely approximates kernel regression, implying that the accuracy requirement holds for random views. We show that XNV consistently outperforms a state-of-the-art algorithm for semi-supervised learning: substantially improving predictive performance and reducing the variability of performance on a wide variety of real-world datasets, whilst also reducing runtime by orders of magnitude.
Summary: This paper brings together two recently 
      popular trends of research, namely random features and multiview 
      regression. It provides a two step algorithm for semi-supervised learning. 
      In the first stage, they generate random features corresponding to two 
      views using the Nystrom method and then in the second stage, they use CCA 
      to bias the optimization towards features correlated across the views via 
      the canonical norm which penalizes less correlated features across the two 
      views more. The experimental results show the superior performance of 
      their approach over a state-of-the-art competitor Laplacian Regularized 
      Least Squares (SSSL) Comments: The paper is well 
      motivated and addresses an important problem. The paper operationalizes 
      the ideas proposed in (Kakade and Foster 2007) and presents a Nystrom 
      method to generate two sets of views which follow the multiview assumption 
      (also detailed in (Kakade and Foster 2007)). In short, the paper 
      harnesses the CCA results from (Kakade and Foster 2007) and Nystrom Method 
      results from (Bach 2013) to come up with an efficient and scalable semi 
      supervised learning algorithm. That said, I found the paper to 
      have limited mathematical novelty for a venue like NIPS and is mostly an 
      engineering paper. The authors could have considered joint 
      learning of the random features and CCA bases, which would have been more 
      novel and could possibly lead to better error bounds than the two methods 
      separately. The experimental results are detailed and the proposed 
      approach (XNV) significantly beats SSSL. The authors should 
      consider adding an additional tuning parameter (\lambda) for the canonical 
      norm in Algorithm 1 (9), which can hopefully improve accuracy further as I 
      can see the term to be on a different scale than the other two terms in 
      the objective.