Recommendations from Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization

• URL: http://arxiv.org/abs/2502.20033v1
• Date: Thu, 27 Feb 2025 12:17:34 GMT
• Title: Recommendations from Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization
• Authors: Suryanarayana Sankagiri, Jalal Etesami, Matthias Grossglauser,
• Abstract summary: 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.
• Score: 12.006706388840934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• AnyLoss: Transforming Classification Metrics into Loss Functions [21.34290540936501]
  evaluation metrics can be used to assess the performance of models in binary classification tasks. Most metrics are derived from a confusion matrix in a non-differentiable form, making it difficult to generate a differentiable loss function that could directly optimize them. We propose a general-purpose approach that transforms any confusion matrix-based metric into a loss function, textitAnyLoss, that is available in optimization processes.
  arXiv  Detail & Related papers  (2024-05-23T16:14:16Z)
• Data-driven Prior Learning for Bayesian Optimisation [5.199765487172328]
  We show that PLeBO and prior transfer find good inputs in fewer evaluations. We validate the learned priors and compare to a breadth of transfer learning approaches. We show that PLeBO and prior transfer find good inputs in fewer evaluations.
  arXiv  Detail & Related papers  (2023-11-24T18:37:52Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Learning by Sorting: Self-supervised Learning with Group Ordering Constraints [75.89238437237445]
  This paper proposes a new variation of the contrastive learning objective, Group Ordering Constraints (GroCo) It exploits the idea of sorting the distances of positive and negative pairs and computing the respective loss based on how many positive pairs have a larger distance than the negative pairs, and thus are not ordered correctly. We evaluate the proposed formulation on various self-supervised learning benchmarks and show that it not only leads to improved results compared to vanilla contrastive learning but also shows competitive performance to comparable methods in linear probing and outperforms current methods in k-NN performance.
  arXiv  Detail & Related papers  (2023-01-05T11:17:55Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• Relational Surrogate Loss Learning [41.61184221367546]
  This paper revisits the surrogate loss learning, where a deep neural network is employed to approximate the evaluation metrics. In this paper, we show that directly maintaining the relation of models between surrogate losses and metrics suffices. Our method is much easier to optimize and enjoys significant efficiency and performance gains.
  arXiv  Detail & Related papers  (2022-02-26T17:32:57Z)
• MIO : Mutual Information Optimization using Self-Supervised Binary Contrastive Learning [19.5917119072985]
  We model contrastive learning into a binary classification problem to predict if a pair is positive or not. The proposed method outperforms the state-of-the-art algorithms on benchmark datasets like STL-10, CIFAR-10, CIFAR-100.
  arXiv  Detail & Related papers  (2021-11-24T17:51:29Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  In rank aggregation problems, users exhibit various accuracy levels when comparing pairs of items. We propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons. We prove that our algorithm can return the true ranking of items with high probability.
  arXiv  Detail & Related papers  (2021-10-08T13:51:55Z)
• Task Affinity with Maximum Bipartite Matching in Few-Shot Learning [28.5184196829547]
  We propose an asymmetric affinity score for representing the complexity of utilizing the knowledge of one task for learning another one. In particular, using this score, we find relevant training data labels to the test data and leverage the discovered relevant data for episodically fine-tuning a few-shot model.
  arXiv  Detail & Related papers  (2021-10-05T23:15:55Z)
• Efficient Multidimensional Functional Data Analysis Using Marginal Product Basis Systems [2.4554686192257424]
  We propose a framework for learning continuous representations from a sample of multidimensional functional data. We show that the resulting estimation problem can be solved efficiently by the tensor decomposition. We conclude with a real data application in neuroimaging.
  arXiv  Detail & Related papers  (2021-07-30T16:02:15Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• Evaluating representations by the complexity of learning low-loss predictors [55.94170724668857]
  We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning a predictor on top of the representation that achieves low loss on a task of interest.
  arXiv  Detail & Related papers  (2020-09-15T22:06:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.