{"ID":2867375,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.20404","arxiv_id":"2509.20404","title":"Sample completion, structured correlation, and Netflix problems","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.","short_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 mod...","url_abs":"https://arxiv.org/abs/2509.20404","url_pdf":"https://arxiv.org/pdf/2509.20404v1","authors":"[\"Leonardo N. Coregliano\",\"Maryanthe Malliaris\"]","published":"2025-09-23T20:06:04Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\",\"math.LO\",\"math.ST\"]","methods":"[]","has_code":false}