






















Abstract: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.
| Comments: | 57 pages, 5 figures |
| Subjects: | Machine Learning (cs.LG) |
| MSC classes: | 90C26, 68T07 |
| Cite as: | arXiv:2605.16520 [cs.LG] |
| (or arXiv:2605.16520v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.16520 arXiv-issued DOI via DataCite (pending registration) |
From: Zeji Yi [view email]
[v1]
Fri, 15 May 2026 18:14:38 UTC (1,394 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。