Blind Regression: Nonparametric Regression for Latent Variable Models via Collaborative Filtering
We introduce the framework of blind regression motivated by matrix completion for recommendation systems: given m users, n movies, and a subset of user-movie ratings, the goal is to predict the unobserved user-movie ratings given the data, i.e., to complete the partially observed matrix. Following the framework of nonparametric statistics, we posit that user u and movie i have features x 1 (u) and x 2 (i) respectively, and their corresponding rating y(u, i) is a noisy measurement of f (x 1 (u), x 2 (i)) for some unknown function f . In contrast with classical regression, the features x = (x 1 (u), x 2 (i)) are not observed, making it challenging to apply standard regression methods to predict the unobserved ratings. Inspired by the classical Taylor's expansion for differentiable functions, we provide a prediction algorithm that is consistent for all Lipschitz functions. In fact, the analysis through our framework naturally leads to a variant of collaborative filtering, shedding insight into the widespread success of collaborative filtering in practice. Assuming each entry is sampled independently with probability at least max(m −1+δ , n −1/2+δ ) with δ > 0, we prove that the expected fraction of our estimates with error greater than is less than γ 2 / 2 plus a polynomially decaying term, where γ 2 is the variance of the additive entry-wise noise term. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides principled improvements over basic collaborative filtering and is competitive with matrix factorization methods.
This paper motivates a method for blind regression, using a nonparametric model for collaborative filtering within the domain of matrix completion. Using some weak assumptions of regularity and smoothness, the paper proposes a model whereby observed entries of the matrix are noisy observations of the output of an unknown Lipschitz function on features relating to a user and an item. In contrast to previous work on collaborative filtering, this paper considers the case where the features on the users and items are themselves latent. Using a multiple Taylor expansions, the paper presents an algorithm and provides a finite same error bound. Intuitively, the bound stems from the accuracy of local Taylor approximations under small amounts of noise and then makes use of the variance between two rows or columns of the unknown matrix as a bound on the squared error. This variance is estimated empirically on the known points. After the discussion of the algorithm and its error bound, the paper extends this matrix completion method to tensor completion in a setting with equivalent assumptions for tensors. This is achieved by partitioning the tensor into two disjoint subsets and flattening in the tensor in each of those subsets to create the rows and columns of a new matrix which satisfies all of the assumptions needed for their earlier blind regression algorithm for matrices. The paper closes by providing some experiments performed on the MovieLens and Netflix datasets, where the algorithm is shown to give competitive results compared to other collaborative filtering and matrix completion methods.  
Explanation of ratings:  Technical Aspect: I thought this paper did a good job of motivating a different approach to user-user or item-item collaborative filtering. It is impressive that equivalent performance (empirically) is achievable with far fewer assumptions on the data, and this is definitely something for practitioners to consider in their research. While less is assumed in the model, less is explained however. A more detailed analysis of the algorithm may benefit this paper.   Novelty: This paper takes a very different, and non-restrictive approach to collaborative filtering and shows good results with it. By using successive Taylor approximations on their latent function, however, it seemed like the paper spent time motivating the idea of a latent function and latent variables but then assumed low noise and removed it from the model. In other words, all of the latency of this model appears to get wrapped into local approximations and then the model appears to proceed by working directly on the observed entries and ignoring the latent features and function entirely. I do think that this idea of weighting based on variance is novel as are the extensions to tensor completion and I would like to see more discussion of the later.   Potential Impact: This paper has the potential for impact by motivating the idea of completing a matrix using the variance as a weighting scheme for selecting representative users and columns. Future theoretical work may well stem from this idea.   Clarity: The paper was mostly clear. I appreciated the section intuitively motivating the algorithm. The section motivating the extension to tensors could be clearer, particularly in the decomposition of the tensor into disjoint sets. It is unclear to me how a matrix is formed from that and how this maps back to the original tensor after the matrix is “flattened.” Furthermore, the algorithm is not described as clearly as it could have been. I think that the steps of the algorithm are somewhat lost in their definition.  Suggestions for revision: Clarify your algorithm section. It is not immediately obvious what you are trying to learn, and how you go about doing so. I understand the goal is to make predictions on unknown entries, but it is not clear where the actual regression is happening. For instance, in the user-user or item-item case, is the regression simply a search problem to find the corresponding rows and columns with minimum variance and weight them accordingly?  Clarify where blind regression plays a role in this paper. It seems as though you motivate the concept of blind regression, but then show that it reduces to a weighting scheme on the variance of the difference between rows and columns.  If there is room, a brief mention of the intuition behind your theorem would be useful. This paper begins to address this in the last paragraph of section 5, but given the length of the full proof, some added intuition would be useful here.   In your abstract, you mentioned the algorithm shedding light on the success of collaborative filtering in practice. I am not sure that this question was fully answered. Perhaps you could add a couple of sentences in the intuition or contribution sections to more fully explain how your nearest-neighbor approach generalizes and explains the success of other, more restrictive models collaborative filtering.