Sample-Efficient Optimization over Generative Priors via Coarse Learnability¶

会议: NeurIPS 2026
arXiv: 2503.06917
领域: 优化算法 / Optimization
关键词: 基于模型的优化 (MBO), 粗可学习性 (Coarse Learnability), 零阶非凸优化, 模拟退火, Metropolis-Hastings

一句话总结¶

针对黑盒复杂生成先验下的零阶优化缺乏有限样本理论保证的难题，本文提出了仅需模型以多项式因子覆盖目标质量的“粗可学习性”假设，并设计了结合模拟退火与 Metropolis-Hastings 修正的 ALDrIFT 算法，证明了多项式样本复杂度并在二次包络非凸全局优化中达成了 $\widetilde{O}(\log 1/\varepsilon)$ 样本复杂度。

研究背景与动机¶

基于模型的优化（Model-Based Optimization, MBO）如交叉熵方法（Cross-Entropy Method）和模型参考自适应搜索（Model Reference Adaptive Search, MRAS）是解决黑盒零阶优化的经典范式。这类方法通过在搜索分布下迭代采样、挑选高表现样本并拟合新模型，逐步引导候选解向最优区域聚集。然而，经典 MBO 的收敛保证通常停留在渐近意义上，且高度依赖于自然指数族等刚性代数结构假设；当生成模型拓展为具备强拟合能力但结构复杂的近似学习器（如深度神经网络或大语言模型）时，由于有限样本拟合误差的非可逆累积与分布漂移，经典理论无法刻画其有限样本复杂度。

在实践中，将表达力强大的生成先验 $\mathcal{L}(s)$（提供局部语法、语义偏好或正规化）与外部算法检验器 $d(s)$（提供全局约束或代价反馈）相结合已成为推理时对齐和组合优化的核心诉求。例如在风景路径规划、带局部度约束的生成树或会议排程中，算法需从目标分布 $p_T(s) \propto \mathcal{L}(s)e^{-T\cdot d(s)}$ 中采样。当退火温度 $T$ 增大时，目标分布与初始先验在测度上呈指数级偏离，朴素的拒绝采样或重要性采样所需样本量爆炸；而简单的启发式方法（如每次挑选最低代价样本拟合新模型）极易诱发模式坍缩，使稀有但至关重要的全局最优区域彻底失去概率质量支撑。

现存理论的核心断层在于：缺乏一个普适的统计假设来描述“表现力近似学习器在迭代拟合中维持目标区域覆盖”的能力。传统的 PAC 学习或严格密度估计要求总变差距离收敛，在模型错误设定（misspecified）或先验极其复杂的场景下过于严苛且不可行。核心 idea：提出只需生成模型在多项式因子内包络目标概率质量的“粗可学习性”（Coarse Learnability）松弛假设，并构建结合温度退火与独立 Metropolis-Hastings 校正的算法 ALDrIFT，以多项式样本复杂度阻断误差累积并实现全局精确收敛。

方法详解¶

整体框架¶

ALDrIFT 算法旨在从目标分布 $p_T(s) \propto \mathcal{L}(s)e^{-T\cdot d(s)}$ 中高效抽取样本，其中成本函数 $d(s) \in [0, D]$ 仅可通过零阶黑盒查询。算法引入一个从 $\tau = 0$ 逐渐升温至 $T$ 的退火序列，中间目标分布为 $p_\tau(s) \propto \mathcal{L}(s)e^{-\tau d(s)}$。在每个温度阶梯上，算法并不直接使用上一轮拟合出的生成模型 $\mathcal{L}_{\tau^-}$ 产生样本，而是将其作为独立提案分布（proposal distribution），通过运行长度为 $M = m^2$ 的 Metropolis-Hastings（MH）马尔可夫链修正采样偏差，获得严格逼近 $p_\tau$ 的非加权样本集 $S_\tau$，最后利用该样本集拟合更新生成模型 $\mathcal{L}_\tau$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["初始先验模型 L_0 = L 与温度 tau = 0"] --> B["温度退火步进<br/>tau_new = min(tau + 1/D, T)"]
    B --> C["以 L_tau- 为提案分布进行独立 Metropolis-Hastings 采样"]
    C --> D["构建纠偏样本集 S_tau (共 m 个高保真样本)"]
    D --> E["模型拟合更新 L_tau (满足粗可学习性覆盖包络)"]
    E -->|tau < T| B
    E -->|tau = T| F["输出最终对齐生成模型 L_T"]

关键设计¶

1. 粗可学习性假设（Coarse Learnability）：动态保障覆盖包络 传统统计学习关注经验误差或密度估计的收敛，但对于 MBO 而言，模型无需精确复现复杂的局部纹理，只需保证其尾部足够厚、不丢失潜在低成本区域的概率质量。粗可学习性（Assumption 2）形式化为：若生成模型族在从分布 $\hat{p}$ 抽取的 $m$ 个样本上训练，能以至少 $1-\delta$ 的概率保证学到的模型 $\mathcal{L}_\tau$ 满足其覆盖比率（coverage ratio）几乎处处受控于多项式因子 $K$： $$\Pr_{s \sim p_\tau}\left[ \mathrm{cov}_{p_\tau, \mathcal{L}_\tau}(s) > K \right] \leq O(d_{\mathrm{tv}}(\hat{p}, p_\tau)) + \varepsilon$$ 其中覆盖度定义为 $\mathrm{cov}_{p, L}(s) = \frac{p(s)}{L(s)}$，$m = \mathrm{poly}(K/\delta, \ln(1/\varepsilon))$。该定义与标准 PAC 学习的根本区别在于其样本量对失效率 $\varepsilon$ 是对数尺度的（$\varepsilon \approx e^{-m^\beta}$），从而在多项式样本预算下将漏覆盖非典型集的概率压制至指数级微小，确保退火过程中低先验但高潜力的全局最优解不被剪除。

2. 独立 Metropolis-Hastings 样本纠偏：阻断跨迭代误差累积 TopIFT 等简单启发式直接利用上一轮拟合模型的样本进行硬截断筛选，拟合误差会在迭代中以乘性复合扩散，迅速导致模式坍缩。ALDrIFT 设计了显式的 MH 纠偏机制：在每个温度步 $\tau$，使用上一轮模型 $\mathcal{L}_{\tau^-}$ 生成候选样本 $\hat{s}_i$，并以权重比率计算转移接受概率 $\beta_i$： $$\beta_i = \min\left(1, \; \frac{w_\tau(\hat{s}_i)}{\mathcal{L}_{\tau^-}(\hat{s}_i)} \cdot \frac{\mathcal{L}_{\tau^-}(s_{i-1})}{w_\tau(s_{i-1})}\right)$$ 其中非归一化权重为 $w_\tau(s) = \mathcal{L}(s)e^{-\tau d(s)}$。通过限制每次升温步长 $\Delta \tau \leq 1/D$，由于 $d(s) \in [0, D]$，相邻目标密度的比率严格受控于 $p_\tau(s) \leq e \cdot p_{\tau^-}(s)$。只要提议分布满足多项式覆盖 $\mathrm{cov}_{p_{\tau^-}, \mathcal{L}_{\tau^-}}(s) \leq m$，MH 链在限制集上的密度比即有界于 $e \cdot m$。依托独立 MH 的一致遍历性（Uniform Ergodicity），运行 $M = m^2$ 步即可将总变差距离偏差压制至 $e^{-m/e}$，实现无偏差纯净抽样。

3. 乐观后验方差膨胀与几何退火：突破二次包络非凸全局优化 在连续域 $\mathbb{R}^n$ 中，目标函数满足全局二次包络 $\frac{\mu_d}{2}\|x-x^*\|^2 \leq d(x) - d(x^*) \leq \frac{L_d}{2}\|x-x^*\|^2$（允许局部任意剧烈非凸震荡）。标准 MBO 直接采用样本方差拟合模型，极易陷入局部陷阱。ALDrIFT 引入类比强盗算法中“乐观探索”的方差膨胀策略：不使用经验方差，而是根据包络曲率严格设定提议分布高斯方差为 $\frac{2}{\mu_\tau}I_n$（其中 $\mu_\tau = \mu_0 + \tau \mu_d$），以此证明了密度比上界全局恒成立： $$\sup_{x \in \mathbb{R}^n} \frac{p_\tau(x)}{\mathcal{L}_\tau(x)} \leq 2^{n/2} B^5 e^{1+2n} := K$$ 其中 $B = \kappa_{\max}^{n/2} \exp(E_{\text{shift}})$ 为与维度和几何曲率比相关的常数，且 $K$ 完全不随温度 $\tau$ 发散。配合乘性几何退火步长 $\tau_{k+1} = (1 + 1/n)\tau_k$，外层迭代仅需 $N = O(n \ln \frac{T L_d}{\mu_0})$ 步，在拒绝采样辅助下达成针对全局最优精度 $\varepsilon$ 的 $\widetilde{O}(\log 1/\varepsilon)$ 样本复杂度，指数级超越经典局部 MCMC 模拟退火在非凸势垒下所需的 $O(\exp(1/\varepsilon))$ 样本瓶颈。

一个完整示例¶

以一维非凸双峰/多峰目标结合高斯提议为例展示单步温度演进： 1. 输入与当前状态：在温度 $\tau$ 下，当前目标密度包含两个深浅不一的局部极小。当前生成模型 $\mathcal{L}_{\tau^-}$ 均值位于经验中心，方差按设计经过膨胀。 2. 提议与 MH 纠偏：从 $\mathcal{L}_{\tau^-}$ 抽取 $m$ 条独立轨迹。对于每条轨迹，以 $\mathcal{L}_{\tau^-}$ 为提议运行 $M=m^2$ 步 MH 链。由于 $w_\tau(s) \propto \mathcal{L}_0(s)e^{-\tau d(s)}$，处于深谷处的候选点由于 $d(s)$ 极低而拥有更高的未归一化权重，接受率引导链在 $m^2$ 步后完全按照真目标分布 $p_\tau$ 分布，落入浅谷的样本被自然筛选淘汰。 3. 模型重估：收集纠偏后的 $m$ 个样本点更新经验均值 $\hat{\omega}_\tau$，并再次以膨胀方差 $\frac{2}{\mu_\tau}I$ 生成 $\mathcal{L}_\tau$。即使真实目标呈现非对称多峰，膨胀高斯依然在支撑集上完整包络目标质量，成功为下一步 $\tau + \Delta \tau$ 奠定覆盖前提。

损失函数 / 训练策略¶

在通用离散/参数化生成模型中，模型拟合步骤采用最大似然估计（MLE）拟合校正后的样本集合 $S_\tau$： $$\mathcal{L}_\tau = \arg\max_\theta \sum_{s \in S_\tau} \ln p(s; \theta)$$ 在实践中，直接以 $\mathcal{L}_{\tau^-}$ 的网络权重作为初始值进行参数微调，大幅降低冷启动训练开销。在连续二次包络设定中，模型参数拟合退化为解析更新：保持方差解析固定为 $\frac{2}{\mu_0 + \tau \mu_d}I_n$，仅需根据样本计算经验均值 $\hat{\omega}_\tau = \frac{1}{m}\sum_{i=1}^m X_i$。

实验关键数据¶

主实验：非凸多极值景观优化（ALDrIFT vs. TopIFT）¶

实验设定 $n=10$ 维优化问题，目标函数包含全局二次包络与高频余弦震荡：$d(x) = \frac{\mu_d}{2}\|x\|^2 + A \sum_{i=1}^{10} (1 - \cos(\omega x_i))$，全局最优位于 $x^* = \mathbf{0}$。初始先验均值 $x_0$ 远离原点，优化器必须跨越多个高能局部势垒。

下表总结了在严格受限的样本预算下（$m=200, M=50, T=20$，退火调度 $\tau_{k+1} = (1+1/10)\tau_k$），不同参数设置下 10 次独立运行的收敛误差表现（$\|\mu - x^*\|$）：

实验环境与曲率参数	算法方案	样本方差处理方式	采样纠偏机制	最终均值误差 $\\|\mu - x^*\\|$	运行结果特征
Setting 1: $\mu_d=0.5, A=2.0, \omega=3.0, x_0=\mathbf{6}, \mu_0=0.1$	TopIFT (基线)	经验协方差估计	无纠偏 (Top-m 硬筛选)	$\approx 3.20$	陷入亚优局部极小，方差过早萎缩坍塌
Setting 1: $\mu_d=0.5, A=2.0, \omega=3.0, x_0=\mathbf{6}, \mu_0=0.1$	ALDrIFT (本文)	乐观曲率膨胀方差 $\frac{2}{\mu_\tau}I$	Metropolis-Hastings 链纠偏	$\approx 0.45$	跨越多个势垒，快速收敛至全局最优吸引域
Setting 2: $\mu_d=1.0, A=0.5, \omega=4.0, x_0=\mathbf{1.35}, \mu_0=2.0$	TopIFT (基线)	经验协方差估计	无纠偏 (Top-m 硬筛选)	$\approx 0.85$	震荡停滞，无法跳出临近鞍点/陷阱
Setting 2: $\mu_d=1.0, A=0.5, \omega=4.0, x_0=\mathbf{1.35}, \mu_0=2.0$	ALDrIFT (本文)	乐观曲率膨胀方差 $\frac{2}{\mu_\tau}I$	Metropolis-Hastings 链纠偏	$\approx 0.10$	稳定单调收敛逼近全局零点

辅助分析实验：LLM 组合推理与微调质量迁移¶

在离散组合任务中，通过零阶反馈指导微调语言模型（GPT-2）验证粗可学习性的外推覆盖行为。下表对比了线路排程问题（Line Scheduling, $K=10$ 站点，要求等待时间为 0，最优解为全 20）和低度生成树问题（Low Degree Spanning Tree, $n=16$ 节点，度 $\leq 2$ 且全连通）各方案表现：

实验任务	对比基准 / 算法阶段	样本/查询预算 $N$	算法目标代价 $d(s)$ (越低越好)	模型约束违背量 (越低越好)	结论与形态描述
线路排程 (Line Scheduling)	Best-of-LLM ($N=1$)	1	中位数 $\approx 125$	0 (先验已微调)	随机均匀采样，对全局等待约束完全盲目
线路排程 (Line Scheduling)	Best-of-LLM ($N=400$)	400	中位数 $\geq 100$ (均值 85.5)	0	盲目暴力采样，命中全最优概率 $\leq 10^{-10}$
线路排程 (Line Scheduling)	单轮微调 TopIFT ($Q=1$)	400 ($m=30, M=12$)	$\approx 81$	0	缺乏多轮渐进迁移，无法形成有效外推
线路排程 (Line Scheduling)	迭代 TopIFT (迭代 $r=4$)	192 ($m=4, M=12$)	中位数 $\approx 40$	0	显著下移代价分布，显现覆盖外推迹象
线路排程 (Line Scheduling)	迭代 TopIFT (迭代 $r=8$)	384 ($m=4, M=12$)	0 (中位数与众数均为 0)	0	20 次独立运行几乎全部完美收敛至最优解
低度生成树 (Spanning Tree)	Best-of-LLM ($N=600$)	600	$\geq 2$ (连通块数量 - 1)	$\geq 3$ (度 $>2$ 节点数)	虽有微弱连通倾向，但仍高度断开且度超标
低度生成树 (Spanning Tree)	Best-of-ALG ($N=600$)	600	0 (全连通树)	$\approx 6-8$ (大量度超标)	无法顾及局部度约束
低度生成树 (Spanning Tree)	迭代 TopIFT ($Q=3$)	600 ($m=4, M=50$)	0 (全连通生成树)	0 (成功合成哈密顿路径)	完美同时满足全局连通与局部度限制约束

关键发现¶

方差膨胀与采样纠偏的不可替代性：在连续非凸优化中，TopIFT 依赖经验方差，由于样本在局部低洼处过早聚集导致方差迅速收缩至 0，彻底丧失探索能力；ALDrIFT 依托乐观曲率设定的膨胀方差维持重尾，并通过 MH 纠偏确保样本保真度，成功定位全局吸引子。
高阶温度下的采样停滞现象：实验观测到当退火温度 $\tau$ 持续走高、目标分布极端尖锐时，在有限马氏链长 $M$ 下 MH 接受率会逐步趋近于 0（Fig. 1 Right）。这表明 ALDrIFT 的核心工程价值在于以极少样本快速定位全局最优所在的“吸引盆”（basin of attraction），而在极后期可无缝切换为局部确定性梯度/局部搜索方法。
小样本微调诱发分布外推覆盖：在 GPT-2 实验中，模型在迭代微调后产生的新候选解平均代价显著优于用于微调它们的 elite 样本自身（Fig. 3b），表明生成模型并非死记硬背训练样本，而是按粗可学习性假设所预测的那样，沿梯度反馈方向对低代价区域形成了具备泛化覆盖能力的概率分布重塑。

亮点与洞察¶

重构 MBO 理论基石：摒弃了要求模型逼近真分布的经典 PAC/TV-distance 强假设，创造性提出以单侧“多项式覆盖度”为核心的“粗可学习性”，将理论重心从要求模型架构的精确完备性转向要求模型容量与尾部的包络能力。
理论闭环与普适性证明：不仅在算法层证明了多项式样本复杂度，更在统计学层证明了高斯混合模型（模型错误设定下的单高斯拟合）、单参数指数族以及过平滑核密度估计（Over-smoothed KDE）天然满足粗可学习性，理论基底坚实。
对数精度样本界 $\widetilde{O}(\log 1/\varepsilon)$：在具备二次包络的非凸优化问题上，证明了 ALDrIFT 的样本量与精度参数呈现对数关系，在无需空间网格剖分的前提下，达到了与确定性乐观优化（DOO/SOO）一致的最优收敛阶数，指数级胜过传统模拟退火与网格搜索。

局限与展望¶

依赖曲率包络先验参数：在连续域非凸优化的严格界分析中，算法需要预先知晓全局二次包络的下界曲率 $\mu_d$ 与上界曲率 $L_d$；若曲率估计严重失真，方差膨胀倍率将无法保证全局覆盖。
概率似然评估假设（Assumption 1）的实际门槛：ALDrIFT 算法的 MH 转移需要计算生成模型 $\mathcal{L}(s)$ 的精确对数概率，这对于闭源 LLM、扩散模型或隐变量生成器而言存在调用成本与工程限制。
未来方向：探索引入对数概率梯度信息（以 Langevin MCMC 替代独立 MH）、弱化对二次包络边界的先验依赖、以及从电路复杂度视角在 Transformer 架构中形式化建立粗可学习性定理。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出粗可学习性概念并建立基于生成先验的有限样本 MBO 理论框架。
实验充分度: ⭐⭐⭐⭐ 理论证明严丝合缝，连续数值实验切中要害，离散 LLM 微调提供了直观定性印证。
写作质量: ⭐⭐⭐⭐⭐ 概念动机阐述层层递进，数学推导详实严密，从抽象假设到具体实例落地过渡自然。
价值: ⭐⭐⭐⭐⭐ 为大模型推理时对齐、神经组合优化及黑盒非凸优化提供了全新的理论分析透镜与算法蓝图。

实验环境与曲率参数	算法方案	样本方差处理方式	采样纠偏机制	最终均值误差 \(\\|\mu - x^*\\|\)	运行结果特征
Setting 1: \(\mu_d=0.5, A=2.0, \omega=3.0, x_0=\mathbf{6}, \mu_0=0.1\)	TopIFT (基线)	经验协方差估计	无纠偏 (Top-m 硬筛选)	\(\approx 3.20\)	陷入亚优局部极小，方差过早萎缩坍塌
Setting 1: \(\mu_d=0.5, A=2.0, \omega=3.0, x_0=\mathbf{6}, \mu_0=0.1\)	ALDrIFT (本文)	乐观曲率膨胀方差 \(\frac{2}{\mu_\tau}I\)	Metropolis-Hastings 链纠偏	\(\approx 0.45\)	跨越多个势垒，快速收敛至全局最优吸引域
Setting 2: \(\mu_d=1.0, A=0.5, \omega=4.0, x_0=\mathbf{1.35}, \mu_0=2.0\)	TopIFT (基线)	经验协方差估计	无纠偏 (Top-m 硬筛选)	\(\approx 0.85\)	震荡停滞，无法跳出临近鞍点/陷阱
Setting 2: \(\mu_d=1.0, A=0.5, \omega=4.0, x_0=\mathbf{1.35}, \mu_0=2.0\)	ALDrIFT (本文)	乐观曲率膨胀方差 \(\frac{2}{\mu_\tau}I\)	Metropolis-Hastings 链纠偏	\(\approx 0.10\)	稳定单调收敛逼近全局零点

实验任务	对比基准 / 算法阶段	样本/查询预算 \(N\)	算法目标代价 \(d(s)\) (越低越好)	模型约束违背量 (越低越好)	结论与形态描述
线路排程 (Line Scheduling)	Best-of-LLM (\(N=1\))	1	中位数 \(\approx 125\)	0 (先验已微调)	随机均匀采样，对全局等待约束完全盲目
线路排程 (Line Scheduling)	Best-of-LLM (\(N=400\))	400	中位数 \(\geq 100\) (均值 85.5)	0	盲目暴力采样，命中全最优概率 \(\leq 10^{-10}\)
线路排程 (Line Scheduling)	单轮微调 TopIFT (\(Q=1\))	400 (\(m=30, M=12\))	\(\approx 81\)	0	缺乏多轮渐进迁移，无法形成有效外推
线路排程 (Line Scheduling)	迭代 TopIFT (迭代 \(r=4\))	192 (\(m=4, M=12\))	中位数 \(\approx 40\)	0	显著下移代价分布，显现覆盖外推迹象
线路排程 (Line Scheduling)	迭代 TopIFT (迭代 \(r=8\))	384 (\(m=4, M=12\))	0 (中位数与众数均为 0)	0	20 次独立运行几乎全部完美收敛至最优解
低度生成树 (Spanning Tree)	Best-of-LLM (\(N=600\))	600	\(\geq 2\) (连通块数量 - 1)	\(\geq 3\) (度 \(>2\) 节点数)	虽有微弱连通倾向，但仍高度断开且度超标
低度生成树 (Spanning Tree)	Best-of-ALG (\(N=600\))	600	0 (全连通树)	\(\approx 6-8\) (大量度超标)	无法顾及局部度约束
低度生成树 (Spanning Tree)	迭代 TopIFT (\(Q=3\))	600 (\(m=4, M=50\))	0 (全连通生成树)	0 (成功合成哈密顿路径)	完美同时满足全局连通与局部度限制约束