第 13 章 通过优化进行平滑Chapter 13 Smoothing by optimization

下确卷积有时简称为 inf-conv。两个函数 $f$ 与 $g$ 的下确卷积会生成一个新函数 $f\square g$，其定义如下。Sometimes abbreviated inf-conv, the infimal convolution between two functions $f$ and $g$ creates a new function $f\square g$. It is defined as follows.

借助变量替换 ${\bm{u}}\coloneqq{\bm{\mu}}+{\bm{z}}$（这是一种位置—尺度变换，见 12.4.1 节），不难验证这三个定义确实彼此等价。It is easy to check that the three definitions are indeed equivalent, by using the change of variable ${\bm{u}}\coloneqq{\bm{\mu}}+{\bm{z}}$, which is a location-scale transform; see Section 12.4.1.

下确卷积可看作通常卷积的对应物，只是其中的积分被换成了最小化，其名称也正由此而来。与经典卷积一样，它具有交换性，即对任意 ${\bm{\mu}}\in\mathbb{R}^{M}$，都有The infimal convolution can be seen as a counterpart of the usual convolution, in which integration has been replaced by minimization (hence its name). Similarly to the classical convolution, it is commutative, meaning that for all ${\bm{\mu}}\in\mathbb{R}^{M}$, we have

$$(f\square g)({\bm{\mu}})=(g\square f)({\bm{\mu}}).$$

计算下确卷积需要求解一个最小化问题，而该问题未必有解析解。表 13.1 列出了若干例子。Computing the infimal convolution involves the resolution of a minimization problem, that may or may not enjoy an analytical solution. Some examples are given in Table 13.1.

当 $R({\bm{z}})\coloneqq\frac{1}{2}\|{\bm{z}}\|^{2}_{2}$ 时，下确卷积 $f\square R$ 给出所谓的 $f$ 的 Moreau 包络，它也称为 $f$ 的 Moreau-Yoshida 正则化。When $R({\bm{z}})\coloneqq\frac{1}{2}\|{\bm{z}}\|^{2}_{2}$, the infimal convolution $f\square R$ gives the so-called Moreau envelope of $f$, which is also known as Moreau-Yoshida regularization of $f$.

直观地说，Moreau 包络是在 ${\bm{u}}\in\mathbb{R}^{M}$ 上取到的最小值，它在按邻近项 $\frac{1}{2}\|{\bm{\mu}}-{\bm{u}}\|_{2}^{2}$ 保持与输入 ${\bm{\mu}}$ 接近与最小化 $f({\bm{u}})$ 之间做出权衡。只要该最小值点存在且唯一，便可定义 $f$ 的相应邻近算子：Intuitively, the Moreau envelope is the minimal value over ${\bm{u}}\in\mathbb{R}^{M}$ of a trade-off between staying close to the input ${\bm{\mu}}$ according to the proximity term $\frac{1}{2}\|{\bm{\mu}}-{\bm{u}}\|_{2}^{2}$ and minimizing $f({\bm{u}})$. Provided that the minimizer exists and is unique, we can define the associated proximal operator of $f$ as

$$\mathrm{prox}_{f}({\bm{\mu}})\coloneqq\argmin_{{\bm{u}}\in\mathbb{R}^{M}}\frac{1}{2}\|{\bm{\mu}}-{\bm{u}}\|_{2}^{2}+f({\bm{u}}).$$

换言之，对良定义的 $\mathrm{prox}_{f}({\bm{\mu}})$，有In other words, we have for $\mathrm{prox}_{f}({\bm{\mu}})$ well defined,

$$\mathrm{env}_{f}({\bm{\mu}})=f(\mathrm{prox}_{f}({\bm{\mu}}))+\frac{1}{2}\|{\bm{\mu}}-\mathrm{prox}_{f}({\bm{\mu}})\|_{2}^{2}.$$

(13.1)

Moreau 包络由 $\mathrm{env}_{f}({\bm{\mu}})\coloneqq\inf_{{\bm{u}}\in\mathbb{R}^{M}}f({\bm{u}})+\frac{1}{2}\|{\bm{\mu}}-{\bm{u}}\|_{2}^{2}$ 定义，因此仅适用于标量值函数 $f\colon\mathbb{R}^{M}\to\mathbb{R}$。为把 Moreau 包络推广到向量值函数 $f\colon\mathbb{R}^{M}\to\mathbb{R}^{T}$，其中 $f({\bm{u}})=(f_{1}({\bm{u}}),\dots,f_{T}({\bm{u}}))$，且对 $i\in[T]$ 有 $f_{i}\colon\mathbb{R}^{M}\to\mathbb{R}$，我们可以选择对每个 $f_{j}$ 分别进行平滑，从而定义The Moreau envelope is defined by $\mathrm{env}_{f}({\bm{\mu}})\coloneqq\inf_{{\bm{u}}\in\mathbb{R}^{M}}f({\bm{u}})+\frac{1}{2}\|{\bm{\mu}}-{\bm{u}}\|_{2}^{2}$. As such, it is limited to scalar-valued functions $f\colon\mathbb{R}^{M}\to\mathbb{R}$. To extend the Moreau envelope to vector-valued functions $f\colon\mathbb{R}^{M}\to\mathbb{R}^{T}$, where $f({\bm{u}})=(f_{1}({\bm{u}}),\dots,f_{T}({\bm{u}}))$ and $f_{i}\colon\mathbb{R}^{M}\to\mathbb{R}$ for $i\in[T]$, we may choose to smooth each $f_{j}$ separately to define

$$\mathrm{\mathbf{env}}_{f}({\bm{\mu}})\coloneqq(\mathrm{env}_{f_{1}}({\bm{\mu}}),\dots,\mathrm{env}_{f_{T}}({\bm{\mu}})),$$

其中where

$$\mathrm{env}_{f_{i}}({\bm{\mu}})=\inf_{{\bm{u}}_{i}\in\mathbb{R}^{M}}f_{i}({\bm{u}}_{i})+\frac{1}{2}\|{\bm{\mu}}-{\bm{u}}_{i}\|_{2}^{2}.$$

这一做法需要求解 $T$ 个各自独立的极小化问题，并对每个输出坐标 $i\in[T]$ 分别做平滑。由命题 2.3.16 可知，$\mathrm{\mathbf{env}}_{f}({\bm{\mu}})$ 沿任意方向 ${\bm{d}}=(d_{1},\dots,d_{T})\in\mathbb{R}^{T}$ 的 VJP 即为This approach requires to solve $T$ separate minimization problems and performs the smoothing of each output coordinate $i\in[T]$ independently. From Proposition 2.3.16, we then have that the VJP of $\mathrm{\mathbf{env}}_{f}({\bm{\mu}})$ with any direction ${\bm{d}}=(d_{1},\dots,d_{T})\in\mathbb{R}^{T}$ is

$$\displaystyle\partial\mathrm{\mathbf{env}}_{f}({\bm{\mu}})^{*}[{\bm{d}}]$$	$$\displaystyle=\sum_{i=1}^{T}\partial\mathrm{env}_{f_{i}}({\bm{\mu}})^{*}[d_{i}]$$
	$$\displaystyle=\sum_{i=1}^{T}d_{i}\nabla\mathrm{env}_{f_{i}}({\bm{\mu}}).$$

在 $f({\bm{u}})=(f_{1}(u_{1}),\dots,f_{T}(u_{T}))$ 这一特殊情形下，可得In the particular case $f({\bm{u}})=(f_{1}(u_{1}),\dots,f_{T}(u_{T}))$, we obtain

$$\partial\mathrm{\mathbf{env}}_{f}({\bm{\mu}})^{*}[{\bm{d}}]=\sum_{i=1}^{T}d_{i}\nabla\mathrm{env}_{f_{i}}(\mu_{i}).$$

文献 [171] 提出了另一种方案。回顾一下，对可微函数 $f\colon\mathbb{R}^{M}\to\mathbb{R}^{T}$，$f$ 沿方向 ${\bm{d}}\in\mathbb{R}^{T}$ 的 VJP 为An alternative was proposed by [171]. For a differentiable function $f\colon\mathbb{R}^{M}\to\mathbb{R}^{T}$, we recall that the VJP of $f$ with a direction ${\bm{d}}\in\mathbb{R}^{T}$ reads

$$\partial f({\bm{u}})^{*}[{\bm{d}}]=\nabla\langle f,{\bm{d}}\rangle({\bm{u}}),$$

其中我们定义了标量值函数 $\langle f,{\bm{d}}\rangle({\bm{u}})\coloneqq\langle f({\bm{u}}),{\bm{d}}\rangle$。于是，倘若 $f$ 不可微，一个自然的思路便是：用 Moreau 包络的梯度 $\nabla\mathrm{env}_{\langle f,{\bm{d}}\rangle}({\bm{\mu}})$ 来近似其（假若存在的话）VJP $\partial f({\bm{u}})^{*}[{\bm{d}}]$：where we defined the scalar-valued function $\langle f,{\bm{d}}\rangle({\bm{u}})\coloneqq\langle f({\bm{u}}),{\bm{d}}\rangle$. As a result, if $f$ is non-differentiable, a natural idea is to approximate its VJP $\partial f({\bm{u}})^{*}[{\bm{d}}]$ (had it existed) by the gradient $\nabla\mathrm{env}_{\langle f,{\bm{d}}\rangle}({\bm{\mu}})$ of the Moreau envelope

$$\mathrm{env}_{\langle f,{\bm{d}}\rangle}({\bm{\mu}})=\inf_{{\bm{u}}\in\mathbb{R}^{M}}\langle f({\bm{u}}),{\bm{d}}\rangle+\frac{1}{2}\|{\bm{\mu}}-{\bm{u}}\|^{2}_{2}.$$

(13.2)

这样只需解一个优化问题，与输出个数 $T$ 无关；而且当 ${\bm{d}}={\bm{e}}_{i}$ 时，还能把 $\mathrm{env}_{f_{i}}({\bm{\mu}})$ 作为一种特殊情形包含进来。This requires solving a single optimization problem, independently of the number of outputs $T$. Moreover, for ${\bm{d}}={\bm{e}}_{i}$, this recovers $\mathrm{env}_{f_{i}}({\bm{\mu}})$ as a special case.

原则上，这一方案使我们能够对层中使用 Moreau 包络的神经网络执行反向模式自动微分（梯度反向传播）。事实上，由命题 13.1.3，$f$ 沿方向 ${\bm{d}}$ 的近似 VJP 由下式给出This approach allows in principle to perform reverse-mode autodiff (gradient backpropagation) on a neural network whose layers use the Moreau envelope. Indeed, following Proposition 13.1.3, the approximate VJP of $f$ with a direction ${\bm{d}}$ is given by

$$\partial f({\bm{\mu}})^{*}[{\bm{d}}]\approx\nabla\mathrm{env}_{\langle f,{\bm{d}}\rangle}({\bm{\mu}})={\bm{\mu}}-{\bm{u}}^{\star},$$

其中 ${\bm{u}}^{\star}$ 是式 13.2 中极小化问题的解。但需要强调，这一极小化问题在一般情况下可能难以求解：执行梯度反向传播时，方向 ${\bm{d}}$ 未必非负，因此即便每个 $f_{i}$ 都是凸的，式 13.2 中所极小化的函数仍可能是非凸的。另一个隐患是：方向 ${\bm{d}}$ 会影响平滑强度，而按理说，无论是否计算函数的 VJP，我们都应能对该函数做平滑。举例来说，在 $f({\bm{u}})=(f_{1}(u_{1}),\dots,f_{T}(u_{T}))$ 这一特殊情形下，容易验证：当 ${\bm{d}}=(d_{1},\dots,d_{T})$ 时，可得where ${\bm{u}}^{\star}$ is the solution of the minimization problem in Eq. 13.2. However, we emphasize that this minimization problem could be difficult to solve in general. Indeed, when performing gradient backpropagation, the direction ${\bm{d}}$ is not necessarily non-negative, therefore the function being minimized in Eq. 13.2 could be nonconvex, even if each $f_{i}$ is convex. Another potential caveat is that the direction ${\bm{d}}$ influences the smoothing strength, while in principle we should be able to smooth a function independently of whether we compute its VJP or not. To see that, for example in the particular case $f({\bm{u}})=(f_{1}(u_{1}),\dots,f_{T}(u_{T}))$, one easily checks that for ${\bm{d}}=(d_{1},\dots,d_{T})$, we get

$$\mathrm{env}_{\langle f,{\bm{d}}\rangle}({\bm{\mu}})=\sum_{i=1}^{T}\mathrm{env}_{d_{i}f_{i}}(\mu_{i}).$$

用 Moreau 包络（更一般地说，用下确卷积）平滑向量值函数，仍是尚待探索的研究方向。第 14 章将说明，用卷积做平滑能更自然地处理向量值函数。Smoothing vector-valued functions by Moreau envelope (or more generally, by infimal convolution) remains an open area of research. We will see in Chapter 14 that smoothing by convolution more naturally supports vector-valued functions.

考虑如下形式的一类仿射函数Consider the class of affine functions of the form

$${\bm{u}}\mapsto\langle{\bm{u}},{\bm{v}}\rangle-b.$$

这些函数由斜率 ${\bm{v}}\in\mathbb{R}^{M}$ 与截距 $-b\in\mathbb{R}$ 参数化。现设 ${\bm{v}}$ 固定。给定函数 $f({\bm{u}})$，$f({\bm{u}})$ 的仿射下界即所有形如 ${\bm{u}}$ 的函数，其中 $b$ 对所有 ${\bm{u}}\in\mathbb{R}^{M}$ 均满足These functions are parametrized by their slope ${\bm{v}}\in\mathbb{R}^{M}$ and their intercept $-b\in\mathbb{R}$. Now, suppose we fix ${\bm{v}}$. Given a function $f({\bm{u}})$, affine lower bounds of $f({\bm{u}})$ are all the functions of ${\bm{u}}$ such that $b$ satisfies for all ${\bm{u}}\in\mathbb{R}^{M}$,

$$\langle{\bm{u}},{\bm{v}}\rangle-b\leq f({\bm{u}})\iff\langle{\bm{u}},{\bm{v}}\rangle-f({\bm{u}})\leq b.$$

最紧的下界由 $b$ 定义，使得The tightest lower bound is then defined by $b$ such that

$$b\coloneqq\sup_{{\bm{u}}\in\dom(f)}\langle{\bm{u}},{\bm{v}}\rangle-f({\bm{u}}),$$

其中，我们记得 $f$ 的定义域定义为where we recall that the domain of $f$ is defined by

$$\dom(f)\coloneqq\{{\bm{u}}\in\mathbb{R}^{M}\colon f({\bm{u}})<\infty\}.$$

由此引出 Legendre-Fenchel 变换的定义，又称凸共轭。This leads to the definition of Legendre-Fenchel transform, a.k.a. convex conjugate.

我们使用 $\sup$ 而非 $\max$，以表明 $f^{*}({\bm{v}})$ 可能为 $\infty$。依据前述讨论，$-f^{*}({\bm{v}})$ 是 $f({\bm{u}})$ 斜率为 ${\bm{v}}$ 的最紧仿射下界的截距。图 13.3 对此作了图示。We use a $\sup$ rather than a $\max$ to indicate that $f^{*}({\bm{v}})$ is potentially $\infty$. Following the previous discussion, $-f^{*}({\bm{v}})$ is the intercept of the tightest affine lower bound with slope ${\bm{v}}$ of $f({\bm{u}})$. This is illustrated in Fig. 13.3.

Legendre-Fenchel 变换是一种函数变换，因为它生成一个新的函数 $f^{*}$。它可以视为函数的一种对偶表示：我们不必再用凸函数 $f$ 在 ${\bm{u}}\in\dom(f)$ 上的图像 $({\bm{u}},f({\bm{u}}))$ 来表示它，而可以用一族切线来表示它：对 ${\bm{v}}\in\dom(f^{*})$，这些切线的斜率为 ${\bm{v}}$、截距为 $-f^{*}({\bm{v}})$，如图 13.4 所示。正如“凸共轭”这一名称所示，即便原函数不是凸的，它也是凸的。The Legendre-Fenchel transform is a function transformation, as it produces a new function $f^{*}$. It can be seen as a dual representation of a function: instead of representing a convex function $f$ by its graph $({\bm{u}},f({\bm{u}}))$ for ${\bm{u}}\in\dom(f)$, we can represent it by the set of tangents with slope ${\bm{v}}$ and intercept $-f^{*}({\bm{v}})$ for ${\bm{v}}\in\dom(f^{*})$, as illustrated in Fig. 13.4. As the name “convex conjugate” indicates, it is convex, even if the original function is not.

计算 $f^{*}({\bm{v}})$ 需要求解一个极大化问题；若对 $f$ 不加任何假设，一般情形下这往往颇为棘手。不过，在某些情形下仍可求得解析表达式，下面举例说明。Computing $f^{*}({\bm{v}})$ involves the resolution of a maximization problem, which could be difficult in general without assumption on $f$. In some cases, however, we can compute an analytical expression, as we now illustrate.

更多示例可参见 [33] 或 [18]。See for instance [33] or [18] for many more examples.

凸共轭具有若干有用的性质，现总结如下。The conjugate enjoys several useful properties, that we now summarize.

推导凸共轭的表达式一般可能相当困难，但在某些情形下，可以借助简单的法则，由其他共轭推导出所需的共轭。While deriving a convex conjugate expression can be difficult in general, in some cases, it is possible to use simple rules to derive conjugates in terms of other conjugates.

当解析表达式不可用时，可借助数值方案近似计算该变换／共轭。当 $f$ 为凸时，由于 $-f$ 为凹，定义 13.2.1 中的极大化即为凹函数的极大化。因此，借助经典的约束优化迭代算法，如投影梯度下降（16.3 节）或条件梯度法（又称 Frank-Wolfe 算法 [100]），可在多项式时间内以任意精度算出该共轭。若不对 $f$ 作凸性假设，则 $f^{*}({\bm{v}})$ 可近似为When an analytical expression is not available, we can resort to numerical schemes to approximately compute the transform / conjugate. When $f$ is convex, because $-f$ is concave, the maximization in Definition 13.2.1 is that of a concave function. Therefore, the conjugate can be computed to arbitrary precision in polynomial time using classical iterative algorithms for constrained optimization such as projected gradient descent (Section 16.3) or conditional gradient a.k.a. Frank-Wolfe [100]. Without convexity assumption on $f$, $f^{*}({\bm{v}})$ can be approximated by

$$f^{*}({\bm{v}})\approx\sup_{{\bm{u}}\in\mathcal{U}}\langle{\bm{u}},{\bm{v}}\rangle-f({\bm{u}}),$$

其中 $\mathcal{U}\subseteq\dom(f)$ 是取值的离散网格。随后，我们可以利用线性时间 Legendre 变换算法 [123]，针对若干个输入 ${\bm{v}}\in\mathcal{V}$ 计算对应的 $f^{*}({\bm{v}})$，其中 $\mathcal{V}\subseteq\dom(f^{*})$ 是另一个离散网格。其复杂度为 $O(|\mathcal{U}|\cdot|\mathcal{V}|)$，随网格规模线性增长。然而，网格规模通常为 $|\mathcal{U}|=|\mathcal{V}|=O(N^{M})$，即在 $M$ 个维度上各取 $N$ 个均匀分布的点。因此，该方法仅限于低维情形，例如 $M\in\{1,2,3\}$。where $\mathcal{U}\subseteq\dom(f)$ is a discrete grid of values. We can then compute $f^{*}({\bm{v}})$ for several inputs ${\bm{v}}\in\mathcal{V}$ using the linear-time Legendre transform algorithm [123], where $\mathcal{V}\subseteq\dom(f^{*})$ is another discrete grid. The complexity is $O(|\mathcal{U}|\cdot|\mathcal{V}|)$, which is linear in the grid sizes. However, the grid sizes are typically $|\mathcal{U}|=|\mathcal{V}|=O(N^{M})$, for $N$ equally-distributed points in each of the $M$ dimensions. Therefore, this approach is limited to small-dimensional settings, e.g., $M\in\{1,2,3\}$.