信念空间动力学中允许的学习率步长的闭式上界

# 信念空间动力学中可容许学习率步长的闭式上界
来源：https://arxiv.org/html/2605.06741
###### 摘要

学习率步长通常被视为超参数。本文隔离出一个局部信念空间计算：当更新被建模为概率单纯形上的投影前向步时，可容许性意味着在自然的 KL/Bregman 几何中具有收缩性。在此模型下，可容许步长的上界不是一个调节口号，而是一个公式。

主要案例是交叉熵分类。设信念状态为 $p \in \Delta^{C-1}_{\circ}$，并将局部更新建模为

$$F_{\eta}(p) = \Pi_{\Delta}\bigl(p - \eta \nabla E(p)\bigr).$$

使用 KL 散度作为由负熵生成的 Bregman 散度，三点恒等式和投影梯度最优性条件得出了收缩估计：

$$D_{\mathrm{KL}}(F_{\eta}(p_{1}) \| F_{\eta}(p_{2})) \leq D_{\mathrm{KL}}(p_{1} \| p_{2}) - \eta(2\mu - \eta L^{2})\|p_{1}-p_{2}\|^{2}.$$

因此，可容许的交叉熵步长必须满足

$$0 < \eta < \frac{2\mu}{L^{2}}.$$

在局部曲率代理 $\nabla^{2}E(p) = \operatorname{diag}(1/p_{i})$ 下，常数为 $\mu(p) = 1/\max_{i}p_{i}$ 和 $L(p) = 1/\min_{i}p_{i}$，从而给出闭式上界

$$\eta^{\mathrm{CE}}_{\max}(p) = \frac{2\mu(p)}{L(p)^{2}} = \frac{2\min_{i}(p_{i})^{2}}{\max_{i}(p_{i})}.$$

来自自适应对偶搜索（ADS）的熵项提供了单独的局部后退（backoff），而不是一个新的端点。使用归一化熵 $B(p) = H(p)/H_{\max}$ 和对数障碍 $\alpha(B) = -\log(1-B)$，可容许的感知熵的 CE 步长为

$$\eta_{\mathrm{CE}}(B,p) = \frac{2\mu(p)}{L(p)^{2}} \cdot \frac{1}{1+\alpha(B)}.$$

作为对比，均方误差（MSE）补偿路径有一个归一化的二次端点 $\eta^{\mathrm{MSE}}_{\max}=1$，因此 $\eta_{\mathrm{MSE}}(B) = 1/(1+\alpha(B))$。本文的主张在于闭式局部上界及其几何证明，而非新的优化器或基准结果。

![[未加标题的图片]](https://arxiv.org/html/2605.06741v1/datawhale-logo.png)

## 1 从启发式可容许性到信念空间可容许性

起点是启发式搜索背后的契约。启发式之所以有用，是因为它比精确求解剩余问题更廉价。但这种经济性是危险的：错误的启发式可能会使搜索过程以破坏最初期望从搜索中获得保证的方式变得快速。A* 通过仅在数学契约下允许近似来解决这种张力：

$$h(n) \leq h^*(n),$$

其中 $h(n)$ 是估计的剩余成本，$h^*(n)$ 是真实的剩余成本。启发式可以是乐观的，但不能高估。因此，速度是通过安全条件而不是不受控制的猜测来购买的。

这种契约比它首次出现的特定图搜索设置更为重要。它表明，只有当加速保持全局不变量时，局部决策规则才能加速。如果 $h(n)=0$，A* 变得保守并过度扩展。如果 $h(n)$ 高估，搜索可能变快但失去最优性。有用区域位于这两种失败之间：启发式必须具有足够的信息量以减少搜索，同时又要足够克制以不破坏证明。

同样的想法可以动态地表述。搜索过程处于当前状态，评估局部方向，并采取有限步长。A* 将这一选择写为最小化

$$f(n) = g(n) + h(n),$$

其中过去成本 $g$ 和未来估计 $h$ 共同决定下一次扩展。梯度流将类似的运动写为能量景观上的连续下降，其欧拉离散化为

$$x_{t+1} = x_t - \eta \nabla E(x_t).$$

这两种形式都提出了相同的局部问题：程序可以在多大程度上移动，同时保持使该程序有意义的保证？

自适应对偶搜索（ADS）将不确定性插入此契约。它不对启发式分配固定的信任权重，而是衡量当前状态的不确定性。对于信念分布 $p$，定义归一化熵

$$B(p) = \frac{H(p)}{H_{\max}}$$

和对数障碍

$$\alpha(B) = -\log(1-B).$$

当信念状态扩散时，$B$ 接近 1 且障碍变大；当信念状态尖锐时，障碍较小。因此，因子 $1/(1+\alpha(B))$ 是一个局部熵刹车：不确定性不仅仅装饰更新，它直接限制步长的可容许大小。

从图搜索到信念空间动力学的转移现在变得直截了当。状态不再是图中的节点，而是概率单纯形中的点 $p$。步长不再是边扩展，而是投影前向移动

$$F_{\eta}(p) = \Pi_{\Delta}\bigl(p - \eta \nabla E(p)\bigr).$$

A* 问题的类似物不再是启发式是否低估了剩余路径长度；而是更新映射是否在概率分布的自然几何中保持收缩性。在图搜索中，可容许性保护最优性。在信念空间中，可容许性保护收缩性。

这就是 KL 散度进入的地方。信念状态是分布，负熵 Bregman 几何给出了精确的三点恒等式。该恒等式揭示了强凸性将附近信念拉在一起而平滑性惩罚过大步长的项。由此产生的条件是信念空间中 A* 契约的类似物：只有当间隙 $2\mu - \eta L^{2}$ 保持正值时，更新才可以是激进的。

这里隔离的公式正是该契约。交叉熵案例是主要对象，因为其在单纯形上的局部曲率产生了非平凡的原始尺度端点 $2\mu/L^{2}$。MSE 案例随后作为归一化的二次对比被包括在内：沿着其补偿路径，端点 simply 为 1。两者都可以使用相同的 ADS 熵后退，但损失几何提供了该后退所退出的端点。

## 2 设置

设

$$\Delta^{C-1}_{\circ} = \{p \in \mathbb{R}^{C} : p_{i} > 0, \ \sum_{i=1}^{C}p_{i}=1\}$$

为概率单纯形的内部。点 $p \in \Delta^{C-1}_{\circ}$ 是 $C$ 个可能标签或答案上的信念分布。归一化约束移除了一个自由度，因此状态空间不是无约束的欧几里得空间，而是具有自身自然几何的弯曲统计域。

局部更新被建模为能量景观上的运动：

$$F_{\eta}(p) = \Pi_{\Delta}\bigl(p - \eta \nabla E(p)\bigr).$$

这里 $E$ 是由损失引起的局部能量，$\eta$ 是步长，$\Pi_{\Delta}$ 在欧拉步之后将点返回到单纯形。可容许性问题是在应用任何熵后退之前提出的：由 $E$ 的局部几何允许的最大步长是多少？

本文中的主要几何是交叉熵分类，

$$E(p) = -\sum_{i=1}^{C}q_{i}\log p_{i},$$

其中 $q$ 是目标分布。这种几何与单纯形固有地联系在一起：梯度和 Hessian 取决于信念状态本身的坐标，因此可容许步长随当前分布而变化。

第二种几何，均方误差（MSE），仅作为比较案例处理。对于 MSE，从 $p$ 到目标分布 $y$ 的归一化补偿路径是一条欧几里得线段，该归一化路径的端点为 1。这种差异是常见混淆的来源：ADS 熵后退是共享的，但未归一化的端点由损失几何提供。因此，CE 和 MSE 不应合并为相同的界限。

## 3 单纯形上的交叉熵几何

对于交叉熵分类，使用

$$E(p) = -\sum_{i=1}^{C}q_{i}\log p_{i}, \quad (1)$$

其中 $q \in \Delta^{C-1}_{\circ}$ 是目标分布。直接微分给出

$$\nabla E(p) = -\left(\frac{q_{1}}{p_{1}},\ldots,\frac{q_{C}}{p_{C}}\right), \quad (2)$$

以及

$$\nabla^{2}E(p) = \operatorname{diag}\left(\frac{q_{i}}{p_{i}^{2}}\right). \quad (3)$$

我们使用 one-hot 或局部归一化的曲率代理

$$\nabla^{2}E(p) = \operatorname{diag}(1/p_{i}). \quad (4)$$

在此代理下，局部强凸性和平滑性常数可从信念状态读取：

$$\mu(p) = \frac{1}{\max_{i}p_{i}}, \qquad L(p) = \frac{1}{\min_{i}p_{i}}. \quad (5)$$

它们不是自由的学习率参数。

## 4 KL 收缩证明

定义投影前向步

$$F_{\eta}(p) = \Pi_{\Delta}\bigl(p - \eta \nabla E(p)\bigr). \quad (6)$$

证明使用 KL 散度作为由负熵生成的 Bregman 散度

$$\phi(p) = \sum_{i}p_{i}\log p_{i},$$

使得

$$D_{\mathrm{KL}}(p \| q) = \phi(p) - \phi(q) - \langle\nabla \phi(q), p-q\rangle. \quad (7)$$

使用 KL 并非装饰性的。信念状态是概率分布，负熵势是单纯形上的自然凸生成器。Bregman 三点恒等式给出了比较投影前后步长所需的精确代数桥梁：

$$
\begin{aligned}
D_{\mathrm{KL}}(p \| q) &= D_{\mathrm{KL}}(p \| r) + D_{\mathrm{KL}}(r \| q) \\
&\quad - \langle\nabla \phi(q) - \nabla \phi(r), p-r\rangle.
\end{aligned} \quad (8)
$$

该恒等式是证明不仅仅诉诸一般收缩假设的原因。它暴露了可以插入 $E$ 曲率的点积项。

设 $q_{1} = F_{\eta}(p_{1})$ 和 $q_{2} = F_{\eta}(p_{2})$。将公式 (8) 应用于三元组 $(p_{1}, q_{1}, q_{2})$ 并重新排列，给出

$$
\begin{aligned}
D_{\mathrm{KL}}(q_{1} \| q_{2}) &= D_{\mathrm{KL}}(p_{1} \| q_{2}) - D_{\mathrm{KL}}(p_{1} \| q_{1}) \\
&\quad + \langle\nabla \phi(q_{2}) - \nabla \phi(q_{1}), p_{1}-q_{1}\rangle.
\end{aligned} \quad (9)
$$

投影梯度最优性条件然后允许通过 $E$ 的梯度差来控制点积项。唯一的分析假设是两个局部不等式：

$$\langle\nabla E(p_{1}) - \nabla E(p_{2}), p_{1}-p_{2}\rangle \geq \mu \|p_{1}-p_{2}\|^{2}, \quad (10)$$

$$\|\nabla E(p_{1}) - \nabla E(p_{2})\| \leq L \|p_{1}-p_{2}\|. \quad (11)$$

强凸性不等式是将附近信念拉在一起的项；平滑性不等式是惩罚过大欧拉步的项。在由此产生的估计中，强凸性贡献了正部分 $2\mu$，平滑性贡献了负部分 $\eta L^{2}$。将它们结合起来得到

$$D_{\mathrm{KL}}(q_{1} \| q_{2}) \leq D_{\mathrm{KL}}(p_{1} \| p_{2}) - \eta(2\mu - \eta L^{2})\|p_{1}-p_{2}\|^{2}. \quad (12)$$

使用 KL 散度与欧几里得范数之间的局部等价性，用常数 $C>0$ 写为

$$D_{\mathrm{KL}}(q_{1} \| q_{2}) \leq \left(1 - \frac{\eta(2\mu - \eta L^{2})}{C}\right) D_{\mathrm{KL}}(p_{1} \| p_{2}). \quad (13)$$

因此，当

$$\eta(2\mu - \eta L^{2}) > 0. \quad (14)$$

时，$F_{\eta}$ 是收缩的。对于 $\eta > 0$，这等价于

$$0 < \eta < \frac{2\mu}{L^{2}}. \quad (15)$$

这是项 $2\mu - \eta L^{2}$ 的来源：强凸性给出了正的 $2\mu$ 贡献，平滑性给出了负的 $\eta L^{2}$ 贡献。可容许性正是要求该间隙保持正值。

$p_{1}, p_{2}$ 初始信念 $\rightarrow$ $p_{i} - \eta \nabla E(p_{i})$ 梯度步 $\rightarrow$ $q_{i} = F_{\eta}(p_{i})$ 投影 $\rightarrow$ 强凸性 $+2\mu$ / 平滑性 $-\eta L^{2}$ $\rightarrow$ $\eta(2\mu - \eta L^{2}) > 0$ 可容许间隙 $\rightarrow$ $D_{\mathrm{KL}}(q_{1} \| q_{2}) \leq k(\eta) D_{\mathrm{KL}}(p_{1} \| p_{2})$

图 1：作为正交计算图的收缩证明。文本仅放置在节点内；边未标记，因此标签不会与框冲突。投影前向映射将 $p_{i}$ 发送到 $q_{i}$，而强凸性和平滑性形成间隙 $2\mu - \eta L^{2}$。

## 5 闭式交叉熵界限和熵后退

公式 (15) 给出了可容许上界

$$\eta_{\max}^{\mathrm{CE}} = \frac{2\mu}{L^{2}}. \quad (16)$$

代入局部曲率常数 (5)：

$$
\begin{aligned}
\eta_{\max}^{\mathrm{CE}}(p) &= \frac{2 \cdot (1/\max_{i}p_{i})}{(1/\min_{i}p_{i})^{2}} \\
&= \frac{2\min_{i}(p_{i})^{2}}{\max_{i}(p_{i})}.
\end{aligned} \quad (17)
$$

这就是标题中陈述的公式。在此局部模型中，学习率步长的上界由当前信念分布决定。

交叉熵界限是原始尺度的端点。熵障碍然后作为从此端点出发的乘法后退发挥作用，而不是替换它。定义

$$H(p) = -\sum_{i}p_{i}\log p_{i}, \qquad H_{\max} = \log C, \qquad B(p) = \frac{H(p)}{H_{\max}},$$

$$\alpha(B) = -\log(1-B), \qquad \bar{\eta}(B) = \frac{1}{1+\alpha(B)}.$$

添加 ADS 熵后退得到

$$\eta_{\mathrm{CE}}(B,p) = \eta_{\max}^{\mathrm{CE}}(p) \bar{\eta}(B), \quad (18)$$

即

$$\eta_{\mathrm{CE}}(B,p) = \frac{2\min_{i}(p_{i})^{2}}{\max_{i}(p_{i})} \cdot \frac{1}{1+\alpha(B)}. \quad (19)$$

等价地，

$$\eta_{\mathrm{CE}}(B,p) = \frac{2\mu(p)}{L(p)^{2}} \cdot \frac{1}{1+\alpha(B)}. \quad (20)$$

当 $B \to 1$ 时，$\alpha(B) \to \infty$ 且步长趋于 0。当 $B \to 0$ 时，$\alpha(B) \to 0$ 且步长接近交叉熵上界 $2\mu/L^{2}$。

图 2 在二元信念切片 $p=(x, 1-x)$ 上可视化此计算。此切片不是单独的实验；它是定理的诊断图。它...