课件地址（Stanford EE364B：Convex Optimization for Neural Networks）

预备知识 (凸函数相关)

核心问题：如何将两层 ReLU 网络的非凸问题转为凸问题求解？

完整的推导路线图

1. 非凸的 L2 正则化网络 ↓ (变量缩放)
2. 等价的 L1 路径范数问题 ↓ (权重规范化)
3. 无限字典的 LASSO 问题 ↓ (凸对偶)
4. 半无限规划 (SIP) ↓ (超平面排列)
5. 有限维的凸对偶问题 (QCQP) ↓ (再次求对偶)
6. 最终的、可解的组 LASSO 问题

通过这个转换来理解“神经网络是凸正则化器”。它通过一个巧妙的变量缩放技巧，将一个看似复杂的 L2 正则化项，变成了一个形式更简单、更利于后续对偶分析的 L1 正则化项。

问题设定

场景设定

• 模型: 两层全连接 ReLU 网络。
• 损失函数: 平方损失。
• 正则化: 标准的 L2 权重衰减 (Weight Decay)。

我们的初始优化问题是：

其中， 是第一层权重矩阵（ 是其第 j 列）， 是第二层权重向量（ 是其第 j 个标量元素）。这是一个关于 和 的非凸问题。

第一步：变量缩放 (The Scaling Trick)

对于单个隐层神经元 j，我们可以对其权重对 进行缩放，而不改变网络的最终输出。

1.1. 定义缩放变换

为每个隐神经元 引入一个缩放因子 。定义新的权重为：

1.2. 为什么网络输出不变？

这一步依赖于 ReLU 函数 的正齐次性 (Positive Homogeneity)，即 对任何 成立。

因此，对任意一个神经元 ，其对最终输出的贡献为：

由于 ， 可以被提出来。可以看到，经过缩放后的新权重 产生的输出与原权重完全相同。因此，总模型的输出 和损失函数 的值也保持不变。

1.3. 正则化项如何变化？

虽然损失项不变，但正则化项会随着 的变化而改变。对于神经元 ，其正则化惩罚从 变为：

1.4. 寻找最优缩放

对于一组固定的 ，我们可以通过选择最优的 来最小化这个惩罚项。我们将 看作是关于 的函数，求其最小值：

令其导数为零：

解得最优的 满足：

将最优的 代回惩罚项，得到最小惩罚值为：

1.5. 结论：从 L2 到 L1 路径范数

这个结果表明，对于任意给定的权重 ，总能找到一组缩放因子 ，使得网络输出不变，但正则化项取得其可能的最小值 。

因此，原始的、带有 L2 权重衰减的优化问题，等价于下面这个新的优化问题：

这个新的正则化项 被称为路径范数 (Path-Norm)。它形似 L1 范数，因为它惩罚的是绝对值的和，这为后续的稀疏性分析和对偶变换奠定了基础。我们成功地将 L2 正则化“搬运”并转化为了一个结构更清晰的 L1 型正则化。

第二步：权重规范化与 LASSO 形式

为了使问题形式更加标准，我们进一步对权重进行分解。

2.1. 再次重参数化

对于每个 ，定义：

• 方向: ，这是一个单位向量，。
• 系数: 。

2.2. 代入模型

网络的输出可以重写为：

而路径范数正则项则变成了对新系数 的 L1 惩罚：

2.3. 等价的 LASSO 问题

吸收常数 2 到 中，我们得到了一个在形式上非常接近 LASSO (L1 正则化回归) 的问题：

这个问题要求我们在所有可能的“特征”（由单位向量 生成的 ）中，寻找一个稀疏的线性组合来拟合 。这正是后续进行凸对偶分析的出发点。

第三步：推导凸对偶，得到半无限规划 (SIP)

我们已经将原问题等价地表示为一个在“特征” 上的稀疏回归问题。这里的“特征”是由第一层单位范数权重 生成的。因为 可以在单位球面上任意取值，所以我们实际上是在一个无限的特征字典里进行选择。

这一步的目标是推导出这个问题的凸对偶 (Convex Dual)形式。

3.1. 定义问题和字典

我们的问题是：

为了进行分析，我们首先将这个问题看作一个两阶段的过程：

1. 先从无限的特征集合 中，选择一个有限的子集（即字典）。

2. 然后在这个固定的字典 上求解标准的 LASSO 问题：

3.2. 固定字典下的标准 LASSO 对偶

现在，我们对这个固定字典 的 LASSO 问题求其对偶。

• 引入对偶变量: 我们引入对偶变量 （n 是样本数）。利用 Fenchel 共轭，二次损失项可以写作：

  *(注：$\frac{1}{2}\|y\|_2^2$ 是常数，为简化通常先省略，最后加回。课件中的 $-\frac{1}{2}\|v-y\|_2^2$ 是一个等价的、更简洁的表达)。*

• 交换 min 和 max: 将上式代入原问题，得到一个 min-max 问题。由于原问题是凸的，强对偶性成立，我们可以交换 min 和 max 的顺序：

• 求解内部 min: 我们关注内部对 的最小化部分：

  这是 L1 范数的共轭函数。其解为：
  其中 $\|\mathcal{A}^\top v\|_\infty \le \lambda$ 等价于对字典的每一列 $\phi_j$ 都有 $|v^\top\phi_j| \le \lambda$。当这个条件不满足时，我们可以让 $c$ 的某些元素朝 $-(\mathcal{A}^\top v)$ 的方向无限增大，使得值为 $-\infty$。

• 得到对偶问题: 将这个结果代回 max 问题， 的情况可以忽略，我们只关心值为 0 的情况，即约束 必须满足。因此，固定字典 下的对偶问题是：

  *(目标函数等价于最小化 $\|v-y\|_2^2$)*

3.3. 从固定字典回到无限字典

现在，我们回到原始设定，即字典 并非固定的，而是包含了所有由单位向量 生成的特征 。

对偶问题的约束 ，即 ，必须对字典中的每一列 都成立。为了让这个对偶问题成为原问题的一个有效下界（并且由于强对偶性，是一个紧密的下界），这个约束必须对整个无限特征集 都成立。

因此，我们将约束替换为：

3.4. 最终的半无限规划 (Semi-Infinite Program, SIP)

将这个无限约束代入，我们得到了最终的对偶问题，它是一个半无限规划：

这个规划被称为半无限，因为它的优化变量 是有限维的（），但它却拥有无限多条约束（每个单位向量 都对应一条约束）。

第四步：将无限约束转化为有限约束 (从 SIP 到可解问题)

我们在第三步得到的半无限规划 (SIP) 是一个理论上优美的结果，但它包含无限条约束，无法直接用算法求解。这一步的目的是展示如何将这无限条约束精确地转化为有限条。

4.1. 回顾 SIP 和其挑战

我们的问题是：

挑战在于约束条件 必须对单位球面 上无穷无尽的向量 u 都成立。

4.2. 关键洞察：超平面排列 (Hyperplane Arrangement)

这里的核心思想是：函数 虽然依赖于连续变化的 u，但其“形状”只有有限多种。

• ReLU 的分段线性特性: 是一个分段线性函数。因此， 也是一个关于 u 的分段线性函数。
• 符号模式 (Sign Pattern): 函数 的具体形式取决于向量 中每个元素 的正负号。
• 超平面: 在 d 维的权重空间中，每个方程 (对于样本 i=1,...,n) 都定义了一个穿过原点的超平面。
• 区域划分: 这 n 个超平面将整个 空间划分成了有限个多面体区域 (Polyhedral Regions)。
• 关键结论: 在任何一个特定的区域 k 内部，所有向量 u 产生的 都具有完全相同的符号模式。

4.3. 用对角矩阵表示符号模式

对于每个区域 k，我们可以用一个 n×n 的对角矩阵 来表示其对应的符号模式。 的对角线元素 为：

利用这个矩阵，只要 u 位于区域 k，我们就可以将非线性的 精确地写成线性形式：

4.4. 分解无限约束

现在，我们可以将原始的无限约束分解到每个区域上。

等价于

其中 p 是区域的总数（有限个）。将 代入，上式变为：

由于 是 u 的线性函数（的绝对值），其在单位球上的最大值一定在整个球面上取到，而不仅仅是在某个区域的交集上。所以我们可以简化并得到一组有限的约束：

根据对偶范数的定义，。因此，每条约束都变成了：

4.5. 等价的有限维对偶问题

我们将 SIP 中的无限约束替换为这 p 条有限的凸约束，得到一个标准的、可求解的凸优化问题（这是一个二次约束二次规划 QCQP）：

4.6. 恢复最终的、可解释的 Primal 问题 (Group LASSO)

虽然上述对偶问题已经可解，但为了得到更具解释性的形式，我们对它再次求对偶，从而得到原问题的最终 primal 形式。这个过程会得到一个组稀疏 (Group LASSO) 回归问题：

• 变量: Z_k 是一个 d 维向量，与第 k 个激活模式相关联。
• 模型: 模型将最终的输出 y 表达为来自不同激活模式的贡献 D_kXZ_k 的线性组合。
• 正则化: 是组 L1/L2 范数。它会鼓励整个向量 Z_k 同时为零。
• 解释: 这个模型通过选择少数几个（稀疏的）重要的激活模式（那些 的模式）来拟合数据。

总结

至此，我们成功地证明了，一个经典的两层 ReLU 网络的训练问题，尽管其原始形式是非凸的，但它与一个标准的、可以高效求解的凸优化问题（组 LASSO）完全等价。这就证明了文稿的核心论点：神经网络可以被看作是凸正则化器。从最终的组 LASSO 解中，可以恢复出原非凸网络的最优权重 和 。

p.s. 在课件中将变换为 的理由

这其实就是把第一层的“长度”吸收到第二层系数里，而不影响网络输出，也不改变正则项的结构。

1. 缩放不改变输出

ReLU 满足正齐次性：

所以如果我们把 放大 倍，并同时把 缩小 倍：

网络输出完全不变。

2. 在最优缩放下，正则项是

经过 优化，我们已经得出最优正则是：

（常数 2 可以并进 里）

3. 吸收长度到第二层

上面的正则是第一层长度 × 第二层绝对值的乘积。 既然输出只依赖两者的乘积，我们完全可以把第一层长度定为 1，然后把它的值乘到第二层系数上去：

令：

这样：

• 输出：

• 正则项：

因为 已固定，所以只剩下对 的 L1 正则。