知识点：随机优化问题

知识点概述

随机优化（Stochastic Optimization, SO）处理目标函数或约束中包含随机变量的问题。其典型形式是最小化一个期望值函数，这在机器学习和数据科学中尤其常见，因为训练数据通常被看作是来自某个未知概率分布的样本。

模型:
- 期望最小化: $min_{x} F (x) = E_{ξ} [f (x, ξ)]$ ，其中 $ξ$ 是一个随机变量。
- 有限和/经验风险最小化: 在机器学习中，真实分布未知，我们用训练样本的经验分布来近似，问题变为 $min_{x} \frac{1}{m} \sum_{i = 1}^{m} f (x, ξ_{i})$ 。当样本量 $m$ 巨大时，计算真实梯度的成本很高，因此仍需使用随机方法。
挑战:
- 期望值通常无法精确计算。
- 即使是有限和形式，当 $m$ 很大时，每一步迭代的计算量（如整个数据集上的梯度）也无法承受。
求解算法:
- 随机梯度下降 (SGD): 在每一步迭代中，随机采样一个（或一小批）数据点，计算该样本上的梯度作为真实梯度的无偏估计，并据此更新参数。 $x_{k + 1} = x_{k} - η_{k} \nabla f (x_{k}, ξ_{k})$ 。
- 方差缩减技术: SGD的梯度估计有较大方差，导致收敛慢且不稳定。SVRG、SAGA等方差缩减算法通过结合全梯度信息来修正随机梯度，实现了更快的收敛速度。