问题建模: Model 参数 
, 输入 
, 给出预测值 
, 真实 label 为 
, 样本 
下的 Loss 为 
, 即: 模型参数为 
时, 评估 
的误差.
优化目标: 对于所有的 
, 找到最小的总 Loss / 平均 Loss: 
.
梯度优化思想: 
可能为极值点.
GD: Gradient Descent / FDG: Full data Gradient Descent
总梯度 / 全量数据平均梯度: 
更新 model 参数:
SGD: Stochastic Gradient Descent
随机选择样本: 
, 其中 
更新 model 参数:
Mini-batch Gradient Descent
随机选择 n 个样本: 
, 
更新 model 参数:
SAG: Stochastic Average Gradient Descent
每次只评估一个样本的梯度, 维护当前已经查询过的各个样本的梯度信息, 将这些针对不同样本求的梯度求和作为上述算法中的 d, 用 d 去近似
.
每次评估样本数变少, 迭代变快; 相较于 SGD 又收敛更快, 因为用的是全量数据梯度的近似估计来更新参数的. 即: SGD 的速度, GD 的收敛, 牺牲存储空间.
实际上是动态更新均值 d 的方法. (滑动平均法)
SAG (包括下面几种方法) 相较于 SGD 的 (核心) 区别: Build an Estimate of the Gradient (即上式的 d )
SVRG: Stochastic Variance Reduced Gradient Descent
过程可以看出, 两个 for 循环嵌套, 大的 for 循环评估全量数据, 小的 for 循环评估一个随机数据.
更新是通过这个式子实现的: 
在 
中, 
是在随机点 
处评估新得到的梯度项, 
是在 
中原来对应的 
处的梯度项. 他这里的评估并没有乘 
, 说明这一步和 SAG 是有区别的, 后面会解释这个区别.
在这个之后, 有两个选择, 即是随机选择或选择最后一项作为本次迭代的梯度.
:::danger
[已解决] 如何解释 “这种特殊的更新项来让方差有一个可以不断减少的上界” ?
_这种方差减少的特性应该是与那一项的评估以及两种选择有关, 这个还需要进一步仔细学习原文. _
~~猜想: 他这种上界不断减少应该是相对于 SGD 而言的, 然后策略类似于 FGD 与 SGD 交替使用, 所以会使 SGD 的随机性降低, 方差逐渐减小, 解逐渐收敛. ~~
可以看出, 这里利用的额外信息是: x 与 z 之间的强相关, 这时两者的协方差会变大, 进而使新的 x_z 的方差降低.
:::
SAGA
这个算法相当于时对 SAG 和 SVRG 的一个融合, 融合两者的优势.
在方差更新过程, 第 9 行是 SVRG 中的梯度更新策略. 但在最开始时, SVRG 是通过嵌套循环实现方差的更新的, 即每用 
评估若干次后, 重新对所有样本进行完整地评估 (评估 FGD 的值). 而 SAG 是对 FGD 的一种估计方式 (每次只更新一个样本的查询, 不断迭代, 逼近 FGD 的值). 这时, SAGA对上述两者做了融合, 即首先用 SAG 中的策略, 评估全部训练样本并记录下来, 然后用类似 SVRG 中 
的方法更新梯度和模型参数, 同时会用类似于 “ SAG 中动态更新 d 的方法”, 用 
的值动态地更新
和 
, 进而实现两者的融合.
本系列论文方法小结
全量数据计算 loss 后的梯度下降 FGD, 效果好收敛快, 但每次都要在整个数据集上评估, 因此时间长速度慢. 此时提出, 采用训练集中一个样本评估的方法 SGD, 迭代快速度快, 但收敛效果不好 (毕竟每次使用一个随机的样本, 每次基本用的样本都不一样).
后面的各种方法都是对两种方法的综合, 即想要综合 FGD 的收敛性能优势和 SGD 的时间性能优势. 最直观的想法是, 可以用 batch 形式的 Mini-batch GD 对两者做平衡.
从另一个角度思考, 能不能用随机的一个样本达到近似 FGD 的效果? 这时提出了 SAG 和 SVRG, 刚开始时做全量数据梯度评估, 后面每次迭代只评估一个样本的梯度, 用这个样本的梯度信息更新梯度信息, 得到全量梯度近似的评估. SAG 和 SVRG 采用了两种不同的方法评估全量梯度近似, SAG 采用 FGD 框架, SVRG 根据梯度查询的特点 (相邻查询的参数梯度之间相关性大, 因为目标函数是连续的), 设计了一种能降方差的梯度优化方案, 但在优化过程中需要不断评估全量数据梯度.
SAG 需要额外存储最近的梯度信息, 存储性能要求增加了; SVRG 构造的优化器框架存在两个 for 循环的嵌套, 时间性能相对较差. SAGA 则综合了 SAG 和 SVRG 两者的思想和优势, 用 SAG 的思想, 完成 SVRG 中全量数据评估的近似, 进而去除了 SVRG 中的循环嵌套 (降方差的更新方式, FGD 的框架可以快速收敛, 采用前置的全量数据评估而不是 for 循环的嵌套).