技术摘要：具有自适应步长的约束优化随机可行性方法

问题表述

本文研究如下约束优化问题：
$$\min_{x} f(x) \quad \text{subject to} \quad x \in X \cap Y$$
其中 $Y \subseteq \mathbb{R}^n$ 是一个“易于投影”的闭凸集（例如球体或方框），而 $X$ 被定义为 $m$ 个凸函数下水平集的交集：
$$X := \bigcap_{i=1}^m \{x \in \mathbb{R}^n \mid g_i(x) \leq 0\}$$
主要挑战在于当 $m$ 非常大且将点投影到交集 $X$ 在计算上难以实现时。作者考虑了目标函数 $f$ 的两种不同情形：

1. 强凸且利普希茨连续（Lipschitz-smooth）： $f$ 具有唯一的极小值点且梯度平滑。
2. 凸且可能非光滑： $f$ 可能缺乏光滑性和强凸性。

目标是开发能够最小化 $f$ 的算法，同时确保相对于 $X$ 的可行性，且不需要在每次迭代时进行对 $X$ 的完整投影。

方法论

所提出的方法通过一个两步迭代框架将目标函数最小化与约束满足解耦：

1. 随机可行性更新（算法 1）

为了处理复杂的约束 $X$，作者采用了一种基于 Polyak 步长的随机可行性算法。该算法并非投影到完整的集合 $X$，而是：

• 从 $\{1, \dots, m\}$ 中均匀采样一个约束索引 $\omega_k$。
• 计算采样约束违反函数 $g^+_{\omega_k}(x) = \max\{0, g_{\omega_k}(x)\}$ 的次梯度。
• 执行一个由参数 $\beta \in (0, 2)$ 缩放的 Polyak 步长次梯度步。
• 将结果投影回“易于处理”的集合 $Y$。
• 在每次外层迭代中重复此过程 $N_k$ 次，其中 $N_k$ 可以是确定性的或随机的。

该内层循环的输出 $x_k$ 作为可行性更新，以几何级数速度降低到可行集 $X \cap Y$ 的距离。

2. 带有自适应步长的目标函数最小化

外层循环使用可行性更新的输出来最小化 $f(x)$。针对 $f$ 的性质，本文提出了两种具体的策略：

• 情形 (i)：强凸且光滑（算法 2）
  该方法将梯度下降步与随机可行性更新相结合。作者引入了一种自适应步长方案，该方案不需要预先知道强凸常数 $\mu$ 或利普希茨常数 $L$。步长根据梯度范数和目标容差 $\epsilon$ 进行调整。

• 情形 (ii)：凸且非光滑（算法 3 & 4）
  对于非光滑目标函数，论文引入了一种基于距离加权次梯度（DoWS）的完全无参数自适应方案，DoWS 是 DoWG 方法的一种变体。

  • 算法 3 (DoWS)： 假设可行集 $Y$ 是有界的。它追踪迭代点距离初始点的最大距离，并累积加权次梯度范数以确定步长。
  • 算法 4 (T-DoWS)： 一种专为无界集（例如 $Y = \mathbb{R}^n$）设计的“驯化（tamed）”变体。它通过修改步长缩放来确保在 $f$ 具有下水平集假设的情况下迭代保持有界，从而消除了对 $Y$ 预先有界性的要求。

核心贡献

1. 误差界与对偶乘子的理论联系：
   作者建立了强 Slater 条件下全局误差界与拉格朗日对偶乘子之间的联系。他们证明了在不假设 $Y$ 是紧致的情况下，存在对偶乘子的统一上界，这一结果源于先前的研究（Lewis & Pang, 1998; Bertsekas, 1999; Mangasarian, 1998），但在本文中明确地与特定的约束结构联系起来。

2. 强凸问题的线性收敛性：
   对于强凸且光滑的目标函数，论文证明了目标函数值向任何给定容差 $\epsilon$ 的期望线性收敛性。这是通过自适应步长和对可行性样本数量 $N_k$ 的特定条件实现的。与以往工作不同，该结果并不预先假设约束函数的次梯度有界，而是证明了它们几乎处处有界。

3. 针对非光滑问题的完全无参数方法：
   本文提出了第一个在无需投影的情况下解决问题 (P) 的完全无参数方法，该方法将 DoWS 与随机可行性更新相结合。

   • 它实现了凸且可能非光滑目标函数的 $O(1/\sqrt{T})$ 期望最坏情况收敛率。
   • 引入了 T-DoWS (算法 4)，即使在 $Y$ 无界的情况下（通过 $f$ 的下水平集有界性假设），也能保证迭代有界并达到最优收敛率。

4. 随机采样策略分析：
   作者分析了每次迭代中可行性样本数量 $N_k$ 的影响。他们表明，迭代的不可行性几乎处处以几何级数速度下降。他们为选择 $N_k$ 的分布（例如 Poisson、Binomial 或确定性增长）提供了理论指导，证明了通过特定的样本量增长计划可以实现最优收敛率。

结果与实证评估

理论保证

• 强凸情形： 算法在 $O(\ln(1/\epsilon))$ 次迭代内达到 $\epsilon$-精度。不可行性间隙随样本数 $N_k$ 呈几何级数衰减。
• 凸非光滑情形： 平均迭代值的期望误差界为 $O(1/\sqrt{T})$（取决于集合直径与初始估计值的比例，包含对数因子）。不可行性界限取决于采样分布，在特定的采样条件下以 $O(1/T)$ 的速率下降。

模拟实验

作者在三类问题上验证了其方法：

1. 二次约束二次规划 (QCQP)： 展示了强凸情况下的线性收敛性，以及在非光滑情况下与 Arrow-Hurwicz、Alt-GDA 和 ACVI 相比的竞争性能。
2. 支持向量机 (SVM)： 表明所提无参数方法在无需通过交叉验证进行步长调优的情况下即可收敛，这与在在线设置中面临高计算开销的原始-对偶方法形成对比。
3. 带有群体公平性约束的逻辑回归： 说明了该方法处理复杂公平性约束（建模为下水平集的交集）的能力，同时实现零可行性违规并收敛至最优目标值。

在所有模拟中，所提算法（算法 2、3 和 4）均展示了计算效率，特别是在需要全投影变得不可行的多约束场景下。这些方法在避免了每次迭代都需要超参数调优或求解子问题的同时，表现出优于或匹配最先进基准线（如 ACVI、Arrow-Hurwicz）的性能。

意义与主张

本文声称通过为具有大量约束的问题提供计算高效、理论完备且完全无参数的算法，推动了优化领域的发展。

• 新颖性： 作者指出，这是首次将 DoWG（或其驯化变体）与无需投影的随机可行性更新结合起来进行研究。
• 鲁棒性： 这些方法不需要了解特定问题的参数（强凸常数、利普希茨常数或最优值），使其适用于这些信息难以获取的实际应用。
• 可扩展性： 通过使用随机可行性更新，算法避免了将点投影到多个约束交集时的计算瓶颈，能够有效地扩展到高维问题（拥有数千个约束）。

这项工作架起了随机可行性方法与自适应梯度方法之间的桥梁，提供了一个统一的框架，既能适应光滑目标函数，也能适应非光滑目标函数，同时确保可行性呈几何级数衰减。