Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing
This work addresses the long-standing lack of convergence guarantees for sampling-based optimization methods, which are widely used in practice, by providing a theoretical framework and a provably convergent algorithm.
The paper provides the first non-asymptotic convergence analysis for sampling-based optimization (SBO) by showing it is equivalent to gradient descent on a smoothed objective, revealing a coverage-optimality trade-off. It proposes an annealed SBO algorithm, DIDA, with provable global convergence and demonstrates superior performance over other gradient-free methods.
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.