声明
先导知识：随机梯度下降法（SGD），矩阵分解。
本文是对学习 LIBMF 2.01 的备忘录，其中相当多的内容直接来自于论文: W.-S. Chin, Y. Zhuang, Y.-C. Juan, and C.-J. Lin. A Learning-rate Schedule for Stochastic Gradient Methods to Matrix Factorization. PAKDD, 2015.
另外可参考LIBMF分析的姊妹篇：FSPD算法与LIBMF API浅析
简介
RPCS 是一种在随机梯度下降过程中动态改变下降速率以提高效率的算法。此方法被用于分解矩阵的开源 API LIBMF （2.01）中，由台湾大学机器学习团队开发。
矩阵分解与SGD
运用SGD分解矩阵，更详细的说明请参考：FSPD算法与LIBMF API浅析的简介部分，这里引用损失函数：
$$\min{P, Q} \sum{u, v}((r_{u,v} - p_u^\mathrm{T}q_v)^2 - \lambda ||p_u||^2 - \lambda ||qv||^2) \label{opt} \tag{1}$$
SGD 需要分解矩阵 $R{u,v}$，求解出最优的 $P{k,u}$ 与 $Q{k,v}$， 其中 ${\lambda}$ 是正则化参数。
求解出梯度：
$$gu = \frac{1}{2} (-e{u,v} q_v + \lambda p_u) \label{gradP} \tag{2}$$
$$hv = \frac{1}{2} (-e{u,v} p_u + \lambda q_v) \label{gradQ} \tag{3}$$
其中，$e{u,v} = r{u,v} - p_u^\mathrm{T} q_v$
$P$, $Q$ 下降公式分别为：
$$p_u \leftarrow p_u - \eta g_u \label{descP} \tag{4}$$
$$q_v \leftarrow q_v - \eta h_v \label{descQ} \tag{5}$$
其中 $\eta$ 为下降速率。
下降速率方案
下降速率 $\eta$ 对梯度下降法有重要的影响，合适的 $\eta$ 往往能减小所需迭代下降的次数。
固定速率
固定速率 $\eta$，相比其他方法，无需计算 $\eta$ 的开销。
单调下降（MDS）
Monotonically Decreasing Schedule (MDS)方法，在第 $z$ 次下降中：
$$\eta^z = \frac{\alpha}{1 + \beta z^{1.5}}$$
其中 $\alpha$, $\beta$ 为指定常数。$\eta$ 随着迭代的进行逐渐下降，类似的公式就不在此列举。
Bold-driver Schedule (BDS)
设 $\Delta_z$ 为损失函数 $(\ref{opt})$ 的值在第z次迭代与在前次迭代之差，BDS的方案是：
if $\Deltaz \lt 0$ then $\eta{z+1} = \alpha \etaz$ else $\eta{z+1} = \beta \eta_z$
其中 $\alpha \gt 1$ 而 $0 \lt \beta \lt 1$。也就是说，当损失函数成功下降时，$\eta$ 增大，反之减小。
Per-coordinate Schedule (PCS)
研发者给出中间矩阵 $G_u$ 和 $P_v$，并给出更新公式 ：
显然 $G_u$, $P_v$ 与 $g_u$, $p_v$ 相关。然后转换下降公式 $(\ref{descP})$, $(\ref{descQ})$ 为：
$$p_u \leftarrow p_u - \eta G_u^{-1/2} g_u \label{PCSDescP} \tag{6}$$
$$q_v \leftarrow q_v - \eta H_v^{-1/2} h_v \label{PCSDescQ} \tag{7}$$
RPCS
Reduced Per-coordinate Schedule (RPCS) 在 RCS 基础上改进并用于矩阵分解。
各元素统一 $\eta$
如果以 $p_u$ 各元素为单位（而非向量）思考式子 $(\ref{PCSDescP})$，可发现每个元素的下降速率是不同的。这造成的问题是，$G_u$ 必须记录每个 $p_u$ 元素的下降速率，共 $k$ 个，考虑到整个 $P$ 矩阵，将消耗 $m \times k$ 个单元。
RPCS的方案是，将 $G$, $H$ 的更新公式改为：
$$G_u \leftarrow G_u + \frac{g_u^\mathrm{T}g_u}{k} \label{RPCSUpdateG} \tag{8}$$
$$H_v \leftarrow H_v + \frac{h_v^\mathrm{T}h_v}{k}$$
$G_v$ 变成了标量，只需1个存储单元，空间开销大大减小。$H_v$ 同理。而且，研究者证明，使用相同的 $\eta$ 对 PCS 方法几乎没影响。
合并循环
研究者注意到 $p_u$ 是一个向量，一次更新需要一个循环，而每次循环需要计算一次 $(g_u)_i$ (即 $g_u$ 的当前更新的第 $i$ 个元素）。同时，$G_u$ 每次更新同样需要一个循环，并且每次需计算 $(g_u)_i$。RPCS 利用这一点，将2个循环合并而无需重复计算 $(g_u)_i$。$qu$ 同理。作者提供的一次迭代伪代码：
Twin Learners (TL)
RPCS 的下降速率总是下降的，然而，作者发现，在经历了头几次迭代后，下降速率急剧下降，甚至在第一次迭代后，下降速率就已经减半。其原因可能是，因为最初没有经过下降，用随机方法初始化的 $P$ 与最优解相差较大，使得梯度误差 $e_{u,v}$，梯度 $g_u$ 较大，导致 $G_u$ 过大，下降速率急剧下降。
TL 方案将 $pu$ 的更新分为2个部分，$p{1:k}$ （取 $pu$ 1至个元素构成一个向量）与 $p{(k+1):u}$， 前者称为慢速学习部分，后者称为快速学习部分。相应有 $G{1:k}$ 与 $G{(k+1):u}$，它们同样分别用式子 $(\ref{RPCSUpdateG})$ 更新。与 RPCS 不同的是，在第一次下降中，$G_{(k+1):u}$ 不更新，也就是说，快速学习部分第一次迭代速率不作下降。
作者的实验表明，慢速学习部分相对 RPCS 在头几次迭代后，下降速率下降得更大，但快速学习部分，因为慢速学习部分“吸收了”误差带来的影响，保持着较高的下降速率。$q_v$ 同理。TL 使得下降次数相对 RPCS 有显著减少。