On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression

技术摘要：论 Bregman 近端梯度法在 Kullback–Leibler 回归中的线性收敛性及其应用

问题陈述
本文研究了如下形式的凸复合泛函的最小化问题：$J(x) = F(x) + R(x)$，其中 $F$ 是可微凸函数，$R$ 是不可微凸正则项。虽然近端梯度法（PGM）是解决此类问题的标准方法，但除非 $F$ 满足强凸性，否则其收敛速度通常是次线性的（$O(1/k)$）。然而，在许多实际应用中，特别是像泊松回归和 Kullback–Leibler (KL) 回归这类逆问题中，涉及到的平滑项 $F$ 并不满足强凸性（例如，当测量矩阵 $A$ 是秩亏缺时）。

尽管 Bregman 近端梯度法（BPGM）已被引入以通过镜像映射 $\phi$ 来适应 $J$ 的几何特性，但现有的 BPGM 线性收敛保证通常要求 $F$ 相对于 $\phi$ 是全局相对强凸的。这种条件对于实际的 KL 回归问题而言往往过于苛刻，这导致在理解何时以及为何在这些设定下发生线性收敛方面存在理论空白。

方法论与理论框架
作者提出了一个新的理论框架，旨在通过比全局相对强凸性更弱的条件来建立 BPGM 的线性收敛性。

1. 限制性相对强凸性 (RRSC)： 本文引入了一个被称为“限制性相对强凸性”的新性质。它将欧几里得空间中的限制强凸性（RSC）概念扩展到了 Bregman 设定中。具体而言，$F$ 相对于 $\phi$ 是 RRSC 的，如果存在 $\mu > 0$，使得对于定义域内的所有 $x$：
   $$\langle \nabla F(x) - \nabla F(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle \geq \mu \langle \nabla \phi(x) - \nabla \phi(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle$$
   其中 $\bar{x}_{\ell_2}$ 是 $x$ 在解集 $S$ 上的欧几里得投影。至关重要的是，该条件依赖于欧几里得投影而非 Bregman 投影，这在处理 KL 散度的几何特性时在技术上是必要的。

2. 限制性对称系数： 为了处理 Bregman 散度中固有的非对称性（除非 $\phi$ 是二次函数，否则散度不对称），作者定义了一个“限制性对称系数” $\alpha_S(\phi)$。该系数衡量了专门限制在解集 $S$ 上的散度 $D_\phi$ 的对称性。作者要求 $\alpha_S(\phi) > 0$ 以确保收敛。

3. 收敛性分析： 在 RRSC、相对平滑性（类 Lipschitz 条件）以及正限制性对称系数的假设下，作者证明了迭代值与解集之间的 Bregman 散度以及目标函数值均呈线性收敛。他们还将这些结果扩展到了通过回溯法实现的自动步长选择规则。

在 Kullback–Leibler 回归中的应用
该理论框架被应用于（正则化）KL 回归问题，其中 $F(x) = KL(y, Ax+b)$。作者针对三种特定的距离生成函数$\phi$ 的选择分析了收敛行为：

• 平方 $\ell_2$-范数： 标准的欧几里得情形。
• Burg's Entropy（Burg 熵）： KL 问题中常用的选择 ($\phi_B(x) = -\sum \log x_n$)。
• Smoothed Burg's Entropy（平滑 Burg 熵）： 一种新颖的提议 ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$)。

主要发现与结果

• Burg's Entropy 的局限性： 分析表明，使用标准的 Burg's entropy ($\phi_B$) 并不能保证在所有 KL 回归场景下都实现线性收敛。具体而言，如果解集位于非负象限的边界 ($\partial C$)，或者迭代值以特定方式接近 $A$ 的核（kernel），则 RRSC 条件失效，仅能观察到次线性收敛。
• Smoothed Burg's Entropy 的优势： 作者证明，采用平滑版本 ($\phi_{sB}$) 可以诱导必要的几何特性，从而在更广泛的场景下满足 RRSC 条件并确保正的对称系数，包括解位于边界的情况。
• 数值验证： 在合成泊松逆问题上的实验证实了理论预测。
  • 对于 $\phi_{sB}$，无论解是唯一的还是非唯一的，无论是在约束集的内部还是边界，都能一致地观察到线性收敛。
  • 对于 $\phi_B$，仅当解严格位于约束集内部时才能观察到线性收敛；否则，收敛会退化为次线性速率。
  • $\phi_{sB}$ 的性能对平滑参数 $\xi$ 较为敏感，存在强凸常数与相对平滑常数之间的最优权衡。

意义与主张
本文声称提供了第一个将限制强凸性推广到 Bregman 设定中的方法，从而在不需要全局相对强凸性的情况下，建立了 BPGM 的线性收敛率。其主要贡献在于识别了实现 KL 回归中线性收敛所需的特定几何条件（RRSC 和限制性对称性）。

作者强调，其工作解释了为什么流行的 Burg's entropy 在某些实际设定下（如边界解）可能无法产生线性收敛，并提出了平滑 Burg's entropy 作为一种能够保证线性收敛的鲁棒替代方案。结果得到了理论和数值的双重验证，显示出其推导出的条件与观察到的经验行为之间高度一致。该工作并不声称解决了非凸问题或扩展到非凸 KL 回归，而是完善了对 KL 散度背景下凸复合优化的理解。