A Simple and Efficient Smoothing Method for Faster Optimization and Local Exploration

Kevin Scaman, Ludovic Dos Santos, Merwan Barlier, Igor ColinNeurIPS 2020 · OpenReview

Introduction

In machine learning, optimizing "messy" functions—those that are non-smooth (having sharp kinks) or non-convex (having many local traps)—is a notoriously difficult challenge. Standard gradient descent often struggles to navigate these complex landscapes.

To address this, researchers frequently use smoothing techniques, which replace the messy objective function with a "blurry" version that is easier to traverse. Historically, there have been two primary approaches, each with a significant trade-off:

  1. Randomized Smoothing (RS): This method is computationally simple (often just adding Gaussian noise), but in high-dimensional spaces ($d$), the smoothed version remains quite far from the original function, suffering an approximation error proportional to $\sqrt{d}$.
  2. Moreau Envelope (ME): This approach is highly accurate and its performance is independent of dimensionality. However, it requires solving a separate optimization problem just to calculate a single gradient, making it prohibitively expensive for large-scale AI applications.

This paper introduces Bend, Mix and Release (BMR), a novel smoothing technique that bridges the gap between the computational simplicity of RS and the theoretical superiority of ME. BMR achieves a $\sqrt{d}$ multiplicative improvement in approximation error over RS in high-dimensional spaces while remaining significantly easier to compute than the ME.

The Bend, Mix and Release (BMR) Method

The BMR method derives its name from a three-step mathematical transformation applied to the objective function $f$:

  1. Bend: The function values are transformed using an exponential-like function ($\phi_\alpha$) to disproportionately weight lower (better) values.
  2. Mix: A Gaussian filter (convolution) is applied. This is the "blurring" step that evaluates the neighborhood of a given point.
  3. Release: The inverse transformation ($\phi_\alpha^{-1}$) is applied to return the values to their original scale.

Mathematically, the smoothed function is defined as: $f_{\gamma,\alpha}(x) = \phi_\alpha^{-1} (\mathbb{E}[\phi_\alpha(f(x + \gamma X))])$.

Effect of BMR on various functions, showing how the parameter alpha interpolates between Randomized Smoothing and the Moreau Envelope.

By adjusting the parameter $\alpha$, BMR effectively acts as a slider. When $\alpha$ is near zero, the method behaves like standard Randomized Smoothing. As $\alpha$ increases, the smoothed function converges toward the Moreau Envelope. To calculate gradients efficiently, the authors employ Importance Sampling. Instead of uniformly averaging gradients in a neighborhood like RS, BMR takes a weighted average that favors points where the function value is lower.

Key Insights and Results

The authors validated BMR using synthetic non-smooth and non-convex functions designed to mimic the treacherous landscapes of deep learning (such as ReLU-based losses and highly oscillatory Fourier functions).

Breaking the Dimension Curse The most significant theoretical insight is BMR's ability to reduce approximation error by a factor of $\sqrt{d}$. In modern machine learning, where the number of parameters ($d$) can easily reach into the millions, this represents a massive theoretical gain over traditional randomized smoothing.

Superior Local Exploration In non-convex optimization, BMR does more than just blur the landscape; it effectively "widens" the basin of attraction for deep local minima. During experiments on highly non-convex Fourier functions, BMR reached significantly better local optima than RS. The biased sampling allows the optimizer to "feel" the direction of deeper valleys, helping it navigate "cracks and crevices" even when the immediate local gradient is misleading.

Robustness and Convergence Empirically, RS proved highly sensitive to the amount of noise ($\gamma$) applied; too much noise prevented it from finding the true minimum. BMR, even with a small $\alpha$, reached the optimum much more reliably. Furthermore, the authors proved that BMR-based distributed optimization converges at a rate that avoids the $d^{1/4}$ penalty typically associated with distributed randomized smoothing.

Limitations and Future Work

While BMR offers a powerful new tool for optimization, it comes with specific trade-offs:

  • Gradient Bias: The gradient estimator for BMR is inherently biased. While the authors quantify this bias, increasing the "bending" parameter $\alpha$ requires more samples ($K$) to obtain an accurate direction.
  • Computational Overhead: Although vastly cheaper than computing the Moreau Envelope, BMR is still more computationally expensive than standard Stochastic Gradient Descent (SGD) because it requires multiple function evaluations per step to estimate the biased gradient.
  • Scaling to Deep Learning: The proof-of-concept experiments were limited to 10-dimensional synthetic problems. While the underlying theory suggests BMR should scale effectively to high-dimensional neural networks, practical implementation details—such as how to dynamically choose $\alpha$ and $\gamma$ during training—remain an open challenge for future research.

Summary updated

Abstract

This work proposes a novel smoothing method, called Bend, Mix and Release (BMR), that extends two well-known smooth approximations of the convex optimization literature: randomized smoothing and the Moreau envelope. The BMR smoothing method allows to trade-off between the computational simplicity of randomized smoothing (RS) and the approximation efficiency of the Moreau envelope (ME). More specifically, we show that BMR achieves up to a $\sqrt{d}$ multiplicative improvement compared to the approximation error of RS, where $d$ is the dimension of the search space, while being less computation intensive than the ME. For non-convex objectives, BMR also has the desirable property to widen local minima, allowing optimization methods to reach small cracks and crevices of extremely irregular and non-convex functions, while being well-suited to a distributed setting. This novel smoothing method is then used to improve first-order non-smooth optimization (both convex and non-convex) by allowing for a local exploration of the search space. More specifically, our analysis sheds light on the similarities between evolution strategies and BMR, creating a link between exploration strategies of zeroth-order methods and the regularity of first-order optimization problems. Finally, we evidence the impact of BMR through synthetic experiments.
BibTeX
@inproceedings{scaman2020simple,
  author = {Kevin Scaman and Ludovic Dos Santos and Merwan Barlier and Igor Colin},
  title = {{A Simple and Efficient Smoothing Method for Faster Optimization and Local Exploration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=IVZJgun_mLx},
}
Figure