Exact Worst-Case Certificates for Cold-Start Recommendations

A new user's recommendations are decided by a handful of interactions: the first five or ten clicks or ratings. That makes cold-start users the easiest people for an adversary to steer. One injected click or a manipulated onboarding screen can redraw their entire top-K list. Nobody currently knows how fragile these early recommendations really are, because the attacks people try only give lower bounds on the damage. This proposal shows that cold start is also where exact worst-case analysis becomes tractable.

The tool is the Karush–Kuhn–Tucker (KKT) bilevel reduction. A "bilevel" problem is one where an outer optimizer, here the attacker, acts against an inner optimizer, here the recommender fitting a new user's preference vector. The reduction replaces the inner training problem with its optimality equations and turns the whole attack into one mixed-integer linear program (MILP) that a solver handles exactly. Such exact reductions have been dismissed for recommendation because they blow up on large problems. The observation here is that a cold user's inner problem is tiny: a vector of a few dozen dimensions, fit on a few dozen interactions. The exact reduction fits the cold-start regime even though it fails for warm collaborative filtering.

Core Claim

Many cold-start recommenders fit the new user with a convex inner problem: item representations are frozen and only the user's vector, or a final linear layer, is adapted on the support set (the user's few observed interactions). For any such recommender, we can compute an exact certificate: the minimum number of injected or flipped support interactions needed to push a target item into, or a current item out of, the user's top-K. The certificate comes from a MILP whose binary variables scale with the support size and the attack budget, not with the number of users or items in the training data.

We expect three things to follow. Certified stability of cold-user recommendations will be far lower than random-noise robustness suggests. Gradient-based attacks will leave a measurable gap below the true worst case. And the certificates will rank cold-start methods differently than accuracy does.

Where This Sits

The method comes directly from Exact Certification of (Graph) Neural Networks Against Label Poisoning. That work treats graph neural network training as a support vector machine through the neural tangent kernel, replaces that training with its KKT conditions, and linearizes the complementarity conditions with Big-M binaries to certify against label poisoning. Big-M is a standard trick that encodes "either this constraint is tight or its multiplier is zero" with one binary variable and a large constant. The authors report that collective certificates prove over 40% of nodes robust on Cora-MLb at a 0.2 perturbation budget. They also acknowledge that branch-and-bound stops scaling beyond graphs of a few thousand nodes.

That limitation is what makes the transfer worthwhile. Their inner problem grows with the whole training graph, while ours grows only with one user's support set. The older attack-synthesis formulation in Using Machine Teaching to Identify Optimal Training-Set Attacks on Machine Learners likewise substitutes KKT conditions for the learner. It targets generic learners, not the per-user structure of recommendation.

The cold-start side supplies both the threat and the models. MeLU treats each user as a few-shot task and adapts decision layers with gradient steps on the support set. It also picks onboarding items by the gradient norm they induce, which is effectively an admission that a few items dominate the adapted model. MAMO adds memory modules that personalize the starting point for each user and improves on MeLU accordingly. DropoutNet trains a content tower by dropping collaborative inputs, so cold items and users are scored from content alone. None of these works asks how stable the output is to adversarial changes in the few interactions it rests on.

The first-order bilevel methods constrain the design rather than supply it. BOME and the inversion-free penalty method solve non-convex bilevel problems approximately, which is fine for training. For certification, an approximate inner solution voids the guarantee. So we deliberately restrict to convex inner adaptation and treat the non-convex case as an explicit limitation, not something to paper over.

Research Program

The inner problem for a cold user $u$ fits a user vector $w \in \mathbb{R}^d$ against frozen item embeddings $v_j$. These embeddings come from a DropoutNet-style content tower or from MeLU's or MAMO's representation layers with only the final linear head adapted. The fit uses a pairwise hinge loss with a prior centered at a content-predicted vector $w_0$:

$$ \min_{w,\ \xi \ge 0}\ \tfrac{\lambda}{2}\|w - w_0\|^2 + \sum_{(i,j) \in P} \xi_{ij} \quad \text{s.t.}\quad w^\top (v_i - v_j) \ge 1 - \xi_{ij}. $$

Here $P$ is the set of (interacted item, sampled non-interacted item) pairs from the support set, $\xi_{ij}$ are slack variables, and $\lambda$ sets how strongly the content prior is trusted. A squared-error variant handles explicit ratings on MovieLens and Book-Crossing.

The attacker's choices enter as binaries. Variable $a_j \in \{0,1\}$ means "inject item $j$ as a positive", drawn from a candidate pool $C$. Variable $f_i$ means "flip support label $i$". Both are capped by a budget $b$.

The inner problem is then replaced by its KKT conditions. Products of binaries and continuous variables are linearized with McCormick envelopes, a standard way to rewrite such products as linear inequalities when bounds are known. Complementarity is linearized with Big-M. The top-K event is encoded as linear constraints on the scores $w^\top v_j$. Minimizing the number of active attack binaries subject to a flipped top-K event gives the certificate. Infeasibility at budget $b$ proves robustness.

The engineering work is to make this solvable when the candidate pool is a full catalogue: about 3,700 movies in MovieLens 1M, about 17,000 articles in CiteULike. Four ingredients go into this. The first is tight Big-M constants derived from the bounded embedding norms. The second is bound propagation that prunes candidates which cannot change any relevant score margin by enough. The third is an incremental scheme that solves first over a small pool of candidates ranked by their effect on the score margin, then grows the pool until the MILP proves no excluded candidate can matter. The fourth is warm starts from the gradient attack.

The output for each user is either an exact minimum budget or, when the solver times out, a valid interval with a lower bound from the MILP relaxation and an upper bound from the best attack found. Intervals are reported as intervals.

A secondary use of the same program is to compute worst-case onboarding. The question is which $k$ items, if the user had been shown them, would most change the adapted recommendations. This turns MeLU's gradient-norm heuristic into an exact quantity we can compare against.

Baselines

The naive reference point measures robustness by injecting $b$ random positives, or random popular positives, into each cold user's support set and counting how often top-K changes. This is what a practitioner would do without our tool. We expect it to overstate robustness substantially. Our certificates beat it if the certified-robust fraction is clearly below the random-injection robust fraction at equal $b$.

The strongest existing competitor for finding the worst case is a gradient-based injection attack. It relaxes the attack binaries to $[0,1]$, differentiates the top-K score margin through the inner solution, and rounds the result greedily. On a convex inner problem this differentiation is exact, so the attack is strong. It gets the same per-user wall-clock budget as the MILP, with random restarts filling that budget. The MILP "beats" it when it finds strictly smaller successful budgets on a meaningful share of users, or proves that the attack's budget is in fact minimal. No reported result was found on Lacuna for adversarial or certified robustness of cold-start recommenders, so these numbers will be new.

On correctness, exhaustive enumeration with re-solving of the convex inner problem is exact whenever it is affordable, for example label flips with $k \le 15$ and $b \le 3$. It serves as ground truth that our MILP must reproduce exactly.

Certificates on a toy model would be uninteresting, so the certified models must also be competitive cold-start recommenders. On MovieLens 1M cold-user/cold-item, MAMO reports MAE 0.8894 against MeLU's 0.9299. We will train the convex-head variants under the identical MeLU/MAMO splits. We target clean MAE within the MeLU-to-MAMO range, and we will state honestly if we fall outside it. On CiteULike, DropoutNet reports a 6% recall@100 gain over DeepMusic, but the file gives no absolute value, so we will rerun DropoutNet ourselves.

The ablation that isolates the key ingredient keeps the model fixed and swaps the exact KKT reduction for a relaxed version. The relaxed version drops complementarity binaries and uses the LP relaxation only. This shows how much of the certificate's tightness comes from encoding the inner optimality exactly.

Why not just…?

Why not just run a strong gradient attack and report its success rate? An attack shows that a user can be steered with $b$ clicks. It can never show that a user cannot be steered with $b-1$, so it cannot certify. Hinge losses also make the inner solution piecewise-linear in the attack, so gradients through the relaxed attack carry no information inside flat regions and change abruptly at boundaries. That is exactly where rounding fails. The experiments measure the attack-versus-exact gap per user. If that gap turns out to be negligible, that is itself a useful finding: it would license cheap attacks as proxies, and we would report it as such.

Why not just enumerate attacks, since cold users have so few interactions? This is a real threat for label flips. With small support sets and budgets, enumeration is exact and cheap, so we use it as ground truth rather than claim to beat it. It does not survive injection from the catalogue. Choosing 3 of roughly 3,700 movies already means billions of inner solves, and CiteULike is larger still. The scaling experiment, which plots solve time against $b$ and catalogue size for both methods, settles where the crossover lies.

Why not just train robustly with dropout or memory and skip certification? DropoutNet-style input dropout and MAMO-style personalized priors may well make cold users more stable. Pulling the adapted vector toward a content prior should damp the influence of each click. But this is a hypothesis that needs measuring, not an alternative to measuring. Our certificates are the instrument that tests it: we compare certified-robust fractions across MeLU-head, MAMO-head and DropoutNet-tower models, and across values of the prior strength $\lambda$.

Why not use first-order bilevel solvers instead of a MILP? BOME and the penalty method scale to non-convex inner problems. They return approximate stationary points, so they amount to better attacks, not certificates. We include BOME as a second attack baseline, but it cannot replace the exact reduction.

Proposed Experiments

Experiments use the MovieLens 1M and Book-Crossing cold-user and cold-item splits used by MeLU and MAMO, plus CiteULike user and item cold start from DropoutNet. The XING RecSys 2017 data serves only as a scalability stress test with sampled candidate pools.

For each model and budget $b \in \{1,\dots,5\}$, we report four quantities. The first is the certified-robust fraction of cold users for top-1, top-10 and target-item promotion. The second is the fraction where the MILP proves the gradient attack suboptimal. The third is the median solve time and timeout rate as functions of support size, embedding dimension and catalogue size. The fourth is clean MAE or recall.

Three checks decide whether the program succeeds. The MILP must match enumeration exactly wherever enumeration runs. It must finish on most MovieLens 1M cold users with full-catalogue injection within minutes per user. And certified robustness must differ meaningfully from both random-injection robustness and attack-based estimates. If the third check fails everywhere, the honest conclusion is that cheap attacks suffice for cold-start auditing. That would still be a result the field lacks.

The main risk is solver time on the 17,000-item CiteULike catalogue. The incremental candidate pool is our mitigation, and timeouts are reported as intervals rather than hidden.