数值优化：经典随机优化算法及其收敛性与复杂度分析

1 随机优化算法概述

随着大数据的出现，确定性优化算法的效率逐渐称为瓶颈。为了说明这一点，我们来看一个用梯度下降法求解线性回归的例子。

给定训练样本\(D = \{(x_i, y_i)\}_{i=1}^n\)，线性回归的目标函数如下：

\[f(w) = \frac{1}{n}\sum_{i=1}^nf_i(w)= \frac{1}{n}\sum_{i=1}^n(w^T x_i - y_i)^2\]