PaperlayerView exact revision on arXiv

Source-linked AI summary

A Generic Coordinate Descent Framework for Learning from Implicit Feedback

Immanuel Bayer, Xiangnan He, Bhargav Kanagal, Steffen Rendle

arXiv:1611.04666v1cs.IRcs.LG

TL;DR

Implicit-feedback recommendation is computationally difficult because standard learning methods scale with the many non-consumed context-item pairs, while efficient coordinate descent was limited mainly to simple models. The paper introduces k-separability and the iCD framework to derive efficient coordinate-descent solvers for complex recommender models. The framework supports several factorization families and yields substantial computational savings in the reported experiments.

  • Problem

    Implicit learning is computationally expensive because training includes observed actions contrasted with all non-observed actions, while efficient coordinate descent was not established for complex recommender models.

  • Method

    The paper reformulates implicit learning using an implicit regularizer and introduces k-separability and iCD to derive efficient coordinate-descent algorithms for k-separable models.

  • Results

    The framework provides efficient algorithms for matrix factorization, factorization machines, PARAFAC, and Tucker decomposition, while FM experiments report a 2x improvement in cold-start recommendation and four orders of magnitude lower cost than conventional CD.

  • Takeaways & Limitations

    The framework gives researchers and practitioners a practical alternative to BPR by enabling coordinate descent for complex models and avoiding explicit iteration over all non-consumed items.

  • Takeaways & Limitations

    For Tucker decomposition, gradients for φ are non-zero for every factor index, so its nested factor loops cannot be further improved, although ψ remains sparse.

Abstract

from arXiv · show

In recent years, interest in recommender research has shifted from explicit feedback towards implicit feedback data. A diversity of complex models has been proposed for a wide variety of applications. Despite this, learning from implicit feedback is still computationally challenging. So far, most work relies on stochastic gradient descent (SGD) solvers which are easy to derive, but in practice challenging to apply, especially for tasks with many items. For the simple matrix factorization model, an efficient coordinate descent (CD) solver has been previously proposed. However, efficient CD approaches have not been derived for more complex models. In this paper, we provide a new framework for deriving efficient CD algorithms for complex recommender models. We identify and introduce the property of k-separable models. We show that k-separability is a sufficient property to allow efficient optimization of implicit recommender problems with CD. We illustrate this framework on a variety of state-of-the-art models including factorization machines and Tucker decomposition. To summarize, our work provides the theory and building blocks to derive efficient implicit CD algorithms for complex recommender models.

1. INTRODUCTION

Recommender research has shifted toward implicit feedback, but efficient learning for complex models remains unresolved. The paper introduces k-separability and iCD as a framework for deriving efficient coordinate-descent solvers across several model families.

  • Implicit feedback is cheaper and more abundant than explicit ratings, but learning requires contrasting observed actions with all non-observed actions.
  • SGD provides a general optimization framework, whereas coordinate descent had been available only for a few simple models.
  • The paper identifies k-separability as a sufficient condition for efficient learning from implicit feedback with coordinate descent.
  • The proposed iCD framework provides a general procedure for deriving efficient implicit coordinate-descent algorithms.
  • The framework is applied to matrix factorization, side-information variants, factorization machines, PARAFAC, and Tucker decomposition.

2. RELATED WORK

Related work contrasts BPR’s sampling-based SGD approach with coordinate descent for implicit feedback. The paper extends efficient coordinate descent beyond matrix factorization to complex models while retaining optimization over non-consumed items without explicit iteration.

  • BPR uses pairwise SGD for ranking, while CD uses an elementwise loss over consumed and non-consumed items.
  • Figure 1 contrasts explicit ratings with implicit watch, purchase, or click counts over all context-item pairs.
  • BPR addresses many training examples by sampling negative items, but large item sets can cause convergence problems and require nonuniform sampling.
  • The proposed framework enables coordinate descent for complex factorization models and optimizes non-consumed items without explicitly iterating over them.

3. PROBLEM STATEMENT

The problem is to optimize recommender scores over implicit data whose training set includes observed feedback and all non-consumed context-item pairs. Standard coordinate descent becomes infeasible because its runtime scales linearly with this data size, motivating efficient reformulations.

  • 3.1 Recommender Model: A recommender model assigns a score to every context-item pair and is learned by choosing parameters that minimize a loss over observed feedback.
  • 3.2 Coordinate Descent Algorithm: Coordinate descent updates one model parameter at a time using the first and second derivatives of the loss, followed by a Newton step.
  • 3.2 Coordinate Descent Algorithm: For multilinear models, a full step η = 1 can be chosen without risking divergence; all models in Section 5 have this property.
  • 3.2 Coordinate Descent Algorithm: Standard coordinate descent is typically linear in training-example complexity and embedding dimension, making it infeasible for implicit problems.
  • 3.3 Learning from Implicit Feedback: Implicit training includes observed feedback and non-consumed tuples, whose count is typically |C||I| rather than the much smaller observed set.
  • 3.3 Learning from Implicit Feedback: Applying standard algorithms directly to implicit data is infeasible because their runtime is linear in |S_impl| = |C||I|.

4. GENERIC COORDINATE DESCENT ALGORITHM FOR IMPLICIT FEEDBACK

The framework reformulates implicit learning around an implicit regularizer, then exploits k-separability to compute context and item contributions independently for efficient coordinate descent.

  • 4.1 Implicit Regularizer: Implicit feedback creates O(|C||I|) training examples, making the general computational complexity O(|C||I|).The implicit set includes context-item pairs absent from the positive set.
  • 4.1 Implicit Regularizer: Implicit learning can be rewritten as learning on a small positive set plus minimizing the scoring function over every context-item pair.This reformulation preserves the optimum after rescaling and collapsing corresponding examples.
  • 4.1 Implicit Regularizer: The resulting implicit regularizer penalizes non-zero predictions rather than non-zero parameters, making it less restrictive than L2.It can be interpreted as an implicit bias toward predicting zeros.
  • 4.2 iCD Algorithm for k-separable Models: A k-separable model partitions context and item parameters into disjoint components that form a separable model representation.The framework applies to models that can be rewritten using context-side φ and item-side ψ functions.
  • 4.2 iCD Algorithm for k-separable Models: Independent context and item computation reduces complexity from O(|C||I|) to O((|C| + |I|) k2).The decomposition supports efficient computation of the implicit regularizer and its coordinate-wise derivatives.
  • 4.2 iCD Algorithm for k-separable Models: The iCD derivation rewrites the model as φ and ψ, derives first and second parameter derivatives, and applies Newton coordinate updates.The generic algorithm alternates updates over context and item parameters, recomputing model quantities when necessary until convergence.

5. APPLICATIONS

The section applies the implicit coordinate-descent framework to matrix factorization, feature-based models, factorization machines, and tensor factorization. These applications exploit model-specific separability and sparsity to obtain efficient learning procedures with stated runtime bounds.

  • Applications: The framework applies to feature-based factorization and tensor factorization models, providing a guide for deriving implicit CD algorithms.The paper presents applications to powerful, frequently used model classes and states that the algorithms can be directly applied to many recommender tasks.
  • 5.1 Matrix Factorization (MF): Matrix factorization is k-separable, enabling coordinate traversal by embedding dimension and full Newton steps because the model is bilinear.The MF procedure alternates over embedding dimensions and updates context and item parameters symmetrically.
  • 5.1 Matrix Factorization (MF): O((|I| + |C|) k2 + |S| k) per iteration is the stated complexity for implicit CD on matrix factorization.The bound combines implicit-regularizer computation over items and contexts with explicit-loss computation over observed feedback.
  • 5.2 Feature-Based Factorization Models: Feature-based models assign embeddings to context and item features, extending matrix factorization to attributes, context variables, and sequential representations.The model assumes feature vectors xc and zi for contexts and items, with corresponding feature embeddings.
  • 5.2 Feature-Based Factorization Models: This work provides an implicit CD algorithm for general feature-based models, whereas prior learning was restricted to BPR.Sparse gradients enable efficient computation, with one epoch over all variables requiring O(k2 (NZ(X)+ NZ(Z))) for the implicit regularizer.
  • 5.2.2 Factorization Machines: Factorization machines use (k + 2)-separability, and their sparse-gradient runtime analysis is the same as for matrix factorization with side information.FM combines global and feature biases with interactions among variables represented by context and item feature vectors.
  • 5.3 Tensor Factorization: Tensor factorization represents multiple categorical variables as tensor modes; PARAFAC uses one factor matrix per mode and supports sparse or dense context.For PARAFAC, the implicit-regularizer runtime is O((|C| + |I|) k2) for sparse context and O((|C1| + |C2| + |I|) k2) for dense context.
  • 5.3.2 Tucker Decomposition: Tucker decomposition introduces a core tensor and is more expensive to evaluate, requiring O(k1 k2 k3) operations per data point.Unlike the other presented models, its context-side gradients are non-zero for every factor index, limiting further nested-loop optimization.

6. EXPERIMENTS

The experiments demonstrate iCD’s versatility across cold-start, offline, and instant recommendation, including complex factorization-machine feature configurations. They also show that iCD retains a major computational advantage over conventional coordinate descent.

  • Experimental setup: The evaluation uses 200,000 YouTube users, 68,000 videos, and side information across cold-start, offline, and instant recommendation tasks.Results report recall and NDCG for the top 100 videos as relative improvements over Popularity.
  • Cold-Start Recommendation: Attribute-aware FM achieves a 2x improvement over the baselines in cold-start recommendation.Users’ age, gender, country, and device information are used as context features; MF and Coview do no better than Popularity in this setting.
  • Offline Recommendation: The offline recommendation study compares FM variants using attributes, the previously watched video, and user id, with all-feature FM achieving the best quality.The compared configurations include iCD-FM A, iCD-FM P, and iCD-FM A+P+U.
  • Instant Recommendation: The instant recommendation study finds that the FM combining attributes, previously watched videos, and all watched videos achieves the best quality.The tested configurations include A, P, H, and A+P+H; sequence-based features support personalization from recent feedback.
  • Computational costs: Four orders of magnitude higher computational costs are observed for conventional CD than for iCD across all three context choices.Figure 8 compares log-scale training costs for an FM on a dataset with approximately 70k items, relative to iCD-FM P.

7. CONCLUSION

The paper presents a general framework for efficient coordinate-descent learning from implicit feedback. It introduces k-separability, shows that it enables efficient optimization for several factorization models, and positions iCD as a blueprint for broader model classes.

  • Conclusion: The framework reformulates implicit-feedback learning around an efficient computation of the implicit regularizer.It avoids iterating over all context-item pairs for k-separable models.
  • Conclusion: k-separability is sufficient for efficient implicit coordinate descent, and it applies to matrix factorization, factorization machines, and tensor factorization.The paper provides efficient learning algorithms for these model families.
  • Conclusion: iCD is intended as a general blueprint for deriving efficient learning algorithms beyond the models discussed in the paper.The conclusion describes the framework as not limited to the demonstrated model classes.
Loading 1611.04666v1…