梯度下降优化算法综述

转自：https://www.cnblogs.com/lxjshuju/p/7397048.html#reference_10

 该文翻译自An overview of gradient descent optimization algorithms。

   总所周知。梯度下降算法是机器学习中使用非常广泛的优化算法，也是众多机器学习算法中最经常使用的优化方法。差点儿当前每一个先进的(state-of-the-art)机器学习库或者深度学习库都会包含梯度下降算法的不同变种实现。

可是，它们就像一个黑盒优化器，非常难得到它们优缺点的实际解释。 
   这篇文章旨在提供梯度下降算法中的不同变种的介绍，帮助使用者依据具体须要进行使用。 
   这篇文章首先介绍梯度下降算法的三种框架，然后介绍它们所存在的问题与挑战。接着介绍一些怎样进行改进来解决这些问题，随后，介绍怎样在并行环境中或者分布式环境中使用梯度下降算法。

最后，指出一些有利于梯度下降的策略。

   梯度下降算法是通过沿着目标函数J(θ)參数θ∈ℜ的梯度(一阶导数)相反方向−∇θJ(θ)来不断更新模型參数来到达目标函数的极小值点（收敛）。更新步长为η。具体的介绍參见：梯度下降。

三种梯度下降优化框架

   有三种梯度下降算法框架，它们不同之处在于每次学习(更新模型參数)使用的样本个数。每次更新使用不同的样本会导致每次学习的准确性和学习时间不同。

• 全量梯度下降(Batch gradient descent) 
     每次使用全量的训练集样本来更新模型參数，即： 
  
  θ=θ−η⋅∇θJ(θ)

   其代码例如以下：

for i in range(epochs):
    params_grad = evaluate_gradient(loss_function,data,params)
    params = params - learning_rate * params_grad

   epochs 是用户输入的最大迭代次数。通过上诉代码能够看出。每次使用所有训练集样本计算损失函数loss_function的梯度params_grad，然后使用学习速率learning_rate朝着梯度相反方向去更新模型的每一个參数params。一般各现有的一些机器学习库都提供了梯度计算api。假设想自己亲手写代码计算，那么须要在程序调试过程中验证梯度计算是否正确，具体验证方法能够參见：这里。 
   全量梯度下降每次学习都使用整个训练集，因此其优点在于每次更新都会朝着正确的方向进行，最后能够保证收敛于极值点(凸函数收敛于全局极值点，非凸函数可能会收敛于局部极值点)。可是其缺点在于每次学习时间过长，而且假设训练集非常大以至于须要消耗大量的内存，而且全量梯度下降不能进行在线模型參数更新。

• 随机梯度下降(Stochastic gradient descent)

   随机梯度下降算法每次从训练集中随机选择一个样本来进行学习，即： 

θ=θ−η⋅∇θJ(θ;xi;yi)

   批量梯度下降算法每次都会使用所有训练样本。因此这些计算是冗余的，由于每次都使用全然同样的样本集。

而随机梯度下降算法每次仅仅随机选择一个样本来更新模型參数，因此每次的学习是非常高速的。而且能够进行在线更新。 
   其代码例如以下：

for i in range(epochs):
    np.random.shuffle(data)
    for example in data:
        params_grad = evaluate_gradient(loss_function,example,params)
        params = params - learning_rate * params_grad

   随机梯度下降最大的缺点在于每次更新可能并不会依照正确的方向进行，因此能够带来优化波动(扰动)。例如以下图：

 
图1 SGD扰动来源

   只是从还有一个方面来看。随机梯度下降所带来的波动有个优点就是。对于相似盆地区域（即非常多局部极小值点）那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到还有一个更好的局部极小值点，这样便可能对于非凸函数，终于收敛于一个较好的局部极值点，甚至全局极值点。

   由于波动，因此会使得迭代次数（学习次数）增多，即收敛速度变慢。只是终于其会和全量梯度下降算法一样，具有同样的收敛性。即凸函数收敛于全局极值点，非凸损失函数收敛于局部极值点。

• 小批量梯度下降(Mini-batch gradient descent)

   Mini-batch梯度下降综合了batch梯度下降与stochastic梯度下降。在每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择m,m<n个样本进行学习，即： 

θ=θ−η⋅∇θJ(θ;xi:i+m;yi:i+m)

   其代码例如以下：

for i in range(epochs):
    np.random.shuffle(data)
    for batch in get_batches(data, batch_size=50):
        params_grad = evaluate_gradient(loss_function,batch,params)
        params = params - learning_rate * params_grad

   相对于随机梯度下降，Mini-batch梯度下降减少了收敛波动性，即减少了參数更新的方差，使得更新更加稳定。

相对于全量梯度下降，其提高了每次学习的速度。而且其不用操心内存瓶颈从而能够利用矩阵运算进行高效计算。一般而言每次更新随机选择[50,256]个样本进行学习。可是也要依据具体问题而选择，实践中能够进行多次试验，选择一个更新速度与更次次数都较适合的样本数。

   mini-batch梯度下降尽管能够保证收敛性。

mini-batch梯度下降经常使用于神经网络中。

问题与挑战

   尽管梯度下降算法效果非常好，而且广泛使用，但同一时候其也存在一些挑战与问题须要解决：

• 选择一个合理的学习速率非常难。

  假设学习速率过小，则会导致收敛速度非常慢。

  假设学习速率过大，那么其会阻碍收敛，即在极值点附近会振荡。

• 学习速率调整(又称学习速率调度，Learning rate schedules)[11]试图在每次更新过程中，改变学习速率，如退火。一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈值。

  不管哪种调整方法，都须要事先进行固定设置。这边便无法自适应每次学习的数据集特点[10]。

• 模型所有的參数每次更新都是使用同样的学习速率。

  假设数据特征是稀疏的或者每一个特征有着不同的取值统计特征与空间，那么便不能在每次更新中每一个參数使用同样的学习速率。那些非常少出现的特征应该使用一个相对较大的学习速率。

• 对于非凸目标函数。easy陷入那些次优的局部极值点中，如在神经网路中。

  那么怎样避免呢。

  Dauphin[19]指出更严重的问题不是局部极值点，而是鞍点(These saddle points are usually surrounded by a plateau of the same error, which makes it notoriously hard for SGD to escape, as the gradient is close to zero in all dimensions.)。

梯度下降优化算法

   以下将讨论一些在深度学习社区中经常使用用来解决上诉问题的一些梯度优化方法。只是并不包含在高维数据中不可行的算法，如牛顿法。

Momentum

   假设在峡谷地区(某些方向较还有一些方向上陡峭得多。常见于局部极值点)[1]。SGD会在这些地方附近振荡，从而导致收敛速度慢。

这样的情况下，动量(Momentum)便能够解决[2]。动量在參数更新项中加上一次更新量(即动量项),即： 

νt=γνt−1+η ∇θJ(θ)

θ=θ−νt

当中动量项超參数γ<1通常是小于等于0.9。

其作用例如以下图所看到的： 
 
图2 没有动量 
 
图3 加上动量

   加上动量项就像从山顶滚下一个球，求往下滚的时候累积了前面的动量(动量不断添加)。因此速度变得越来越快，直到到达终点。同理，在更新模型參数时，对于那些当前的梯度方向与上一次梯度方向同样的參数。那么进行加强，即这些方向上更快了；对于那些当前的梯度方向与上一次梯度方向不同的參数，那么进行削减。即这些方向上减慢了。因此能够获得更快的收敛速度与减少振荡。

NAG[7]

   从山顶往下滚的球会盲目地选择斜坡。更好的方式应该是在遇到倾斜向上之前应该减慢速度。 
   Nesterov accelerated gradient(NAG,涅斯捷罗夫梯度加速)不仅添加了动量项。而且在计算參数的梯度时，在损失函数中减去了动量项，即计算∇θJ(θ−γνt−1)，这样的方式预估了下一次參数所在的位置。即： 

νt=γνt−1+η⋅∇θJ(θ−γνt−1)

θ=θ−νt

例如以下图所看到的： 
 
图4 NAG更新

   具体介绍能够參见Ilya Sutskever的PhD论文[9]。假设动量因子參数γ=0.9，首先计算当前梯度项，如上图小蓝色向量，然后加上动量项，这样便得到了大的跳跃，如上图大蓝色的向量。

这便是仅仅包含动量项的更新。

而NAG首先来一个大的跳跃（动量项)。然后加上一个小的使用了动量计算的当前梯度（上图红色向量）进行修正得到上图绿色的向量。

这样能够阻止过快更新来提高响应性，如在RNNs中[8]。 
   通过上面的两种方法，能够做到每次学习过程中能够依据损失函数的斜率做到自适应更新来加速SGD的收敛。下一步便须要对每一个參数依据參数的重要性进行各自自适应更新。

Adagrad

   Adagrad[3]也是一种基于梯度的优化算法，它能够对每一个參数自适应不同的学习速率，对稀疏特征，得到大的学习更新，对非稀疏特征，得到较小的学习更新，因此该优化算法适合处理稀疏特征数据。Dean等[4]发现Adagrad能够非常好的提高SGD的鲁棒性。google便用起来训练大规模神经网络(看片识猫:recognize cats in Youtube videos)。Pennington等[5]在GloVe中便使用Adagrad来训练得到词向量(Word Embeddings), 频繁出现的单词赋予较小的更新，不经常出现的单词则赋予较大的更新。 
   在前述中，每一个模型參数θi使用同样的学习速率η。而Adagrad在每一个更新步骤中对于每一个模型參数θi使用不同的学习速率ηi，设第t次更新步骤中，目标函数的參数θi梯度为gt,i，即： 

gt,i=∇θJ(θi)

   那么SGD更新方程为： 

θt+1,i=θt,i−η⋅gt,i

   而Adagrad对每一个參数使用不同的学习速率。其更新方程为： 

θt+1,i=θt,i−ηGt,ii+ϵ‾‾‾‾‾‾‾√⋅gt,i

当中。Gt∈ℜd×d是一个对角矩阵，当中第i行的对角元素eii为过去到当前第i个參数θi的梯度的平方和，epsilon是一个平滑參数。为了使得分母不为0(通常ϵ=1e−8)。另外假设分母不开根号，算法性能会非常糟糕。 
   进一步。将所有Gt,ii,gt,i 的元素写成向量Gt,gt，这样便能够使用向量点乘操作： 

θt+1=θt−ηGt+ϵ‾‾‾‾‾‾√⊙gt

   Adagrad主要优势在于它能够为每一个參数自适应不同的学习速率，而一般的人工都是设定为0.01。

同一时候其缺点在于须要计算參数梯度序列平方和，而且学习速率趋势是不断衰减终于达到一个非常小的值。

下文中的Adadelta便是用来解决该问题的。

### Adadelta    Adadelta[[6]](#reference_6)是Adagrad的一种扩展，为了减少Adagrad中学习速率衰减过快问题。其改进了三处，一是使用了窗体w；二是对于參数梯度历史窗体序列(不包含当前)不再使用平方和。而是使用均值取代。三是终于的均值是历史窗体序列均值与当前梯度的时间衰减加权平均。即：

E[g2]t=γE[g2]t−1+(1−γ)g2t

当中γ与动量项中的一样，都是

RMSprop

   事实上RMSprop是Adadelta的中间形式，也是为了减少Adagrad中学习速率衰减过快问题，即： 

E[g2]t=γE[g2]t−1+(1−γ)g2t

θt+1=θt−ηE[g2]t+ϵ‾‾‾‾‾‾‾‾‾‾√⊙gt

Hinton建议γ=0.9,η=0.001

Adam

   Adaptive Moment Estimation(Adam) 也是一种不同參数自适应不同学习速率方法，与Adadelta与RMSprop差别在于。它计算历史梯度衰减方式不同。不使用历史平方衰减。其衰减方式相似动量。例如以下： 

mt=β1mt−1+(1−β1)gt

vt=β2vt−1+(1−beta2)g2t

   mt与vt各自是梯度的带权平均和带权有偏方差，初始为0向量，Adam的作者发现他们倾向于0向量(接近于0向量)，特别是在衰减因子(衰减率)β1,β2接近于1时。

为了改进这个问题，对mt与vt进行偏差修正(bias-corrected)： 

mt^=mt1−betat1

vt^=vt1−betat2

   终于，Adam的更新方程为： 

θt+1=θt−ηvt^‾‾√+ϵmt^

论文中建议默认值：β1=0.9。β2=0.999，ϵ=10−8。

论文中将Adam与其它的几个自适应学习速率进行了比較，效果均要好。

各优化方法比較

   以下两幅图可视化形象地比較上述各优化方法。具体參见这里，如图： 
 
图5 SGD各优化方法在损失曲面上的表现

   从上图能够看出。 Adagrad、Adadelta与RMSprop在损失曲面上能够马上转移到正确的移动方向上达到高速的收敛。而Momentum 与NAG会导致偏离(off-track)。

同一时候NAG能够在偏离之后高速修正其路线，由于其依据梯度修正来提高响应性。

 
图6 SGD各优化方法在损失曲面鞍点处上的表现

   从上图能够看出。在鞍点（saddle points）处(即某些维度上梯度为零，某些维度上梯度不为零)，SGD、Momentum与NAG一直在鞍点梯度为零的方向上振荡。非常难打破鞍点位置的对称性。Adagrad、RMSprop与Adadelta能够非常快地向梯度不为零的方向上转移。 
   从上面两幅图能够看出，自适应学习速率方法(Adagrad、Adadelta、RMSprop与Adam)在这些场景下具有更好的收敛速度与收敛性。

怎样选择SGD优化器

   假设你的数据特征是稀疏的。那么你最好使用自适应学习速率SGD优化方法(Adagrad、Adadelta、RMSprop与Adam)。由于你不须要在迭代过程中对学习速率进行人工调整。 
   RMSprop是Adagrad的一种扩展，与Adadelta相似，可是改进版的Adadelta使用RMS去自己主动更新学习速率，而且不须要设置初始学习速率。而Adam是在RMSprop基础上使用动量与偏差修正。

RMSprop、Adadelta与Adam在相似的情形下的表现几乎相同。Kingma[15]指出收益于偏差修正，Adam略优于RMSprop，由于其在接近收敛时梯度变得更加稀疏。

因此，Adam可能是眼下最好的SGD优化方法。 
   有趣的是，近期非常多论文都是使用原始的SGD梯度下降算法，而且使用简单的学习速率退火调整（无动量项）。现有的已经表明：SGD能够收敛于最小值点，可是相对于其它的SGD。它可能花费的时间更长。而且依赖于鲁棒的初始值以及学习速率退火调整策略，而且easy陷入局部极小值点。甚至鞍点。因此，假设你在意收敛速度或者训练一个深度或者复杂的网络。你应该选择一个自适应学习速率的SGD优化方法。

并行与分布式SGD

   假设你处理的数据集非常大。而且有机器集群能够利用。那么并行或分布式SGD是一个非常好的选择。由于能够大大地提高速度。

SGD算法的本质决定其是串行的(step-by-step)。因此怎样进行异步处理便是一个问题。

尽管串行能够保证收敛。可是假设训练集大。速度便是一个瓶颈。假设进行异步更新，那么可能会导致不收敛。

以下将讨论怎样进行并行或分布式SGD，并行通常是指在同一机器上进行多核并行。分布式是指集群处理。

• Hogwild 
     Niu[23]提出了被称为Hogwild的并行SGD方法。该方法在多个CPU时间进行并行。处理器通过共享内存来訪问參数，而且这些參数不进行加锁。它为每一个cpu分配不重叠的一部分參数（分配相互排斥）。每一个cpu仅仅更新其负责的參数。该方法仅仅适合处理数据特征是稀疏的。该方法差点儿能够达到一个最优的收敛速度。由于cpu之间不会进行同样信息重写。

• Downpour SGD 
     Downpour SGD是Dean[4]提出的在DistBelief(Google TensorFlow的前身)使用的SGD的一个异步变种。它在训练子集上训练同一时候多个模型副本。这些副本将各自的更新发送到參数server(PS,parameter server)，每一个參数server仅仅更新相互排斥的一部分參数。副本之间不会进行通信。因此可能会导致參数发散而不利于收敛。

• Delay-tolerant Algorithms for SGD 
     McMahan与Streeter[12]扩展AdaGrad。通过开发延迟容忍算法(delay-tolerant algorithms)。该算法不仅自适应过去梯度，而且会更新延迟。该方法已经在实践中表明是有效的。

• TensorFlow 
     TensorFlow[13]是Google开源的一个大规模机器学习库，它的前身是DistBelief。它已经在大量移动设备上或者大规模分布式集群中使用了。已经经过了实践检验。其分布式实现是基于图计算，它将图切割成多个子图。每一个计算实体作为图中的一个计算节点。他们通过Rend/Receive来进行通信。具体參见这里。

• Elastic Averaging SGD 
     Zhang等[14]提出Elastic Averaging SGD(EASGD)，它通过一个elastic force(存储參数的參数server中心）来连接每一个work来进行參数异步更新。This allows the local variables to fluctuate further from the center variable, which in theory allows for more exploration of the parameter space. They show empirically that this increased capacity for exploration leads to improved performance by finding new local optima. 这句话不太懂，须要去看论文。

很多其它的SGD优化策略

   接下来介绍很多其它的SGD优化策略来进一步提高SGD的性能。

另外还有众多其它的优化策略。能够參见[22]。

• Shuffling and Curriculum Learning 
     为了使得学习过程更加无偏，应该在每次迭代中随机打乱训练集中的样本。 
     还有一方面，在非常多情况下。我们是逐步解决这个问题的。而将训练集依照某个有意义的顺序排列会提高模型的性能和SGD的收敛性。怎样将训练集建立一个有意义的排列被称为Curriculum Learning[16]。 
     Zaremba与Sutskever[17]在使用Curriculum Learning来训练LSTMs以解决一些简单的问题中，表明一个相结合的策略或者混合策略比对训练集依照依照训练难度进行递增排序要好。（表示不懂。衰）

• Batch normalization 
     为了方便训练，我们一般会对參数依照0均值1方差进行初始化，随着不断训练，參数得到不同程度的更新，这样这些參数会失去0均值1方差的分布属性，这样会减少训练速度和放大參数变化随着网络结构的加深。 
     Batch normalization[18]在每次mini-batch反向传播之后又一次对參数进行0均值1方差标准化。这样能够使用更大的学习速率，以及花费更少的精力在參数初始化点上。

  Batch normalization充当着正则化、减少甚至消除掉Dropout的必要性。

• Early stopping 
     在验证集上假设连续的多次迭代过程中损失函数不再显著地减少。那么应该提前结束训练，具体參见NIPS 2015 Tutorial slides，或者參见防止过拟合的一些方法。

• Gradient noise 
     Gradient noise[21]即在每次迭代计算梯度中加上一个高斯分布N(0,σ2t)的随机误差，即 
  

  gt,i=gt,i+N(0,σ2t)
  
     高斯误差的方差须要进行退火： 
  
  σ2t=η(1+t)γ
  
     对梯度添加随机误差会添加模型的鲁棒性，即使初始參数值选择地不好，并适合对特别深层次的负责的网络进行训练。其原因在于添加随机噪声会有很多其它的可能性跳过局部极值点并去寻找一个更好的局部极值点，这样的可能性在深层次的网络中更常见。

总结

   在上文中，对梯度下降算法的三种框架进行了介绍。而且mini-batch梯度下降是使用最广泛的。随后，我们重点介绍了SGD的一些优化方法：Momentum、NAG、Adagrad、Adadelta、RMSprop与Adam。以及一些异步SGD方法。最后，介绍了一些提高SGD性能的其它优化建议，如：训练集随机洗牌与课程学习(shuffling and curriculum learning)、batch normalization,、early stopping与Gradient noise。

   希望这篇文章能给你提供一些关于怎样使用不同的梯度优化算法方面的指导。假设还有很多其它的优化建议或方法还望大家提出来？或者你使用什么技巧和方法来更好地训练SGD能够一起交流？Thanks。

引用

[1] Sutton, R. S. (1986). Two problems with backpropagation and other steepest-descent learning procedures for networks. Proc. 8th Annual Conf. Cognitive Science Society.

[2] Qian, N. (1999). On the momentum term in gradient descent learning algorithms. Neural Networks : The Official Journal of the International Neural Network Society, 12(1), 145–151. http://doi.org/10.1016/S0893-6080(98)00116-6.

[3] Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159. Retrieved from http://jmlr.org/papers/v12/duchi11a.html.

[4] Dean, J., Corrado, G. S., Monga, R., Chen, K., Devin, M., Le, Q. V, … Ng, A. Y. (2012). Large Scale Distributed Deep Networks. NIPS 2012: Neural Information Processing Systems, 1–11. http://doi.org/10.1109/ICDAR.2011.95.

[5] Pennington, J., Socher, R., & Manning, C. D. (2014). Glove: Global Vectors for Word Representation. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, 1532–1543. http://doi.org/10.3115/v1/D14-1162.

[6] Zeiler, M. D. (2012). ADADELTA: An Adaptive Learning Rate Method. Retrieved from http://arxiv.org/abs/1212.5701.

[7] Nesterov, Y. (1983). A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Doklady ANSSSR (translated as Soviet.Math.Docl.), vol. 269, pp. 543– 547.

[8] Bengio, Y., Boulanger-Lewandowski, N., & Pascanu, R. (2012). Advances in Optimizing Recurrent Networks. Retrieved from http://arxiv.org/abs/1212.0901.

[9] Sutskever, I. (2013). Training Recurrent neural Networks. PhD Thesis.

[10] Darken, C., Chang, J., & Moody, J. (1992). Learning rate schedules for faster stochastic gradient search. Neural Networks for Signal Processing II Proceedings of the 1992 IEEE Workshop, (September), 1–11. http://doi.org/10.1109/NNSP.1992.253713.

[11] H. Robinds and S. Monro, “A stochastic approximation method,” Annals of Mathematical Statistics, vol. 22, pp. 400–407, 1951.

[12] Mcmahan, H. B., & Streeter, M. (2014). Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning. Advances in Neural Information Processing Systems (Proceedings of NIPS), 1–9. Retrieved from http://papers.nips.cc/paper/5242-delay-tolerant-algorithms-for-asynchronous-distributed-online-learning.pdf.

[13] Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., … Zheng, X. (2015). TensorFlow : Large-Scale Machine Learning on Heterogeneous Distributed Systems.

[14] Zhang, S., Choromanska, A., & LeCun, Y. (2015). Deep learning with Elastic Averaging SGD. Neural Information Processing Systems Conference (NIPS 2015), 1–24. Retrieved from http://arxiv.org/abs/1412.6651.

[15] Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13

[16] Bengio, Y., Louradour, J., Collobert, R., & Weston, J. (2009). Curriculum learning. Proceedings of the 26th Annual International Conference on Machine Learning, 41–48. http://doi.org/10.1145/1553374.1553380.

[17] Zaremba, W., & Sutskever, I. (2014). Learning to Execute, 1–25. Retrieved from http://arxiv.org/abs/1410.4615.

[18] Ioffe, S., & Szegedy, C. (2015). Batch Normalization : Accelerating Deep Network Training by Reducing Internal Covariate Shift. arXiv Preprint arXiv:1502.03167v3.

[19] Dauphin, Y., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. arXiv, 1–14. Retrieved from http://arxiv.org/abs/1406.2572.

[20] Sutskever, I., & Martens, J. (2013). On the importance of initialization and momentum in deep learning. http://doi.org/10.1109/ICASSP.2013.6639346.

[21] Neelakantan, A., Vilnis, L., Le, Q. V., Sutskever, I., Kaiser, L., Kurach, K., & Martens, J. (2015). Adding Gradient Noise Improves Learning for Very Deep Networks, 1–11. Retrieved from http://arxiv.org/abs/1511.06807.

[22] LeCun, Y., Bottou, L., Orr, G. B., & Müller, K. R. (1998). Efficient BackProp. Neural Networks: Tricks of the Trade, 1524, 9–50. http://doi.org/10.1007/3-540-49430-8_2.

[23] Niu, F., Recht, B., Christopher, R., & Wright, S. J. (2011). Hogwild ! : A Lock-Free Approach to Parallelizing Stochastic Gradient Descent, 1–22.

[24] Duchi et al. [3] give this matrix as an alternative to the full matrix containing the outer products of all previous gradients, as the computation of the matrix square root is infeasible even for a moderate number of parameters dd.