A search engine that learns while it serves sees one query at a time and must improve its ranking function after each one. The standard approach updates a listwise loss with plain gradient steps. A listwise loss scores the whole candidate list at once, usually by putting a softmax over all documents for a query. Plain gradient steps scale every feature by the same step size, which suits poorly conditioned ranking features badly. Web ranking features come in correlated families, such as many BM25 variants computed over different document fields. Second-order online methods, which rescale and rotate each update using an estimate of the loss's curvature, are the textbook fix. In ranking they have been ignored. The online rankers in the literature are first-order and pairwise, and the listwise rankers are trained offline.
This note proposes a simple observation and builds a learner around it. Because a listwise softmax loss is normalized over the whole list, its curvature (its second derivative, the Hessian) is exactly the covariance of document features under the model's own distribution over that list. That quantity depends only on the documents shown and the current model, never on relevance labels or clicks. Every query therefore delivers an exact, label-free, rank-up-to-$(n-1)$ curvature estimate, even when feedback is only a few clicks. Bandit-style second-order methods instead build curvature from noisy, rank-one outer products of gradient estimates. We propose an Online Newton ranker that accumulates this "list covariance," sketched to low rank when the feature space is large. We test whether it learns a good ranker from far fewer queries than first-order online rankers, and whether it resists feature rescaling and correlation.
Core Claim
Let a query's candidate list have feature vectors $x_1,\dots,x_n \in \mathbb{R}^d$ and let a linear ranker with weights $w$ assign top-one probabilities $p_i = \exp(w^\top x_i)/\sum_j \exp(w^\top x_j)$. Train it with the listwise cross-entropy $\ell(w) = -\sum_i q_i \log p_i$, where $q$ is a target distribution built from graded labels or clicks. The gradient is $g = \sum_i (p_i - q_i)\, x_i$, and the Hessian is
$$ H(w) = \sum_{i=1}^{n} p_i\,(x_i - \bar{x})(x_i - \bar{x})^\top, \qquad \bar{x} = \sum_{i=1}^n p_i x_i , $$
which contains no $q$. This is the familiar fact from globally normalized models such as conditional random fields: the second derivative of the log partition function equals the covariance of the features under the model. The proposed learner keeps $A_t = \lambda I + \sum_{\tau \le t} H_\tau(w_\tau)$ and updates $w_{t+1} = w_t - \eta\, A_t^{-1} g_t$, where $\lambda>0$ is a ridge term, $\eta$ a step size, and $H_\tau$ the list covariance of query $\tau$ at the weights in force when it arrived.
Three properties follow, and each is testable. First, the curvature is concentrated where ranking quality is decided. The weights $p_i$ put most mass on the documents the model currently ranks highly, so $H$ captures which features separate the top candidates from each other. A pointwise sigmoid loss gives a sum of per-item terms that grows with list size and is dominated by the many irrelevant documents. Second, because $\sum_i p_i = 1$, each query contributes curvature of bounded trace regardless of how many candidates it has. This avoids the query-size bias that makes pairwise objectives favor large queries, which Learning to Link Entities with Knowledge Base identifies as a reason to prefer listwise losses. Third, under click feedback only the gradient is noisy; the curvature is exact.
Relation to Prior Work
The proposal reuses its machinery from second-order online learning. Logarithmic regret algorithms for online convex optimization introduces the Online Newton Step, which accumulates gradient outer products and achieves logarithmic regret for exp-concave losses. "Exp-concave" means, roughly, that the loss curves upward at least in the direction of its own gradient. Newtron carries this to multiclass prediction with 1-bit feedback. It builds curvature from randomized gradient estimates, and its constant grows exponentially in the curvature parameter $\alpha$. Its fast diagonal variant, PNEWTRON, lacks a proof. Efficient Second Order Online Learning by Sketching keeps a low-rank Frequent Directions sketch of the curvature so that updates cost time linear in the active features, but it is evaluated only on scalar classification and regression.
Two further methods use second-order information through a different matrix. Exact Convex Confidence-Weighted Learning and adPredictor track a feature covariance or parameter variance. That is curvature of a per-example, locally normalized model.
Our departure is the matrix being accumulated. We use the exact list covariance, which is label-free and has rank up to $n-1$ per round. Newtron and the Online Newton Step use rank-one gradient outer products, and confidence-weighted methods use per-example feature covariance. In the multiclass special case, where the "list" is the set of classes, the list covariance can be computed in Newtron's setting without seeing feedback. That gives us a direct comparison on Newtron's own benchmarks.
Global sequence normalization supplies the motivating lens and one constraint. Globally Normalized Transition-Based Neural Networks proves that models normalized over whole structures are strictly more expressive than step-wise normalized ones. Global Normalization for Streaming Speech Recognition in a Modular Framework shows global normalization closing more than half the streaming gap on LibriSpeech. Both are trained offline with first-order optimizers.
In ranking, the step-wise analogue is ListMLE's top-down factorization. Learning to Rank by Directly Optimizing Full-Order Probabilities shows that this factorization breaks order-reversal invariance, meaning the loss changes if the ranking is read bottom-to-top instead of top-to-bottom. Its Hessian is a sum of covariances over shrinking remainder sets, which gives bottom positions as much curvature as top ones. That matches the paper's report that full-order objectives misalign with NDCG unless patched with a LambdaFOB variant.
We therefore restrict ourselves to losses with a single list-level partition function: top-one softmax cross-entropy and a truncated top-$k$ variant. The global-normalization literature tells us their curvature is a model covariance. FOB itself is offline, bilevel, and loses its convexity guarantee when relevance labels are tied. Graded labels enter our target $q$ directly, so ties need no special handling.
The online ranking work defines the regime. Robust Online Learning to Rank via Selective Pairwise Approach Based on Evaluation Measures (PARank-NDCG) makes one first-order Passive-Aggressive step on the single pair with the largest NDCG loss. Online Learning to Rank with Features (RecurRank) handles click feedback with linear experimental design. It discards clicks below the first position of each interval and tracks no curvature for nonlinear losses. Neither uses a list-normalized loss or second-order updates.
Research Program
The first component is algorithmic. We will implement full-matrix list-covariance Newton updates for feature spaces of a few hundred dimensions; MSLR has 136 features and Istella and Yahoo up to about 700, so a $d\times d$ inverse updated by Woodbury identities is cheap. For high-dimensional sparse features we add a sketched variant. Each list covariance factors as $H = V^\top V$ with rows $\sqrt{p_i}(x_i-\bar x)$, and those rows are fed into a Frequent Directions sketch exactly as SON feeds gradients. We also define a top-$k$ truncated loss: a Plackett-Luce likelihood (the probability of drawing items in a given order, each with chance proportional to its exponentiated score) over the first $k$ positions. Its curvature is a sum of $k$ list covariances over shrinking candidate sets, giving a top-heavy curvature with tractable cost.
The second component is theoretical and modest. The top-one loss with a linear scorer on a bounded domain is exp-concave, so the standard Online Newton analysis applies, but its $\alpha$ decays exponentially with the score range. That is the Newtron pathology. We will try to bound regret for the Hessian-based update in terms of the accumulated list covariance rather than $\alpha$, using the fact that log-sum-exp curvature changes in a controlled way between nearby weights. We treat this as a goal that may fail. If it fails, the empirical claims stand on their own.
The third component handles clicks. A displayed list with clicks gives an inverse-propensity-weighted target $q$ under a position-based or cascade click model, which is unbiased but noisy. The curvature step is unchanged. We will measure how much of the gain from second-order updates survives the move from full labels to clicks. Because the curvature is label-free, our prediction is that the gain should grow, not shrink, as feedback becomes sparser.
Baselines
The naive reference point is the same linear ListNet-style softmax loss trained online by SGD with a tuned global step size, one pass over queries in a fixed random order. Any second-order benefit must show up against this, with identical data order, loss, and initialization.
The strongest existing online method is PARank-NDCG (Robust Online Learning to Rank via Selective Pairwise Approach Based on Evaluation Measures). It is the most competitive published online ranker on MSLR-WEB10K and WEB30K, reported to beat Stochastic Pairwise Descent, Committee Perceptron, and batch RankingSVM at every NDCG cutoff. We found no reported NDCG@k values for PARank-NDCG on Lacuna, so we will reimplement it and report its numbers under our protocol alongside its reported 7-second training time on MSLR-WEB10K as a cost reference. Beating it means higher progressive NDCG@10 and higher final held-out NDCG@10 on both MSLR sets at matched passes, with significance across five random query orders.
Diagonal adaptive methods on the same listwise loss (AdaGrad and Adam) are the strongest generic optimizer competitors and get the same hyperparameter budget as ours: a fixed grid of 20 configurations tuned on the validation fold.
Two ablations isolate the key ingredient. In the first, the Online Newton Step accumulates gradient outer products $g_t g_t^\top$ on the same loss; this is Newtron's and SON's choice of curvature. In the second, the preconditioner is the running uncentered feature covariance $\sum_i x_i x_i^\top$, the confidence-weighted and online-whitening choice. If ours does not beat both, the list covariance is not what matters.
For the bandit check we compare against Newtron and PNEWTRON on REUTERS4. Newtron reports PNEWTRON at 13.08% error versus BANDITRON at 18.10%. A sketched list-covariance learner below 13.08% at equal rounds would count as a win. For click feedback we run RecurRank (Online Learning to Rank with Features) in the same simulated environments; no reported scalar regret was found on Lacuna for it. Offline batch training of the same linear ranker, plus FOB from its public repository, give a ceiling rather than a competitor.
Why not just…?
Why not just use Adam or AdaGrad on the listwise loss? Diagonal methods rescale features one at a time but cannot undo correlation between features. MSLR's 136 features are dominated by correlated families of the same signal computed over different document fields. Efficient Second Order Online Learning by Sketching reports that a sketched second-order learner beats AdaGrad on most of 23 classification datasets, which is suggestive but untested for ranking. Our feature-transform stress test settles it directly: we apply a random invertible linear map to the features. Newton-type updates are invariant to such maps and diagonal ones are not, so we expect a widening gap. If the gap stays small on untransformed real data, we will report that second-order updates matter only under adversarial conditioning.
Why not just whiten the features once, or track their running covariance, and then run SGD? This is the most serious threat. On data with fixed feature geometry, whitening captures much of what any preconditioner can. Whitening uses the covariance of all documents, though, while the list covariance weights documents by the model's current top-one probability and centers within each query. It therefore targets features that separate competing top candidates rather than features that vary across the collection. The uncentered-covariance ablation is exactly this alternative. If it matches our method on NDCG@10, the claim reduces to "precondition by feature covariance" and we will say so. The expected separation is largest early in training and on NDCG@1–3.
Why not just apply the Online Newton Step or SON with gradient outer products, as in Newtron? Under full labels this may come close. Under clicks, gradient estimates are importance-weighted and high-variance, so curvature built from their outer products inherits that noise and grows with it, while the list covariance does not. The click-feedback experiments and the REUTERS4 bandit replication test exactly this difference. The prediction is that our method's advantage over gradient-outer-product curvature grows as feedback becomes sparser.
Why not just train LambdaMART or FOB offline and retrain periodically? That answers a different question. Offline training needs the stored data and repeated passes, and retraining lags behind drift. We report offline linear ranker and FOB results as the ceiling and measure how many queries the online learners need to reach 95% of that ceiling.
Proposed Experiments
The full-information streaming study runs on MSLR-WEB10K, MSLR-WEB30K, Yahoo! LTR Set 1, Istella, and LETOR 4.0 MQ2007/MQ2008, using standard folds. Yahoo! Learning to Rank Challenge Overview reports a top batch ERR of 0.46861 on Yahoo Set 1, which we cite only to place linear online results relative to tuned ensembles. Training queries arrive one at a time for a single pass. We report progressive NDCG@1/5/10 (each list scored before the update), final test NDCG@10 and Kendall's $\tau$, and queries needed to reach 95% of the offline ceiling.
The decisive check is the learning curve over the first 1,000 queries, under both original and randomly transformed features. If the list-covariance learner does not reach the ceiling in clearly fewer queries than both the gradient-outer-product and whitening ablations, the central claim fails.
The click study simulates cascade and position-based users on MSLR-WEB30K and Yahoo, following the click environments of Online Learning to Rank with Features. It reports cumulative NDCG of displayed top-10 lists and test NDCG@10 after 100k sessions. The decisive check is whether the gap over gradient-outer-product curvature grows as click noise increases.
The bandit replication runs on SYNSEP and REUTERS4 from Newtron, using the Frequent Directions sketch at ranks 10 to 50 for REUTERS4's 346,000 features. Targets are PNEWTRON's reported 0.89% on SYNSEP and 13.08% on REUTERS4.
A final top-heavy study compares top-one curvature, top-$k$ curvature at $k\in\{3,5,10\}$, and full ListMLE curvature. If our analysis of where ListMLE's curvature goes is right, full-list curvature should improve Kendall's $\tau$ while hurting NDCG@3, and top-$k$ curvature should do the reverse.
References
- Learning to Link Entities with Knowledge Base
- Logarithmic regret algorithms for online convex optimization
- Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction
- Efficient Second Order Online Learning by Sketching
- Exact Convex Confidence-Weighted Learning
- Web-Scale Bayesian Click-Through rate Prediction for Sponsored Search Advertising in Microsoft's Bing Search Engine
- Globally Normalized Transition-Based Neural Networks
- Global Normalization for Streaming Speech Recognition in a Modular Framework
- Learning to Rank by Directly Optimizing Full-Order Probabilities
- Robust Online Learning to Rank via Selective Pairwise Approach Based on Evaluation Measures
- Online Learning to Rank with Features
- Yahoo! Learning to Rank Challenge Overview