复合优化问题如下： 其中
为可微函数(可能非凸)，
可能为不可微函数。上述优化问题出现在很多应用领域中，例如压缩感知、图像处理、机器学习等，如何高效求解该问题是近年来的热门课题。
需要注意的是，许多实际问题并不直接具有这里介绍的算法所能处理的形式，需要利用拆分、引入辅助变量等技巧将其进行等价变形，最终化为合适的优化问题。以一图开始~
在机器学习、图像处理领域中，许多模型包含两部分：一部分是误差项，一般为光滑函数；另外一部分是正则项，可能为非光滑函数，用来保证求解问题的特殊结构。由于有非光滑部分的存在，此类问题属于非光滑的优化问题，可以考虑使用次梯度算法进行求解。然而次梯度算法并不能充分利用光滑部分的信息，也很难在迭代中保证非光滑项对应的解的结构信息，这使得次梯度算法在求解这类问题时往往收敛较慢。
近似点梯度算法，它能克服次梯度算法的缺点，充分利用光滑部分的信息，并在迭代过程中显式地保证解的结构，从而能够达到和求解光滑问题的梯度算法相近的收敛速度。引入邻近算子，它是近似点梯度算法中处理非光滑部分的关键，进而得到近似点梯度算法的迭代公式。
邻近算子是处理非光滑问题的一个非常有效的工具，也与许多算法的设计密切相关。
邻近算子：对于凸函数，其临近算子定义如下
可以看到，邻近算子的目的是求解一个距
不算太远的点，并使函数值
也相对较小。
定理：如果是适当的闭凸函数，则对任意的
，
的值存在且唯一。
上述定理表明，式(2)定义中的优化问题的解是存在且唯一的,因此可使用邻近算子去构建迭代公式。
临近算子与次梯度关系：如果为适当的闭凸函数，则有
邻近算子的计算可以看成是次梯度算法的隐式公式（后向迭代），这实际是近似点算法的迭代公式。对于非光滑情形，由于次梯度不唯一，显式公式的迭代并不唯一，而隐式公式却能得到唯一解。此外在步长的选择上面，隐式公式也要优于显式公式。
邻近算子实例：
除了直接利用定义计算，很多时候可以利用已知邻近算子的结果，计算其他邻近算子。
邻近算子的运算规则：
运用上述简单的规则，可以求解更复杂的邻近算子。
对于一般的复合函数，很难给出其邻近算子的显式解。不过当外层函数的邻近算子有显式解且内层函数是特殊的仿射函数的时候，求解复合函数的邻近算子就会容易得多。
仿射变换与邻近算子：
闭凸集上的投影：
近似点梯度法的思想非常简单： 注意到有两部分，对于光滑部分
做梯度下降，对于非光滑部分
使用邻近算子，则近似点梯度法的迭代公式为:
其中
为迭代步长，可以为一个常数或由线搜索得出。近似点梯度法跟众多算法都有很强的联系，在一些特定条件下，近似点梯度法还可以转化为其他算法。
迭代公式变为梯度下降法： 迭代公式变为投影梯度法：
近似点梯度法计算流程总结如下：
近似点梯度法本质上是对光滑部分做显式的梯度下降，关于非光滑部分做隐式的梯度下降，近似点梯度算法可以形式上写成：
LASSO 问题求解：
即第一步做梯度下降，第二步做收缩。特别地，第二步收缩算子保证了迭代过程中解的稀疏结构。这也解释了为什么近似点梯度算法效果好的原因。如下图所示。
可以看到结合线搜索的BB 步长能够显著提高算法的收敛速度，且比光滑化梯度法收敛得更快。
低秩矩阵恢复：考虑低秩矩阵恢复模型
小波模型求解：
平衡小波模型求解：
近似点梯度算法的收敛速度：如果光滑部分的梯度是利普希茨连续的，则目标函数的收敛速度可以达到。Nesterov 分别在1983 年、1988 年和2005 年提出了三种改进的一阶算法，收敛速度能达到
。开始由于牛顿法更快的收敛速度，Nesterov加速算法并没有得到重视。但近年来，随着数据量的增大，牛顿型方法由于其过大的计算复杂度，不便于有效地应用到实际中，Nesterov 加速算法作为一种快速的一阶算法重新被挖掘出来并迅速流行起来。Beck 和Teboulle 就在2008 年给出了Nesterov 在1983 年提出的算法的近似点梯度法版本—FISTA。
考虑如下优化问题： 其中
是连续可微的凸函数且梯度是利普希茨连续的(利普希茨常数是
），
为适当的闭凸函数。
FISTA 算法：第一步沿着前两步的计算方向计算一个新点，第二步在该新点处做一步近似点梯度迭代，即
下图给出FISTA 算法的迭代序列图。
可以看到这一做法对每一步迭代的计算量几乎没有影响，而带来的效果是显著的。如步长满足，则其收敛速度达到了
的条件为：
完整的FISTA 算法计算流程如下：
为了对算法做更好的推广，可以给出FISTA 算法的一个等价变形，只是把原来算法中的第一步拆成两步迭代，当且取固定步长时，两者时等价的。其算法计算流程如下：
每一次的起始步长取为前一步的步长，通过不断指数式地减小步长，得到如下算法：
在改变步长的同时改变参数，形成如下算法：
总的来说，固定步长的FISTA 算法对于步长的选取是较为保守的，为了保证收敛，有时不得不选取一个很小的步长，这使得固定步长的FISTA 算法收敛较慢。如果采用线搜索，则在算法执行过程中会有很大机会选择符合条件的较大步长，因此线搜索可能加快算法的收敛，但代价就是每一步迭代的复杂度变高。在实际的FISTA 算法中，需要权衡固定步长和线搜索算法的利弊，从而选择针对特定问题的高效算法。
原始的FISTA 算法不是一个下降算法，这里给出一个FISTA 的下降算法变形。在计算邻近算子之后，并不立即选取此点作为新的迭代点，而是检查函数值在当前点处是否下降，只有当函数值下降时才更新迭代点。假设经过近似点映射之后的点为，则对当前点 做如下更新:
完整的下降FISTA 算法计算流程如下所示：
第二类Nesterov 加速算法如下所示：
第二类Nesterov 加速算法的一步迭代可参考下图。第二类Nesterov 加速算法中的三个序列都可以保证在定义域内。而FISTA 算法中的序列
不一定在定义域内。
第三类Nesterov 加速算法如下图所示：
第三类Nesterov加速算法计算 时需要利用全部已有的
。第二类和第三类Nesterov 加速算法取
时，都具有
的收敛速度。
除了针对凸问题的加速算法，还有针对非凸复合优化问题的加速算法。要求是可微的且梯度是利普希茨连续的,非凸复合优化问题的加速梯度法算法如下所示。
在非凸函数情形下，一阶算法一般只能保证收敛到一个稳定点，并不能保证收敛到最优解，因此无法用函数值与最优值的差来衡量优化算法解的精度。
LASSO 问题求解：FISTA 算法三类加速算法迭代公式如下图所示：
求解结果如下图所示。
就固定步长而言，FISTA 算法相较于第二类Nesterov加速算法收敛得略快一些，也可注意到FISTA 算法是非单调算法。同时，BB步长和线搜索技巧可以加速算法的收敛速度。此外，带线搜索的近似点梯度法可以比带线搜索的FISTA 算法更快收敛。
小波模型求解：FISTA 算法和第二类Nesterov 加速算法迭代公式如下
平衡小波模型求解：FISTA 算法和第二类Nesterov 加速算法迭代公式如下
对于一般形式的目标函数，可以用近似点算法，该算法是近似点梯度算法的一种特殊情况。
考虑一般优化问题如下： 其中
为适当闭凸函数，并不要求其可微或连续的。对于不可微的，可以用次梯度算法，但是该方法往往收敛较慢，且收敛条件比较苛刻。也可以考虑如下隐式公式的次梯度算法：
类似于之前的近似点梯度算法，可以用邻近算子，近似点算法格式可以写成：
其中
为第
步迭代时的步长，可为固定值或通过某种合适的线搜索策略得到。回顾近似点梯度法的迭代公式，会发现这个算法可以看做是近似点梯度法在
时的情况，但不同之处在于:在近似点梯度法中，非光滑项
的邻近算子通常比较容易计算;而在近似点算法中，
的邻近算子通常是难以求解的，绝大多数情况下需借助其他类型的迭代法进行(不精确)求解。
在近似点算法迭代式(17)中，我们构造了一个看似比原问题式(15) 形式更复杂的子问题。这样的构造带来的好处是:子问题的目标函数是一个强凸函数，更加便于使用迭代法进行求解。
与近似点梯度法类似，同样可以对近似点算法进行加速.与其对应的 FISTA 算法的迭代格式可以写成： 第二类 Nesterov 加速算法的迭代格式可以写成:
LASSO 问题求解： 引入变量，上式可以转化为
其中
为集合
的示性函数。上式采用近似点算法进行求解，其第
步迭代为
由于式(22)没有显式解，需要采用迭代算法来进行求解，比如罚函数法、增广拉格朗日函数法。
除了直接求解问题式(39)，另一种比较实用的方式是通过对偶问题的解来构造。引入拉格朗日乘子
，上式的对偶问题为：
那么问题(39)的对偶问题为 设对偶问题的逼近最优解为
，则问题(39)的最优性条件为
在第步迭代，LASSO 问题的近似点算法的迭代公式为：
因为的最大值点的显式表达式是未知的，所以需要使用迭代算法近似求解。根据
的连续可微性，可以调用梯度法进行求解。另外，还可以证明
是半光滑的，从而调用半光滑牛顿法来更有效地求解。结果如下图所示：
近似点算法收敛所需要的外部迭代数很少，主要计算都在内迭代求解更新的子问题上。对于
的子问题求解，我们利用了半光滑牛顿法来进行加速。
在许多实际的优化问题中，人们所考虑的目标函数虽然有成千上万的 自变量，对这些变量联合求解目标函数的极小值通常很困难，但这些自变量具有某种“可分离”的形式:当固定其中若干变量时，函数的结构会得到极大的简化。这种特殊的形式使得人们可以将原问题拆分成数个只有少数自变量的子问题。分块坐标下降法(block coordinate descent，BCD)正是利用了这样的思想来求解这种具有特殊结构的优化问题，在多数实际问题中有良好的数值表现。
考虑具有如下形式的问题: 其中
是函数的可行域，这里将自变量
拆分成
个变量块
， 每个变量块
函数
是关于
的可微函数，每个
关于
是适当的闭凸函数，但不一定可微。
具体实例：下述问题都可以转化成式(24)的形式：
上述的所有例子中，函数关于变量全体一般是非凸的，这使得求解问题式(24) 变得很有挑战性。首先，应用在非凸问题上的算法的收敛性不易分析，很多针对凸问题设计的算法通常会失效;其次，目标函数的整体结构十分复杂，这使得变量的更新需要很大计算量。对于这类问题，最终的目标是要设计一种算法，它具有简单的变量更新公式，同时具有一定的(全局)收敛性。而分块坐标下降法则是处理这类问题较为有效的算法。
分块坐标下降法具有如下更新方式：按照的次序依次固定其他
块变量极小化
，完成一块变量的极小化后，它的值便立即被更新到变量空间中，更新下一块变量时将使用每个变量最新的值。
在每一步更新中，通常使用以下三种更新格式之一：
分块坐标下降计算流程如下：
分块坐标下降法迭代轨迹如下图所示。可以看到在进 行了 7 次迭代后迭代点与最优解已充分接近。对比梯度法的收敛相当缓慢，一个直观的解 释是:对于比较病态的问题，由于分块坐标下降法是对逐个分量处理，它能较好地捕捉目标函数的各向异性，而梯度法则会受到很大影响。
LASSO 问题：可直接写出它的最小值点如下
其计算流程为：
分块坐标下降法求解 LASSO 问题如下图所示。
其他问题如K-均值聚类算法、非负矩阵分解、字典学习、最大割问题的非凸松弛都可以通过分块坐标下降法求解，这里不再详细介绍了。
对于复合优化问题，许多实际问题的原始问题有时候比较难以处理，这时候一个非常重要的技巧是考虑它的对偶问题。本节将讲解两种算法:一种是把前面提到的算法应用到对偶问题上，例如对偶近似点梯度法;另一种是同时把原始问题和对偶问题结合起来考虑，例如原始 – 对偶混合梯度类的算法。我们将看到这两种算法的思想将极大地丰富求解问题的手段。为了方便起见，这一节主要考虑如下形式的问题: 其中
为闭凸函数，
为实数矩阵。利用共轭函数的定义，可计算拉格朗日对偶问题为
特别值得注意的是，本章讲解的算法不局限于求解上述形式的问题，在学习过程中注意灵活推广到求解其他形式的问题。
迭代公式等价于：
下述例子说明如何拆分和使用对偶近似点梯度法。
本小节介绍另外一种非常重要的算法—原始 – 对偶混合梯度(primal- dual hybrid gradient, PDHG)算法。对于给定的优化问题，可以从原 始问题或对偶问题出发来设计相应算法求解。那么能否将两个方面结合起来呢?PDHG 算法就是借鉴了这样的思想。相比于直接在原始问题上或者对偶问题上应用优化算法求解，PDHG 算法在每次迭代时同时考虑原始变量和对偶变量的更新。这使得它在一定程度上可以有效避免单独针对原始问题或对偶问题求解算法中可能出现的问题。
鞍点问题：
PDHG 算法交替更新原始变量以及对偶变量，其迭代公式如下:
LASSO 问题：
结果如下图所示。可以看到，尽管 PDHG 算法在某些情况下没有收敛性保证，但它在这个例子上比 Chambolle-Pock 算法稍快一些。
类似去噪TV-L1 模型、图像填充模型、图像反卷积模型都可以通过PDHG 算法进行求解，不再一一描述了。
统计学、机器学习和科学计算中出现了很多结构复杂且可能非凸、非光滑的优化问题。交替方向乘子法很自然地提供了一个适用范围广泛、容易理解和实现、可靠性不错的解决方案。该方法是在20世纪70年代发展起来的，与许多其他算法等价或密切相关，如对偶分解、乘子方法、Douglas- Rachford Splitting 方法、Dykstra 交替投影方法、Bregman 对于带 l1 范数问题的迭代算法、近似点算法等。
考虑如下凸问题 这个问题的特点是目标函数可以分成彼此分离的两块，但是变量被线性约束结合在一起。常见的一些无约束和带约束的优化问题都可以表示成这一形式。下面的一些例子将展示如何把某些一般的优化问题转化为适用交替方向乘子法求解的标准形式。
下面给出交替方向乘子法(alternating direction method of multipliers, ADMM)的迭代公式：
其中为步长，通常取值为
。与无约束优化问题不同，交替方向乘子法针对的问题是带约束的优化问题，因此算法的收敛准则应当借助约束优化问题的最优性条件(KKT 条件)。
Douglas-Rachford Splitting (DRS) 算法是一类非常重要的算子分裂算法。它可以用于求解下面的无约束优化问题: 其中
为闭凸函数。DRS 算法的迭代公式如下：
线性化：构造 ADMM 的初衷是将自变量拆分，最终使得关于的子问题有显式解。但是在实际应用中，有时子问题并不容易求解，或者没有必要精确求解。线性化技巧实际上是使用近似点项对子问题目标函数进行二次近似。
缓存分解：虽然子问题有显式解，但是每步求解的复杂度仍然比较高，这时候可以考虑用缓存分解的方法。
优化转移：可以用一个性质好的矩阵近似二次项。
二次罚项系数的动态调节：动态调节二次罚项系数在交替方向乘子法的实际应用中是一个非常重要的数值技巧。在每次迭代时动态调节惩罚系数 ρ 的大 小，从而使得原始可行性和对偶可行性能够以比较一致的速度下降到零。这 种做法通常可以改善算法在实际中的收敛效果，以及使算法表现更少地依赖于惩罚系数的初始选择。
超松弛：
多块与非凸问题的 ADMM：有两块变量的凸问题上的 ADMM 格式相比，多块(非凸)ADMM 可能不具有收敛性。但在找到有效算法之前，这两种 ADMM 算法的变形都值得一试,它们在某些实际问题上也有不错的效果。
LASSO 问题：交替方向乘子法迭公式为
实验结果如下图所示。对于这个例子，求解原始问 题需要的迭代步数较少，但求解对偶问题每一次迭代所需要的时间更短，综合来看 ADMM 求解对偶问题时更快。
类似广义 LASSO 问题、逆协方差矩阵估计、矩阵分离问题、全局一致性优化问题、非凸集合上的优化问题、非负矩阵分解和补全等问题可以采用交替方向乘子法求解。
随着大数据时代的来临，以及机器学习和深度学习等人工智能领域的发展，许多大规模的优化问题随之产生，它们对传统优化理论和算法都产生了巨大的挑战。幸运的是，这些问题往往与概率和统计学科有很大联系， 由此促使了随机优化算法的广泛使用。随机算法的思想可以追溯到 Monro- Robbins 算法 ，相比传统优化算法，随机优化算法能极大地节省每步迭代的运算量，从而使得算法在大规模数据中变得可行。
主要考虑如下随机优化问题： ?其中
对应第i个样本的损失函数。上式也称为随机优化问题的有限和形式。
假设是凸的、可微的，可以运用梯度下降算法:
在绝大多数情况下，我们不能通过化简的方式得到
的表达式，要计算这个梯度必须计算出所有的
然后将它们相加。然 而在机器学习中，采集到的样本量是巨大的，因此计算
需要非常大 的计算量。使用传统的梯度法求解机器学习问题并不是一个很好的做法。
随机梯度下降算法 (SGD)：迭代公式为 小批量(mini-batch)随机梯度法: 迭代公式为
当
是凸函数但不一定可微时，可以用
的次梯度代替梯度进行迭代，这就是随机次梯度算法，它的迭代公式为：
传统的梯度法在问题比较病态时收敛速度非常慢，随机梯度下降法也有类似的问题。为了克服这一缺陷，人们提出了动量方法(momentum)， 旨在加速学习。该方法在处理高曲率或是带噪声的梯度上非常有效，其思想是在算法迭代时一定程度上保留之前更新的方向，同时利用当前计算的梯 度调整最终的更新方向。这样一来，可以在一定程度上增加稳定性，从而学习得更快，并且还有一定摆脱局部最优解的能力。动量方法的具体迭代公式如下:
下图对比了梯度法和动量方法。可以看到普通梯度法生成的点列会在椭圆的短轴方向上来回移动，而动量方法生成的点列更 快收敛到了最小值点。
针对光滑问题的 Nesterov 加速算法迭代公式为:
与动量方法相比，二者的主要差别在梯度的计算上。Nesterov 加速算法先对点施加速度的作用，再求梯度，这可以理解为对标准动量方法做了一个校正。
在一般的随机梯度法中，调参是一个很大的难点，参数设置的好坏对算法的性能有显著的影响。所以希望算法能在运行的过程中，根据当前情况自发地调整参数，这就是 AdaGrad(adaptive subgradient methods) 的出发点。当梯度的某个分量较大时，可以推断出在该方向上函数变化比较剧烈，此时应该用小步长;当梯度的某个分量较小时，在该方向上函数比较平缓，此时应该用大步长。AdaGrad 就是根据这个思想设计的。
令,为了记录整个迭代过程中梯度各个分量的累积情况，引入向量
从
的定义可知
的每个分量表示在迭代过程中，梯度在该分量处的累积平方和。当
的某分量较大时，认为该分量变化比较剧烈，因此应采用小步长，反之亦然。因此AdaGrad 的迭代格式为：
可以看到 AdaGrad的步长大致反比于历史梯度累计值的算术平方根，所以梯度较大时步长 降很快，反之则下降较慢，这样做的效果就是在参数空间更平缓的方向上， 前后两次迭代的距离较大。在凸优化问题中 AdaGrad 有比较好的理论性质， 但实际应用中也发现在训练深度神经网络模型时，从训练开始就积累梯度 平方会导致步长过早或过多减小。
如果在AdaGrad 中使用真实梯度，那么AdaGrad 也可以看成是一种介于一阶和二阶的优化算法。考虑
在点
的二阶泰勒展开如下：
使用常数倍单位矩阵近似
时可得到梯度法；利用海瑟矩阵作为
时可得到牛顿法。而AdaGrad 则是使用一个对角矩阵来作为
。具体地，取
时，推导出的算法。
RMSProp(root mean square propagation)是对 AdaGrad 的一个改进，该方法在非凸问题上可能表现更好。AdaGrad 会累加之前所有的梯度分量平方，这就导致步长是单调递减的，因此在训练后期步长会非常小，同 时这样做也加大了计算的开销。所以 RMSProp 提出只需使用离当前迭代点比较近的项，同时引入衰减参数。具体的令：
再对其每个分量分别求根，就得到均方根 (root mean square)：
最后将均方根的倒数作为每个分量步长的修正，得到 RMSProp 迭代格式：
引入参数同样是为了防止分母为0的情况发生。一般取
。可以看到RMSProp 和AdaGrad 的唯一区别是将
替换成了
。
AdaDelta 在 RMSProp 的基础上，对历史的也同样累积平方并求均方根:
然后使用和
的商对梯度进行校正，其计算流程如下图所示：
AdaDelta 的特点是步长选择较为保守，同时也改善了AdaGrad 步长单调下降的缺陷。
Adam(adaptive moment estimation)本质上是带动量项的 RMSProp， 它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数步长。虽然 RMSProp 也采用了二阶矩估计，但是缺少修正因子，所以它在训练初期可能有比较大的偏差。Adam 的优点主要在于经过偏差修正后，每一次迭代的步长都有一 个确定范围，使得参数比较平稳。
与 RMSProp 和动量方法相比，Adam 可以看成是带修正的二者的结合。在 Adam 中不直接使用随机梯度作为基础的更新方向，而是选择了一个动量项进行更新： 于此同时它和 RMSProp 类似，也会记录迭代过程中梯度的二阶矩:
与原始动量方法和 RMSProp 的区别是，由于
和
本身带有偏差，Adam不直接使用这两个量更新，而是在更新前先对其进行修正:
Adam 最终使用修正后的一阶矩和二 阶矩进行迭代点的更新:
这里参数通常选择为
,全局步长
。
其完整计算流程如下图所示：
上面的很多算法已经被实现在主流的深度学习框架中，可以非常方便地 用于训练神经网络:Pytorch 里实现的算法有 AdaDelta，AdaGrad，Adam，Nesterov，RMSProp 等;Tensorflow 里实现的算法则有 AdaDelta，Ada- GradDA，AdaGrad，ProximalAdagrad，Ftrl，Momentum，Adam 和 CenteredRMSProp 等。
逻辑回归：逻辑回归是最基本的线性分类模型，它经常用来作为各种分类模型的比较标准。给定数据集，带
范数平方正则项的逻辑回归对应的优化问题如下：
每步随机选取下标
对应得梯度
做随机梯度下降，其迭代公式如下：
不同的数值结果如下图所示。可以看到，加入了动量之后，随机梯度法的收敛加快，但没有自适应类梯度方法快。值得注意的是，当批量大小从 1 变成 10 时，随机梯度法和动量方法达到相同精度需要的时期数变多，但大的批量大小对应的算法效率更高(计算梯度时矩阵乘法的并行效率以及内存利用率会更高)。在自适应梯度类方法,AdaGrad 对该凸问题收敛最快，Adam 次之。在 a9a 数据集上，RMSProp 和 AdaDelta 在批量大小为 1 时尾部出现函数值上升(尽管设置更小的
可以避免出现上升，但会大大降低目标函数值的下降 速度)，批量大小为 10 时算法产生的 x 对应的目标函数值更小。
在次梯度情形以及 可微强凸的条件下，随机梯度方法的算法复杂度要小于普通的梯度法。但是也发现随机方法容易受到梯度估计噪声的影响，这使得它在固定步长下不能收敛，并且在递减步长下也只能达到R-次线性收敛
，而普通梯度法在强凸且梯度L-利普希茨连续的条件下可以达到Q-线性收敛速度。
对梯度下降法有：
对随机梯度下降法，利用条件期望的性质有：
简化表达为下式： 从上面的分析中可以看到两种算法的主要差别就在
项上，也就是梯度估计的某种方差。以为了能获得 比较快的渐进收敛速度，主要目标就是减少方差项
来加快随机梯度算法的收敛速度。
方差减小相对于普通的随机梯度算法使用更多的样本点，这些算法的基本思想都是通过利用之前计算得到的信息来减小方差，最终获得Q-线性收敛速度。
SAG (stochastic average gradient)：在随机梯度下降法中，每一步迭代仅仅使用了当前点的随机梯度，而迭代计算的历史随机梯度则直接丢弃不再使用。当迭代接近收敛时，上一步的随机梯度同样也是当前迭代点处梯度的一个很好的估计。随机平均梯度法(SAG) 就是基于这一想法构造的在迭代中，SAG 算法记录所有之前计算过的随机梯度，再与当前新计算的随机梯度求平均，最终作为下一步的梯度估计。其迭代公式为
每次迭代只有一个的内容发生变化，而其他
是直接沿用上一步的值，因此SAG 迭代公式还可以写成：
在SAG 算法中
的初值可简单地取为零向量或中心化的随机梯度向量，不加证明地指出，SAG 算法每次使用的随机梯度的条件期望并不是真实梯度，但随着迭代进行，随机梯度的期望和真实梯度的偏差会越来越小。
SAGA (并不是四个英文单词的缩写)算法：使用无偏的梯度向量作为更新方向，其更新公式为 可以证明每次迭代使用的梯度方向都是无偏的，即
SAGA 算法同样有Q-线性收敛速度。
SVRG((stochastic variance reduced gradient) 算法: 通过周期性缓存全梯度的方法来减小方差。具体做法是在随机梯度下降方法中，每经过m 次迭代就设置一个检查点，计算一次全梯度，在之后的m次迭代中，将这个全梯度 作为参考点来达到减小方差的目的。
令为第j个检查点，则计算器全梯度为
在之后的迭代中使用方向下述方向进行更新：
在条件期望的意义下是梯度的一个无偏估计。
其计算流程如下图所示。
总结了求解复合优化问题的算法，可以用来根据具体实际问题进行查阅。关于优化建模与算法介绍就到这里了。最优化永久的话题。最后以一图收尾。
[1]. 刘浩洋等《最优化：建模、算法与理论》
[2]. Sebastian Ruder: An overview of gradient descent optimization algorithms
