Ömer Deniz Akyildiz (来自 The Alan Turing Institute 和 University of Warwick)、Dan Crisan (来自 Imperial College London) 以及 Joaquín Miguez (来自 Instituto de Investigación Sanitaria Gregorio Marañón 和 Universidad Carlos III de Madrid) 的研究成果《并行序贯蒙特卡洛用于随机无梯度非凸优化》(Parallel Sequential Monte Carlo for Stochastic Gradient-Free Nonconvex Optimization) 于2020年7月29日在线发表于期刊 *statistics and computing*。
这项研究隶属于计算统计学与优化算法的交叉领域，核心目标是解决大规模数据背景下，目标函数为多个分量之和的复杂优化问题。在机器学习和信号处理中，此类问题非常常见，例如基于大量观测数据的参数估计。传统的解决方案，尤其是随机梯度下降及其变体，因其高效性而被广泛采用。然而，这些方法存在显著局限性：首先，它们依赖于梯度信息，而在许多实际场景中（如黑盒系统、不可微分代码），梯度可能无法获取或计算成本极高；其次，当目标函数存在多个局部极小值或宽阔的“平坦”区域（梯度近乎为零）时，基于梯度的方法容易陷入局部最优或收敛极其缓慢。尽管存在一些无梯度优化方法（如随机搜索、有限差分梯度近似、进化策略），但它们通常需要精确或确定性的函数评估，难以处理只能通过噪声评估或仅能计算目标函数子集分量的随机优化设置。此外，一些基于模型随机搜索的方法（如模拟退火、马尔可夫链蒙特卡洛方法）虽可处理非凸问题，但大多针对确定性函数评估设计，扩展到随机优化并保证理论收敛性并非易事。因此，本研究旨在开发一种新型的随机零阶优化算法，它仅需评估目标函数的小批量分量，无需任何梯度信息，并能够有效处理具有多峰或平坦区域的非凸代价函数，同时提供坚实的理论收敛保证。
研究团队提出了一种名为并行序贯蒙特卡洛优化器（PSMCO, Parallel Sequential Monte Carlo Optimizer）的全新算法。其详细工作流程基于将优化问题转化为概率推断问题的核心思想。具体而言，算法将待优化的参数向量θ视为随机变量，通过构造一系列概率测度{π_t}，使得这些测度的概率密度函数的全局最大值与原始代价函数f(θ)的全局最小值完全重合。这样，寻找f(θ)的最小值就等价于寻找π_t(θ)的最大值。这一序列通过递归方式构建：从先验分布π_0开始，每次迭代引入一个由小批量数据定义的势函数（potential function）gt(θ) = exp(-Σ{i∈I_t} f_i(θ))，其中I_t是从所有分量中均匀、无放回地抽取的大小为k的索引子集。通过贝叶斯更新公式 π_t(dθ) ∝ gt(θ) π{t-1}(dθ)，即可得到新的后验测度。最终，当遍历所有数据分量（即所有子集的并集为全集）后，后验密度π_T(θ)即与exp(-f(θ))成比例。
PSMCO算法利用蒙特卡洛采样来近似上述递归过程。它并行运行M个独立的采样器（称为“工作者”），每个工作者看到的是对原始数据集的不同随机划分（即各自独立生成的小批量索引序列{I_t^(m)}）。每个采样器维护一个包含N个粒子（即参数样本）的集合。单次迭代（对应处理一个小批量）的工作流程包含三个核心步骤：抖动（Jittering）、加权（Weighting）和重采样（Resampling）。在抖动步骤，每个粒子通过一个特定的马尔可夫核κ进行传播，以探索参数空间。研究采用了形式为 κ(dθ|θ‘) = (1 - ε_N)δ_θ’(dθ) + ε_N τ(dθ|θ’) 的抖动核，其中ε_N ≤ 1/√N，τ可以是简单的多元高斯或t分布。这种设计使得大部分粒子保持不变，只有一小部分（比例约为ε_N）被扰动，既保持了多样性，又保证了算法的稳定性（满足假设：核的 Lipschitz 常数与 1/√N 相关）。在加权步骤，根据当前小批量定义的势函数g_t^(m)(θ)，为抖动后产生的新粒子计算重要性权重 w_t^(i,m) ∝ g_t^(m)(θ̂_t^(i,m))。随后进行重采样（如多项式重采样），根据权重从这些粒子中抽取N个新粒子，形成对当前后验测度π_t^(m)的粒子近似 π_t^(m),N。所有M个工作者独立执行此流程。
为了从并行运行的结果中给出一个最终的优化解，算法需要一个选择机制。每个工作者在迭代过程中会计算其路径上的增量边缘似然（incremental marginal likelihood）的估计值 Z_{1:t}^{(m),N}，这反映了该粒子系统对已见数据的拟合质量。当需要在时刻t给出一个最优估计时，算法选择具有最高累积边缘似然估计的工作者 m_t。然后，利用该最佳工作者的粒子集，通过核密度估计（Kernel Density Estimator, KDE）方法构造其后验密度 π_t^(m_t)(θ) 的近似 p_t^(m_t*),N(θ)，最后选取使该密度估计值最大的粒子作为当前对全局最小值的估计 θ_t^N。这里，核密度估计的带宽h被设置为与 N^{-1/(d+4)} 成比例，这是理论分析所需的最优选择。
本研究不仅提出了算法，还对其进行了深入的理论分析，这是工作的主要贡献之一。理论分析证明了每个采样器产生的估计量几乎必然（almost surely）收敛到代价函数的全局最小值，并给出了明确的收敛速率。具体地，研究者证明了对于任意有界函数φ，粒子系统对后验期望的近似误差满足 ‖(φ, π_t) - (φ, π_t^N)‖_p ≤ (c_t,p ‖φ‖_∞)/√N。进而，通过更精细的分析，得到了几乎必然意义下的误差上界：|(φ, π_t^N) - (φ, π_t)| ≤ u_t,δ / N^{(1⁄2 - δ)}，其中δ是任意小正常数。最重要的是，在关于后验密度π_t和核函数的适当正则性假设下（如Lipschitz连续性、核函数有界、参数空间紧致等），研究证明了由算法产生的优化估计量 θ_t^N 的误差界：π_t(θ_t^*) - π_t(θt^N) ≤ w{t,d,ε} / N^{1/(d+4) - ε}，其中θ_t是真实后验模。由于在特定先验选择下（如均匀先验），π_t(θ) ∝ exp(-f(θ))，这直接意味着对于原始代价函数，有 0 ≤ f(θ_t^N) - f(θ^) ≤ w̃_{t,d,ε} / N^{1/(d+4) - ε}，其中θ*是全局最小值点。这些结果不仅证明了算法的渐近最优性，而且给出了收敛速率与蒙特卡洛样本数N以及参数空间维度d的显式关系，这在以往大多数蒙特卡洛优化方法的纯渐近分析中是罕见的。
研究的数值实验部分展示了PSMCO算法在三个传统随机梯度方法难以处理的优化问题上的性能。第一个例子是包含四个全局最小值的函数最小化问题，目的是展示算法能够用粒子同时覆盖多个最优解区域。实验设定N=50个粒子，M=100个并行工作者，结果显示粒子成功聚集在四个最大值（即最小值）周围。第二个例子是最小化一个Sigmoid回归问题中的损失函数，该函数存在宽阔的平坦区域，梯度信息微弱。将PSMCO与并行随机梯度下降（PSGD）在“差”和“好”两种初始化条件下比较，PSMCO能够有效搜索到全局最小值，而PSGD在差初始化下无法移动，在好初始化下也会在平坦区域停滞。第三个例子是一个高维、非光滑、非凸的约束优化问题（带有SCAD罚项的线性回归），用于比较PSMCO、单工作者版本的SMCO、文献[Stinis, 2012]的PFSGO算法以及随机进化策略（SES）。在维数d=10和d=30的设置下，结果表明SMCO和PSMCO在收敛精度上优于对比算法，而SES由于梯度估计效率低下而表现缓慢。这些实验验证了PSMCO在处理具有挑战性的非凸、多峰、平坦区域问题时的有效性。
该研究的结论是，PSMCO算法为一大类随机、无梯度、非凸优化问题提供了一种强有力的解决方案。其科学价值在于：第一，方法论上，创新地将序贯蒙特卡洛采样框架与随机优化问题紧密结合，通过并行采样和基于边缘似然的选择机制，实现了稳健的全局优化搜索。第二，理论上，提供了超越标准SMC收敛分析的、针对优化问题的严格理论保证，包括几乎必然收敛性和明确的非渐近收敛速率，这填补了相关文献的空白。第三，应用上，算法仅需函数值评估，对问题形态要求宽松，能够处理梯度无效或不可得的场景，具有广泛的潜在应用前景，如机器学习中的黑盒超参数优化、复杂工程系统设计等。
本研究的亮点突出体现在以下几个方面：首先，算法的强鲁棒性：它不依赖于梯度，因此能够克服梯度消失（平坦区域）或梯度误导（多局部极小）的困境，适用于更广泛的函数类别。其次，并行架构的实用性：非交互的并行采样器不仅带来了计算上的便利，更重要的是，它们能够独立探索参数空间的不同区域，从而更好地追踪多个潜在的最优解，最后通过性能指标选择最佳结果，这比单个大型采样器更具优势。再次，理论分析的深度与新颖性：研究没有停留在算法描述和实验验证，而是给出了扎实的概率论分析，将优化误差与蒙特卡洛采样误差直接联系起来，并获得了依赖于样本数和维度的收敛速率，这是对现有随机优化理论的重要贡献。最后，实验设计的针对性：所选的三个数值例子分别瞄准了多全局最小值、宽阔平坦区域和高维非光滑非凸问题，精准地验证了算法旨在解决的核心难点，并与现有方法进行了有意义的对比，增强了结果的说服力。此外，文中对抖动核设计的讨论（可融入梯度估计以加速搜索）也为算法的进一步扩展提供了思路。