Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization¶

会议: ICML 2025
arXiv: 2502.20033
代码: 未公开
领域: 推荐系统 / 优化理论
关键词: 成对比较, 协同过滤, 非凸矩阵分解, 投影梯度下降, 收敛保证

一句话总结¶

首次为基于成对比较数据的推荐系统非凸矩阵分解问题提供理论恢复保证：证明在warm start条件下，投影梯度下降以指数速率收敛到真实低秩特征矩阵，样本复杂度为近乎最优的 \(O(nr^2 \log n)\)，关键技术贡献是将matrix Bernstein不等式扩展到成对比较的采样矩阵结构。

研究背景与动机¶

领域现状¶

经典推荐系统通过矩阵补全（Matrix Completion）从用户评分数据中学习偏好：假设用户-物品效用矩阵 \(X^* = U^* \Sigma^* V^{*T}\) 是低秩的，从部分观测条目恢复完整矩阵。先前工作已为这一非凸问题建立了成熟的理论框架（Keshavan et al. 2010, Zheng & Lafferty 2016, Ge et al. 2016）。

核心问题¶

然而，成对比较数据（pairwise comparisons）在实际中同样普遍：用户点击其中一个选项本身就隐含了对被选项的偏好。比较数据相较评分有三大优势：(1) 自然消除用户评分偏差；(2) 避免评分离散化问题；(3) 比较两个物品认知负担低于给出绝对评分。

当用户 \(u\) 比较物品 \(i\) 和 \(j\) 时，选择 \(i\) 的概率为 \(g(x_{u,i}^* - x_{u,j}^*)\)，其中 \(g(\cdot)\) 是链接函数（如sigmoid）。目标是从稀疏比较数据中恢复低秩效用矩阵 \(X^*\) 的特征矩阵 \(Z^*\)。

已有工作的不足¶

Park et al. (2015) 和 Negahban et al. (2018) 为此问题提供了凸松弛版本的理论保证，但凸方法需要优化整个 \(n_1 \times n_2\) 的效用矩阵，计算代价高昂。实际中（如BPR算法 Rendle et al. 2009），人们使用非凸矩阵分解 \(X = UV^T\)，参数从 \(n_1 n_2\) 降至 \((n_1+n_2)r\)，计算效率大幅提升。但非凸版本缺乏理论保证，Negahban et al. (2018) 明确将此列为重要开放问题。

本文贡献¶

首次为比较数据的非凸矩阵分解提供收敛保证，填补了理论空白。

方法详解¶

整体框架¶

问题建模：\(X^* = U^* \Sigma^* V^{*T}\) 低秩效用矩阵 → 转换为对称形式 \(Z^* = [U^*; V^*] \Sigma^{*1/2}\) → 定义负对数似然损失 \(\mathcal{L}(Z)\) + 正则化 \(\mathcal{R}(Z)\) 消除尺度不变性 → 投影梯度下降恢复 \(Z^*\)

关键设计¶

1. 问题对称化与正则化¶

功能：将非对称矩阵分解 \(X = UV^T\) 转化为对称形式 \(Y = ZZ^T\)，其中 \(Z = [U; V] \in \mathbb{R}^{n \times r}\)。

正则化设计：添加 \(\mathcal{R}(Z) = \|Z^T D Z\|_F^2\)（\(D = \text{diag}(I_{n_1}, -I_{n_2})\)）消除尺度不变性，使目标函数为：

\[f(Z) = \mathcal{L}(Z) + \frac{\lambda}{4}\mathcal{R}(Z)\]

设 \(\lambda = \xi\gamma/4\) 可精确消除旋转不变性带来的不利项。

设计动机：原问题对 \(Z \to ZR\)（旋转）和 \((U, V) \to (UP^T, VP^{-1})\)（尺度）不变，这些对称性阻碍了强凸性的建立。正则化将问题约束到"平衡"解空间 \(\mathcal{H} = \{Z: \mathbf{1}^T V = 0\}\)。

2. 投影梯度下降（Algorithm 1）¶

算法流程：

\[Z_{t+1} = \mathcal{P}_\mathcal{H}(\mathcal{P}_\mathcal{C}(Z_t - \eta \nabla f(Z_t)))\]

两步投影： 1. \(\mathcal{P}_\mathcal{C}\)：将每行的 \(\ell_2\) 范数裁剪到 \(\beta = \frac{4}{3}\sqrt{\mu/n}\|Z_0\|_F\)，保持incoherence 2. \(\mathcal{P}_\mathcal{H}\)：投影到子空间 \(\mathcal{H}\)，消除平移不变性

设计动机：损失函数仅在incoherent矩阵区域内展现类强凸性质，投影保证迭代始终留在该区域。

3. 集中不等式的新技术（核心理论贡献）¶

挑战：经典矩阵补全中，采样矩阵 \(A\) 对应单个 \((u, i)\) 条目，可利用 Candès & Recht (2009) 的投影算子性质或二部图结构。但比较数据中，每个数据点对应 \((u; i, j)\) 三元组，采样矩阵结构不同：

\[A = \begin{bmatrix} 0 & e_u(e_i - e_j)^T \\ 0 & 0 \end{bmatrix}\]

这使得经典集中结果不再适用。

本文方法：从Matrix Bernstein不等式出发，定义辅助"对偶采样矩阵" \(B = e_u(e_i + e_j)^T\)，分别建立 \(\|S_\mathcal{D} - \bar{S}\|_2\) 和 \(\|B_\mathcal{D} - \bar{B}\|_2\) 的集中界，推导出类强凸和类光滑性质（Lemma 5.1 和 5.2）。

主定理（Theorem 4.1）¶

假设样本数 \(m \geq 10^7 (\mu r \kappa / \tau)^2 n \log(8n/\delta)\)，且初始点 \(Z_0\) 在真解 \(\tau/50\) 邻域内，步长 \(\eta\alpha \leq 2.5 \times 10^{-6} (\tau/\mu r \kappa)^2\)，则以概率 \(\geq 1-\delta\)：

\[\|\Delta(Z_t)\|_F^2 \leq \left(1 - \frac{\alpha\eta}{4}\right)^t \|\Delta(Z_0)\|_F^2\]

即指数收敛到真解。样本复杂度对问题规模的依赖为 \(O(nr^2 \log n)\)，近乎最优。

实验关键数据¶

仿真实验（合成数据）¶

设置	\((n_1, n_2)\)	秩 \(r\)	结论
不同初始化 (\(\vartheta \in \{0.5, 1, 2\}\))	(200,300) 和 (2000,3000)	3	均线性收敛，验证理论预测
不同数据量 \(m\)	(200,300) 和 (2000,3000)	3	\(m\) 超过理论门槛即线性收敛，否则误差不收敛到零
不同秩 \(r \in \{2,...,6\}\)	(2000,3000)	变化	误差随 \(r\) 增加，样本需求经验上近似 \(O(nr)\)

关键发现¶

Warm start在实践中不必要：理论要求初始点在真解附近，但仿真中随机初始化也能收敛
投影在实践中不必要：不做投影的普通梯度下降也能工作
理论常数保守：理论要求的样本量 \(c_0 = 10^7\) 远大于实际需要的 \(c_0 \approx 1/4\)
样本复杂度可能更优：实验显示 \(m\) 实际与 \(r\) 线性相关而非 \(r^2\)，存在理论改进空间

亮点与洞察¶

填补重要理论空白：BPR算法在推荐系统中使用超过15年，本文首次为其建立理论保证，回答了Negahban et al. (2018)提出的开放问题
对偶采样矩阵的技巧：引入 \(B = e_u(e_i + e_j)^T\) 处理三元组结构的集中问题，是将矩阵补全理论工具箱扩展到比较模型的关键创新
理论与实践的差距是正面信号：理论需要warm start和投影，实践中都不需要，说明问题的实际景观比理论分析更加friendly

局限与展望¶

假设无噪声观测：当前假设观测的是比较概率 \(g(x_{u,i}^* - x_{u,j}^*)\) 的期望值而非二值结果，扩展到噪声设置是重要方向
需要warm start：理论分析依赖初始点在真解附近，去除此假设（如证明所有局部极小都是全局极小）是开放问题
仅合成数据实验：缺乏真实推荐数据集（如Netflix）的验证，作者也承认当前缺乏公开的成对比较推荐数据集
常数过大：\(10^7\) 的样本复杂度前常数距实际情况差距大，精细化分析可能改善

评分¶

新颖性: ⭐⭐⭐⭐ 首次为比较数据非凸分解提供理论保证，填补重要空白
实验充分度: ⭐⭐⭐ 仅合成数据仿真验证，缺乏真实数据实验
写作质量: ⭐⭐⭐⭐ 理论陈述清晰，证明结构well-organized
价值: ⭐⭐⭐⭐ 对推荐系统理论社区有重要贡献，但实际影响受限于无噪声假设