Revisiting Randomized Smoothing: Nonsmooth Nonconvex Optimization Beyond Global Lipschitz Continuity

Jingfan Xia, Zhenwei Lin, MengChu ZhouarXiv 2025 · DOI · arXiv

In the world of machine learning and engineering, we often encounter "messy" functions—those that are both nonsmooth (have sharp kinks) and nonconvex (have multiple valleys). To optimize these without direct access to gradients, researchers often turn to Randomized Smoothing (RS). By adding a bit of noise to the input and averaging the results, we turn a jagged function into a smooth one that we can navigate using only function evaluations (zeroth-order optimization).

However, there’s a catch: almost all existing theory for RS assumes the function is Globally Lipschitz Continuous. In plain English, this means the function's "steepness" is capped by a single constant everywhere in space. In reality, many functions—like simple quadratics or exponentials—get steeper the further you go. This paper finally bridges that gap.

TL;DR

This paper extends the theory of randomized smoothing to functions that lack global Lipschitz continuity by introducing a flexible "subgradient growth condition." The authors propose new algorithms that achieve near-optimal convergence rates for nonsmooth, nonconvex problems, even when the function's steepness grows significantly as you move through the search space.

What Problem Does This Paper Address?

The standard theoretical "safety net" for optimization is the Global Lipschitz assumption. If your function is $f(x) = x^2$, it isn't globally Lipschitz because the slope keeps increasing as $x$ grows. Most randomized smoothing proofs break down here.

In practical applications like black-box adversarial attacks on neural networks or fine-tuning large language models, we often don't have gradients and can't guarantee global Lipschitzness. This creates a disconnect between theory (which assumes a constant slope) and practice (where slopes vary wildly). The authors tackle two main challenges:

  1. How do we mathematically model functions where the "local steepness" changes?
  2. Can we design algorithms that adapt their step sizes to this changing landscape without getting lost or diverging?

Methods

The authors introduce a new $(\alpha, \beta)$ subgradient growth condition. Instead of one global constant, they use a function $\alpha(x)$ to bound the local steepness and a function $\beta$ to describe how that steepness changes. This covers a much broader class of functions, including polynomials and exponentials.

They propose three main algorithms:

  • RS-GF (Randomized Smoothing Gradient-Free): A foundational method using an adaptive step size based on local growth.
  • RS-NGF (Normalized Gradient-Free): By normalizing the gradient estimate, they reduce the algorithm's sensitivity to the dimension ($d$) of the problem.
  • RS-NVRGF (Normalized Variance Reduction Gradient-Free): This version incorporates variance reduction techniques (similar to SPIDER or SARAH) to achieve the fastest possible convergence.

The goal of these algorithms is to find a $(\delta, \epsilon)$-Goldstein stationary point—a standard measure of "success" in nonsmooth optimization where we look for a point where the average gradient in a small neighborhood ($\delta$) is nearly zero ($\epsilon$).

Datasets

The authors validated their approach using:

  1. Simulation Experiments: Synthetic nonlinear optimization problems using high-order polynomials ($x^5$) and exponential growth functions ($\exp(x^3)$) specifically designed to violate the global Lipschitz assumption.
  2. Black-box Adversarial Attacks: Attacking a pre-trained ResNet model on the CIFAR-10 dataset. Here, the "function" being optimized is the loss of the image classifier, which is notoriously nonsmooth and nonconvex.

Key Insights and Ideas

  • Smoothing Still Works on "Explosive" Functions: The paper proves that even if a function grows very fast (like an exponential), its smoothed version still behaves well enough to be optimized, provided the step size is chosen carefully.
  • Adaptive Step Sizes are Mandatory: You cannot use a constant step size if the function's steepness varies. The authors provide a formula for a "locally aware" step size that prevents the algorithm from overshooting in steep regions.
  • Normalization is a Dimension-Killer: In high-dimensional spaces, gradient estimates can become very noisy. Normalizing the gradient helps the algorithm focus on the direction of the descent rather than the potentially massive magnitude of the estimated gradient, leading to better scaling with the number of variables ($d$).

Key Results

  • Optimal Complexity: Their most advanced algorithm, RS-NVRGF, achieves a sample complexity of $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-3})$. This is significant because it matches the best-known bounds for the easier global Lipschitz case, proving that we don't have to sacrifice much efficiency to handle more complex functions.
  • Superior Attacks: In the CIFAR-10 adversarial attack experiments, the proposed RS-NGF method achieved the highest test loss (meaning a more successful attack) and the lowest test accuracy on the target model compared to standard baselines like VRGF.
  • Stability: The proposed methods showed much lower variance in performance across different runs, suggesting they are more robust to the random noise inherent in zeroth-order optimization.

Limitations and Future Work

The primary limitation is that the current algorithms require some prior knowledge (or a good estimate) of the growth parameters $\alpha$ and $\beta$ to set the step size correctly. If these are unknown, the user might still need to perform a grid search for hyperparameters.

The authors suggest that a promising future direction is the development of parameter-free versions of these algorithms that can automatically sense the local growth rate of the function and adjust on the fly without manual tuning.

Summary updated

Abstract

Randomized smoothing is a widely adopted technique for optimizing nonsmooth objective functions. However, its efficiency analysis typically relies on global Lipschitz continuity, a condition rarely met in practical applications. To address this limitation, we introduce a new subgradient growth condition that naturally encompasses a wide range of locally Lipschitz functions, with the classical global Lipschitz function as a special case. Under this milder condition, we prove that randomized smoothing yields a differentiable function that satisfies certain generalized smoothness properties. To optimize such functions, we propose novel randomized smoothing gradient algorithms that, with high probability, converge to $(δ, ε)$-Goldstein stationary points and achieve a sample complexity of $\tilde{\mathcal{O}}(d^{5/2}δ^{-1}ε^{-4})$. By incorporating variance reduction techniques, we further improve the sample complexity to $\tilde{\mathcal{O}}(d^{3/2}δ^{-1}ε^{-3})$, matching the optimal $ε$-bound under the global Lipschitz assumption, up to a logarithmic factor. Experimental results validate the effectiveness of our proposed algorithms.
BibTeX
@misc{xia2025revisiting,
  author = {Jingfan Xia and Zhenwei Lin and MengChu Zhou},
  title = {{Revisiting Randomized Smoothing: Nonsmooth Nonconvex Optimization Beyond Global Lipschitz Continuity}},
  year = {2025},
  eprint = {2508.13496},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.13496},
  howpublished = {arXiv},
}
Figure