The cold-start problem

Why the failure is structural#

In a pure collaborative model the item representation is a free parameter $\mathbf{q}_i \in \mathbb{R}^k$ estimated only from observations involving $i$. For a new item, ${(u,i) \in \mathcal{K}} = \varnothing$, so the objective is independent of $\mathbf{q}_i$ and the regularised solution is $\mathbf{q}_i = \mathbf{0}$. The score $\mathbf{p}_u^\top \mathbf{q}_i$ is then identically zero for every user.

The item is not badly ranked. It is unidentifiable. No amount of optimisation changes that, because the gradient with respect to $\mathbf{q}_i$ has no data flowing into it.

The fix is to make the representation a function of features rather than a free parameter:

$$ \mathbf{q}i = g\theta(\mathbf{c}_i) $$

Where $\mathbf{c}i$ are content features (text, category, image, price, creator) and $g\theta$ is shared across all items. Now a new item inherits $\theta$, which was estimated from the whole catalogue, and gets a usable vector from features alone. This is the single most important structural idea in cold-start work, and it is why two-tower models with content features are the default answer today.

Approaches, with their trade-offs#

Feature-based factorisation. Factorisation Machines (Rendle, 2010) put user, item and side features into one model with pairwise interactions, so a cold item is represented by its feature interactions. Cost: the feature engineering is now the model.

Hybrid with a learned gate. Train both a collaborative and a content model, and learn a mixing weight conditioned on interaction count. Cost: two models to maintain, and the gate needs its own validation.

DropoutNet (Volkovs, Yu and Poutanen, 2017) trains a network that consumes both collaborative and content input, and randomly zeroes the collaborative half during training. The model is therefore forced to perform when the preference input is missing, which is exactly the cold condition. The elegance is that no separate cold model exists — the warm model degrades gracefully by construction.

Meta-learning. MeLU (Lee et al., 2019) frames per-user adaptation as MAML: learn an initialisation from which a few gradient steps on a handful of interactions produce a good user model. Cost: substantially more complex training, and the reported gains are sensitive to the evaluation protocol.

Explicit exploration. Treat the new item as an arm of a bandit and allocate impressions to reduce uncertainty about its value. LinUCB (Li et al., 2010) does this with a linear reward model over context features and a confidence bound, and was evaluated on Yahoo front-page news, which is a maximally cold domain.

The cost of exploration, quantified#

Exploration is not free, and the trade is explicit. For a contextual bandit over $T$ rounds with $d$-dimensional context, LinUCB-style algorithms achieve regret

$$ R(T) = O!\left( d \sqrt{T \log T} \right) $$

Where $R(T)$ is the difference in cumulative reward between the algorithm and an oracle that always picks the best arm. Regret growing as $\sqrt{T}$ means average per-round loss decays like $1/\sqrt{T}$ — exploration cost is real, bounded, and amortises.

The awkward part in recommendation is that the "arms" are items, $|I|$ is enormous, and item value is non-stationary. Practical deployments therefore explore over item clusters or over a small reserved traffic slice rather than over the raw catalogue.

Measure the right things#

Accuracy metrics computed on logged data are blind to cold start, because a cold item appears in nobody's held-out set. Report alongside them:

• Catalogue coverage — the fraction of items appearing in any user's top-$N$.
• Cold-item exposure — impressions to items with age below some threshold, as a share of total impressions.
• Time-to-first-impression — the distribution of the delay between an item entering the catalogue and its first serve. A long tail here is a supply-side fairness problem.
• Gini coefficient over item exposure — inequality of attention, discussed in diversity and filter bubbles.

Papers#

• Schein et al. (2002), Methods and Metrics for Cold-Start Recommendations, SIGIR — the paper that named and framed the problem.
• Rendle (2010), Factorization Machines, ICDM.
• Li et al. (2010), A Contextual-Bandit Approach to Personalized News Article Recommendation (LinUCB), WWW — arxiv.org/abs/1003.0146
• Van den Oord, Dieleman and Schrauwen (2013), Deep content-based music recommendation, NIPS.
• Volkovs, Yu and Poutanen (2017), DropoutNet: Addressing Cold Start in Recommender Systems, NeurIPS.
• Lee et al. (2019), MeLU: Meta-Learned User Preference Estimator for Cold-Start Recommendation, KDD — arxiv.org/abs/1908.00413

What to learn next#

• Two-tower retrieval models — feature-conditioned item towers as the standard fix.
• Hybrid recommenders — combination strategies and their formal taxonomy.
• Diversity and filter bubbles — exposure inequality, measured.