In the Netflix Prize Competition (2006-2009), we are given a finite set U of users, a finite set M of movies and a partial
function f: U x M ⇀ R, where f(u,m) indicates how user u rates movie m and we are tasked with
completing f to a total function to predict how all users U rate all movies in M. Although some algorithms did fairly well
in the competition, giving a satisfactory theoretical explanation for their success has been difficult.

In this second talk of
the series on high-arity learning frameworks, I will discuss how the Netflix Prize Competition can be seen as an instance of a
high-arity learning framework called "sample completion learning". I will also discuss how sample completion learning is
completely characterized by the model-theoretic notion of k-dependence introduced by Shelah (which can be seen as a
high-dimensional version of the Vapnik--Chervonenkis dimension). In turn, this gives a full theoretical characterization of when
the Netflix problem is "solvable".

No background in learning theory or model theory is required for this talk.

This talk is based on joint work with Maryanthe Malliaris.