Technical Summary: Probabilistic Smoothing with Ratio-Monotone Transforms for Global Optimization

Problem Statement

Global optimization over compact domains remains a significant challenge in machine learning and engineering, particularly when objective functions are highly nonconvex, multimodal, or accessible only via black-box evaluations. In such settings, standard gradient-based methods are prone to converging to suboptimal local extrema due to sensitivity to initialization.

Existing probabilistic smoothing approaches, such as Gaussian homotopy, attempt to mitigate this by replacing the original objective with a smoothed surrogate. However, classical methods rely on explicit continuation schedules (multi-loop procedures) that incur substantial computational overhead and hyperparameter sensitivity. Recent single-loop methods that apply amplification (e.g., power or exponential transforms) before smoothing have shown promise in achieving approximate global optimality guarantees. Yet, these approaches often suffer from a trade-off between localization strength and optimization stability: strong amplification sharpens curvature and inflates the variance of Monte Carlo gradient estimators, leading to pronounced sensitivity to parameter tuning. Furthermore, many existing methods are restricted to Gaussian kernels and specific transformation classes, limiting their robustness in high-dimensional or heterogeneous landscapes.

Methodology

The authors propose ProMoT (Probabilistic Smoothing with Ratio-Monotone Transforms), a unified single-loop framework that generalizes both the smoothing distribution and the transformation applied to the objective.

1. Generalized Smoothing Framework

The framework defines a smoothed objective $G_{\theta, \sigma}(\mu)$ by combining two flexible components:

• Flexible Kernels: Instead of restricting the smoothing distribution to Gaussians, ProMoT allows for a broad class of symmetric unimodal kernels, including heavy-tailed distributions (e.g., Student-t, Logistic, Hyperbolic Secant). The kernel is defined as a product density $p_{\mu, \sigma}(x) = \prod_{i=1}^d \sigma^{-1} p((x_i - \mu_i)/\sigma)$, which can be extended to anisotropic smoothing via diagonal scale matrices.
• Ratio-Monotone Transforms: The objective values are transformed via a function $g(\theta, \cdot)$ before smoothing. The authors introduce the class of ratio-monotone transformations, which are strictly increasing in the objective value and strictly increasing in the ratio $g(\theta, a)/g(\theta, b)$ for $a > b$. This class subsumes power transforms ($y^\theta$) and exponential transforms ($e^{\theta y}$) while allowing for more moderate forms (e.g., softplus, sigmoid-power) that reduce variance.

The smoothed objective is defined as:
$$G_{\theta, \sigma}(\mu) := \mathbb{E}_{X \sim p_{\mu, \sigma}} [g(\theta, f(X)); S]$$

2. Optimization and Variance Reduction

Optimization is performed via stochastic gradient ascent using a score-function estimator, which does not require derivatives of the original objective $f$.

• Gradient Estimation: The gradient is estimated using Monte Carlo sampling: $\hat{\nabla}_\mu G_{\theta, \sigma}(\mu) = \frac{1}{B} \sum h(X^{(k)}) S(X^{(k)})$, where $S(x)$ is the score function.
• ProMoT-loo: To address the variance inflation caused by amplification, the authors introduce ProMoT-loo, a variance-reduced variant using a leave-one-out (LOO) baseline. This estimator centers each sample's contribution using information from the remaining samples in the mini-batch, preserving unbiasedness while strictly reducing the second-moment bound of the gradient estimator.

Key Contributions

1. Unified Theoretical Framework: The paper establishes explicit conditions on both smoothing distributions (symmetry, unimodality, regularity) and transformations (monotonicity, ratio-monotonicity). This generalizes prior work, allowing for heavy-tailed kernels and a broader class of transforms beyond simple power/exponential forms.
2. Global Localization Guarantees: Under mild conditions, the authors prove that for sufficiently large amplification parameters $\theta$, the global maximizer of the original objective is preserved. Crucially, they show that all stationary points of the smoothed objective concentrate within a $\delta$-neighborhood of the true global optimum, without requiring a decreasing smoothing schedule.
3. Complexity Analysis with Variance Reduction: The paper derives explicit iteration complexity bounds for stochastic gradient ascent. A significant theoretical contribution is the quantification of how the LOO baseline improves the complexity constant. The analysis shows that the iteration complexity is strictly improved by a factor of $(1 - C_{\theta, \Sigma}/2)$ compared to baseline-free estimators, without altering the asymptotic convergence rate.
4. Robustness to Hyperparameters: Theoretical and empirical results demonstrate that the combination of flexible kernels and ratio-monotone transforms yields a landscape that is less sensitive to hyperparameter choices (specifically the amplification parameter $\theta$) compared to existing Gaussian-based amplification methods.

Experimental Results

The authors evaluated ProMoT and ProMoT-loo on two categories of tasks:

• Canonical High-Dimensional Benchmarks: Experiments were conducted on Ackley, Rosenbrock, and Griewank functions with dimension $d=500$. ProMoT-loo consistently achieved the lowest Mean Squared Error (MSE) and best objective values compared to baselines including EPGS, RSGF, ZO-SGD, ZO-AdaMM, ZO-SLGH, and CMA-ES. The results highlight that heavy-tailed kernels enable more effective global exploration in high dimensions compared to Gaussian kernels.
• Black-Box Targeted Adversarial Attacks: The methods were tested on CIFAR-10 ($d=3,072$) and VitalDB ($d=42$) datasets. ProMoT-loo achieved high attack success rates while generating perturbations with the smallest $L_\infty$ norms (indicating higher imperceptibility) compared to most baselines. Notably, on VitalDB, it achieved a ~5% reduction in mean $L_\infty$ compared to CMA-ES while maintaining comparable reconstruction quality.

Significance and Claims

The paper claims that ProMoT offers a more robust and theoretically grounded approach to global optimization in black-box settings. By decoupling the smoothing kernel from the amplification transform, the method avoids the instability associated with aggressive Gaussian amplification. The introduction of the leave-one-out baseline provides the first explicit iteration-complexity analysis showing that variance reduction directly improves the convergence constant in probabilistic smoothing. The authors position this work as a generalization of existing single-loop smoothing methods, offering improved performance on high-dimensional benchmarks and real-world adversarial attack scenarios without the computational overhead of multi-loop continuation schedules.