Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms

技术摘要：带有保证的学习优化方法

问题表述
本文旨在解决一个挑战：如何在提高迭代优化算法在特定问题分布上的平均性能的同时，严格保持其在整个问题类上的最坏情况线性收敛保证。虽然“学习优化”（L2O）方法经常采用神经网络来设计更新规则，但它们往往缺乏理论上的收敛保证。相反，经典算法（如梯度下降、Nesterov 加速梯度）提供了严谨的最坏情况界限，但在特定应用分布（例如，问题结构具有重复性的模型预测控制）中可能表现欠佳。作者寻求一种理论框架，对所有线性收敛算法进行参数化，使其能够通过增加可学习组件来增强性能，而不牺牲收敛速率或可行性。

方法论与理论框架
核心方法论涉及对复合优化问题 $\min_x f(x) + g(x)$ 中线性收敛算法的完整表征。作者提出，任何线性收敛算法都可以分解为两个部分：

1. 一个基准算法 ($\pi$)，已知其以速率 $\gamma \in (0,1)$ 线性收敛至一组不动点 ($\text{Fix}_\pi$)。
2. 一个增广项 ($v_t$)，代表对更新规则的、可学习的、指数级衰减的扰动。

更新规则定义为：
$$\xi_{t+1} = \pi(F, \xi_t) + v_t(F, \xi_{t:0})$$
其中 $\xi_t$ 是状态变量，$F$ 代表目标函数。

本文建立了两个主要的理论结果：

• 定理 1（充分性）： 证明了向线性收敛基准中注入指数级衰减信号 $v_t$ 会保持线性收敛性。具体而言，如果基准算法以速率 $\gamma$ 和多项式因子 $p(t)$ 收敛，则增广算法的收敛性可能会发生退化，其退化程度由非零扰动的频率 ($N$) 和 $v_t$ 的衰减速率决定。至关重要的是，如果基准算法是单调线性收敛的，那么即使在每一步都应用扰动，只要 $v_t$ 指数级衰减，渐近速率 $\gamma$ 就保持不变。
• 定理 2（完备性）： 作者为“正则”线性收敛算法建立了完备性结果。如果一个算法的更新序列以与到不动点距离相同的指数速率消失，则该算法被定义为正则。定理指出，任何正则线性收敛算法 $\sigma$ 都可以表示为一个 Lipschitz 连续的基准 $\pi$ 与一个指数级衰减的增广项 $v$ 之和。这意味着所提出的参数化方式对于正则线性收敛算法类是详尽的。

主要贡献

1. 完整表征： 本文提供了线性收敛的充要条件，表明所有正则线性收敛算法都可以参数化为基准加上一个指数级衰减的修正项。这排除了病态的非收敛或非正则情况。
2. 权衡量化： 本研究量化了学习更新的频率与最坏情况收敛速率退化之间的权衡。研究表明，只要基准算法是单调线性收敛的，就可以在每一步都应用学习到的更新，而不会改变渐近收敛速率。
3. 广泛的适用性： 该表征实例化于三类主要的优化问题：
   • 非凸、梯度占优函数（满足限制性割线性质/Restricted Secant Inequality）。
   • 光滑、强凸函数（使用 Nesterov 加速梯度作为基准）。
   • 多面体可行集上的优化（使用投影梯度下降）。
4. 学习框架： 作者提出了一个元优化方法，其中增广项 $v_t$ 被参数化为一个由神经网络（具体为 LSTM）乘以一个可训练的指数级衰减标量序列。这确保了通过设计满足指数级衰减的结构约束，从而允许使用 PAC-Bayes 泛化界限来量化在未见实例上的性能。

结果与数值验证
论文通过两项数值实验验证了该框架：

• 病态线性系统： 在求解 $Ax=b$（其中$A$ 是病态矩阵）的任务中，学习到的增广项（应用于 Nesterov 加速梯度）相比标准梯度下降（GD）和 NAG，显著提高了瞬态性能。值得注意的是，学习到的优化器最初会增加代价函数以建立动量，这种行为在经典优化器中并不存在。至关重要的是，作者证明了如果没有指数级衰减约束，学习到的优化器在展开超过训练时界后会发散，这凸显了理论保证对于稳定性的必要性。
• 模型预测控制 (MPC)： 在具有多面体约束的线性动力系统控制任务中，投影梯度下降的学习增广降低了闭环控制成本。学习到的优化器有效地学会了比基准算法更迅速地使约束饱和，从而在实时控制典型的紧凑迭代预算内提高了性能。

意义与主张
本文声称，其表征弥合了基于学习的方法的表达能力与经典优化方法的可靠性之间的鸿沟。通过证明所有正则线性收敛算法都允许这种分解，作者认为人们可以安全地“学习”相对于鲁棒基准的最优偏差，而无需担心发散风险。这使得设计针对特定问题分布的求解器成为可能（提高平均性能），同时保留了安全关键应用（如 MPC）所需的严谨最坏情况保证。这项工作将增广收敛算法的过程定位为类似于控制理论中的 Youla 参数化，为“带有可证明保证的学习优化”提供了一条系统的路径。