第 16 章 一阶优化Chapter 16 First-order optimization

考虑 $L({\bm{w}})$ 在 ${\bm{w}}^{t}$ 附近的线性近似，Consider the linear approximation of $L({\bm{w}})$ around ${\bm{w}}^{t}$,

$$L({\bm{w}})\approx L({\bm{w}}^{t})+\langle\nabla L({\bm{w}}^{t}),{\bm{w}}-{\bm{w}}^{t}\rangle.$$

容易验证，式 16.1 中的梯度下降更新可以改写为如下极小化问题的解，即：One can easily check that the gradient descent update in Eq. 16.1 can be rewritten as the solution of a minimization problem, namely,

$${\bm{w}}^{t+1}=\argmin_{{\bm{w}}\in\mathcal{W}}L({\bm{w}}^{t})+\langle\nabla L({\bm{w}}^{t}),{\bm{w}}-{\bm{w}}^{t}\rangle+\frac{1}{2\gamma}\|{\bm{w}}-{\bm{w}}^{t}\|_{2}^{2}.$$

(16.2)

用文字来说，梯度下降的一次更新优化了这样一个权衡：一方面借助邻近项 $\frac{1}{2\gamma}\|{\bm{w}}-{\bm{w}}^{t}\|_{2}^{2}$ 保持与当前 ${\bm{w}}^{t}$ 接近，另一方面极小化 $L$ 在 ${\bm{w}}^{t}$ 附近的线性化。直观上，只要选取足够小的 $\gamma$，就能保证正则化线性近似的极小值点仍落在该线性近似有效的邻域内。这一视角有助于引出梯度下降的各种推广。In words, a gradient descent update optimizes a trade-off between staying close to the current ${\bm{w}}^{t}$, thanks to the proximity term $\frac{1}{2\gamma}\|{\bm{w}}-{\bm{w}}^{t}\|_{2}^{2}$, and minimizing the linearization of $L$ around ${\bm{w}}^{t}$. Intuitively, by choosing $\gamma$ sufficiently small, we ensure that the minimizer of the regularized linear approximation stays in a neighborhood where the linear approximation is valid. This viewpoint is useful to motivate gradient descent extensions.

只要 $\nabla L({\bm{w}}^{t})\neq{\mathbf{0}}$，函数 $L_{t}(\gamma)\coloneqq L({\bm{w}}^{t}-\gamma\nabla L({\bm{w}}^{t}))$ 在 0 处的导数就为负，即 $L^{\prime}_{t}(0)=-\|\nabla L({\bm{w}}^{t})\|_{2}^{2}$。因此，只要 $\nabla L({\bm{w}}^{t})\neq{\mathbf{0}}$，就存在一个步长，使得每次迭代的目标函数值都下降。然而，若没有进一步的假设，这样的步长可能依赖于每一次迭代，并且可能小到无穷小。为了定量刻画采用常数步长的梯度下降的收敛性，我们限定在光滑函数类中讨论。对梯度下降的迭代值应用命题 15.4.4，可得As long as $\nabla L({\bm{w}}^{t})\neq{\mathbf{0}}$, the function $L_{t}(\gamma)\coloneqq L({\bm{w}}^{t}-\gamma\nabla L({\bm{w}}^{t}))$ has a negative derivative at 0, i.e., $L^{\prime}_{t}(0)=-\|\nabla L({\bm{w}}^{t})\|_{2}^{2}$. Hence, as long as $\nabla L({\bm{w}}^{t})\neq{\mathbf{0}}$, there exists a stepsize ensuring a decrease in objective values at each iterate. However, without further assumptions, such a stepsize may depend on each iterate and may be infinitesimally small. To quantify the convergence of gradient descent with a constant stepsize, we restrict to the class of smooth functions. By applying Proposition 15.4.4 on the iterate of gradient descent, we obtain that

$$L({\bm{w}}^{t+1})\leq L({\bm{w}}^{t})-\gamma\|\nabla L({\bm{w}}^{t})\|_{2}^{2}+\frac{\beta\gamma^{2}}{2}\|\nabla L({\bm{w}}^{t})\|_{2}^{2}.$$

因此，对于 $\beta$-光滑函数，选取 $\gamma\leq\frac{1}{\beta}$，便有Therefore, for $\beta$-smooth functions, by selecting $\gamma\leq\frac{1}{\beta}$, we get that

$$L({\bm{w}}^{t+1})-L({\bm{w}}^{t})\leq-\frac{\gamma}{2}\|\nabla L({\bm{w}}^{t})\|_{2}^{2},$$

这揭示了梯度下降背后的主要机制：每一次迭代都使目标函数值下降一个常数乘以当前迭代值的梯度范数。该式还可以对所有直至 $T$ 的迭代求和。这样目标函数值便相互抵消，从而得到which illustrates the main mechanism behind gradient descent: each iteration decreases the objective by a constant times the norm of the gradient of the current iterate. This equation can further be summed over all iterates up to $T$. This telescopes the objective values, leading to

$$\displaystyle\min_{t\in\{0,\ldots,T-1\}}\|\nabla L({\bm{w}}^{t})\|_{2}^{2}$$	$$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla L({\bm{w}}^{t})\|_{2}^{2}$$
	$$\displaystyle\leq\frac{2}{\gamma T}\left(L({\bm{w}}^{0})-L({\bm{w}}^{T})\right)$$
	$$\displaystyle\leq\frac{2}{\gamma T}\left(L({\bm{w}}^{0})-L^{\star}\right),$$

其中回顾 $L^{\star}$ 是 $L$ 的下确界。因此，经过足够多次迭代后，梯度下降会找到一个梯度范数任意小的点。where we recall that $L^{\star}$ is the infimum of $L$. Therefore, after sufficiently many iterations, gradient descent finds a point whose gradient norm is arbitrarily small.

我们从梯度下降这一一阶优化算法的简单示例出发。然而，根据所能获得的一阶 oracle 以及对所考虑函数类的了解，可以设计出不同的优化算法。例如，考虑二次凸函数 ${\bm{w}}\mapsto\frac{1}{2}{\bm{w}}^{\top}{\bm{A}}{\bm{w}}+{\bm{b}}^{\top}{\bm{w}}$；若 ${\bm{A}}$ 为正定矩阵，则它们是光滑强凸函数的一个基本例子。在这种情况下，一个最优方法是 [159] 的重球法，它可以写成We started with gradient descent as a simple example of first-order optimization algorithm. However, different optimization algorithms can be designed from the access to first-order oracles and the knowledge of the class of functions considered. For example, consider quadratic convex functions ${\bm{w}}\mapsto\frac{1}{2}{\bm{w}}^{\top}{\bm{A}}{\bm{w}}+{\bm{b}}^{\top}{\bm{w}}$, that are a basic example of smooth strongly convex functions if ${\bm{A}}$ is positive definite. An optimal method in this case is the heavy-ball method of [159], that can be written as

$$\displaystyle{\bm{v}}^{t+1}$$	$$\displaystyle\coloneqq\nu{\bm{v}}^{t}-\gamma\nabla L({\bm{w}}^{t})$$
$$\displaystyle{\bm{w}}^{t+1}$$	$$\displaystyle\coloneqq{\bm{w}}^{t}+{\bm{v}}^{t+1}.$$

重球法使用了一个额外的变量 ${\bm{v}}^{t}$，它可以被解释为一个由负梯度驱动的、朝着极小值收敛的小球的速度。直观地说，这个额外的速度避免了梯度下降可能出现的振荡，如图 16.2 与图 16.1 的对比所示。当 $\nu=0$ 时，我们恢复出通常的梯度下降。当 $\nu>0$ 时，这些速度累积成一种惯性动量的形式，其中 $\nu$ 被解释为小球的“质量”。就收敛速率而言，可以证明重球法与梯度下降类似地线性收敛，但在适当选取 $\nu,\gamma$ 时，其速率为 $O(\exp(-T\sqrt{\mu/\beta}))$。相比之下，通过为梯度下降选取最优步长，其收敛速率为 $O(\exp(-T\mu/\beta))$，而这一速率可证明更差，因为我们总有 $\mu/\beta\leq 1$。The heavy-ball method uses an additional variable ${\bm{v}}^{t}$, that can be interpreted as the velocity of a ball driven by the negative gradient to converge towards a minimum. Intuitively, this additional velocity circumvents the oscillations that a gradient descent may present as illustrated in Fig. 16.2 compared to Fig. 16.1. For $\nu=0$, we recover usual gradient descent. For $\nu>0$, the velocities accumulate a form of an inertia momentum, where $\nu$ is interpreted as the “mass” of the ball. In terms of convergence rates, the heavy-ball method can be shown to converge linearly similarly to gradient descent, but with a rate $O(\exp(-T\sqrt{\mu/\beta}))$ for appropriate choices of $\nu,\gamma$. In comparison, by choosing an optimal stepsize for the gradient descent, its convergence rate is $O(\exp(-T\mu/\beta))$ which is provably worse, as we always have $\mu/\beta\leq 1$.

除二次函数的情形之外，[146] 还针对凸函数或强凸函数开发了梯度下降的加速变体。这类变体启发了下文所介绍的随机设定下优化算法的设计。Beyond the case of quadratic functions, accelerated variants of gradient descent for convex or strongly convex functions have been developed by [146]. Such variants have inspired the design of optimization algorithms in stochastic settings presented below.

通常，即便我们并不知道 $\rho$，也仍可从中采样，也就是说，我们能够获得样本 $S\sim\rho$。于是，便可将形如 $\nabla L({\bm{w}};S)$ 的随机梯度用作 $\nabla L({\bm{w}})$ 的随机估计。这看似只是一个粗略的估计，但平均而言，它是有效的近似，因为Usually, even if we do not know $\rho$, we can sample from it, i.e., we have access to samples $S\sim\rho$. We can then use a stochastic gradient of the form $\nabla L({\bm{w}};S)$ as a random estimate of $\nabla L({\bm{w}})$. This may look like a rough estimate but, on average, this is a valid approximation since

$$\mathbb{E}_{S\sim\rho}\left[\nabla L({\bm{w}};S)\right]=\nabla L({\bm{w}}).$$

我们称 $\nabla L({\bm{w}};S)$ 为 $\nabla L({\bm{w}})$ 的无偏估计量。为进一步改善近似，还可以考虑小批量估计：采样 $m\ll n$ 个数据点 $S_{i}\coloneqq(X_{i},Y_{i})$，并采用 $\frac{1}{m}\sum_{i=1}^{m}\nabla L({\bm{w}};S_{i})$，其期望仍与 $\nabla L({\bm{w}})$ 相符，同时通过对多个随机梯度取平均，还可能减小近似误差。从计算角度看，其主要优势在于代价现在与 $m$ 成正比，而非与 $n$ 成正比。We say that $\nabla L({\bm{w}};S)$ is an unbiased estimator of $\nabla L({\bm{w}})$. To further improve the approximation, we may also consider mini-batch estimates by sampling $m\ll n$ data points $S_{i}\coloneqq(X_{i},Y_{i})$ and using $\frac{1}{m}\sum_{i=1}^{m}\nabla L({\bm{w}};S_{i})$, whose expectation still matches $\nabla L({\bm{w}})$, while potentially reducing the approximation error by averaging multiple stochastic gradients. Computationally, the main advantage is that the cost is now proportional to $m$ instead of $n$.

在最一般的情况下，可以考虑下文所定义的随机一阶 oracle。In whole generality, one can consider stochastic first-order oracles defined below.

当 $q=\rho$ 时，即得到随机梯度；当 $q$ 是按 $p$ 独立抽取的 $m$ 个样本的乘积时，则得到小批量随机梯度。一阶随机优化算法以随机一阶 oracle 为基础，近似地求期望目标函数的最小值。在这种设定下，算法的迭代值按定义即是随机的。因此，收敛速率需要以概率的方式表述，例如考察针对 oracle 随机性所取的期望目标值。When $q=\rho$, we recover stochastic gradients. When $q$ is the product of $m$ independent samples according to $p$, we recover mini-batch stochastic gradients. First-order stochastic optimization algorithms build upon stochastic first-order oracles to approximately find the minimum of the expected objective. In such a setting, the iterates of the algorithm are by definition random. Convergence rates therefore need to be expressed in probabilistic terms by considering for example the expected objective value according to the randomness of the oracles.

有了随机一阶 oracle（例如（小批量）随机梯度），我们便可将随机梯度下降定义为Equipped with a stochastic first-order oracle, such as (mini-batch) stochastic gradients, we can define stochastic gradient descent as

$${\bm{w}}^{t+1}={\bm{w}}^{t}-\gamma g({\bm{w}}^{t};S^{t})\quad\text{where}\ S^{t}\sim q.$$

我们假设 $S^{t}$ 与 ${\bm{w}}^{t}$ 相互独立。与通常的梯度下降相比，随机设定下的主要障碍在于随机估计所引入的额外噪声，即其方差。We assume that $S^{t}$ is independent of ${\bm{w}}^{t}$. Compared to the usual gradient descent, the main impediment of the stochastic setting is the additional noise induced by the stochastic estimates: their variance.

例如，考虑对 $\beta$-光滑凸函数 $L({\bm{w}};{\bm{s}})$ 的期望施加随机梯度下降，并使用无偏 oracle。为利用迭代值的随机性，可考虑在 $T$ 次迭代后输出前 $T$ 个迭代值的平均，即 $\bar{\bm{w}}^{T}\coloneqq\frac{1}{T}\sum_{t=1}^{T}{\bm{w}}^{t}$。此外，假设对 $L$ 的所有极小值点 ${\bm{w}}^{\star}$，随机一阶 oracle 的方差都以 $\sigma^{2}$ 为界。以 $\mathbb{E}_{S_{0},\ldots,S_{T-1}}$ 表示与随机 oracle 关联的随机性，则在步长为 $\gamma\leq 1/(4\beta)$ 时 [115]，有For example, consider applying a stochastic gradient descent on the expectation of $\beta$-smooth convex functions $L({\bm{w}};{\bm{s}})$ with unbiased oracles. To harness the randomness of the iterates, consider after $T$ iterations outputting the average of the first $T$ iterates, that is $\bar{\bm{w}}^{T}\coloneqq\frac{1}{T}\sum_{t=1}^{T}{\bm{w}}^{t}$. Moreover, suppose that the variance of the stochastic first-order oracles is bounded by $\sigma^{2}$ for all minimizers ${\bm{w}}^{\star}$ of $L$. Denoting by $\mathbb{E}_{S_{0},\ldots,S_{T-1}}$ the randomness associated to the stochastic oracles, we have then that for a stepsize $\gamma\leq 1/(4\beta)$ [115],

$$\mathbb{E}_{S_{0},\ldots,S_{T-1}}[L(\bar{\bm{w}}^{T})]-L^{\star}\\ \leq\frac{1}{\gamma T}\|{\bm{w}}_{0}-{\bm{w}}^{\star}\|_{2}^{2}+2\gamma\sigma^{2}.$$

所得的收敛速率表明，随机梯度下降会收敛到期望目标函数的最小值，但相差一个依赖于 oracle 方差与步长的常数项。人们可以通过采用小批量来减小该方差：若单个随机梯度的方差为 $\sigma_{1}^{2}$，则由 $m$ 个梯度组成的小批量会将相应 oracle 的方差降低为 $\sigma^{2}_{m}=\sigma_{1}^{2}/m$。为减小这一附加项，也可以在迭代过程中逐渐减小步长。例如，通过选择如 $\gamma^{t}=t^{-1/2}$ 这样的递减步长，收敛速率便为 $O((\|{\bm{w}}_{0}-{\bm{w}}^{\star}\|_{2}^{2}+\sigma^{2}\ln t)/\sqrt{t})$ 量级。步长也可以取为常数 $\gamma_{0}$，它使前 $T_{0}$ 次迭代的平均目标值下降，并以固定间隔乘以一个乘性因子，例如对 $\rho\in(0,1)$ 取 $\gamma_{j}=\rho\gamma_{j-1}$，以处理 $T_{j},T_{j+1}$ 之间的迭代。诸如余弦衰减 [122] 之类的其他步长调度方案近来也颇为流行。The resulting convergence rate illustrates that a stochastic gradient descent converges to the minimum of the expected objective up to a constant term depending on the variance of the oracle and the stepsize. One can diminish the variance by considering mini-batches: if the variance of a single stochastic gradient is $\sigma_{1}^{2}$, considering a mini-batch of $m$ gradients reduces the variance of the corresponding oracle to $\sigma^{2}_{m}=\sigma_{1}^{2}/m$. To decrease the additional term, one may also decrease the stepsizes over the iterations. For example, by choosing a decreasing stepsize like $\gamma^{t}=t^{-1/2}$, the convergence rate is then of the order $O((\|{\bm{w}}_{0}-{\bm{w}}^{\star}\|_{2}^{2}+\sigma^{2}\ln t)/\sqrt{t})$. The stepsize can also be selected as a constant $\gamma_{0}$ that decreases the average objective for the first $T_{0}$ iterations and is reduced by a multiplicative factor at regular intervals like $\gamma_{j}=\rho\gamma_{j-1}$ for $\rho\in(0,1)$ to handle iterations between $T_{j},T_{j+1}$. Alternative stepsize schedules such as a cosine decay [122] have recently become popular.

关于随机优化的其他方案的文献仍在迅速发展，新的启发式方法不断被提出。下面我们介绍两种流行的方法。The literature on alternative optimization schemes for stochastic optimization is still rapidly evolving, with new heuristics regularly proposed. We present below two popular techniques.

确定性设定下发展出的加速优化算法，可以推广到随机设定。例如，将重球法适配到随机设定，便得到带动量的随机梯度下降 [191]，其通常实现为Accelerated optimization algorithms developed in the deterministic setting may be extended to the stochastic setting. For example, the heavy-ball method can be adapted to the stochastic setting, leading to stochastic gradient descent with momentum [191] generally implemented as

$$\displaystyle{\bm{v}}^{t+1}$$	$$\displaystyle\coloneqq\nu{\bm{v}}^{t}+{\bm{g}}({\bm{w}}^{t};S^{t})$$
$$\displaystyle{\bm{w}}^{t+1}$$	$$\displaystyle\coloneqq{\bm{w}}^{t}-\gamma{\bm{v}}^{t+1}.$$

如前所述，可以对动量方法加以修改，以处理非二次的光滑强凸函数。这在确定性设定下引出了 Nesterov 加速方法；该方法已被适配到随机设定，并采用所谓的 Nesterov 动量 [191]As mentioned earlier the momentum method can be modified to handle non-quadratic smooth strongly convex functions. This leads to Nesterov’s accelerated method in the deterministic setting. This has been adapted to the stochastic setting with a so-called Nesterov momentum [191]

$$\displaystyle{\bm{v}}^{t+1}$$	$$\displaystyle\coloneqq\nu{\bm{v}}^{t}+{\bm{g}}({\bm{w}}^{t}-\gamma\nu{\bm{v}}^{t};S^{t})$$
$$\displaystyle{\bm{w}}^{t+1}$$	$$\displaystyle\coloneqq{\bm{w}}^{t}-\gamma{\bm{v}}^{t+1}.$$

在任何类梯度下降算法中，步长的选取都是获得良好性能的关键。若函数光滑，可以使用常数步长，但我们可能事先并不知道目标函数的光滑性常数，这意味着可能需要额外的过程来适当地选取步长。在确定性情形下，可以使用诸如 Armijo 或 Wolfe 准则 [211] 之类的线搜索，在每次迭代中检验所选步长是否使目标函数充分下降。此类准则已被调整以适应随机设定 [200]。In any gradient descent-like algorithm, selecting the stepsize is key for good performance. While a constant stepsize may be used if the function is smooth, we may not know in advance the smoothness constant of the objective, which means that additional procedures may be required to select appropriately the stepsize. In the deterministic case, line-searches such as the Armijo or Wolfe’s rules [211] can be used to check whether the selected stepsize sufficiently decreases the objective at each iteration. Such rules have been adapted in the stochastic setting [200].

降低算法对步长敏感性的另一条途径，是估计梯度的一阶矩与二阶矩，并将后者用作一种预条件，以平滑迭代值的轨迹。这引出了流行的 Adam 优化器 [106]，其形式为Another way to decrease the sensitivity of the algorithm with respect to the stepsize has been to estimate first- and second-order moments of the gradients and use the latter as a form of preconditioning to smooth the trajectory of the iterates. This led to the popular Adam optimizer [106]. It takes the form,

$$\displaystyle{\bm{m}}^{t+1}$$	$$\displaystyle\coloneqq\nu_{1}{\bm{m}}^{t}+(1-\nu_{1}){\bm{g}}^{t}$$
$$\displaystyle{\bm{v}}^{t+1}$$	$$\displaystyle\coloneqq\nu_{2}{\bm{v}}^{t}+(1-\nu_{2})({\bm{g}}^{t})^{2}$$
$$\displaystyle\hat{{\bm{m}}}^{t}$$	$$\displaystyle\coloneqq{\bm{m}}^{t}/{(1-\nu_{1}^{t})}$$
$$\displaystyle\hat{{\bm{v}}}^{t}$$	$$\displaystyle\coloneqq{\bm{v}}^{t}/{(1-\nu_{2}^{t})}$$
$$\displaystyle{\bm{w}}^{t+1}$$	$$\displaystyle\coloneqq{\bm{w}}^{t}-\gamma\ \hat{{\bm{m}}}^{t+1}/\left({\sqrt{\hat{{\bm{v}}}^{t+1}}+\varepsilon}\right),$$

其中 ${\bm{g}}^{t}\coloneqq{\bm{g}}({\bm{w}}^{t};S^{t})$，$({\bm{g}}^{t})^{2}$ 表示 ${\bm{g}}^{t}$ 的逐元素平方，$\nu_{1},\nu_{2},\gamma,\varepsilon$ 则是该算法的超参数。该算法变体众多，例如可在迭代过程中改变上式中的步长 $\gamma$。where ${\bm{g}}^{t}\coloneqq{\bm{g}}({\bm{w}}^{t};S^{t})$, $({\bm{g}}^{t})^{2}$ denotes the element-wise square of ${\bm{g}}^{t}$ and $\nu_{1},\nu_{2},\gamma,\varepsilon$ are hyper-parameters of the algorithm. Numerous variants exist, such as varying the stepsize $\gamma$ above along the iterations.

投影梯度下降是基于欧几里得投影 oracle 对梯度下降的自然推广。其迭代值写为Projected gradient descent is a natural generalization of gradient descent, based on the Euclidean projection oracle. Its iterates read

$${\bm{w}}^{t+1}\coloneqq\mathrm{proj}_{\mathcal{C}}({\bm{w}}^{t}-\gamma\nabla L({\bm{w}}^{t})).$$

在每次迭代中，我们尝试沿负梯度方向移动以降低目标函数值，同时借助投影步骤确保下一个迭代值仍然可行。At each iteration, we attempt to decrease the objective by moving along the negative gradient direction, while ensuring that the next iterate remains feasible, thanks to the projection step.

与式 16.2 中梯度下降的变分视角类似，投影梯度下降的更新等价于Similarly to the variational perspective of gradient descent in Eq. 16.2, the projected gradient descent update is equivalent to

$${\bm{w}}^{t+1}=\argmin_{{\bm{w}}\in\mathcal{C}}L({\bm{w}}^{t})+\langle\nabla L({\bm{w}}^{t}),{\bm{w}}-{\bm{w}}^{t}\rangle+\frac{1}{2\gamma}\|{\bm{w}}-{\bm{w}}^{t}\|_{2}^{2}.$$

这表明，投影梯度下降最小化的是这样一种权衡：既要接近 ${\bm{w}}^{t}$，又要最小化 $L$ 在 ${\bm{w}}^{t}$ 附近的线性化，同时保持在 $\mathcal{C}$ 中。This shows that projected gradient descent minimizes a trade-off between staying close to ${\bm{w}}^{t}$ and minimizing the linearization of $L$ around ${\bm{w}}^{t}$, while staying in $\mathcal{C}$.

就收敛速率而言，它们与梯度下降保持一致 [146]。例如，对于光滑凸函数，投影梯度下降仍以 $R(T)=O(1/T)$ 的速率收敛。In terms of convergence rates, they remain the same as gradient descent [146]. For example, projected gradient descent on a smooth convex function still converges at a rate $R(T)=O(1/T)$.

朴素投影梯度下降有许多扩展。与梯度下降类似，步长可以通过线搜索技术自动调整，并且存在加速变体。若将 $\nabla L({\bm{w}})$ 替换为随机梯度 $\nabla L({\bm{w}};S)$，就得到随机投影梯度下降。There are numerous extensions of vanilla projected gradient descent. Similarly to gradient descent, the stepsize can be automatically adjusted using linesearch techniques and there exists accelerated variants. If we replace $\nabla L({\bm{w}})$ with a stochastic gradient $\nabla L({\bm{w}};S)$, we obtain a stochastic projected gradient descent.

在无约束情形下，极小值点的梯度必然为零。在约束设定下，可能不存在梯度为零的可行参数。此时，一个点的最优性由如下事实刻画：在该点沿梯度移动且保持在约束内时，找不到更好的解。形式上，这意味着对任意 $\gamma>0$，$L$ 在 $\mathcal{C}$ 上的极小值点 ${\bm{w}}^{\star}$ 满足In the unconstrained case, a minimum necessarily has a zero gradient. In the constrained setting, there may not be any feasible parameters with zero gradient. Instead, the optimality of a point is characterized by the fact that no better solution can be found by moving along the gradient at that point, while staying in the constraints. Formally, it means that for any $\gamma>0$, a minimizer ${\bm{w}}^{\star}$ of $L$ on $\mathcal{C}$ satisfies

$${\bm{w}}^{\star}=\mathrm{proj}_{\mathcal{C}}({\bm{w}}^{\star}-\gamma\nabla L({\bm{w}}^{\star})).$$

可以证明，该条件等价于 [146]It can be shown that this condition is equivalent [146] to

$$\langle\nabla L({\bm{w}}^{\star}),{\bm{w}}-{\bm{w}}^{\star}\rangle\geq 0\quad\forall{\bm{w}}\in{\mathcal{C}}.$$

下面我们简要回顾几个有用的欧几里得投影。We now briefly review a few useful Euclidean projections.

• •

  若 $\mathcal{C}=\mathbb{R}^{P}$，显然有If $\mathcal{C}=\mathbb{R}^{P}$, we obviously have

  $$\mathrm{proj}_{\mathcal{C}}({\bm{w}})={\bm{w}}.$$

  因此，在无约束设定下，投影梯度下降确实退化为梯度下降。Therefore, in the unconstrained setting, projected gradient descent indeed recovers gradient descent.

• •

  若 $\mathcal{C}=[a,b]^{P}$（盒约束），则有If $\mathcal{C}=[a,b]^{P}$ (box constraints), we have

  $$\mathrm{proj}_{\mathcal{C}}({\bm{w}})=\mathrm{clip}({\bm{w}},a,b)\coloneqq\min\{\max\{{\bm{w}},a\},b\}.$$

  其中 $\min$ 与 $\max$ 是按坐标逐一施加的。where the $\min$ and $\max$ are applied coordinate-wise.

• •

  作为上述情形的特例，若 $\mathcal{C}=\mathbb{R}_{+}^{P}$（非负象限），As a special case of the above, if $\mathcal{C}=\mathbb{R}_{+}^{P}$ (non-negative orthant),

  $$\mathrm{proj}_{\mathcal{C}}({\bm{w}})=\max\{{\bm{w}},0\},$$

  这也称为非负部分或 ReLU。also known as non-negative part or ReLU.

• •

  若 $\mathcal{C}=\triangle^{P}$（单位概率单纯形），If $\mathcal{C}=\triangle^{P}$ (unit probability simplex),

  $$\mathrm{proj}_{\mathcal{C}}({\bm{w}})=\max\{{\bm{w}}-\tau\operatorname{\mathbf{1}},0\},$$

  其中 $\tau\in\mathbb{R}$ 是一个常数，用来确保 $\mathrm{proj}_{\mathcal{C}}({\bm{w}})$ 归一化为 $1$。已知可通过一次排序在 $O(P\log P)$ 时间内求出 $\tau$。利用类似寻找中位数的算法，可将其改进为 $O(P)$。where $\tau\in\mathbb{R}$ is a constant ensuring that $\mathrm{proj}_{\mathcal{C}}({\bm{w}})$ normalizes to $1$. It is known that $\tau$ can be found in $O(P\log P)$ using a sort. This can be improved to $O(P)$ using a median-finding like algorithm.

在该方法中，更新式为With this method, the update reads

$${\bm{w}}^{t+1}=\mathrm{prox}_{\gamma\Omega}({\bm{w}}^{t}-\gamma\nabla L({\bm{w}}^{t})).$$

这一更新同样具有直观的变分解释，即This update again enjoys an intuitive variational perspective, namely,

$${\bm{w}}^{t+1}=\argmin_{{\bm{w}}\in\mathcal{W}}L({\bm{w}}^{t})+\langle\nabla L({\bm{w}}^{t}),{\bm{w}}-{\bm{w}}^{t}\rangle+\frac{1}{2\gamma}\|{\bm{w}}-{\bm{w}}^{t}\|_{2}^{2}+\Omega({\bm{w}}).$$

也就是说，我们把 $L$ 在 ${\bm{w}}^{t}$ 附近线性化，而保持 $\Omega$ 不变。That is, we linearize $L$ around ${\bm{w}}^{t}$, but keep $\Omega$ as is.

当目标函数含有促稀疏的正则化项 $\Omega$ 时，邻近梯度法尤为常用。例如，LASSO [195] 旨在由观测 ${\bm{X}}=({\bm{x}}_{1},\ldots,{\bm{x}}_{n})^{\top}\in\mathbb{R}^{N\times P}$ 预测目标值 ${\bm{y}}=(y_{1},\ldots,y_{n})^{\top}\in\mathbb{R}^{N}$，此时我们取 $L({\bm{w}})=\frac{1}{2}\|{\bm{X}}{\bm{w}}-{\bm{y}}\|_{2}^{2}$、$\Omega({\bm{w}})=\lambda\|{\bm{w}}\|_{1}$，其中 $\lambda>0$ 控制正则化强度。这时，$\mathrm{prox}_{\Omega}$ 正是所谓的软阈值算子（见下文）。The proximal gradient method is popularly used when the objective function contains a sparsity-inducing regularizer $\Omega$. For example, for the LASSO [195], which aims at predicting targets ${\bm{y}}=(y_{1},\ldots,y_{n})^{\top}\in\mathbb{R}^{N}$ from observations ${\bm{X}}=({\bm{x}}_{1},\ldots,{\bm{x}}_{n})^{\top}\in\mathbb{R}^{N\times P}$, we set $L({\bm{w}})=\frac{1}{2}\|{\bm{X}}{\bm{w}}-{\bm{y}}\|_{2}^{2}$ and $\Omega({\bm{w}})=\lambda\|{\bm{w}}\|_{1}$, where $\lambda>0$ controls the regularization strength. In this case, $\mathrm{prox}_{\Omega}$ is the so-called soft-thresholding operator (see below).

邻近梯度法的收敛性保证与梯度下降相同，例如对光滑凸函数可达到 $O(1/T)$ 的速率。Convergence guarantees of the proximal gradient method remain the same as for gradient descent, such as a $O(1/T)$ rate for smooth convex functions.

该问题的最优解由如下不动点方程刻画：An optimal solution of the problem is characterized by the fixed point equation

$${\bm{w}}^{\star}=\mathrm{prox}_{\gamma\Omega}({\bm{w}}^{\star}-\gamma\nabla L({\bm{w}}^{\star})),$$

对一切 $\gamma>0$ 成立 [146]。换言之，邻近梯度法（梯度下降与投影梯度下降均为其特例）可视为不动点迭代方案。这一视角提示我们可采用不动点文献中的加速方法，例如 Anderson 加速 [157]；在设计第 8 章所述的隐式微分方案时，这一视角同样有用。for all $\gamma>0$ [146]. In other words, the proximal gradient method (which includes gradient descent and projected gradient descent as special cases), can be seen as fixed point iteration schemes. Such a viewpoint suggests using acceleration methods from the fixed point literature such as Anderson acceleration [157]. It is also useful when designing implicit differentiation schemes as presented in Chapter 8.

下面简要回顾几个有用的邻近算子。We now briefly review a few useful proximal operators.

• •

  若 $\Omega({\bm{w}})=0$，则If $\Omega({\bm{w}})=0$, we have

  $$\mathrm{prox}_{\gamma\Omega}({\bm{w}})={\bm{w}}.$$

  因此，采用这一邻近算子时，邻近梯度法即退化为梯度下降。Therefore, with this proximal operator, the proximal gradient method recovers gradient descent.

• •

  若 $\Omega({\bm{w}})=\iota_{\mathcal{C}}({\bm{w}})$，则If $\Omega({\bm{w}})=\iota_{\mathcal{C}}({\bm{w}})$, we have

  $$\mathrm{prox}_{\gamma\Omega}({\bm{w}})=\mathrm{proj}_{\mathcal{C}}({\bm{w}}).$$

  因此，采用这一邻近算子时，邻近梯度法即恢复为投影梯度下降。Therefore, with this proximal operator, the proximal gradient method recovers projected gradient descent.

• •

  若 $\Omega({\bm{w}})=\lambda\|{\bm{w}}\|_{1}$，则If $\Omega({\bm{w}})=\lambda\|{\bm{w}}\|_{1}$, we have

  $$\mathrm{prox}_{\gamma\Omega}({\bm{w}})=(\mathrm{sign}({\bm{w}})\cdot\max(|{\bm{w}}|-\gamma\lambda,0)),$$

  其中各运算均按坐标逐一进行。这就是所谓的软阈值算子。where the operations are applied coordinate-wise. This is the so-called soft-thresholding operator.

• •

  若 $\Omega({\bm{w}})=\lambda\sum_{g\in G}\|{\bm{w}}_{g}\|_{2}$，其中 $G$ 是 $[P]$ 的一个划分，${\bm{w}}_{g}$ 表示限制在 $g$ 上的子向量，则有$\Omega({\bm{w}})=\lambda\sum_{g\in G}\|{\bm{w}}_{g}\|_{2}$ where $G$ is a partition of $[P]$ and ${\bm{w}}_{g}$ denotes the subvector restricted to $g$, then we have

  $$\left[\mathrm{prox}_{\gamma\Omega}({\bm{w}})\right]_{g}=\max(1-\lambda\cdot\gamma/\|{\bm{w}}_{g}\|_{2},0){\bm{w}}_{g},$$

  该算子用于 group lasso [213]，可用来促使组稀疏。which is used in the group lasso [213] and can be used to encourage group sparsity.

关于更多邻近算子的综述，可参见例如 [7, 150]。For a review of more proximal operators, see for instance [7, 150].