The Query Complexity of Local Search in Rounds on General Graphs¶

会议: NeurIPS 2026
arXiv: 2601.13266
领域: 优化/理论
关键词: 局部搜索、查询复杂度、多轮交互复杂度、分离数、最速下降

一句话总结¶

本文首次系统研究了一般图上限制 $t$ 轮交互查询的局部搜索黑盒复杂度，针对 $n$ 节点图证明了关于分离数 $s$ 与最大度 $\Delta$ 的确定性上界 $O(t n^{1/t}(s\Delta)^{1-1/t})$、对任意连通图均成立的随机下界 $\Omega(t n^{1/t} - t)$，并证明对高分离数常度图随机并行最速下降可达亚线性 $O(n/\log n)$。

研究背景与动机¶

局部搜索是求解组合优化、非凸正则化回归、鲁棒低秩矩阵估计以及深度神经网络超参数调优等复杂任务的基础启发式方法。在黑盒查询模型中，算法无法获知目标函数在全图上的解析形式，必须通过向预言机（Oracle）逐点查询节点函数值来确定局部极小值（即函数值不大于所有相邻节点的顶点）。经典理论在全自适应序列查询设定下已取得丰富成果，例如 Aldous 证明的带热启动最速下降在超立方体和网格图上均需 $O(\sqrt{n\Delta})$ 次查询，但这种完全串行的交互在单次查询极度耗时（例如训练一次完整大模型或评估大规模复杂损失）的高并发计算架构下面临极高的时延瓶颈。

为了利用现代并行算力加速黑盒优化，研究者引入了受限轮数（Rounds / Adaptivity）交互模型，即算法必须在至多 $t$ 轮批处理查询内终止并输出局部极小值。以往针对多轮局部搜索的研究主要受限于规则网格拓扑（如 $d$ 维 Grid 图），严重依赖网格的欧氏对齐与超立方分解，完全无法刻画图具有高展开性（Expansion）、存在大量三角形环结构（如低秩矩阵扰动图）或非欧不规则拓扑的普遍几何形态。一般图上交互轮数、图结构拓扑与查询复杂度之间的基本权衡关系此前仍属于理论空白。

本文的核心矛盾在于：强行要求算法在极少数轮数内完成收敛，意味着算法必须在大规模并行查询的同时精确规约候选集，但非规则图缺乏坐标轴切分结构，难以直接像网格那样做自适应网格细化。本文的切入角度是利用图论中刻画拓扑瓶颈的深层不变量——图分离数（Separation Number）与支撑树层级结构，将空间剪枝转化为递归子图划分。核心 idea：利用图划分引理建立多轮层级分离树，使每一轮只需并行探测当前最小值的相邻分支，从而获得以分离数与度数控制的紧致上界；同时基于任意连通图上的支撑树构造阶梯型困难函数族，证明即使允许随机化也存在 $\Omega(t n^{1/t} - t)$ 的不可逾越下界。

方法详解¶

整体框架¶

算法的目标是在给定的连通无向图 $G=(V, E)$ 上，针对未知函数 $f: V \to \mathbb{R}$，在至多 $t$ 轮交互中找到一个局部极小值点 $v^*$（满足对任意 $(u, v^*) \in E$ 均有 $f(v^*) \le f(u)$）。在第 $i$ 轮中，算法根据前 $i-1$ 轮观测到的函数值提交一批查询节点集合 $Q_i \subseteq V$，并在获得全部函数反馈后更新当前全局观测最小值 $v_i$。

本文针对不同图拓扑特征提出了两套互补算法，并建立了通用下界： 1. 针对低/中分离数图的确定性层级分离算法（Deterministic Hierarchical Separator Algorithm）：基于图粉碎引理（Shattering Lemma），预先构建 $t-1$ 层嵌套分离器；第 1 轮全量查询顶层分离器 $S_1$ 锁定初始最小值，后续各轮仅定向查询与当前运行最小值相邻子图的分离器，最后一轮一次性探测终末连通块。 2. 针对高分离数、有界度图的随机并行最速下降算法（Randomized Parallel Steepest Descent）：首轮通过均匀有放回采样快速获得高质量“热启动”种子；随后 $t-1$ 轮以当前点为中心批量查询半径为 $r+1$ 的局部测地邻域球，在单轮内模拟多步沿严格偏序的最速下降路径。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["输入图 G=(V,E) 与轮数预算 t"] --> Dec{"图拓扑分离特性判别"}
    Dec -->|低/中分离数 s < n| A["第1轮：顶层全局分离器查询<br/>查询 S1 确定当前运行最小值 v1"]
    A --> B["第2至t-1轮：受限连通分支分离器查询<br/>仅查询与 vi-1 相邻分支的第 i 级分离器"]
    B --> C["第t轮：终末叶子连通块全量查询<br/>锁定与 vt-1 相邻的极小块并输出最终局部极小点"]
    Dec -->|高分离数/常度展开图| D["第1轮：均匀热启动采样<br/>独立有放回随机采样 q1 个点选出最小值"]
    D --> E["第2至t轮：局部测地拓扑球批量探测<br/>每轮全量查询半径 r+1 拓扑球并行模拟 r 步下降"]
    C --> Out["输出验证无误的严格局部极小值 v*"]
    E --> Out

关键设计¶

1. 基于图粉碎引理的平衡多级分治：消除非欧图的维数依赖

针对缺乏几何坐标轴的任意图，关键痛点是如何在不依赖欧氏网格投影的前提下设计分治结构。本文基于图分离数 $s(G)$（即任意子图均存在至多 $s$ 个节点将其分为不大于原规模 $2/3$ 的不连通两部分）引入图粉碎引理（Shattering Lemma）：对于任意规模参数 $K$，存在大小至多 $3sn/K$ 的分割集 $S$，将其余节点分割为连通分支规模均不超过 $K$ 的子图集合。通过选取调和参数序列 $n \ge K_1 \ge K_2 \ge \dots \ge K_{t-1} \ge 1$，算法递归在子图内部提取分离器。

在执行过程中，第 1 轮查询 $S_1$ 得到运行最小值 $v_1$；在第 $i$ 轮中（$2 \le i \le t-1$），由于 $v_{i-1}$ 的度数至多为 $\Delta$，其相邻的上一级分支个数 $|\mathcal{A}_{i-1}| \le \Delta$。算法证明了非探索引理（Non-Exploration Lemma）：若某个连通块不与当前运行最小值直接相连，则其内部绝不可能包含更优的下降路径起点，从而保证后续轮数完全无需碰触无关分支。通过算术-几何平均不等式（AM-GM）优化连续松弛目标函数： $$f(\mathbf{K}) = \frac{3sn}{K_1} + \sum_{i=2}^{t-1} \frac{3s\Delta K_{i-1}}{K_i} + \Delta K_{t-1}$$ 解得最优分治阈值 $K_i^* = (3s)^{i/t} (n/\Delta)^{1 - i/t}$，严格证明了当 $3s\Delta < n$ 时确定性总查询量不超过 $4t n^{1/t} (s\Delta)^{1-1/t}$。

2. 测地球批量前瞻展开：突破常度展开图的确定性壁垒

对于展开图（Expander Graphs）等拓扑结构，分离数高达 $s = \Theta(n)$，确定性分治退化为平凡的 $O(n)$ 查询。本文设计的随机并行最速下降算法利用了有界最大度 $\Delta$ 图的局部体积控制性质。痛点在于经典最速下降单步只能移动到相邻节点，具有强序列依赖。算法首先引入严格全序 $\prec$（以函数值为主、节点索引为辅打破平局），保证最速下降轨迹的唯一定义与无环性。

在首轮热启动中，算法通过有放回均匀采样 $q_1$ 个节点，利用概率阶梯求和证明采样极小值 $v^{(0)}$ 的最速下降路径长度期望严格满足 $\mathbb{E}[\mathcal{L}(v^{(0)})] < n/(q_1 + 1)$。随后，在每个后续轮次中，算法并不逐跳询问，而是一次性查询以当前节点为中心、半径为 $r+1$ 的测地闭球 $B(v^{(i-1)}, r+1)$。由于 $\Delta$ 有界，半径为 $r+1$ 的球大小受到几何级数 $\frac{\Delta}{\Delta-2}(\Delta-1)^{r+1}$ 的严格控制。这允许算法在单个交互轮中精确沿路径向前“瞬移” $r$ 步，将 $T=t-1$ 轮搜索覆盖的总路径长度扩展至 $T \cdot r$。通过联合优化采样规模 $q_1 = \lceil 10n / (T r) \rceil$ 与搜索半径 $r = \lceil \frac{1}{2}\log_{\Delta-1} n \rceil$，在两轮交互（$t=2$）且度数恒定时直接将查询复杂度降至亚线性的 $O(n / \log n)$。

3. 支撑树阶梯函数族与收缩因子伸缩证明：通用的随机下界技术

为了证明任何多轮算法在一般连通图上的物理极限，痛点在于图结构千差万别，无法直接套用网格上的正交超平面阻断技巧。本文的核心设计是在图 $G$ 上任意固定一棵以 $r$ 为根的支撑树 $T=(V, E_T)$，并基于树上祖先关系构造恶质输入分布 $\mathcal{D}$：随机均匀选取目标局部极小点 $Z \in V$，定义函数族 $f_Z(x) = -\text{dist}_T(r, x)$（若 $x$ 是 $Z$ 的祖先）或 $+\text{dist}_T(r, x)$（否则）。在此构造下，$Z$ 是全图唯一的严格局部极小值，且任意查询 $x$ 仅暴露符号信息——即 $x$ 是否位于根到 $Z$ 的路径上。

本文提出了签名引理（Signature Lemma）：任意查询批次 $Q$ 在树节点集上产生的不同祖先交集签名数严格不超过 $|Q| + 1$。这意味着 $Q$ 次查询至多将候选集划分为 $|Q|+1$ 个互不相交的连通子树。通过定义第 $i$ 轮的候选集收缩因子 $\rho_i(Z) = |C_{i-1}(Z)| / |C_i(Z)|$，本文证明了期望分支数与期望收缩因子的等价性 $\mathbb{E}[m_i] = \mathbb{E}[\rho_i]$。借助 AM-GM 不等式，多轮收缩因子连乘发生伸缩消除（Telescoping）： $$\prod_{i=1}^t \rho_i(Z) = \frac{|\mathcal{C}_0(Z)|}{|\mathcal{C}_t(Z)|} = \frac{n}{|\mathcal{C}_t(Z)|}$$ 结合凸多面体极点上的严格凹函数最小化分析，证明最终候选集要区分出概率至少为 $c$ 的正确解，期望总查询量必定受到 $\Omega(t \cdot c \cdot n^{1/t} - t)$ 的严格约束，确认了算法对轮数 $t$ 的指数级衰减依赖在本质上是不可避免的。

实验关键数据¶

主实验¶

论文聚焦于理论计算复杂性刻画，给出了不同图族与轮数约束下的完备上界与下界闭式渐近表达式。下表总结了本文建立的查询复杂度边界与前序经典工作（序列自适应 $t=n$、网格图多轮以及全自适应分离数模型）的对照：

图类型 / 拓扑特征	交互轮数 $t$	本文确定性上界	本文随机上界 / 下界	前序 SOTA 对照	理论提升 / 刻画意义
任意连通图（通用下界）	$t \ge 1$ 任意整数	—	下界：$\Omega(t n^{1/t} - t)$	网格图下界 $\Omega(t n^{1/t})$ [BL22]	首次将多轮下界从网格推广至任意连通图
一般图（参数化拓扑）	$t \ge 2$ 轮	$O(t n^{1/t} (s\Delta)^{1-1/t})$	匹配 $s,\Delta$ 极端情况	$O((s+\Delta)\log n)$ [SS04] ($t$ 无限制)	首次建立有限轮数下依赖分离数 $s$ 的多项式平滑插值
平面图 / 树宽有界图 ($s=O(\sqrt{n})$)	$t = 2$ 轮	$O(n^{3/4} \sqrt{\Delta})$	下界：$\Omega(\sqrt{n})$	启发式局部搜索无理论保证	两轮交互即实现严格次线性 $O(n^{3/4})$ 查询
常度展开图 ($s=\Theta(n), \Delta=O(1)$)	$t = 2$ 轮	平凡界 $O(n)$	随机上界：$O(n / \log n)$	序列最速下降 $O(\sqrt{n})$ ($t=O(\sqrt{n})$ 轮)	证明常度展开图在 $t=2$ 轮即可打破线性平凡瓶颈
环图 / 路径图 ($\Delta \le 2$)	$t \ge 2$ 轮	$O(t n^{1/t})$	随机上界：$O(\sqrt{n} + t)$	经典全自适应 $O(\log n)$	给出了常数轮下接近 $\sqrt{n}$ 极限的并行搜索算子

消融实验¶

论文在附录与理论推导中针对参数选择与模型组件进行了系统性理论消融与灵敏度分析：

算法组件 / 参数配置	理论复杂度输出	相对最优配置的变化	机制说明
确定性分治：最优几何级数 $K_i^*$	$O(t n^{1/t} (s\Delta)^{1-1/t})$	最优平衡态	各轮查询量通过 AM-GM 严格均摊，达成各阶段开销相等
确定性分治：退化常数步长 $K_i = n - i \cdot \frac{n}{t}$	$O(n)$	丧失次线性加速	顶层分离器过大或底层连通块暴涨，破坏分治效果
随机下降：自适应半径 $r \approx \frac{1}{2}\log_{\Delta-1} n$	$O(\frac{n}{t\log_\Delta n} + t\Delta^2 \sqrt{n})$	平衡采样与前瞻代价	测地球体积按指数爆发，超过对数半径导致单轮查询直接超标
随机下降：无热启动 ($q_1 = 0$)	失败概率退化至接近 1	路径长度退化至 $\Omega(n)$	缺乏均匀初筛导致下降轨迹过长，无法在 $t-1$ 轮内截断
随机下降：固定半径 $r=1$（仅查一度邻居）	$O(n)$	退化为普通批处理	每轮仅前进一步，至多走 $t-1$ 步，对全局极小覆盖率趋近于 0

关键发现¶

分离数是决定多轮确定性复杂度的支配性几何拓扑量：在固定轮数 $t$ 下，确定性查询复杂度由 $(s\Delta)^{1-1/t}$ 严格调控。对于平面图（$s=O(\sqrt{n})$）、有界树宽图或网格图，只要分离数满足 $s \ll n$，哪怕只有 2 轮交互也能取得显著的次线性查询复杂度。
展开图的确定性与随机性分水岭：对于拉普拉斯谱间隙良好的展开图，$s = \Theta(n)$，确定性分治失效（退化为 $n$）。但随机并行最速下降表明，通过常数半径拓扑球的前瞻探测，随机算法即使在 2 轮内也可以压制到 $O(n / \log n)$，证明展开图在局部几何受限时仍存在并行加速空间。
轮数上限的指数级收益递减：无论是上界的 $n^{1/t}$ 还是下界的 $t n^{1/t}$，均表现出对轮数 $t$ 的极端敏感性。从 $t=1$（完全无交互，必须全图查询 $\Omega(n)$）增加到 $t=2$，查询复杂度发生从线性到根号级的质变；但随着 $t$ 进一步增大，轮数边际收益迅速衰减。

亮点与洞察¶

任意图支撑树嵌入技术：以往下界构造通常深度绑定特定几何网格坐标，本文证明任意连通图只需固定任意一棵支撑树并赋予祖先距离势能，就能通过签名引理将任意复杂的图查询问题规约到树上单链识别，通用性极强。
分支因子与收缩因子的期望对偶性：在下界证明中，通过严密的双重计数证明了查询诱导的平均子树分支数与搜索空间收缩因子在期望意义下完全相等（$\mathbb{E}[m_i] = \mathbb{E}[\rho_i]$），这一对偶关系使原本极其错综的多轮动态自适应树剪枝过程能够通过 AM-GM 简洁收缩。
AI 辅助深度理论推导的方法学范式：作者在方法论章节详细披露了借助 Gemini Deep Think 推进理论研究的过程，展示了由人类学者提出高阶概念引理与架构方向、大模型协助合成初版证明细节、再由人类严密纠错闭环（如修复历史-候选集双射中的循环论证缺陷）的高效协同范式。

局限与展望¶

高分离数图的上界与下界间隙：对于最大度 $\Delta=O(1)$ 的一般展开图，本文给出的下界为 $\Omega(\sqrt{n})$（$t=2$），而随机上界为 $O(n/\log n)$，两者之间存在 $\tilde{O}(\sqrt{n})$ 的理论差距，尚未完全收敛到紧致界。
分离器计算本身的计算复杂度：确定性算法假设预处理阶段能够获知或计算出高质量的图分离器，但在实际大规模图处理中，精确求解最小平衡分离器或最优树宽分解本身属于 NP-hard 范畴，依赖近似算法可能引入额外的常数损失。
面向连续非凸优化流形的应用拓展：论文探讨了鲁棒低秩矩阵估计诱导的三角环图，但离散化图步长 $\delta$ 与连续非凸极值点邻域之间的逼近误差和光滑性参数尚未直接融入到查询复杂度闭式中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统攻克一般图上多轮交互局部搜索的复杂度理论，消除了网格图假设。
实验充分度: ⭐⭐⭐⭐⭐ 纯理论工作，数学推导极为详尽，上界构造、下界证明及消融分析均完备自洽。
写作质量: ⭐⭐⭐⭐⭐ 逻辑主线极为清晰，图示直观，动机与方法论披露翔实坦诚。
价值: ⭐⭐⭐⭐⭐ 为并行分布式黑盒优化、连续非凸平稳点理论及深度学习调参并行度边界提供了坚实理论基础。

图类型 / 拓扑特征	交互轮数 \(t\)	本文确定性上界	本文随机上界 / 下界	前序 SOTA 对照	理论提升 / 刻画意义
任意连通图（通用下界）	\(t \ge 1\) 任意整数	—	下界：\(\Omega(t n^{1/t} - t)\)	网格图下界 \(\Omega(t n^{1/t})\) [BL22]	首次将多轮下界从网格推广至任意连通图
一般图（参数化拓扑）	\(t \ge 2\) 轮	\(O(t n^{1/t} (s\Delta)^{1-1/t})\)	匹配 \(s,\Delta\) 极端情况	\(O((s+\Delta)\log n)\) [SS04] (\(t\) 无限制)	首次建立有限轮数下依赖分离数 \(s\) 的多项式平滑插值
平面图 / 树宽有界图 (\(s=O(\sqrt{n})\))	\(t = 2\) 轮	\(O(n^{3/4} \sqrt{\Delta})\)	下界：\(\Omega(\sqrt{n})\)	启发式局部搜索无理论保证	两轮交互即实现严格次线性 \(O(n^{3/4})\) 查询
常度展开图 (\(s=\Theta(n), \Delta=O(1)\))	\(t = 2\) 轮	平凡界 \(O(n)\)	随机上界：\(O(n / \log n)\)	序列最速下降 \(O(\sqrt{n})\) (\(t=O(\sqrt{n})\) 轮)	证明常度展开图在 \(t=2\) 轮即可打破线性平凡瓶颈
环图 / 路径图 (\(\Delta \le 2\))	\(t \ge 2\) 轮	\(O(t n^{1/t})\)	随机上界：\(O(\sqrt{n} + t)\)	经典全自适应 \(O(\log n)\)	给出了常数轮下接近 \(\sqrt{n}\) 极限的并行搜索算子

算法组件 / 参数配置	理论复杂度输出	相对最优配置的变化	机制说明
确定性分治：最优几何级数 \(K_i^*\)	\(O(t n^{1/t} (s\Delta)^{1-1/t})\)	最优平衡态	各轮查询量通过 AM-GM 严格均摊，达成各阶段开销相等
确定性分治：退化常数步长 \(K_i = n - i \cdot \frac{n}{t}\)	\(O(n)\)	丧失次线性加速	顶层分离器过大或底层连通块暴涨，破坏分治效果
随机下降：自适应半径 \(r \approx \frac{1}{2}\log_{\Delta-1} n\)	\(O(\frac{n}{t\log_\Delta n} + t\Delta^2 \sqrt{n})\)	平衡采样与前瞻代价	测地球体积按指数爆发，超过对数半径导致单轮查询直接超标
随机下降：无热启动 (\(q_1 = 0\))	失败概率退化至接近 1	路径长度退化至 \(\Omega(n)\)	缺乏均匀初筛导致下降轨迹过长，无法在 \(t-1\) 轮内截断
随机下降：固定半径 \(r=1\)（仅查一度邻居）	\(O(n)\)	退化为普通批处理	每轮仅前进一步，至多走 \(t-1\) 步，对全局极小覆盖率趋近于 0