Sample completion, structured correlation, and Netflix problems

2025/09/23 by Coregliano, Leonardo N., Malliaris, Maryanthe · 2 citations
#60F15 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Primary: 68Q32. Secondary: 68T05 #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2509.20404

Abstract

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.

Cited by

• Remarks on a recent preprint of Chernikov and Towsner
• Higher-arity PAC learning, VC dimension and packing lemma

Related

• On Universal Features for High-Dimensional Learning and Inference
• A Combinatorial Characterization of Supervised Online Learnability
• Discovering Structure in High-Dimensional Data Through Correlation Explanation
• Statistical Learning of Arbitrary Computable Classifiers
• Perspective: A Phase Diagram for Deep Learning unifying Jamming, Feature Learning and Lazy Training