Probabilistic Smoothing with Ratio-Monotone Transforms for Global Optimization

Kukyoung Jang, Taehyun Cho, Junrui Zhang, Ping Xu, Kyungjae Lee · 2026

Read Probabilistic Smoothing with Ratio-Monotone Transforms for Global Optimization by Kukyoung Jang, Taehyun Cho, Junrui Zhang, Ping Xu, Kyungjae Lee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27316.txt.

Introduction

Kukyoung Jang and colleagues smooth global optimization problems with flexible symmetric kernels and ratio-based transforms. The smoothed version keeps the same best point, with flat points clustering near the true best at strong amplification. A leave-one-out baseline cuts variance for sure, and tests show tougher behavior with results to match the best.

Catalog record

CREATORKukyoung Jang, Taehyun Cho, Junrui Zhang, Ping Xu, Kyungjae Lee
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95807
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.27316

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Probabilistic Smoothing with Ratio-Monotone Transforms for Global Optimization Kukyoung Jang, Taehyun Cho, Junrui Zhang, Ping Xu, Kyungjae Lee Abstract Probabilistic smoothing is a standard tool for global optimization, but existing methods rely on Gaussian kernels and specific transforms, often resulting in strong hyperparameter sensitivity and limited robustness. We propose a general smoothing framework that combines flexible symmetric unimodal kernels with monotonic ratio-based transformations. Under mild conditions, we show that the smoothed objective preserves the global maximizer and that all stationary points concentrate near the true optimum for sufficiently large amplification, without requiring a decreasing smoothing schedule. We further provide explicit complexity bounds for stochastic gradient ascent and show that a leave-one-out baseline provably reduces variance. Experiments on high-dimensional benchmarks and black-box adversarial attacks demonstrate improved robustness and competitive performance. 1 Introduction Global optimization over a compact domain is a long-standing challenge in machine learning and engineering, especially when the objective function is highly nonconvex, multimodal, or accessible only through black-box evaluations ( 14 ) . In such settings, gradient-based methods are sensitive to initialization and often converge to suboptimal local extrema. A classical approach to global optimization is homotopy-based optimization , also known as continuation or graduated non-convexity methods, which replace the original objective with a smoothed surrogate and gradually recover the original landscape. Among these, Gaussian homotopy , which smooths the objective via Gaussian convolution, has been widely used in vision, inverse problems, and adversarial robustness ( 1 ; 2 ; 17 ; 13 ; 9 ) . Classical Gaussian homotopy relies on an explicit continuation schedule implemented through a multi-loop procedure, leading to substantial computational overhead and sensitivity to hyperparameter tuning. To mitigate this cost, single-loop Gaussian smoothing methods update the optimization variable and smoothing scale simultaneously ( 10 ) . While these methods reduce computational burden, their theoretical guarantees remain local, characterizing convergence only to stationary points of the smoothed objective rather than the global optimum. A major advance within Gaussian smoothing was introduced by 18 , which replaces explicit continuation by applying power or exponential transformations before smoothing. This amplification forces stationary points of the smoothed objective to concentrate near the global maximizer, yielding the first approximate global optimality guarantee in a single-loop Gaussian smoothing setting. However, strong amplification also sharpens curvature and inflates the variance of Monte Carlo gradient estimators, resulting in pronounced sensitivity to the amplification parameter and a clear trade-off between localization strength and optimization stability. In parallel, zeroth-order optimization has shown that Gaussian smoothing enables gradient-free optimization via Monte Carlo score-function estimators ( 6 ; 15 ; 4 ) . While subsequent work generalized the perturbation distribution beyond Gaussian kernels to reduce estimator variance ( 5 ) , these approaches provide guarantees only for local stationarity and do not address global localization. Table 1 : Comparison of representative zeroth-order optimization methods. The table summarizes the evaluation setting (stochastic or deterministic), the type of optimality guarantee (local stationarity or approximate global localization), the required assumptions on the objective f , and the iteration complexity to achieve \|\nabla f\|^{2}\leq\varepsilon . Method Sto. / Det. Optimality Assumptions on f Iteration Complexity RSGF ( 6 ) Stochastic Local f smooth, Lipschitz gradient \mathcal{O}(d/\varepsilon^{2}) ZO-SGD ( 15 ) Stochastic Local f smooth or weakly smooth \mathcal{O}^{a}(M/\varepsilon^{2}) ZO-AdaMM ( 4 ) Stochastic Local f smooth, Lipschitz gradient \mathcal{O}(d^{2}/\varepsilon^{2}) ZO-SLGH ( 10 ) Deterministic Local f smooth, Lipschitz gradient \mathcal{O}^{b}(d/\varepsilon) ZO-SLGH ( 10 ) Stochastic Local f smooth, Lipschitz gradient \mathcal{O}^{b}(d/\varepsilon^{2}) BeS ( 5 ) Stochastic Local f smooth, bounded; biased gradients \mathcal{O}^{a}(M/\varepsilon^{2}) EPGS ( 18 ) Deterministic Approx. global f bounded on compact domain \mathcal{O}(d^{4}/\varepsilon^{2}) Ours Deterministic Approx. global f bounded on compact domain \mathcal{O}\!\left(d^{2}/\varepsilon^{2}\right) Ours with Variance Reduction Deterministic Approx. global f bounded on compact domain \mathcal{O}^{c}\!\left((1-C/2)\,d^{2}/\varepsilon^{2}\right) a The dependence on the dimension d is not explicit. Here, M denotes an upper bound on the second moment of the stochastic gradient estimator, which may implicitly depend on d . b The original results in 10 are stated for \|\nabla f\|\leq\varepsilon ; all bounds are converted to \|\nabla f\|^{2}\leq\varepsilon for consistency. c The constant C depends on the objective function f and algorithmic hyperparameters, but is independent of \varepsilon . While this does not change the asymptotic order of the iteration complexity, the exact bound is strictly smaller since (1-C/2)<1 . This paper revisits probabilistic smoothing from a unified perspective. We view Gaussian homotopy, single-loop smoothing, and amplification-based methods as instances of a broader design space defined by (i) the smoothing distribution and (ii) the transformation applied to objective values prior to smoothing. From this viewpoint, instability arises not from smoothing itself, but from restrictive kernel choices combined with overly aggressive transformations. Motivated by this observation, we propose Probabilistic Smoothing with Ratio-Monotone Transforms (ProMoT) , a single-loop framework that generalizes both components. We allow a broad class of symmetric unimodal smoothing kernels, including heavy-tailed distributions, and introduce ratio-monotone transformations that subsume power and exponential forms. Under mild conditions, we show that the global maximizer of the original objective is preserved and that all stationary points of the smoothed objective concentrate near the true optimum without requiring a decreasing smoothing schedule. Finally, since probabilistic smoothing relies on Monte Carlo gradient estimation, its variance is a fundamental bottleneck. We introduce ProMoT-loo , a variance-reduced variant based on a leave-one-out baseline. We show that this estimator is unbiased and yields a strictly smaller second-moment bound, and we explicitly quantify how this variance reduction improves the iteration-complexity. We summarize our contributions as follows: • We identify explicit conditions on both smoothing distributions and transformations, covering a broad class of symmetric unimodal kernels, including heavy-tailed distributions beyond Gaussian, and introducing ratio-monotone transformations that strictly generalize the power and exponential transforms of 18 . • Under the proposed distributional and transformation conditions, ProMoT achieves the same \varepsilon -approximate global localization guarantees as 18 . • We first introduce a leave-one-out variance reduction scheme for gradient estimation and demonstrate that it strictly improves the iteration-complexity constant. • We show that ProMoT is significantly more robust to hyperparameter choices than existing methods, with strong performance on high-dimensional benchmarks. 2 Related Work Gaussian homotopy methods. Smoothing-based optimization replaces the original objective with a smoothed surrogate, most commonly via Gaussian convolution. Classical Gaussian homotopy or graduated optimization methods rely on a continuation schedule that gradually decreases the smoothing scale to recover the original landscape ( 1 ; 13 ; 9 ) . While effective in practice, such multi-loop procedures incur additional computational overhead and are sensitive to the choice of the smoothing schedule. To mitigate this issue, single-loop Gaussian homotopy (SLGH) methods update the optimization variable and the smoothing scale simultaneously ( 10 ) . Under smoothness and Lipschitz-gradient assumptions on f , deterministic and stochastic variants of SLGH guarantee convergence to stationary points with iteration complexity \mathcal{O}(d/\varepsilon) and \mathcal{O}(d/\varepsilon^{2}) , respectively. As reported in Table 1 , these guarantees are purely local, characterizing convergence to stationary points of the smoothed objective rather than to the global maximizer of f . A further line of work removes explicit continuation schedules by modifying the objective prior to Gaussian smoothing. In particular, exponential and power-based Gaussian smoothing (EPGS) was the first to provide a global optimality guarantee in a Gaussian

Read the complete text