CoRectron: Breaking the Projection Barrier in Contextual Recommendation

TL;DR

The paper presents CoRectron, a simple yet powerful algorithm for contextual recommendation that eliminates the computational "tax" of Mahalanobis projections. By exploiting the improperness inherent in recommendation tasks, it achieves the state-of-the-art O(d log T) regret bound while being significantly faster than ONS-based methods. It also offers built-in robustness to noise and extends naturally to kernelized models.

Contextual Recommendation: The Choice-Only Challenge

In many real-world systems, we don't see a numerical reward (like a 5-star rating). Instead, we only see an action: a user bought item A instead of item B. The goal is to learn the user's hidden preference vector $u$ by observing these "optimal" choices.

Historically, this was solved using Online Newton Step (ONS). While ONS is mathematically elegant, it comes with a heavy price: the Mahalanobis projection. Every round, the algorithm must project its estimate back onto a valid unit ball, solving a complex quadratic form that scales poorly ($O(d^3)$) as dimensions grow.

The Insight: Embracing "Improper" Learning

The author makes a brilliant observation: Scale doesn't matter. If you believe item A has utility 10 and item B has utility 5, you recommend A. If you multiply those values by 1,000, you still recommend A.

Because recommendations are scale-invariant, we don't need to force our internal model $w_t$ to stay within a bounded "unit ball." By letting the model grow to any scale (Improper Learning), we can throw away the projection step entirely.

Methodology: The Power of the Second-Order Perceptron

CoRectron uses an update rule reminiscent of the classical Second-Order Perceptron. It maintains a cumulative residual ${\zeta }_t$ (the difference between what was recommended and what the user chose) and a second-order preconditioner $A_t$.

Algorithm Architecture

1. Predict: $w_t\leftarrow -A_{t-1}^{-1}{\zeta }_{t-1}$
2. Recommend: ${\hat{x}}_t\in \arg \max ⟨w_t,x⟩$
3. Observe: True user action $x_t$.
4. Update: Add the residual $g_t={\hat{x}}_t-x_t$ to the Gram matrix.

By utilizing the Sherman-Morrison formula, the matrix inversion $A_t^{-1}$ can be updated in $O(d^2)$ time, making it significantly faster than standard ONS.

Robustness and Generalization

One standout feature is robustness. If a user makes a suboptimal choice (noise), standard algorithms usually require complex adaptations (like MetaGrad) to maintain performance. CoRectron handles this naturally—its regret bound degrades gracefully at the rate of the square root of the total "noise," without changing a single line of code.

The paper also introduces a Kernelized version of the algorithm, allowing it to handle complex, non-linear preferences in Hilbert spaces. In these settings, avoiding projections is even more critical, as projections in high-dimensional feature spaces are often practically impossible.

Experimental Evidence

In simulations of selecting $m$-out-of-$n$ items, CoRectron consistently outperformed ONS and Online Gradient Descent (OGD).

Key Findings:

• Stability: Unlike ONS, which becomes unstable if hyperparameters (like the learning rate) are set too aggressively, CoRectron remains stable and high-performing across a wide range of settings.
• Speed: CoRectron’s runtime is strictly lower than ONS because it skips the projection count that scales with $T$.

Deep Insights & Conclusion

This work highlights a fundamental shift in thinking for online learning: Constraints are not always necessary. By identifying that recommendation only requires directional accuracy, the author removes a major computational barrier.

Limitations: The algorithm still requires an "Oracle" to solve the inner maximization $\arg \max ⟨w,x⟩$. If the set of available items is astronomically large or satisfies complex constraints, this oracle itself might become the new bottleneck. However, for most recommendation sub-problems, CoRectron provides a much-needed speed boost without any loss in theoretical regret.