Automated Algorithm Design via Nevanlinna-Pick Interpolation¶

会议: NeurIPS 2025 (DynaFront Workshop)
arXiv: 2509.21416
代码: 无
领域: 优化与控制
关键词: 算法自动设计, Nevanlinna-Pick 插值, 鲁棒控制, 等式约束优化, 收敛速率

一句话总结¶

提出基于频域鲁棒控制理论中 Nevanlinna-Pick 插值的自动化算法设计框架，用于求解带等式约束的强凸优化问题，获得了矩阵乘法次数与收敛速率之间的最优权衡。

研究背景与动机¶

传统优化算法的设计通常遵循"先设计后分析"的范式：首先基于问题的最优性条件选择合适的算法结构，然后进行收敛性分析。这种方法存在几个根本性缺陷：

掩盖性能极限：设计与分析的分离使得难以系统性地识别算法类的基本性能边界

非系统化：推导紧致的分析不等式在本质上是困难且高度依赖问题特性的任务

Lyapunov 函数设计困难：通过 Lyapunov 稳定性理论理解算法行为需要深入的问题洞察

近年来，基于鲁棒控制理论中频域技术的框架已成为自动化算法综合的强大工具。该框架通过将设计与分析阶段整合，能够识别基本的性能极限。例如，Nesterov 梯度方法复杂度下界的构造性证明已通过此框架得到。

本文考虑的核心问题是带等式约束的强凸优化： $$\min_x f(x) \quad \text{s.t.} \quad Ex = q$$ 其中 $f$ 是 $m$-强凸函数，具有 $L$-Lipschitz 连续梯度。这类问题广泛出现在联邦学习、成像、最优传输和流体动力学中。一个尤为重要的特殊情形是去中心化优化。

方法详解¶

整体框架¶

本文的核心思想是将优化算法设计转化为控制器综合问题，然后通过 Nevanlinna-Pick 插值理论求解。框架分为以下步骤：

算法规格说明：明确设计目标（线性性、显式性、最优性、线性收敛）
Z 变换表示：利用 Z 变换将算法迭代表示为传递函数
Lur'e 系统建模：将算法视为线性时不变系统与非线性块的反馈互联
坐标变换与环路变换：简化系统结构
插值求解：通过 Nevanlinna-Pick 插值构造满足所有设计规格的传递函数
算法实现：将传递函数转化为可执行的优化迭代格式

关键设计¶

算法表示：具有线性更新的算法可表示为： $$z\mathcal{K}_0(z, W)\hat{x}(z) = \mathcal{K}_1(z, W)\hat{x}(z) + \mathcal{K}_2(z, W)\widehat{\nabla f}(z)$$

其中 $\hat{x}(z)$ 和 $\widehat{\nabla f}(z)$ 分别是迭代序列和梯度序列的 Z 变换。三个传递函数分别决定： - $\mathcal{K}_0$：优化变量与梯度输入之间的映射 - $\mathcal{K}_1$：过去迭代的利用方式 - $\mathcal{K}_2$：过去梯度的利用方式

Lur'e 系统视角：算法被建模为传递函数 $\mathcal{H}(z, W)$ 定义的线性系统与静态非线性块 $\Delta$ 的反馈互联： $$\mathcal{H}(z, W) = (z\mathcal{K}_0 - \mathcal{K}_1)^{-1}\mathcal{K}_2, \quad \Delta(e) = \nabla f(e + x^\star) - \nabla f(x^\star)$$

设计规格的解析刻画： - 显式性 → 因果性：传递函数严格正则，即 $\mathcal{H}(\infty, W) = 0$ - 线性收敛：收敛速率至少为 $\rho$，即 $\|x_k - x^\star\| \leq M\|x_0 - x^\star\|\rho^k$ - 最优性：算法渐近收敛到问题的唯一解

核心方法：插值化梯度法 (I-GM)¶

通过上述框架，作者综合出了插值化梯度法 (Interpolated-Gradient Method, I-GM)，其特点是： - 提供参数 $\ell$（每次迭代的矩阵-向量乘法次数）与收敛速率之间的精确权衡 - 迭代复杂度为 $O(\max(\kappa_f, \kappa_E/\ell) \log(1/\epsilon))$

其中 $\kappa_f = L/m$ 是函数条件数，$\kappa_E = \sigma_1/\sigma_r$ 是约束矩阵条件数。

实验关键数据¶

主实验：与现有算法的比较¶

算法	每迭代矩阵乘法次数	迭代复杂度	总矩阵乘法复杂度
GDA	1	$O(\kappa_f \kappa_E \log(1/\epsilon))$	$O(\kappa_f \kappa_E \log(1/\epsilon))$
PAPC	1	$O(\max(\kappa_f, \kappa_E) \log(1/\epsilon))$	$O(\max(\kappa_f, \kappa_E) \log(1/\epsilon))$
最优多环方法	$O(\kappa_E)$	$O(\sqrt{\kappa_f} \log(1/\epsilon))$	$O(\sqrt{\kappa_f} \kappa_E \log(1/\epsilon))$
I-GM (本文)	$\ell$	$O(\max(\kappa_f, \kappa_E/\ell) \log(1/\epsilon))$	$O(\ell \cdot \max(\kappa_f, \kappa_E/\ell) \log(1/\epsilon))$

消融实验：参数 $\ell$ 的权衡¶

参数 $\ell$	单次迭代计算量	收敛速度	适用场景
$\ell = 1$	最低（单次矩阵乘法）	$O(\max(\kappa_f, \kappa_E))$	通信受限的分布式优化
$\ell = \sqrt{\kappa_E}$	中等	$O(\max(\kappa_f, \sqrt{\kappa_E}))$	平衡计算与通信
$\ell = \kappa_E$	最高	$O(\kappa_f)$	计算资源充足场景

关键发现¶

I-GM 在单环算法中实现了最优的迭代复杂度-计算量权衡
当 $\ell = 1$ 时，I-GM 退化为与 PAPC 相当的复杂度
增加 $\ell$ 可以有效摊销约束矩阵条件数 $\kappa_E$ 对收敛的影响
在去中心化优化场景中，$\ell$ 可直观理解为局部信息传播的步数

亮点与洞察¶

统一设计与分析：通过将算法设计转化为控制器综合问题，框架天然地将性能极限的识别与算法构造统一起来
参数化权衡：I-GM 提供了可调参数 $\ell$，可根据实际计算与通信约束灵活调整
构造性证明：不仅证明了性能下界的存在，还构造性地给出了达到该下界的算法
频域方法的力量：展示了鲁棒控制理论中的经典工具在算法设计中的深刻应用

局限与展望¶

目前框架限于线性更新的算法，无法处理非线性迭代格式（如近端算子）
仅考虑强凸目标函数，对一般凸或非凸问题的扩展尚不明确
实际数值实验较少，主要停留在理论分析层面
Nevanlinna-Pick 插值的计算在高维问题中可能面临数值稳定性挑战
与近端算子结合的扩展仅做了简要讨论，缺乏完整分析

评分¶

维度	评分 (1-5)
创新性	4
理论深度	5
实验充分性	2
写作质量	4
总评	4

算法	每迭代矩阵乘法次数	迭代复杂度	总矩阵乘法复杂度
GDA	1	\(O(\kappa_f \kappa_E \log(1/\epsilon))\)	\(O(\kappa_f \kappa_E \log(1/\epsilon))\)
PAPC	1	\(O(\max(\kappa_f, \kappa_E) \log(1/\epsilon))\)	\(O(\max(\kappa_f, \kappa_E) \log(1/\epsilon))\)
最优多环方法	\(O(\kappa_E)\)	\(O(\sqrt{\kappa_f} \log(1/\epsilon))\)	\(O(\sqrt{\kappa_f} \kappa_E \log(1/\epsilon))\)
I-GM (本文)	\(\ell\)	\(O(\max(\kappa_f, \kappa_E/\ell) \log(1/\epsilon))\)	\(O(\ell \cdot \max(\kappa_f, \kappa_E/\ell) \log(1/\epsilon))\)