Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908493802373120 |
|---|---|
| author | Sankagiri, Suryanarayana Etesami, Jalal Grossglauser, Matthias |
| author_facet | Sankagiri, Suryanarayana Etesami, Jalal Grossglauser, Matthias |
| contents | This paper provides a theoretical analysis of a new learning problem for recommender systems where users provide feedback by comparing pairs of items instead of rating them individually. We assume that comparisons stem from latent user and item features, which reduces the task of predicting preferences to learning these features from comparison data. Similar to the classical matrix factorization problem, the main challenge in this learning task is that the resulting loss function is nonconvex. Our analysis shows that the loss function exhibits (restricted) strong convexity near the true solution, which ensures gradient-based methods converge exponentially, given an appropriate warm start. Importantly, this result holds in a sparse data regime, where each user compares only a few pairs of items. Our main technical contribution is to extend certain concentration inequalities commonly used in matrix completion to our model. Our work demonstrates that learning personalized recommendations from comparison data is computationally and statistically efficient. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20033 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization Sankagiri, Suryanarayana Etesami, Jalal Grossglauser, Matthias Machine Learning This paper provides a theoretical analysis of a new learning problem for recommender systems where users provide feedback by comparing pairs of items instead of rating them individually. We assume that comparisons stem from latent user and item features, which reduces the task of predicting preferences to learning these features from comparison data. Similar to the classical matrix factorization problem, the main challenge in this learning task is that the resulting loss function is nonconvex. Our analysis shows that the loss function exhibits (restricted) strong convexity near the true solution, which ensures gradient-based methods converge exponentially, given an appropriate warm start. Importantly, this result holds in a sparse data regime, where each user compares only a few pairs of items. Our main technical contribution is to extend certain concentration inequalities commonly used in matrix completion to our model. Our work demonstrates that learning personalized recommendations from comparison data is computationally and statistically efficient. |
| title | Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.20033 |