Sample completion, Netflix Prize Competition and k-dependence

Add to your list(s) Download to your calendar using vCal

• Leonardo Coregliano (University of Chicago)
• Wednesday 14 January 2026, 14:45-15:30
• MR13, CMS.

If you have a question about this talk, please contact Julia Wolf.

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.

This talk is part of the Discrete Analysis Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Discrete Analysis Seminar
• Hanchen DaDaDash
• Interested Talks
• MR13, CMS
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.