技术摘要：带有对数屏障的镜像下降算法

1. 问题陈述

本文研究如下凸极小化问题：
$$\min_{x \in \mathbb{R}^d} f(x) \quad \text{subject to} \quad x \in C \cap S$$
其中 $C$ 和 $S$ 是非空闭凸集。集合 $S$ 被显式处理，而可能较为复杂的集合 $C$ 则通过一个对数屏障函数 $h: C \to \mathbb{R} \cup \{+\infty\}$ 来处理。该函数 $h$ 作为距离生成函数（镜像）来定义 Bregman 散度：
$$D_h(y, x) := h(y) - h(x) - \langle \nabla h(x), y - x \rangle$$
作者考虑了两种算法变体：

1. 镜像下降 (Mirror Descent, MD)： 使用 $f$ 的线性化进行显式更新。
2. 近端镜像下降 (Proximal Mirror Descent, proxMD)： 使用隐式更新，最小化完整的目标函数 $f$ 加上 Bregman 项。

核心难点： 标准的镜像下降收敛性分析依赖于 $f(x_k) - f^\star \leq \frac{D_h(x^\star, x_0)}{\sum \alpha_i}$ 的界。然而，当最优解 $x^\star$ 位于 $C$ 的边界上时（这是一个常见场景），且 $h$ 是对数屏障时（$h$ 在边界处会趋于无穷大），项 $D_h(x^\star, x_0)$ 会变得无穷大。因此，经典的保证会变得失效（vacuous）。虽然对数屏障已在特定语境下被使用过（例如 D-最优设计和泊松逆问题中的相对平滑性条件），但先前的理论在这些情况下（即解位于边界时）缺乏针对镜像下降的定量收敛保证。本研究旨在推导出此类非失效的收敛速率。

2. 方法论与理论框架

2.1. 指数凹性与对数屏障

作者利用了对数屏障 $h$ 是 $\nu$-指数凹 ($\nu$-exp-concave) 的性质。如果映射 $x \mapsto \exp(-h(x)/\nu)$ 是凹的，则称函数 $h$ 是 $\nu$-指数凹的。该性质比凸性更强，并提供以下不等式：
$$\nu \exp\left(\frac{h(x) - h(y)}{\nu}\right) + \langle \nabla h(x), y - x \rangle \leq \nu$$
该不等式是用于限制迭代过程接近边界时产生的“爆炸”项的关键技术工具。

2.2. Lyapunov 分析

(proxMD) 和 (MD) 的收敛证明都依赖于构造一个 Lyapunov 函数。对于 (proxMD)，分析定义了一个序列 $B_k$（累积步长）和一个势函数：
$$\Psi_k = B_k (f(x_k) - f^\star) + \langle \nabla h(x_k), x_k - x^\star \rangle$$
通过分析差值 $\Psi_{k+1} - \Psi_k$，作者推导出了一个包含残差项 $H_k$ 的递归不等式。至关重要的是，$\nu$-指数凹性允许他们将 $H_k$ 限制为涉及 $\log(B_{k+1}/B_k)$ 的项，而不是无界的量。

2.3. 相对平滑性

对于镜像下降 (MD) 变体，论文假设了相对平滑性：如果 $f$ 关于 $h$ 是 $L$-相对平滑的，则满足 $D_f(x, y) \leq L D_h(x, y)$。已知当 $h$ 为对数屏障时，这一条件在 D-最优设计和泊松逆问题等问题中成立。

2.4. 通过性能评估验证紧致性

为了证明推导出的速率并非松散证明的产物，作者使用性能估计问题 (Performance Estimation Problems, PEP) 构建了一个特定的反例。他们插值了一个凸函数 $f$ 和一个 1-指数凹屏障 $h$，使得 (proxMD) 的迭代精确地达到了推导出的下界。该构造涉及一个二维匹配示例，其目标函数和屏障是通过满足特定插值条件的采样点定义的。

3. 关键结果

3.1. 收敛速率

论文证明，在使用对数屏障时，(MD) 和 (proxMD) 均能实现 $O(\frac{\log k}{k})$ 的收敛速率，即使解位于边界上也是如此。

• 近端镜像下降 (Theorem 1)： 对于步长序列 $\alpha_i$，令 $A_k = \sum_{i=1}^k \alpha_i$。误差界为：
  $$f(x_k) - f^\star \leq \frac{\langle \nabla h(x_0), x_0 - x^\star \rangle + 2\nu + \frac{\nu}{4}\log\left(\frac{A_k}{A_1}\right)}{A_k}$$
  使用常数步长 $\alpha_k = \alpha$ 时，得到 $O(\frac{\log k}{k})$。使用几何增长步长时，速率是指数级的，但与内点法 (IPMs) 相比，总复杂度略差。

• 镜像下降 (Theorem 2)： 在相对平滑性条件下，步长取 $\alpha = 1/L$，界为：
  $$f(x_k) - f^\star \leq \frac{f(x_0) - f^\star + L(\langle \nabla h(x_0), x_0 - x^\star \rangle + 2\nu + \nu \log k)}{k+1}$$
  这也确认了 $O(\frac{\log k}{k})$ 的速率。

3.2. 紧致性 (Theorem 3)

作者证明了 $O(\frac{\log k}{k})$ 的速率是紧致的。具体而言，对于 $\nu=1$ 且采用常数步长，存在一个问题实例使得：
$$k(f(x_k) - f^\star) \sim 1 + \frac{1}{4}\log k$$
这证实了当使用对数屏障且解在边界上时，对数因子是该方法的固有特性，而非分析缺陷。

3.3. 与内点法 (IPMs) 的比较

论文将 (proxMD) 与经典的 IPMs 进行了比较。

• IPMs 可以被视为 (proxMD) 的“固定中心”版本，其中近端中心固定在解析中心 $x_0$（即 $x_k = \arg\min \{f(x) + \frac{1}{\alpha_k} D_h(x, x_0)\}$）。
• 复杂度： 具有 $\nu$-自共形屏障的经典 IPMs 达到 $O(\nu \log(1/\delta))$ 的复杂度。
• ProxMD： 作者表明，使用几何增长步长的 (proxMD) 达到总复杂度为 $O(\nu \log^2(1/\delta))$。
• 结论： 虽然 (proxMD) 的总复杂度略低（由于 $\log^2$ 因子对比 $\log$），但它是一个直接的替代方案，不需要特定的自共形结构，仅依赖于指数凹性。

4. 意义与贡献

该论文声称有三个主要贡献：

1. 解决边界爆炸问题： 它提供了使用对数屏障进行镜像下降和近端镜像下降时，当最优解位于边界上的首次定量收敛保证。虽然对数屏障此前已在相对平滑性语境中使用，但先前的理论并未针对这些 $D_h(x^\star, x_0)$ 项会爆炸的具体设置提供收敛速率。
2. 速率的紧致性： 它确立了在该设定下 $O(\frac{\log k}{k})$ 的速率是最优的，解决了理解相对平滑性应用于对数屏障时的差距。
3. 搭建与内点法的桥梁： 它阐明了 Bregman 型近端方法与 IPMs 之间的关系。它表明 (proxMD) 可以被视为 IPMs 的一种泛化，提供了一个统一的视角，尽管对于非线性目标函数的复杂度界稍高。

这项工作表明，虽然内点法在特定的自共形设定下总复杂度仍然更优，但近端镜像下降提供了一个可行的、更通用的一阶替代方案，它通过指数凹性处理了边界爆炸问题，而不要求解必须保持在严格的内部，也不要求将目标函数移动到约束之外。