Sample completion, structured correlation, and Netflix problems
We develop a new high-dimensional statistical learning model which can take advantage of structured correlation in data even in the presence of randomness. We completely characterize learnability in this model in terms of VCN${}_{k,k}$-dimension (essentially $k$-dependence from Shelah's classification theory). This model suggests a theoretical explanation for the success of certain algorithms in the 2006~Netflix Prize competition.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Survey of Matrix Completion Algorithms
Matrix completion problem has been investigated under many different conditions since Netflix announced the Netflix Prize problem. Many research work has been done in the field once it has been discovered that many real …
compressed sensingMatrix CompletionSurveyMatrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
In this paper, we study the popularly dubbed matrix completion problem, where the task is to "fill in" the unobserved entries of a matrix from a small subset of observed entries, under the assumption that the underlying …
Matrix CompletionCollaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
We show that matrix completion with trace-norm regularization can be significantly hurt when entries of the matrix are sampled non-uniformly, but that a properly weighted version of the trace-norm regularizer works well …
Collaborative FilteringMatrix CompletionBayesian matrix completion: prior specification
Low-rank matrix estimation from incomplete measurements recently received increased attention due to the emergence of several challenging applications, such as recommender systems; see in particular the famous Netflix ch…
Matrix CompletionRecommendation SystemsMatrix Completion for Structured Observations
The need to predict or fill-in missing data, often referred to as matrix completion, is a common challenge in today's data-driven world. Previous strategies typically assume that no structural difference between observed…
Matrix Completion