第 15 章 优化基础Chapter 15 Optimization basics

考虑一个函数 $L$，例如它评估带有参数 ${\bm{w}}\in\mathcal{W}$ 的模型所达到的误差或“损失”$L({\bm{w}})$，其中 $\mathcal{W}=\mathbb{R}^{P}$。为了找到尽可能好的模型参数化，我们寻求最小化 $L({\bm{w}})$，也就是近似计算Consider a function $L$, for example evaluating the error or “loss” $L({\bm{w}})$ achieved by a model with parameters ${\bm{w}}\in\mathcal{W}$, where $\mathcal{W}=\mathbb{R}^{P}$. To find the best possible model parameterization, we seek to minimize $L({\bm{w}})$, that is, to compute approximately

$$L^{\star}\coloneqq\inf_{{\bm{w}}\in\mathcal{W}}L({\bm{w}}),$$

假设下确界存在（即 $L({\bm{w}})$ 有下界）。若解存在，我们将把它记为assuming that the infimum exists (i.e., $L({\bm{w}})$ is lower bounded). We will denote a solution, if it exists, by

$${\bm{w}}^{\star}\in\argmin_{{\bm{w}}\in\mathcal{W}}L({\bm{w}})\coloneqq\left\{{\bm{w}}\in\mathcal{W}:L({\bm{w}})=\min_{{\bm{w}}^{\prime}\in\mathcal{W}}L({\bm{w}}^{\prime})\right\}.$$

通常情况下，解析解并不存在，因而要近似求出这样的最小值，就需要借助优化算法。优化算法是一种迭代过程：它从初始点 ${\bm{w}}^{0}$ 出发，经过 $t$ 次迭代后，输出一个点 ${\bm{w}}^{t}$，该点可在一定精度 $\varepsilon$ 内近似 $L$ 的最小值，即In general, an analytical solution is not available and computing such a minimum approximately requires an optimization algorithm. An optimization algorithm is an iterative procedure, which, starting from an initial point ${\bm{w}}^{0}$, outputs after $t$ iterations a point ${\bm{w}}^{t}$ that approximates the minimum of $L$ up to some accuracy $\varepsilon$, i.e.,

$$L({\bm{w}}^{t})-L^{\star}\leq\varepsilon.$$

(15.1)

为了产生收敛到最小值的迭代值 ${\bm{w}}^{1},{\bm{w}}^{2},\dots$，算法自然需要获取关于 $L$ 的信息。例如，算法首先要能对 $L$ 求值，以判断它是否使函数值下降。这类关于函数的信息由 oracle 的概念加以形式化[143]。形式上，oracle 是算法可以调用的过程，用以在任意给定点 ${\bm{w}}\in\mathcal{W}$ 处获取关于目标函数 $L({\bm{w}})$ 的信息。我们通常主要考虑以下三种 oracle。To produce iterates ${\bm{w}}^{1},{\bm{w}}^{2},\dots$ that converge to a minimum, the algorithm naturally needs to have access to information about $L$. For example, the algorithm needs a priori to be able to evaluate $L$ to know if it decreased its value or not. Such information about the function is formalized by the notion of oracles [143]. Formally, oracles are procedures that an algorithm can call to access information about the objective $L({\bm{w}})$ at any given point ${\bm{w}}\in\mathcal{W}$. We usually mainly consider the following three oracles.

• •

  零阶 oracle：对函数 $L({\bm{w}})\in\mathbb{R}$ 求值。Zero-order oracle: evaluating the function $L({\bm{w}})\in\mathbb{R}$.

• •

  一阶 oracle：当 $L$ 可微时，对梯度 $\nabla L({\bm{w}})\in\mathcal{W}$ 求值。First-order oracle: evaluating the gradient $\nabla L({\bm{w}})\in\mathcal{W}$ for $L$ differentiable.

• •

  二阶 oracle：当 $L$ 二次可微时，对 Hessian 矩阵 $\nabla^{2}L({\bm{w}})$ 求值，或对任意向量 ${\bm{v}}\in\mathcal{W}$ 求 Hessian—向量乘积（HVP）$\nabla^{2}L({\bm{w}}){\bm{v}}\in\mathcal{W}$。Second-order oracle: evaluating the Hessian matrix $\nabla^{2}L({\bm{w}})$, or evaluating the Hessian-vector product (HVP) $\nabla^{2}L({\bm{w}}){\bm{v}}\in\mathcal{W}$, for $L$ twice differentiable and any vector ${\bm{v}}\in\mathcal{W}$.

给定函数 $L$ 的一个 oracle $\mathcal{O}$，便可将优化算法形式化地定义为一个过程：它根据此前与当前的全部信息计算下一个迭代值。形式上，算法 $\mathcal{A}$ 从起点 ${\bm{w}}^{0}$ 出发，构造序列 ${\bm{w}}^{1},\ldots,{\bm{w}}^{t}$ 如下：Given an oracle $\mathcal{O}$ for a function $L$, we can formally define an optimization algorithm as a procedure which computes the next iterate as a function of all past and current information. Formally, an algorithm $\mathcal{A}$ builds a sequence ${\bm{w}}^{1},\ldots,{\bm{w}}^{t}$ from a starting point ${\bm{w}}^{0}$ as

$${\bm{w}}^{t+1}\coloneqq\mathcal{A}({\bm{w}}^{0},\ldots,{\bm{w}}^{t},\mathcal{O}({\bm{w}}^{0}),\ldots,\mathcal{O}({\bm{w}}^{t}),{\bm{\lambda}}),$$

其中 ${\bm{\lambda}}\in\Lambda\subseteq\mathbb{R}^{Q}$ 封装了算法的若干超参数，例如步长。算法往往只依据当前迭代值处收集到的信息来构造下一个迭代值，而不动用全部过去的迭代值，即它们具有 ${\bm{w}}^{t+1}=\mathcal{A}({\bm{w}}^{t},\mathcal{O}({\bm{w}}^{t}),{\bm{\lambda}})$ 的形式。梯度下降算法便是一个经典例子：它借助一阶 oracle，算出如下形式的迭代值：where ${\bm{\lambda}}\in\Lambda\subseteq\mathbb{R}^{Q}$ encapsulates some hyperparameters of the algorithm, such as the stepsize. Oftentimes, algorithms build the next iterate simply from the information collected at the current iterate, without using all past iterates. That is, they take the form ${\bm{w}}^{t+1}=\mathcal{A}({\bm{w}}^{t},\mathcal{O}({\bm{w}}^{t}),{\bm{\lambda}})$. A classical example is the gradient descent algorithm, which uses a first-order oracle to compute iterates of the form

$${\bm{w}}^{t+1}\coloneqq{\bm{w}}^{t}-\gamma\nabla L({\bm{w}}^{t}),$$

其中步长 $\gamma$ 是该算法的一个超参数。可见，oracle 的概念划分出了不同的算法类别。例如，我们可以考虑零阶算法或一阶算法。where the stepsize $\gamma$ is a hyperparameter of the algorithm. The notion of oracle therefore delineates different classes of algorithms. For instance, we may consider zero-order algorithms or first-order algorithms.

最基本的优化算法之一是邻近点方法，它由 ${\bm{w}}^{t}$ 按下式产生 ${\bm{w}}^{t+1}$：One of the most basic optimization algorithms is the proximal point method, which produces ${\bm{w}}^{t+1}$ from ${\bm{w}}^{t}$ by

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

换言之，下一个迭代值来自在最小化函数 $L$ 与保持接近 ${\bm{w}}^{t}$ 之间所做的权衡。遗憾的是，执行这一参数更新所涉及的优化问题，其难度与原优化问题相当，因而邻近点方法并不实用。In words, the next iterate is produced by solving a trade-off between minimizing the function $L$ and staying close to ${\bm{w}}^{t}$. Unfortunately, the optimization problem involved in performing this parameter update is as difficult as the original optimization problem, making the proximal point method impractical.

正如我们将在第 16 章和第 17 章中看到的那样，许多优化算法都可以看作邻近点方法的一种近似，其含义是：这些算法求解As we shall see in Chapter 16 and Chapter 17, many optimization algorithms can be seen as an approximation of the proximal point method, in the sense that they solve

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

或更一般地，求解or more generally

$${\bm{w}}^{t+1}\coloneqq\argmin_{{\bm{w}}\in\mathcal{W}}\tilde{L}({\bm{w}},{\bm{w}}^{t})+\frac{1}{\gamma}d({\bm{w}},{\bm{w}}^{t}),$$

其中 $\tilde{L}({\bm{w}},{\bm{w}}^{t})$ 是 $L({\bm{w}})$ 在 ${\bm{w}}^{t}$ 附近的一个近似，而 $d({\bm{w}},{\bm{w}}^{\prime})$ 表示 ${\bm{w}}$ 与 ${\bm{w}}^{\prime}$ 之间的某种距离。对 $\tilde{L}$ 与 $d$ 的不同选择，会导出不同的优化算法以及不同的权衡。where $\tilde{L}({\bm{w}},{\bm{w}}^{t})$ is an approximation of $L({\bm{w}})$ around ${\bm{w}}^{t}$ and $d({\bm{w}},{\bm{w}}^{\prime})$ is some form of distance between ${\bm{w}}$ and ${\bm{w}}^{\prime}$. Different choices of $\tilde{L}$ and $d$ lead to different optimization algorithms, and to different trade-offs.

在理论上研究算法时，往往可以通过限制到某些函数类来陈述更强的结果。我们在第 2 章中已经讨论了连续函数与可微函数。本节再回顾另外几个重要的函数类。When studying algorithms theoretically, stronger results can often be stated by restricting to certain classes of functions. We already covered continuous and differentiable functions in Chapter 2. We review a few important other classes in this section.

对于给定的函数类，我们可以把算法的性能定义为：该算法找到一个如式 15.1 所示的 $\varepsilon$-精确解所需的迭代次数。这称为算法的计算复杂度，记为For a given class of functions, we can define the performance of an algorithm as the number of iterations the algorithm would need to find an $\varepsilon$-accurate solution as in Eq. 15.1. This is called the computational complexity of the algorithm, denoted

$$t=T(\varepsilon).$$

或者，算法的性能也可以用收敛速率来表述，即在 $t$ 次迭代后算法所达到的精度，Alternatively, the performance of an algorithm can be stated in terms of convergence rate, i.e., the accuracy that the algorithm reaches after $t$ iterations,

$$\varepsilon=R(t),$$

其中 $R$ 是一个随 $t\rightarrow+\infty$ 趋于零的递减正函数。通常，$R$ 会包含被极小化的函数的性质（例如其光滑性常数 $\beta$），以及关于初始点的信息（例如其函数值）。相应地，计算复杂度 $T(\varepsilon)$ 则定义为满足 $R(t)\leq\varepsilon$ 所需的最小迭代次数 $t$，where $R$ is a decreasing positive function vanishing as $t\rightarrow+\infty$. Usually, $R$ incorporates properties of the function minimized, such as its smoothness constant $\beta$ and information on the initial point, such as its function value. The corresponding computational complexity $T(\varepsilon)$ is then given as the minimum number of iterations $t$ such that $R(t)\leq\varepsilon$,

$$T(\varepsilon)=\min\{t\in\mathbb{N}\colon R(t)\leq\varepsilon\}.$$

收敛速率一般可以通过考察第 $t$ 次迭代的进展比来分类，该比值定义为Convergence rates can generally be classified by considering the progress ratio on iteration $t$, defined by

$$\rho_{t}\coloneqq\frac{R(t)}{R(t-1)}.$$

渐近收敛速率则定义为The asymptotic convergence rate is then defined by

$$\rho_{\infty}\coloneqq\lim_{t\rightarrow+\infty}\rho_{t}.$$

我们可以按如下方式对速率进行分类。We can classify the rates as follows.

1. 1.

   次线性收敛速率，$\rho_{\infty}=1$：算法运行得越久，进展越慢。也就是说，随着 $t\rightarrow+\infty$，相对进展最终趋于停滞。属于这一类的 $R(t)$ 的例子包括 $O(1/t),O(1/t^{2})$，或者更一般地，对某个 $\alpha>0$ 有 $O(1/t^{\alpha})$。这等价于 $T(\varepsilon)=O(\varepsilon^{-1/\alpha})$。Sublinear convergence rates, $\rho_{\infty}=1$: the longer the algorithm runs, the slower it makes progress. That is, the relative progress eventually tends to stall as $t\rightarrow+\infty$. Examples of $R(t)$ in this category include $O(1/t),O(1/t^{2})$ or more generally $O(1/t^{\alpha})$ for some $\alpha>0$. This is equivalent to $T(\varepsilon)=O(\varepsilon^{-1/\alpha})$.

2. 2.

   线性收敛速率，$\rho_{\infty}=c\in(0,1)$：算法最终会在每次迭代时达到恒定的相对进展状态，从而给出 $c$ 的总体速率 $R(t)=O(\exp(-ct))$，具体取决于目标函数的性质。这对应 $T(\varepsilon)=O(c^{-1}\ln\varepsilon^{-1})$。Linear convergence rates, $\rho_{\infty}=c\in(0,1)$: the algorithm eventually reaches a state of constant relative progress at each iteration, leading to an overall rate $R(t)=O(\exp(-ct))$ for $c$ depending on the properties of the objective. This corresponds to $T(\varepsilon)=O(c^{-1}\ln\varepsilon^{-1})$.

3. 3.

   超线性收敛速率，$\rho_{\infty}=0$：每次新的迭代中相对进展都更好。例如，$R(t)=O(\exp(-t^{2}))$ 时便可能发生这种情况，从而导致 $T(\varepsilon)=O(\sqrt{\ln\varepsilon^{-1}})$；或者 $R(t)=O(\exp(-2^{t}))$，这专门称为二次速率，会导致 $T(\varepsilon)=O(\ln\ln\varepsilon^{-1})$。Superlinear convergence rates, $\rho_{\infty}=0$: the relative progress is better at each new iteration. This can happen for, e.g., $R(t)=O(\exp(-t^{2}))$, leading to $T(\varepsilon)=O(\sqrt{\ln\varepsilon^{-1}})$, or $R(t)=O(\exp(-2^{t}))$, which is specifically called a quadratic rate, leading to $T(\varepsilon)=O(\ln\ln\varepsilon^{-1})$.

这一点如图 15.4 所示。This is illustrated in Fig. 15.4.

注意，“线性”一词可能引起误解，因为这些速率实际上按指数方式变化。它们之所以被称为“线性”，是因为其在对数尺度下的表现。Note that the term “linear” may be misleading as the rates are in fact exponential. They are called “linear” because of their behavior in log scale.

• •

  我们所能获得的关于某个函数的信息，可以用 oracle 这一概念来形式化。零阶 oracle 只能对函数求值；一阶 oracle 还能计算梯度；二阶 oracle 还能计算Hessian 矩阵或Hessian 矩阵—向量乘积（HVP）。The information available to us on a function can be formalized by the notion of oracle. Zero-order oracles can only evaluate the function; first-order oracles can also compute the gradient; second-order oracles can also compute the Hessian or the Hessian-vector product (HVP).

• •

  本书回顾的大多数优化算法都可以从变分视角来看待：在这一视角下，下一次迭代是通过在函数近似与邻近项之间进行权衡优化而产生的。不同的近似方式与不同的邻近项会导出不同的算法。Most optimization algorithms reviewed in this book can be viewed from a variational perspective, in which the next iteration is produced by optimizing a trade-off between an approximation of the function and a proximity term. Different approximations and different proximity terms lead to different algorithms.

• •

  我们还回顾了不同的函数类以及性能保证。We also reviewed different classes of functions, and performance guarantees.