《动手学深度学习》凸性（Convexity）全解析：从凸集与凸函数到约束优化

人工智能深度学习机器学习教程【免费下载链接】d2l-zh《动手学深度学习》面向中文读者、能运行、可讨论。中英文版被70多个国家的500多所大学用于教学。项目地址https://gitcode.com/GitHub_Trending/d2/d2l-zh点击查看免费下载凸性是《动手学深度学习》d2l-zh优化章节的理论基石它决定了我们能否严格分析优化算法、能否在约束条件下高效求解。本文以 chapter_optimization/convexity_origin.md中文版见 chapter_optimization/convexity.md为核心完整讲解凸集、凸函数、詹森不等式、凸函数的关键性质以及拉格朗日、惩罚与投影三类处理约束的手段并结合仓库源码d2l/torch.py 等给出可运行的实验代码。读完本文你将掌握如何用定义与二阶导数判定函数凸性、为何凸函数的局部极小值必然是全局极小值以及权重衰减、梯度裁剪等日常技巧背后的约束优化原理。为什么优化算法设计离不开凸性凸性convexity在优化算法的设计中扮演着至关重要的角色其根本原因在于在凸性设定下对算法进行分析和测试要容易得多。换句话说如果一个算法在凸性条件下表现都很差那通常很难期望它在其他条件下产生好的结果——凸性相当于算法性能的基线测试。此外即使深度学习中的优化问题普遍是非凸的它们也经常在局部极小值附近表现出一定的凸性。这一观察催生了一些有趣的新优化变体如 :cite:Izmailov.Podoprikhin.Garipov.ea.2018所讨论的随机加权平均类方法使得凸性分析对深度学习实践依然具有直接价值。定义凸集与凸函数在进行凸分析之前需要先定义两个基础概念凸集convex sets与凸函数convex functions。凸集Convex Sets集合是凸性的基础。简单地说如果对于任何 $a, b \in \mathcal{X}$连接 $a$ 和 $b$ 的线段也位于 $\mathcal{X}$ 中则向量空间中的集合 $\mathcal{X}$ 是凸convex的。用数学语言表述即对所有 $\lambda \in [0, 1]$ 有$$\lambda a (1-\lambda) b \in \mathcal{X} \text{ 当 } a, b \in \mathcal{X}.$$如图 img/pacman.svg 所示第一组集合中存在不在集合内部的线段跨越了缺口所以该集合是非凸的另外两组则没有这样的问题。凸集有几个便于推导的性质交集保持凸性若 $\mathcal{X}$ 和 $\mathcal{Y}$ 都是凸集则 $\mathcal{X} \cap \mathcal{Y}$ 也是凸集。对任意 $a, b \in \mathcal{X} \cap \mathcal{Y}$由于 $\mathcal{X}$、$\mathcal{Y}$ 各自凸连接 $a$、$b$ 的线段同时包含在两个集合中故也包含在交集中见 img/convex-intersect.svg。这一结论可以毫不费力地推广到任意多个凸集的交集 $\cap_{i} \mathcal{X}_i$。并集不保持凸性考虑两个不相交的集合 $\mathcal{X} \cap \mathcal{Y} \emptyset$取 $a \in \mathcal{X}$、$b \in \mathcal{Y}$连接它们的线段必然包含一部分既不在 $\mathcal{X}$ 也不在 $\mathcal{Y}$ 中的点因此线段也不在 $\mathcal{X} \cup \mathcal{Y}$ 中即凸集的并集不一定是凸的见 img/nonconvex.svg。深度学习中的问题通常定义在凸集上。例如 $\mathbb{R}^d$实数 $d$ 维向量全体是凸集——$\mathbb{R}^d$ 中任意两点之间的线段仍位于 $\mathbb{R}^d$ 中。有时我们会处理有界长度的变量例如半径 $r$ 的球 ${\mathbf{x} \mid \mathbf{x} \in \mathbb{R}^d \text{ 且 } |\mathbf{x}| \leq r}$它同样是凸集。凸函数Convex Functions有了凸集就可以引入凸函数。给定凸集 $\mathcal{X}$若对所有 $x, x \in \mathcal{X}$ 和所有 $\lambda \in [0, 1]$ 满足$$\lambda f(x) (1-\lambda) f(x) \geq f(\lambda x (1-\lambda) x),$$则函数 $f: \mathcal{X} \to \mathbb{R}$ 是凸的。直观理解凸函数图像上任意两点间的弦总是位于函数图像上方或与之重合。下面用代码绘制几个函数直观检查哪些满足凸性条件# 以 PyTorch 版 d2l 包为例d2l/torch.py %matplotlib inline from d2l import torch as d2l import numpy as np from mpl_toolkits import mplot3d import torch f lambda x: 0.5 * x**2 # 凸函数抛物线 g lambda x: d2l.cos(np.pi * x) # 非凸函数余弦 h lambda x: d2l.exp(0.5 * x) # 凸函数指数 x, segment d2l.arange(-2, 2, 0.01), d2l.tensor([-1.5, 1]) d2l.use_svg_display() _, axes d2l.plt.subplots(1, 3, figsize(9, 3)) for ax, func in zip(axes, [f, g, h]): d2l.plot([x, segment], [func(x), func(segment)], axesax)如预期余弦函数是非凸的抛物线 $0.5x^2$ 与指数函数 $e^{0.5x}$ 是凸的。注意要求 $\mathcal{X}$ 是凸集是必要的——否则 $f(\lambda x (1-\lambda) x)$ 可能根本没有定义。这里的绘图工具d2l.plot、d2l.use_svg_display均定义在仓库的 d2l 包中例如 d2l/torch.py 中use_svg_display切换到 SVG 格式、set_figsize设置图表尺寸与plot绘制数据点并配置坐标轴、图例、网格d2l.cos、d2l.exp、d2l.arange、d2l.tensor则是 d2l/torch.py 中对 NumPy/Torch 常用接口的别名MXNet、TensorFlow、PaddlePaddle 版本分别在 d2l/mxnet.py、d2l/tensorflow.py、d2l/paddle.py 中提供了等价实现。詹森不等式Jensens Inequality给定凸函数 $f$最有用的数学工具之一是詹森不等式它是凸性定义的一种推广$$\sum_i \alpha_i f(x_i) \geq f\left(\sum_i \alpha_i x_i\right) \quad \text{且} \quad E_X[f(X)] \geq f\left(E_X[X]\right),$$其中 $\alpha_i$ 是满足 $\sum_i \alpha_i 1$ 的非负实数$X$ 是随机变量。换言之凸函数的期望不小于期望的凸函数而后者$f(E[X])$通常是一个更简单的表达式。证明第一个不等式只需对求和中的每一项逐一反复应用凸性定义即可。詹森不等式的一个常见应用是用简单表达式约束复杂表达式。例如对部分观测随机变量的对数似然由于 $\int P(Y) P(X \mid Y) dY P(X)$可得$$E_{Y \sim P(Y)}[-\log P(X \mid Y)] \geq -\log P(X).$$这在变分方法variational methods中非常有用$Y$ 通常是未观测到的随机变量$P(Y)$ 是对其分布的最佳猜测$P(X)$ 是将 $Y$ 积分掉后的分布。例如在聚类中$Y$ 可以是簇标签$P(X \mid Y)$ 是应用簇标签时的生成模型。凸函数的三个关键性质性质一局部极小值即全局极小值凸函数最重要的一条性质是凸函数的局部极小值也是全局极小值。可用反证法证明假设 $x^{\ast} \in \mathcal{X}$ 是一个局部极小值即存在很小的正值 $p$使得当 $x \in \mathcal{X}$ 满足 $0 |x - x^{\ast}| \leq p$ 时$f(x^{\ast}) f(x)$。再假设 $x^{\ast}$ 不是全局极小值存在 $x \in \mathcal{X}$ 使得 $f(x) f(x^{\ast})$。取 $\lambda 1 - \frac{p}{|x^{\ast} - x|}$$\lambda \in [0, 1)$则 $0 |\lambda x^{\ast} (1-\lambda) x - x^{\ast}| \leq p$即点 $\lambda x^{\ast} (1-\lambda) x$ 落在局部极小值点的邻域内。然而由凸性定义$$\begin{aligned} f(\lambda x^{\ast} (1-\lambda) x) \leq \lambda f(x^{\ast}) (1-\lambda) f(x) \ \lambda f(x^{\ast}) (1-\lambda) f(x^{\ast}) \ f(x^{\ast}), \end{aligned}$$这与$x^{\ast}$ 是局部极小值矛盾。因此不存在 $f(x) f(x^{\ast})$ 的点局部极小值 $x^{\ast}$ 必为全局极小值。例如凸函数 $f(x) (x-1)^2$ 在 $x1$ 处取得局部极小值同时这也是全局极小值。代码验证如下f lambda x: (x - 1) ** 2 d2l.set_figsize() d2l.plot([x, segment], [f(x), f(segment)], x, f(x))这条性质意味着最小化凸函数时我们不会卡住。但要注意它并不保证全局极小值唯一或必然存在$f(x) \mathrm{max}(|x|-1, 0)$ 在区间 $[-1, 1]$ 上处处取得最小值最小值集合是一个区间$f(x) \exp(x)$ 在 $\mathbb{R}$ 上没有最小值——当 $x \to -\infty$ 时函数值趋近于 $0$但不存在任何 $x$ 使 $f(x) 0$。性质二凸函数的下水平集是凸的可以通过凸函数的下水平集below sets方便地构造凸集。给定定义在凸集 $\mathcal{X}$ 上的凸函数 $f$任意下水平集$$\mathcal{S}_b : {x \mid x \in \mathcal{X} \text{ 且 } f(x) \leq b}$$都是凸的。证明很直接对任意 $x, x \in \mathcal{S}_b$即 $f(x) \leq b$、$f(x) \leq b$由凸性定义有$$f(\lambda x (1-\lambda) x) \leq \lambda f(x) (1-\lambda) f(x) \leq b,$$故 $\lambda x (1-\lambda) x \in \mathcal{S}_b$ 对一切 $\lambda \in [0, 1]$ 成立。性质三凸性与二阶导数Hessian的关系当函数的二阶导数存在时检验凸性非常简单只需检查 Hessian 是否半正定。对 $f: \mathbb{R}^n \to \mathbb{R}$记 Hessian 矩阵 $\nabla^2 f$ 为 $\mathbf{H}$则$$\nabla^2 f \succeq 0 \quad \iff \quad \mathbf{x}^\top \mathbf{H} \mathbf{x} \geq 0 \text{ 对所有 } \mathbf{x} \in \mathbb{R}^n.$$例如 $f(\mathbf{x}) \frac{1}{2}|\mathbf{x}|^2$ 是凸的因为 $\nabla^2 f \mathbf{I}$单位矩阵显然半正定。严格表述为一维情形二次可微函数 $f: \mathbb{R} \to \mathbb{R}$ 是凸的当且仅当 $f \geq 0$。多维情形二次可微函数 $f: \mathbb{R}^n \to \mathbb{R}$ 是凸的当且仅当 Hessian $\nabla^2 f \succeq 0$。一维情形的证明分为两步凸性 $\Rightarrow f \geq 0$由凸性定义直接有$$\frac{1}{2} f(x \epsilon) \frac{1}{2} f(x - \epsilon) \geq f\left(\frac{x \epsilon}{2} \frac{x - \epsilon}{2}\right) f(x),$$而二阶导数由有限差分极限给出故$$f(x) \lim_{\epsilon \to 0} \frac{f(x\epsilon) f(x - \epsilon) - 2f(x)}{\epsilon^2} \geq 0.$$$f \geq 0 \Rightarrow 凸性$f \geq 0$ 意味着 $f$ 单调非递减。设 $a x b$其中 $x (1-\lambda)a \lambda b$$\lambda \in (0, 1)$。由中值定理存在 $\alpha \in [a, x]$、$\beta \in [x, b]$ 使得$$f(\alpha) \frac{f(x) - f(a)}{x-a}, \quad f(\beta) \frac{f(b) - f(x)}{b-x}.$$由单调性 $f(\beta) \geq f(\alpha)$整理得$$\frac{x-a}{b-a}f(b) \frac{b-x}{b-a}f(a) \geq f(x).$$代入 $x (1-\lambda)a \lambda b$ 即得 $\lambda f(b) (1-\lambda)f(a) \geq f((1-\lambda)a \lambda b)$凸性得证。多维情形的证明借助一个引理$f: \mathbb{R}^n \to \mathbb{R}$ 是凸的当且仅当对任意 $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$一元函数 $g(z) : f(z\mathbf{x} (1-z)\mathbf{y})$$z \in [0, 1]$是凸的。方向一的验证如下$$\begin{aligned} g(\lambda a (1-\lambda) b) f\left((\lambda a (1-\lambda) b)\mathbf{x} (1-\lambda a - (1-\lambda) b)\mathbf{y}\right) \ f\left(\lambda (a\mathbf{x} (1-a)\mathbf{y}) (1-\lambda)(b\mathbf{x} (1-b)\mathbf{y})\right) \ \leq \lambda f(a\mathbf{x} (1-a)\mathbf{y}) (1-\lambda) f(b\mathbf{x} (1-b)\mathbf{y}) \ \lambda g(a) (1-\lambda) g(b). \end{aligned}$$反向只需取特殊点$$\begin{aligned} f(\lambda \mathbf{x} (1-\lambda) \mathbf{y}) g(\lambda \cdot 1 (1-\lambda) \cdot 0) \ \leq \lambda g(1) (1-\lambda) g(0) \ \lambda f(\mathbf{x}) (1-\lambda) f(\mathbf{y}). \end{aligned}$$最后把一维情形的结论套用到 $g(z)$ 上$g (\mathbf{x} - \mathbf{y})^\top \mathbf{H}(\mathbf{x} - \mathbf{y}) \geq 0$ 对一切 $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ 成立等价于 $\mathbf{H} \succeq 0$半正定矩阵定义。约束优化拉格朗日、惩罚与投影凸优化的一个突出优势是能高效处理约束constraints即求解如下约束优化问题$$\begin{aligned} \mathop{\mathrm{minimize~}}_{\mathbf{x}} \ f(\mathbf{x}) \ \text{subject to } \ c_i(\mathbf{x}) \leq 0 \text{ for all } i \in {1, \ldots, n}, \end{aligned}$$其中 $f$ 是目标函数$c_i$ 是约束函数。例如 $c_1(\mathbf{x}) |\mathbf{x}|_2 - 1$ 把参数限制在单位球内再加一个 $c_2(\mathbf{x}) \mathbf{v}^\top \mathbf{x} b$则对应半空间约束同时满足两者等价于取球的一个切片作为可行域。拉格朗日函数Lagrangian求解带约束优化问题通常是困难的。一个源自物理学的直观类比想象一个球在盒子里球会滚到最低处重力目标函数的负梯度方向与盒壁的推力约束函数梯度达到平衡。那些未被球接触的墙不活跃的约束不会对球施加任何力。这一推理可以用拉格朗日函数的鞍点优化问题来表达$$L(\mathbf{x}, \alpha_1, \ldots, \alpha_n) f(\mathbf{x}) \sum_{i1}^n \alpha_i c_i(\mathbf{x}) \text{ where } \alpha_i \geq 0.$$其中 $\alpha_i$$i 1, \ldots, n$称为拉格朗日乘数Lagrange multipliers取值恰好大到足以保证 $c_i(\mathbf{x}) \leq 0$ 对所有 $i$ 成立对天然满足 $c_i(\mathbf{x}) 0$ 的约束取 $\alpha_i 0$。这是一个鞍点优化问题需要关于 $\alpha_i$最大化$L$同时关于 $\mathbf{x}$最小化$L$。关于如何导出 $L$ 有大量文献这里只需知道$L$ 的鞍点处原始约束优化问题达到最优解。惩罚Penalties权重衰减的约束视角一种至少近似满足约束的办法是改造拉格朗日函数不强制 $c_i(\mathbf{x}) \leq 0$而是直接把 $\alpha_i c_i(\mathbf{x})$ 加到目标函数上确保约束不会被严重违反。事实上这个技巧在本书中一直在使用。以权重衰减为例详见 chapter_optimization/weight-decay.md在目标函数中加入 $\frac{\lambda}{2}|\mathbf{w}|^2$ 以确保 $\mathbf{w}$ 不会长得太大。从约束优化的角度看这等价于保证对某个半径 $r$ 有 $|\mathbf{w}|^2 - r^2 \leq 0$调节 $\lambda$ 即可改变 $\mathbf{w}$ 的大小——$\lambda$ 越大等效半径 $r$ 越小$\mathbf{w}$ 被压得越紧。一般而言添加惩罚是确保近似满足约束的好方法实践中比精确满足更稳健此外对非凸问题许多使精确方法在凸情形下富有吸引力的性质如最优性保证不再成立。投影Projections梯度裁剪的约束视角满足约束的另一条策略是投影projections。本书此前同样遇到过在 RNN 手写实现一章chapter_recurrent-neural-networks/rnn-scratch.md的梯度裁剪中通过$$\mathbf{g} \leftarrow \mathbf{g} \cdot \mathrm{min}(1, \theta/|\mathbf{g}|)$$把梯度长度限制在 $\theta$ 内。这本质上就是把 $\mathbf{g}$投影到半径为 $\theta$ 的球上。一般地凸集 $\mathcal{X}$ 上的投影定义为$$\mathrm{Proj}\mathcal{X}(\mathbf{x}) \mathop{\mathrm{argmin}}{\mathbf{x} \in \mathcal{X}} |\mathbf{x} - \mathbf{x}|,$$即 $\mathcal{X}$ 中离 $\mathbf{x}$ 最近的点。如图 img/projections.svg 所示图中有两个凸集——一个圆和一个菱形。位于两个集合内部的点黄色在投影后保持不变位于集合外部的点黑色被投影到集合内距离它们最近的点红色。对 $L_2$ 球而言投影不改变方向红色点在圆心到黑色点的射线上但一般而言并非如此——菱形$L_1$ 球在二维的形态情形下方向就可能改变。凸投影的一个典型用途是计算稀疏权重向量把权重向量投影到 $L_1$ 球上即 img/projections.svg 中菱形例子的广义版本这与 Lasso 类稀疏化方法一脉相承。小结在深度学习背景下凸函数的主要作用是帮助我们在细节层面理解优化算法——本节的后续内容chapter_optimization/gd.md 的梯度下降、chapter_optimization/minibatch-sgd.md 的随机梯度下降正是依托凸性框架推导的。核心结论归纳如下凸集的交集是凸的并集不一定是凸的由詹森不等式凸函数的期望不小于期望的凸函数二次可微函数是凸的当且仅当其 Hessian二阶导数矩阵半正定凸约束可通过拉格朗日函数处理实践中只需在目标函数中加入惩罚项即可近似满足投影把点映射到凸集中距离最近的点。练习假设我们想通过绘制集合内所有点对之间的连线并检查是否都在集合内来验证凸性(i) 证明只需检查边界上的点(ii) 证明只需检查集合的顶点。用 $p$-范数定义半径 $r$ 的球 $\mathcal{B}_p[r] : {\mathbf{x} \mid \mathbf{x} \in \mathbb{R}^d, |\mathbf{x}|_p \leq r}$证明 $\mathcal{B}_p[r]$ 对所有 $p \geq 1$ 是凸的。已知凸函数 $f$ 和 $g$证明 $\mathrm{max}(f, g)$ 也是凸函数并说明 $\mathrm{min}(f, g)$ 一般不是凸的。证明 softmax 函数的规范化项 $f(x) \log \sum_i \exp(x_i)$ 是凸的。证明线性子空间 $\mathcal{X} {\mathbf{x} \mid \mathbf{W}\mathbf{x} \mathbf{b}}$ 是凸集。证明当 $\mathbf{b} \mathbf{0}$ 时线性子空间上的投影可写成 $\mathrm{Proj}_\mathcal{X}(\mathbf{x}) \mathbf{M}\mathbf{x}$某个矩阵 $\mathbf{M}$。对二次可微凸函数 $f$证明存在 $\xi \in [0, \epsilon]$ 使 $f(x \epsilon) f(x) \epsilon f(x) \frac{1}{2}\epsilon^2 f(x \xi)$。给定向量 $\mathbf{w} \in \mathbb{R}^d$ 且 $|\mathbf{w}|_1 1$计算其在 $L_1$ 单位球上的投影(i) 写出带惩罚的目标 $|\mathbf{w} - \mathbf{w}|^2 \lambda|\mathbf{w}|_1$ 并对给定 $\lambda 0$ 求解(ii) 思考能否避免反复试错直接找到合适的 $\lambda$。给定凸集 $\mathcal{X}$ 和两个向量 $\mathbf{x}$、$\mathbf{y}$证明投影不会增加距离$|\mathbf{x} - \mathbf{y}| \geq |\mathrm{Proj}\mathcal{X}(\mathbf{x}) - \mathrm{Proj}\mathcal{X}(\mathbf{y})|$。以上练习与正文共同构成凸性一章的完整学习闭环进一步可结合 chapter_optimization/index.md 中其他章节梯度下降、随机梯度下降、动量、Adam 等体会凸性在优化算法分析中的贯穿作用。赞分享人工智能深度学习机器学习教程【免费下载链接】d2l-zh《动手学深度学习》面向中文读者、能运行、可讨论。中英文版被70多个国家的500多所大学用于教学。项目地址https://gitcode.com/GitHub_Trending/d2/d2l-zh点击查看免费下载相关推荐凸性与凸优化动手学深度学习中的优化算法理论基础凸性与凸优化动手学深度学习中的优化算法理论基础 本篇文章以《动手学深度学习》d2l zh 凸性章节 https://link.gitcode.com/i/人工智能深度学习机器学习教程凸性Convexity详解深度学习优化算法的理论基石与 D2L 实战指南凸性Convexity详解深度学习优化算法的理论基石与 D2L 实战指南 本文基于 D2Ld2l en https://link.gitcode.co文档教程人工智能深度学习NLP计算机视觉强化学习D2L 深度学习优化算法全指南从凸优化基础到 SGD 系列与学习率调度实战D2L 深度学习优化算法全指南从凸优化基础到 SGD 系列与学习率调度实战 本文围绕《动手学深度学习》D2L优化算法章节展开系统梳理从梯度下降、随机梯度文档教程人工智能深度学习NLP计算机视觉强化学习创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考