CTR in Lago Atitlan, Guatemala [Photo: Sria Louis]

From Click to Conversion, Part 4: Yoshikawa & Imai (2018) [AdTech]

About this series

From Click to Conversion is a series on the ML foundations behind conversion prediction and autobidding in adtech.

Like the rest of the series, this post is my way of learning the topic — written slowly, in collaboration with AI and many editorial rounds. Specifically: I didn’t dig deep into L-BFGS. It’s just the optimizer, no offense. So treat that bit as a high-level sketch. Corrections welcome.

• Part 1 — the exponential distribution and survival analysis: the mathematical foundation of conversion delay
• Part 2 — the EM algorithm: a probabilistic optimization approach for partially observed labels
• Part 3 — Chapelle (2014): the industry-standard delayed-feedback model
• Part 4 — this post — Yoshikawa & Imai (2018): dropping the exponential assumption entirely

Main takeaway. NoDeF keeps everything from Chapelle — the two-model split, the fake-negative formulation, the EM loop — and changes exactly one thing: the exponential delay distribution becomes nonparametric. The hazard is built as a kernel-weighted sum of feature-dependent intensities over fixed pseudo-points, so it can take any shape, including the decreasing (and even multimodal) hazards real data shows. A Gaussian kernel keeps the survival function S(t) analytically tractable. The price is a heavier delay M-step (gradient-based, not closed form) and extra hyperparameters. The delay problem is, for practical purposes, solved — but the self-feeding-weights and click-only-sampling issues remain.

Recap

The business problem. In online advertising, the bidding system must estimate the probability a click converts in order to bid the right amount. But conversions are delayed — a user might convert minutes after the click, days later, or never. That makes training labels ambiguous: a click that has not converted is either a true non-converter or a converter whose conversion has not arrived. Treat every not-yet-converted click as a negative and you systematically underestimate conversion rates — and the faster you retrain on fresh data, the worse the bias. This is the delayed-feedback problem.

Chapelle’s model. Chapelle (2014) [1] splits the task in two: a conversion model p(X) = Pr(eventual conversion | X), and a delay model for how long conversion takes given that it happens. Because a Y = 0 label is ambiguous, the two are trained with EM — the E-step assigns each not-yet-converted click a weight wᵢ (its probability of being a true eventual converter), and the M-step refits both models. Chapelle modeled the delay as exponential.

In Part 3 we closed with two limitations. The second — self-feeding EM weights — is a structural property of EM that is hard to eliminate. The first — the exponential delay assumption — is fixable. Yoshikawa & Imai (2018) [2] fix it.

Their model, NoDeF (Nonparametric Delayed Feedback), keeps everything from Chapelle: the two-model decomposition, the fake-negative formulation, the EM loop. It changes exactly one thing — the parametric exponential delay distribution becomes nonparametric. That single change lets the delay model capture any shape, including the decreasing hazard real conversion data exhibits. If you read Parts 1–3 carefully, the math here will feel familiar; the novelty is entirely in how h(t) is constructed.

The problem with exponential delay, revisited

Recall from Part 1 that the exponential forces h(t) = λ — a constant hazard regardless of elapsed time. Real conversion hazard decreases steeply after the click: interest fades, intent cools, and within a week or two whoever has not converted has almost certainly moved on. More generally, observed delay distributions are often non-exponential, with a hazard that varies over time rather than staying flat. The exponential captures none of this. A miscalibrated delay model produces miscalibrated E-step weights wᵢ, which in turn bias p(X). The fix is to let h(t) take whatever shape the data suggests.

The key idea: nonparametric hazard via kernels

NoDeF constructs h(t) as a weighted sum of kernel functions placed at fixed pseudo-points on the time axis. The kernel weights are learned and feature-dependent — so the shape of the hazard can vary across users and ads.

Step 1 — place L pseudo-points (fixed anchor times) on the time axis:

s₁, s₂, …, s_L      (equally spaced, fixed — not learned, just anchors)

Step 2 — define a per-pseudo-point intensity:

αₗ(X; V) = σ(Vₗᵀ X) = (1 + exp(−Vₗᵀ X))⁻¹       (σ = logistic sigmoid)

where V ∈ ℝ^{L×M} is a learned parameter matrix and Vₗ is its l-th row. The intensity αₗ(X) controls how much pseudo-point sₗ contributes to the hazard for a given X, allowing different intensity profiles for different users and ads. Yoshikawa & Imai use the logistic sigmoid here (their Eq. 7) — not just for positivity (which softplus or exp would also give) but because it bounds each intensity to (0, 1), capping the peak per-point hazard.

Step 3 — define the hazard as a kernel-weighted sum:

h(t; X, V) = Σₗ αₗ(X; V) · k(sₗ, t)

where k is a kernel (e.g. Gaussian) measuring similarity between pseudo-point sₗ and query time t. Both αₗ and k are positive, so h(t) > 0 — a valid hazard. The hazard at t is a smooth interpolation of the intensities at nearby pseudo-points, weighted by proximity. Rather than fixing h(t) = λ or any parametric form, NoDeF lets h(t; X) be any smooth non-negative function, determined by the data through V.

To make this concrete: suppose the true delay distribution is multimodal — a burst of fast conversions right after the click, a second bump several days later from slower deliberation, then near zero. An exponential is forced to average these into a single flat rate, losing the structure. NoDeF can place pseudo-points around those locations and learn high intensity there, recovering the actual shape. That is the payoff of going nonparametric.

The survival function for NoDeF

From Part 1, the general survival function:

S(t) = exp( −∫₀ᵗ h(u) du )

Plugging in NoDeF’s hazard:

S(t; X, V) = exp( −Σₗ αₗ(X; V) · ∫₀ᵗ k(sₗ, u) du )

For a Gaussian kernel k(sₗ, u) = exp(−(sₗ − u)² / (2b²)) with bandwidth b, the integral ∫₀ᵗ k(sₗ, u) du has a closed form in terms of the error function erf (their Eqs. 4–5) — so S(t) stays analytically tractable despite the nonparametric hazard. This is the core engineering insight: the kernel family is not arbitrary. It is chosen precisely so that S(t) can be computed exactly rather than approximated numerically. A less careful choice would make S(t) intractable and break the EM loop. (Yoshikawa & Imai write the bandwidth as h; we use b to avoid colliding with the hazard h(t).)

The delay density at an observed conversion then follows from the survival framework of Part 1, f(t) = h(t)·S(t):

f(Dᵢ; X, V) = h(Dᵢ; X, V) · S(Dᵢ; X, V)        (their Eq. 9)

this is the term a confirmed converter contributes to the likelihood, exactly as p(X)·f(Dᵢ) did in Part 3 — only the functional form of f has changed.

Training with EM

The likelihood structure is identical to Part 3 — only S(t) changes. The E-step weight follows the same Bayes derivation:

wᵢ = p(Xᵢ) · S(tᵢ; Xᵢ, V) / [ (1 − p(Xᵢ)) + p(Xᵢ)·S(tᵢ; Xᵢ, V) ]

Structurally identical to Chapelle’s wᵢ — just with NoDeF’s S(t) in place of exp(−λ(X)·t).

• E-step: compute wᵢ for all Y = 0 examples using current θ = {βₚ, V}. Identical in structure to Chapelle.
• M-step: the conversion model p(X) still reduces to weighted logistic regression — same as Chapelle. The delay model now requires gradient-based optimization over V; Yoshikawa & Imai use L-BFGS. This is the main practical cost of going nonparametric: the delay M-step is no longer closed form — it needs iterative gradient optimization at each EM iteration.

A one-minute primer on L-BFGS

Intuition. When a problem has no closed-form solution — like NoDeF’s delay M-step — you minimize it iteratively, stepping in the direction the gradient points. Plain gradient descent only feels the slope, so it can zig-zag down long narrow valleys. L-BFGS is a smarter version: it also senses the curvature of the landscape and uses it to head more directly toward the minimum, usually in far fewer steps. You give it two things — a way to compute the objective and a way to compute its gradient — and it returns the optimum. NoDeF supplies that gradient (with respect to V), so each M-step just calls L-BFGS to refit the delay model. It is the same optimizer Chapelle used in Part 3.

Technical details (skip on a first read). The name is limited-memory Broyden–Fletcher–Goldfarb–Shanno. It is a quasi-Newton method: Newton’s method captures curvature exactly via the Hessian (the matrix of second derivatives), but storing and inverting that matrix costs on the order of N² memory and N³ time — hopeless for many parameters. L-BFGS never forms the Hessian; it approximates the curvature from just the last 5–20 gradient-and-step pairs, so memory grows linearly with the number of parameters. That makes it a standard off-the-shelf choice for smooth, unconstrained, medium-sized problems like this one.

Hyperparameters and practical considerations

NoDeF’s overhead over Chapelle is its additional hyperparameters:

• L — number of pseudo-points. More means a more expressive hazard but more parameters. Chosen by cross-validation.
• Kernel bandwidth b — controls smoothness of the hazard. Yoshikawa & Imai recommend b = (sₗ₊₁ − sₗ)/2, i.e. half the spacing between pseudo-points.
• Regularization — ℓ₂ regularizers on both βₚ and V, controlled by strengths γ_β and γ_V. (We write these as γ to avoid clashing with the delay rate λ from Parts 1–3.)

L is the most important choice. Too few pseudo-points and the model cannot capture fine-grained delay patterns; too many and you risk overfitting the delay distribution.

What changes vs. Chapelle

The first four rows are where NoDeF diverges; the last two are inherited unchanged.

Limitations

NoDeF solves Chapelle’s parametric assumption cleanly. Together, Parts 3 and 4 give the full delay-modeling toolkit: a principled probabilistic framework (Chapelle) and a flexible nonparametric delay distribution (NoDeF). The delay problem is, for practical purposes, solved.

But the self-feeding weights issue remains — wᵢ still depends on the current model, making EM circular. This is a structural property of the EM approach that neither paper addresses.

More fundamentally, both Chapelle and NoDeF share a deeper assumption: the training set consists only of clicked examples. Both are therefore trained on a biased sample — users who clicked are not representative of all users who saw the ad. A user who never clicks is never in the training data, even though the bidding system must estimate conversion probability for all impressions. This selection-bias problem is orthogonal to the delay problem, and neither paper addresses it.

Summary

NoDeF retains from Chapelle:
p(X; βₚ) = σ(βₚᵀ X)                                         conversion model — unchanged
wᵢ = p(Xᵢ)·S(tᵢ) / [ (1 − p(Xᵢ)) + p(Xᵢ)·S(tᵢ) ]           E-step weight — same Bayes structure

NoDeF changes:
h(t; X, V) = Σₗ αₗ(X; V) · k(sₗ, t)                         nonparametric hazard — any shape
S(t; X, V) = exp( −Σₗ αₗ(X; V) · ∫₀ᵗ k(sₗ, u) du )          analytically tractable
delay M-step: closed form  →  gradient-based (L-BFGS)

Key tradeoff: a more expressive delay model at the cost of L×M parameters (vs M) and a heavier M-step.

This closes the series. Parts 1–2 built the foundations (exponential delay, survival analysis, EM); Parts 3–4 applied them to the two papers that define modern delayed-feedback modeling. The open frontier is the selection bias from click-only training data — a problem for another series.

References

[1] Chapelle, O. (2014). Modeling Delayed Feedback in Display Advertising. KDD 2014. PDF

[2] Yoshikawa, Y. & Imai, Y. (2018). A Nonparametric Delayed Feedback Model for Conversion Rate Prediction. arXiv:1802.00255