随机算法在机器学习中有着悠久的历史，可以追溯到20世纪50年代经典随机梯度下降算法(Robbins和Monro 1951)。研究随机算法有“直观的、实用的和理论的动机”(Bottou等人，2018年)。直观地说，如果许多训练样本在统计上是相似的，随机算法可以比它们的确定性对应算法更有效(Bertsekas 1999)，在某种意义上，在第110页。这种直觉在实践中得到了证实:随机算法通常比确定性/批处理算法快得多，初始训练误差减少。最后，为了支持实际结果，建立了随机算法的收敛理论。如今，深度神经网络是用随机算法训练的，重申了它们的有效性和实用价值。

有序子集(OS)算法在图像重建中很流行，就像随机算法在机器学习中很流行一样。自1994年Hudson和Larkin自核医学图像重建以来，由于数据量的增加和对及时交付图像的高要求，OS算法继续蓬勃发展。OS该算法通常将投影视图分成小组，并在每组循环后进行图像更新。尽管这些OS算法中可能没有随机元素，但在使用数据子集(小批量)进行更频繁的参数更新时，它们本质上与随机算法非常相似。因此，OS算法通常有快速的初始进展，这可能会导致可接受的图像质量通过批处理相应的计算成本的一小部分来获得。但由于对算法行为缺乏一般的理解，OS由于极限环或发散，算法经常受到批评。OS该算法本质上可能受益于随机算法的凸优化，特别是后者通常有收敛保证。

在文献中，术语随机算法可以模棱两可，因为它可以指：

(a)在预期风险最小化中，用于最小化随机目标函数的算法；

(b)算法是基于返回扰动函数值或梯度信息的随机预测

?用于确定性有限、最小化的算法，如经验风险最小化，其中随机机制仅产生于子集(小批量)对目标函数中组件的随机访问。

由于我们的主要兴趣是解决具有有限确定性和目标函数的图像重建问题，我们主要关注第三种随机算法。在文献中，它们有时也被称为随机算法。随机性是可选的，而不是强制性的，该选项可以有效地利用其计算优势。

机器学习中常见的问题之一是以下正则化经验风险最小化： min x ? ( x ) = f ( x ) g ( x ) , f ( x ) = 1 n ∑ i = 1 n f i ( x ) (4.1) \min_x \phi(x)=f(x) g(x),f(x)=\frac{1}{n}\sum_{i=1}^nf_i(x)\tag{4.1} xmin?(x)=f(x) g(x),f(x)=n1​i=1∑n​fi​(x)(4.1) 其中 f i ( x ) , i = 1 , . . . , n f_i(x),i=1,...,n fi​(x),i=1,...,n，是CCP， L i L_i Li​-光滑，正则化g(x)是CCP，非光滑，简单。我们假设 x ∗ ∈ a r g m i n ϕ ( x ) x_*\in argmin\phi(x) x∗​∈argminϕ(x)存在。

经典的随机梯度下降(SGD)算法假定g(x)=0，并使用f(x)估计解x*。 x k + 1 = x k − η ▽ f i k ( x k ) (4.2) x_{k+1}=x_k-\eta \triangledown f_{i_k}(x_k)\tag{4.2} xk+1​=xk​−η▽fik​​(xk​)(4.2) 其中 i k i_k ik​从 1 ， . . . ， n {1，...，n} 1，...，n中随机抽取， η k > 0 η_k>0 ηk​>0是步长。处理复合目标函数(4.1)的自然概括是(4.2)的以下近端变体(肖2010，Dekel等人2012)： x k + 1 : = a r g min ⁡ x { g ( x ) + f ( x k ) + < ▽ f i k ( x k ) , x − x k > + 1 2 η k ∣ ∣ x − x k ∣ ∣ 2 } (4.3) x_{k+1}:=arg\min_x \{g(x)+f(x_k)+<\triangledown f_{i_k}(x_k),x-x_{k}>+\frac1{2\eta_k}||x-x_k||^2\}\tag{4.3} xk+1​:=argxmin​{ g(x)+f(xk​)+<▽fik​​(xk​),x−xk​>+2ηk​1​∣∣x−xk​∣∣2}(4.3) 当g(x不存在时，(4.3)等同于(4.2)；当g(x)存在时，(4.3)是(4.2)的近端梯度变量。在(4.2)和(4.3)中， ∇ f i k ( x k ) {\rm{\nabla }}{f}_{ {i}_{k}}({x}_{k}) ∇fik​​(xk​)可视为真梯度 ∇ f ( x k ) = ∑ i ∇ f i ( x k ) / n ∇f(x_k)=∑_i∇f_i(x_k)/n ∇f(xk​)=∑i​∇fi​(xk​)/n的估计.显然， E ξ { ∇ f ξ ( x k ) } = ∇ f ( x k ) E_ξ\{∇f_ξ(x_k)\}=∇f(x_k) Eξ​{ ∇fξ​(xk​)}=∇f(xk​)， 18 ^{18} 18因此 ∇ f ξ ( x k ) ∇f_ξ(x_k) ∇fξ​(xk​)是一个无偏估计；而且，计算一个分量函数的 ∇ f i ( x k ) ∇f_i(x_k) ∇fi​(xk​)比计算全梯度 ∇ f ( x k ) ∇f(x_k) ∇f(xk​)简单n倍.。如果我们假设 ∥ ∇ f i ( x ) ∥ 2 < = M ∥∇f_i(x)∥^2<=M ∥∇fi​(x)∥2<=M对所有i，对所有x，则可以证明 E ξ { ∥ ∇ f ξ ( x k ) − ∇ f ( x k ) ∥ 2 } < = M E_ξ\{∥∇f_ξ(x_k)−∇f(x_k)∥^2\}<=M Eξ​{ ∥∇fξ​(xk​)−∇f(xk​)∥2}<=M(Konečnèet al2015)，即 ∇ f ξ ( x k ) ∇f_ξ(x_k) ∇fξ​(xk​)，作为 ∇ f ( x k ) ∇f(x_k) ∇f(xk​)的估计，有有限的方差。在步长 η k = η η_k=η ηk​=η不变的情况下，梯度估计的有限方差导致期望目标值 19 ^{19} 19的有限误差界，即 E f ( x k ) − f ( x ∗ ) → B {E}f({x}_{k})-f({x}_{* })\to B Ef(xk​)−f(x∗​)→B为 k → ∞ k→∞ k→∞。误差界B取决于步长η和梯度方差：η越小，B越小，M越小。

由于梯度估计的方差M有限，SGD(4.2)、(4.3)的收敛通常需要减小步长。在f(x)是L-光滑且μ-强凸的假设下，(4.3)用递减步长 η k ∼ 1 / k η_k∼1/k ηk​∼1/k以O(M/k)的速度收敛于 E ϕ ( x k ) → ϕ ( x ∗ ) {\mathbb{E}}\phi ({x}_{k})\to \phi ({x}_{* }) Eϕ(xk​)→ϕ(x∗​)，当分支f(x)仅是L光滑时，收敛速度(由 E ϕ ( x ˉ k ) → ϕ ( x ∗ ) {\mathbb{E}}\phi ({\bar{x}}_{k})\to \phi ({x}_{* }) Eϕ(xˉk​)→ϕ(