梯度下降及其收敛性
1. 通用下降方法 1.1 下降方法基本形式 注：下降方法不会要求凸性，但拥有凸性会让求解得到显著保障。对凸性的定义见[[凸集与凸函数深入#2.1 凸函数定义|凸函数定义]] 我们先来回顾梯度下降的原型 - 下降方法 下降算法会产生优化点列 $x^{(k)}, k=1, \cdots$，其中 $$ x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)} $$且 $t^{(k)} > 0$（除非 $x^{(k)}$ 已经最优了）。该概念参考自[[Convex Optimization.pdf|Convex Optimization]]1 此处 $\Delta x^{(k)}$ 是一个向量，称为搜索方向，$t^{(k)}\Delta x^{(k)}$ 称为步径（实践中常为和参数同尺寸的多维数组）；$k$ 代表迭代次数；标量 $t^{(k)}$ 是更新步长。 1.2 下降条件 对于所有下降方法，只要 $x^{(k)}$ 不是最优点，则都有： $$ f(x^{(k+1)}) < f(x^{(k)}) $$ 注意：下降算法默认为最小化目标函数，一切最初形式为"最大化目标函数"的问题(例如TD误差)均可被描述为如此形式 以下是下降方法的下降条件： 凸函数情况下，若选择 $d=y-x$ 方向更新，现考虑凸函数的[[凸集与凸函数深入#2.2.1 一阶条件|一阶条件]]2 $f(y) \geq f(x)+\nabla f(x)^T(y-x)$，要使函数下降，即 $f(y) < f(x)$，则必须有 $\nabla f(x)^{T}(y-x) < 0$。 此处，$\nabla f(x)^{T}(y-x)$ 即为方向导数 特征 搜索方向 步径 方向导数 数学定义 $d^{(k)}$ $\alpha^{(k)} d^{(k)}$ $\nabla f(x)^{T}(y-x)$ 几何含义 移动的方向 实际的位移向量 函数沿方向的变化率 1.3 通用下降法算法框架 通用下降方法通常有如下的步骤： ...