Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness¶

会议: NeurIPS 2026
arXiv: 2603.20826
OpenReview: https://openreview.net/forum?id=uGztbZRzrg
论文: https://arxiv.org/abs/2603.20826
领域: 推荐系统
关键词: 上下文推荐, 在线逆线性优化, 无投影算法, 对数遗憾界, 二阶感知机

一句话总结¶

针对隐式反馈下的上下文推荐（在线逆线性优化）问题，本文提出利用推荐决策的正缩放不变性（非良规性）消除传统在线牛顿步必须的马氏距离投影，构造出每轮仅需 $O(d^2)$ 时间、具备 $O(d \log T)$ 对数遗憾界且天然抵抗次优动作反馈的无投影二阶算法 CoRectron。

研究背景与动机¶

在现代个性化推荐、路线规划以及临床决策等场景中，系统往往只能记录用户或专家的实际选择动作（例如加购某组商品、选定某条路径），而无法直接观测到驱动该选择背后的显式效用标量。这种仅凭动作反馈推断用户潜在偏好的问题在在线学习中被称为上下文推荐（Contextual Recommendation），数学上亦等价于在线逆线性优化（Online Inverse Linear Optimization）。学习者在每一轮接收到上下文决定的候选动作集合，根据当前估计的效用偏好推荐一个动作，随后观察用户的真实动作并评估两者在真实效用下的差距（累积遗憾）。

此前在线逆优化领域的最优算法依赖在线凸优化（OCO）框架下的在线牛顿步（Online Newton Step, ONS），虽将遗憾界压到了与轮数无关的理论极限 $O(d \log T)$，却在每一轮更新中都需要执行一次将效用向量投影回有界凸域的马氏距离投影（Mahalanobis Projection）。在高维空间或基于核技巧的无穷维希尔伯特空间中，这种带权投影需要极高代价的矩阵分解与迭代寻优，时间复杂度至少高达 $\Omega(d^\omega)$（工程实现常为 $O(d^3)$），成为了阻碍在线实时推荐的绝对算力瓶颈。更为严峻的是，当用户动作受到随机噪声干扰而呈现次优反馈时，以往方法必须借由 MetaGrad 同时并行维护 $O(\log T)$ 个不同学习率的 ONS 实例，进一步加剧了计算开销。

这一困境的核心症结在于传统算法将推荐模型教条地限制在良规（Proper）的凸参数球内。本文敏锐地洞察到，上下文推荐的最终动作是通过在候选集上最大化内积产生的，效用向量乘以任意正标量完全不改变最终推荐动作的选取结果。核心 idea：充分利用上下文推荐中决策对效用尺度的正缩放不变性，打破参数范数必须受限的良规假定，将在线分类中的二阶感知机机制引入推荐领域，设计无需马氏投影的二阶残差预条件更新，在彻底摆脱投影算力瓶颈的同时实现 $O(d \log T)$ 对数遗憾界与天然的次优鲁棒性。

方法详解¶

整体框架¶

算法 CoRectron（Contextual Recommendation via Second-Order Perceptron）在真实希尔伯特空间 $\mathcal{V}$（有限维 $\mathbb{R}^d$ 或再生核希尔伯特空间 $\mathcal{H}$）中运行。每一轮开始时，学习者利用历史累积动作残差与协方差二阶预条件算子直接计算无约束效用预测向量 $\hat{w}_t$，通过线性优化预言机在当前候选动作集 $\mathcal{X}_t$ 中选取最优推荐动作 $\hat{x}_t$；在观测到用户反馈动作 $x_t$ 后，构建单轮残差 $g_t = \hat{x}_t - x_t$，并通过秩一更新迭代协方差算子与累积残差。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["上下文到达：候选动作集 𝒳t ⊆ 𝒱"] --> B["尺度不变非良规效用预测<br/>w^t = - At-1⁻¹ ζt-1（无投影）"]
    B --> C["线性预言机推荐<br/>x^t = argmax ⟨w^t, x⟩"]
    C --> D["观察用户动作反馈 xt<br/>构建残差 gt = x^t - xt"]
    D --> E["双势能与符号条件分析<br/>At 秩一更新与 ζt 累加"]
    E -->|次优反馈统一处理| F["输出遗憾与次优平方根界"]

关键设计¶

1. 尺度不变非良规效用预测：利用决策不变性彻底移除马氏投影

在传统 ONS 算法中，为了套用标准凸优化遗憾界，必须强行限定效用估计 $\hat{w}_t$ 落在有界球（如单位球）内，这导致每轮必须求解 $\min_{w: \|w\|_2 \le 1} (w' - w)^\top A_{t-1} (w' - w)$，单轮开销高达 $O(d^3)$。本文指出，推荐系统的决策映射 $x \mapsto \arg\max_{x \in \mathcal{X}_t} \langle \hat{w}_t, x \rangle$ 具有严格的正缩放不变性，用户动作反馈也仅蕴含真实偏好向量 $u$ 的方向信息而非绝对范数。基于此，CoRectron 完全放弃对 $\hat{w}_t$ 的范数约束，直接由正则化二阶协方差逆矩阵与累积残差向量相乘得到： $$ \hat{w}t = -A g_s $$ 该更新公式在结构上与在线分类中的二阶感知机（Second-Order Perceptron）完全对齐。在有限维空间中，利用 Sherman-Morrison 逆矩阵秩一更新公式，每轮计算 }^{-1} \zeta_{t-1}, \quad \text{其中 } A_{t-1} = \lambda \mathrm{I} + \sum_{s=1}^{t-1} g_s \otimes g_s, \quad \zeta_{t-1} = \sum_{s=1}^{t-1$A_t^{-1}$ 仅需 $O(d^2)$ 的矩阵向量乘法，完全免去了代价高昂的投影步骤。

2. 单侧符号条件与累积椭圆双势能控制：突破传统二阶感知机分类遗憾瓶颈

分类问题中的经典二阶感知机仅能给出依赖样本分类间隔（Margin）的错误界，在最坏情况下该界可能任意恶化。CoRectron 能在推荐问题上取得严格对数遗憾界的数学基石在于推荐决策本身诱导出的单侧最优性符号条件。由于推荐动作 $\hat{x}_t$ 是在 $\mathcal{X}_t$ 上关于预测向量 $\hat{w}_t$ 的最大化解，而用户反馈 $x_t \in \mathcal{X}_t$，因此内积满足： $$ \langle g_t, A_{t-1}^{-1} \zeta_{t-1} \rangle = -\langle \hat{w}t, \hat{x}t - x_t \rangle \le 0 $$ 借助该符号条件，定义累积势能 $\Phi_t = \langle \zeta_t, A_t^{-1} \zeta_t \rangle$，论文严格证明了累积势能受单轮椭圆势能增量之和控制的 CP-EP 不等式（$\Phi_T \le \sum_{t=1}^T \langle g_t, A_t^{-1} g_t \rangle$）。结合经典椭圆势能引理，累积遗憾 $R_T(u) = -\langle u, \zeta_T \rangle$ 可由柯西-施瓦茨不等式放缩为： $$ R_T(u) \le |u| \le |u|} \sqrt{\Phi_T $$ 其中 } \sqrt{\log\det(\mathrm{I}_T + \lambda^{-1} K_T)$K_T \in \mathbb{R}^{T \times T}$ 是残差向量的格拉姆（Gram）矩阵。这一分析优雅地避开了分类间隔敏感性，确立了与 ONS 相当的紧致势能上界。

3. 数据自适应范数自抵消：免超参数搜索的内在次优鲁棒性

在真实推荐交互中，用户受注意力偏差或界面呈现限制，给出的反馈动作 $x_t$ 往往并非全局最优解，具有累积次优度 $\Delta_T(u) = \sum_{t=1}^T (\max_{x \in \mathcal{X}_t} \langle u, x \rangle - \langle u, x_t \rangle)$。先前方法无法预知次优程度，必须通过 MetaGrad 算法运行多重学习率实例。而 CoRectron 的核心设计使得算法在不做任何修改、保持单实例运行的前提下天生具备鲁棒性。其内在机理在于椭圆范数项 $\|u\|_{A_T}^2 = \lambda \|u\|^2 + \sum_{t=1}^T r_t^2$ 能够直接自适应吸收次优动作造成的单轮平方损失。利用有界性条件展开二次不等式： $$ |u|_{A_T}^2 \le \lambda |u|^2 + B R_T(u) + 2B \Delta_T(u) $$ 解该关于 $R_T(u)$ 的二次不等式后，直接得出与次优度平方根 $\sqrt{\Delta_T(u)}$ 成正比的优雅鲁棒遗憾界，无需引入任何额外复杂度。

4. 希尔伯特空间统一提升范式：面向核化非线性推荐的递推加速

为了处理复杂的上下文特征交互与非线性用户偏好，论文建立了从欧氏基础动作空间 $\mathcal{X}_t^{\mathrm{base}} \subseteq \mathbb{R}^n$ 到希尔伯特空间 $\mathcal{V}$ 的算子提升框架 $\mathcal{X}_t = \Psi_t(\mathcal{X}_t^{\mathrm{base}})$。在向量值再生核希尔伯特空间（RKHS）中，真实效用函数被建模为核特征映射。在该无限维设定下，由于无需马氏投影，CoRectron 可以完全基于核矩阵 $K_{t-1} + \lambda \mathrm{I}_{t-1}$ 的分块 Cholesky 分解维护表示系数，通过前向与后向代换将单轮求逆开销压至 $O(t^2)$，彻底规避了核化 ONS（KONS）每轮执行核空间凸二次规划导致的 $O(t^3)$ 灾难性开销。

损失函数 / 训练策略¶

算法不显式执行梯度下降反向传播，而是维护分析型在线二阶递推系统。超参数为正则化强度 $\lambda > 0$。理论推荐设定为 $\lambda = B^2 d$（非上下文模型 $d=n$，线性上下文模型 $d=np$）。在核化模型中，$\lambda \in (0, T]$ 任意选取，最终遗憾界由核格拉姆矩阵的有效维度 $d_{\mathrm{eff}}^T(\lambda) = \operatorname{tr}(K_T(K_T + \lambda \mathrm{I}_T)^{-1})$ 与算子范数共同决定。

实验关键数据¶

主实验¶

实验在经典上下文 $m$-out-of-$n$ 推荐任务（$n=10$ 个候选物品中选 $m=5$ 个推荐位，上下文维度 $p=10$，线性参数空间 $d=np=100$）上开展，评估 $T=10000$ 轮下的累积遗憾与单核 CPU 运行耗时（10 个独立随机种子平均值）。

方法	设定	最终累积遗憾 $R_T$ (最优超参)	运行时间 (s)	单轮复杂度	每轮马氏投影次数
OGD (在线梯度下降)	线性上下文	~40.2	0.82	$O(d + \tau_{\mathrm{opt}})$	0
ONS (在线牛顿步) [Sakaue 2025]	线性上下文	~35.6	4.85	$O(d^\omega + \tau_{\mathrm{opt}})$	频繁触发 (小 $c$ 时可达数千次)
CoRectron-L (本文方法)	线性上下文	15.1	1.35	$O(d^2 + \tau_{\mathrm{opt}})$	0 (严格免投影)
KONS (核化 ONS)	核化 RBF ($T=1000$)	~22.4	42.10	$O(t^3 + \tau_{\mathrm{opt}})$	1000
CoRectron-K (本文方法)	核化 RBF ($T=1000$)	18.7	8.62	$O(t^2 + \tau_{\mathrm{opt}})$	0 (严格免投影)

消融实验¶

消融实验重点考察正则化缩放系数 $c$（其中 $\lambda = c \bar{\lambda}$，覆盖 $10^{-3}$ 到 $10^3$ 跨度 7 个数量级）对稳定性的影响，以及在不同用户次优动作反馈扰动下的鲁棒性表现。

实验配置	变化维度 / 扰动参数	CoRectron-L 遗憾	ONS 遗憾	关键结论与说明
正则化敏感度	弱正则 $c = 10^{-3}$	15.1	发散 / 遗憾大幅恶化	ONS 强依赖投影且参数脆弱，CoRectron 极稳健
正则化敏感度	基准正则 $c = 1$	19.8	38.2	CoRectron 在宽泛区间内遗憾均显著优于 ONS
正则化敏感度	强正则 $c = 10^{3}$	54.3	68.9	强正则使更新保守，两者均平滑退化
次优扰动：单物品交换	交换概率 $\alpha = 0.2$	12.4	29.8	次优动作下 CoRectron 保持超过 50% 性能优势
次优扰动：单物品交换	交换概率 $\alpha = 0.8$	8.1	18.5	目标效用基线弱化导致实际累积遗憾降低
次优扰动：分数相对加噪	扰动噪声 $\xi = 0.5$	10.5	24.1	连续高斯扰动下保持最优抗噪性能

关键发现¶

算法速度与计算稳定性优势极为显著：CoRectron 耗时仅略高于最简单的一阶 OGD，相比 ONS 加速近 4 倍；在核化设置下相比 KONS 加速近 5 倍。ONS 和 KONS 的耗时曲线与其马氏投影触发次数完全重合，证实投影是制约在线逆优化的绝对瓶颈。
超参数平坦性优异：ONS 在较小的正则化系数 $c$ 下由于更新步长过大导致投影频繁发散、遗憾激增；而 CoRectron 在极小的正则化系数 $c=10^{-3}$ 下依然稳定收敛并取得最低遗憾。
扰动鲁棒性验证：在离散替换（One-swap）与连续打分高斯扰动（Score-perturb）两种次优反馈模型下，CoRectron-L 在所有噪声强度下均持续超越基线，且由于次优基线目标本身更容易逼近，实测遗憾呈现与理论悲观界相反的自然下降趋势。

亮点与洞察¶

巧妙利用物理特性的非良规逆向思维：传统在线优化思维定式认为必须将估计参数拘束在单位球内以保证有界性，本文逆向思考，发现推荐系统动作输出具有本质的尺度不变性，从而顺理成章地丢弃投影瓶颈。
理论界在推荐与分类之间的反差洞见：在线分类中的二阶感知机受困于未知的几何间隔，而在线推荐任务中，候选动作集上的最优化机制天然提供了 $\langle g_t, A_{t-1}^{-1} \zeta_{t-1} \rangle \le 0$ 的非正符号约束，从机制上消除了分类间隔项，换来了干净的对数遗憾界。
理论与算法实现的自洽内生鲁棒性：无需使用任何外层元学习包装（如 MetaGrad），仅凭二阶椭圆范数对残差内积的内在抵消机制，便以零额外代价获得了对次优反馈的理论与经验双重鲁棒性。

局限与展望¶

依赖精确的线性优化预言机：算法在每一轮仍需调用 $\arg\max_{x \in \mathcal{X}_t} \langle \hat{w}_t, x \rangle$ 预言机。当候选动作集具有极为复杂的组合约束（如旅行商问题或非凸组合约束）时，预言机本身的求解时间 $\tau_{\mathrm{opt}}(t)$ 可能成为新的计算瓶颈。
核化大规模场景下的显存与时间增长：虽然核化 CoRectron 将单轮开销从 $O(t^3)$ 降至 $O(t^2)$，但其累计时间仍随轮数呈二次方增长，在超长生命周期或千万级海量推荐交互中，仍需引入随机特征映射（RFF）或核草图（Kernel Sketching）等稀疏化加速技术。
偏好模型局限于线性/RKHS 形式：现实工业界推荐模型大量采用深层非线性神经网络表示，如何将非良规二阶感知机思想推广至具有非凸隐式表示的深度交互模型中是值得探索的方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙利用推荐决策正缩放不变性移除非良规约束，在经典二阶感知机与在线逆优化间建立了深刻联系。
实验充分度: ⭐⭐⭐⭐ 覆盖了线性与核化两类上下文设定，详尽对比了超参数敏感度与两类次优扰动模型，实验扎实可信。
写作质量: ⭐⭐⭐⭐⭐ 动机清晰，数学推导行云流水，势能引理证明严密自洽，结构规范。
价值: ⭐⭐⭐⭐⭐ 彻底解决了困扰在线逆优化与上下文推荐的投影计算瓶颈，为理论在线决策算法走向实用化迈出坚实一步。

实验配置	变化维度 / 扰动参数	CoRectron-L 遗憾	ONS 遗憾	关键结论与说明
正则化敏感度	弱正则 \(c = 10^{-3}\)	15.1	发散 / 遗憾大幅恶化	ONS 强依赖投影且参数脆弱，CoRectron 极稳健
正则化敏感度	基准正则 \(c = 1\)	19.8	38.2	CoRectron 在宽泛区间内遗憾均显著优于 ONS
正则化敏感度	强正则 \(c = 10^{3}\)	54.3	68.9	强正则使更新保守，两者均平滑退化
次优扰动：单物品交换	交换概率 \(\alpha = 0.2\)	12.4	29.8	次优动作下 CoRectron 保持超过 50% 性能优势
次优扰动：单物品交换	交换概率 \(\alpha = 0.8\)	8.1	18.5	目标效用基线弱化导致实际累积遗憾降低
次优扰动：分数相对加噪	扰动噪声 \(\xi = 0.5\)	10.5	24.1	连续高斯扰动下保持最优抗噪性能