通过扩散模型启发的平滑机制，揭示了无梯度优化的全局收敛原理。
Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing
- 将采样优化重构成平滑目标上的梯度下降，类比扩散模型得分上升。
- 证明算法可收敛到全局最优附近，且存在覆盖性与最优性权衡。
- 提出新型退火算法DIDA，理论保证全局收敛，实测性能领先。
基于采样的优化（SBO）如交叉熵方法和进化算法在无梯度非凸优化中取得诸多成功，但其收敛性尚不明确。本文从平滑视角建立SBO的非渐近收敛分析：将SBO重构为平滑目标上的梯度下降，类比扩散模型中的噪声条件得分上升。首先，我们对平滑目标进行了景观分析，揭示平滑能扩大全局极小值附近的局部凸区域，帮助逃离局部极小，但引入最优性间隙。基于此，我们建立了SBO算法收敛至全局极小邻域的非渐近保证。进一步提出一种退火型SBO算法——扩散启发双退火（DIDA），理论上可收敛至全局最优。大量数值实验验证了景观结论，并展示了DIDA相较其他无梯度优化方法的卓越性能。最后讨论了结果对扩散模型的启示。
原文摘要 · Abstract (English)
Sampling-based optimization (SBO), like cross-entropy method and evolutionary algorithms, has achieved many successes in solving non-convex problems without gradients, yet its convergence is poorly understood. In this paper, we establish a non-asymptotic convergence analysis for SBO through the lens of smoothing. Specifically, we recast SBO as gradient descent on a smoothed objective, mirroring noise-conditioned score ascent in diffusion models. Our first contribution is a landscape analysis of the smoothed objective, demonstrating how smoothing helps escape local minima and uncovering a fundamental coverage-optimality trade-off: smoothing renders the landscape more benign by enlarging the locally convex region around the global minimizer, but at the cost of introducing an optimality gap. Building on this insight, we establish non-asymptotic convergence guarantees for SBO algorithms to a neighborhood of the global minimizer. Furthermore, we propose an annealed SBO algorithm, Diffusion-Inspired Dual-Annealing (DIDA), which is provably convergent to the global optimum. We conduct extensive numerical experiments to verify our landscape results and also demonstrate the compelling performance of DIDA compared to other gradient-free optimization methods. Lastly, we discuss implications of our results for diffusion models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。