1.2　一阶优化算法

在机器学习中，参数w的维度n往往很大，如果使用标准的二阶算法求解机器学习模型，我们需要在每次迭代中计算和存储一个n×n的海森矩阵，计算和存储开销都很大．另一方面，很多机器学习模型并不需要求解到很高的数值精度．一阶优化算法由于其每次迭代计算复杂度低，并且能够较快地找到一个精度适中的解，成为机器学习中的主流算法．

尽管“一阶算法”在复杂度理论中严格定义为只基于函数值f（xk）和梯度∇f（xk）来计算的优化算法，其中xk为任意给定的点，这里我们采用更广义的定义，即定义“一阶算法”为不使用目标函数高阶导数信息的算法．因此，这里讨论的一阶优化算法允许使用子问题的闭解和邻近映射（Proximal Mapping，见定义25）．本书并不准备介绍机器学习中所有常用的一阶算法，感兴趣的读者可参考［Beck，2017；Bottou et al.，2018；Boyd et al.，2011；Bubeck，2015；Hazan，2016，2019；Jain and Kar，2017；Nesterov，2018；Parikh and Boyd，2014；Sra et al.，2012］．在本书中，我们将重点介绍加速一阶优化算法，其中“加速”表示在不需要更强的假设条件下，算法收敛速度能够更快．另外，我们主要介绍基于精巧的“外推”和“内插”技巧的加速一阶优化算法．