# Gaussian smoothing gradient descent for minimizing high-dimensional non-
convex functions

Andrew Starnes Behavioral Research Learning Lab, Lirio AI Research, Lirio,
Knoxville, TN<EMAIL_ADDRESS><EMAIL_ADDRESS>cwebster@lirio.com). Anton Dereventsov11footnotemark: 1 Clayton
Webster11footnotemark: 1

###### Abstract

This work analyzes the convergence of a class of smoothing-based gradient
descent methods when applied to high-dimensional non-convex optimization
problems. In particular, Gaussian smoothing is employed to define a nonlocal
gradient that reduces high-frequency noise, small variations, and rapid
fluctuations in the computation of the descent directions while preserving the
structure and features of the loss landscape. The resulting Gaussian smoothing
gradient descent (GSmoothGD) approach can facilitate gradient descent in
navigating away from and avoiding local minima with increased ease, thereby
substantially enhancing its overall performance when applied to non-convex
optimization problems. This work also provides rigorous theoretical error
estimates on the rate of convergence of GSmoothGD iterates. These estimates
exemplify the impact of underlying function convexity, smoothness, input
dimension, and the Gaussian smoothing radius. To combat the curse of
dimensionality, we numerically approximate the $d$-dimensional GSmoothGD
nonlocal gradient using Monte Carlo (MC) sampling and provide a theory in
which the iterates converge regardless of the function smoothness and
dimension. Finally, we present several strategies to update the smoothing
parameter aimed at diminishing the impact of local minima, thereby rendering
the attainment of global minima more achievable. Computational evidence
complements the present theory and shows the effectiveness of the MC-GSmoothGD
method compared to other smoothing-based algorithms, momentum-based
approaches, and classical gradient-based algorithms from numerical
optimization.

Key words.  Gaussian smoothing, gradient-free optimization, high-dimensional
optimization, non-convex optimization, black-box optimization, Monte Carlo
integration

##  1\. Introduction

Our aim is to solve for the global extrema of a high-dimensional non-convex
objective function $f:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$. To achieve
this goal we consider the unconstrained optimization problem, parameterized by
a $d$-dimensional vector $\bm{x}=(x_{1},\ldots,x_{d})\in{\mathbb{R}}^{d}$,
i.e.,

$\min_{\bm{x}\in{\mathbb{R}}^{d}}f(\bm{x}).$ (1.1)

This challenging setting appears in a myriad of applications including:
training neural networks and large-scale language models [4, 47]; object
detection and feature learning (see, e.g., [57] and the references therein);
portfolio optimization and option pricing [49, 18]; as well as material, drug,
and structural design [27, 52].

Consequently, standard gradient-based optimization (GD) methods prove
inefficient due to the abundance of local minima that can ensnare the
optimization process. Thus (1.1) is typically solved with a derivative- or
gradient-free optimization approach [11, 36, 42, 25, 28, 44, 6, 16, 15, 40, 8,
53, 54]. As such, throughout this effort we also assume that $f(\bm{x})$ is
only available by virtue of function evaluations, and the gradient $\nabla
f(\bm{x})$ is generally inaccessible, either because it is undefined, rapidly
fluctuating, noisy, or too difficult to compute.

Of particular interest to this effort is a class of such techniques known as
Gaussian smoothing (GS), which involves a convolution operation that
integrates the product of a given target function and a Gaussian kernel over
all possible shifts. The amount of smoothing is controlled by the standard
deviation of the Gaussian distribution, with larger values resulting in
broader and more pronounced smoothing effects, while smaller values preserve
more details of the function. In particular, similar to the works [37, 36, 8],
we introduce the notion of GS of the objective function $f(\bm{x})$ in (1.1).
Let $\sigma>0$ be a global smoothing parameter and denote by
$f_{\sigma}(\bm{x})$ the Gaussian smoothing of $f$ with radius $\sigma$, i.e.,

$f_{\sigma}(\bm{x})=\frac{1}{\pi^{\nicefrac{{d}}{{2}}}}\int_{\mathbb{R}^{d}}f(\bm{x}+\sigma\bm{u})\,e^{-\|\bm{u}\|_{2}^{2}}\,\mathrm{d}\bm{u}=\mathbb{E}_{\bm{u}\sim\mathcal{N}(0,\frac{1}{2}\mathbb{I}_{d})}\big{[}f(\bm{x}+\sigma\sqrt{2}\bm{u})\big{]},$
(1.2)

where $\mathcal{N}(0,\mathbb{I}_{d})$ is a standard $d$-dimensional Gaussian
distribution. We remark that $f_{\sigma}(\bm{x})$ preserves important features
and structure of the objective function including, e.g., convexity, $L$
smoothness, and is always differential even when $f(\bm{x})$ is not for
$\sigma>0$.

We exploit the gradient of $f_{\sigma}(\bm{x})$, given by

$\nabla
f_{\sigma}(\bm{x})=\frac{2}{\sigma\pi^{\nicefrac{{d}}{{2}}}}\int_{\mathbb{R}^{d}}\bm{u}f(\bm{x}+\sigma\bm{u})\,e^{-\|\bm{u}\|_{2}^{2}}\,\mathrm{d}\bm{u}=\frac{2\sqrt{2}}{\sigma}\,\mathbb{E}_{\bm{u}\sim\mathcal{N}(0,\frac{1}{2}\mathbb{I}_{d})}\big{[}\bm{u}f(\bm{x}+\sigma\sqrt{2}\bm{u})\big{]},$
(1.3)

to replace the standard local gradient with a nonlocal approximation, which
aims to reduce high-frequency noise, small variations, and rapid fluctuations
in the computation of the descent directions. The resulting Gaussian smoothing
gradient descent (GSmoothGD), described by Algorithm 1, aims to solve (1.1) by
replacing it with the following $(d+1)$-dimensional surrogate problem

$\min_{(\sigma,\bm{x})\in\mathbb{R}^{+}\times{\mathbb{R}}^{d}}f_{\sigma}(\bm{x}),$
(1.4)

such that $\bm{x}^{\star}_{\sigma}\rightarrow\bm{x}^{\star}$ as
$\sigma\rightarrow 0$ with

$\bm{x}^{\star}=\operatorname*{argmin}_{\bm{x}\in\mathbb{R}^{d}}f(\bm{x})\quad\text{
and
}\quad\bm{x}^{\star}_{\sigma}=\operatorname*{argmin}_{\bm{x}\in\mathbb{R}^{d}}f_{\sigma}(\bm{x}).$
(1.5)

The GSmoothGD approach can facilitate gradient descent in navigating away from
and avoiding local minima with increased ease, thereby substantially enhancing
the overall performance when applied to non-convex optimization problems. As
such, this work also provides rigorous theoretical error estimates on the
GSmoothGD iterates rate of convergence, that exemplify the impact of
underlying function convexity, smoothness, and input dimension, as well as the
Gaussian smoothing radius. As far as we are aware, this is the first detailed
analysis of convergence rates of GSmoothGD for general non-convex, $L$-smooth
problems (1.1). In addition, to provide a better theoretical understanding
GSmoothGD we also rigorously estimate the relationship between
$\bm{x}^{\star}$ and $\bm{x}^{\star}_{\sigma}$ for convex, $L$-smooth
functions.

Algorithm 1 Gaussian smoothing gradient descent (GSmoothGD)

1:$f:\mathbb{R}^{d}\to\mathbb{R}$, $(\sigma_{k})_{k=1}^{K}$,
$x_{0}\in\mathbb{R}^{d}$, $t>0$

2:for $k=1\to K$ do

3: $x_{k}=x_{k-1}-t\nabla f_{\sigma_{k}}(x_{k-1})$

4:end for

Numerical estimation of the search directions is an additional problem due to
the complex nature of objective functions in high-dimensional spaces. A
popular set of approaches to compute the gradient of a Gaussian smoothed
function are known as evolutionary strategies (ES) [44, 14, 15, 26, 6], which
are a class of algorithms inspired by natural evolution [51]. Recently,
interest in ES methods has been reinvigorated and has become a popular
approach in several machine learning problems such as training neural networks
[46, 35, 7] and reinforcement learning [55, 22, 45, 44]. Covariance matrix
adaptation evolution strategy (CMA-ES) is a popular evolutionary algorithm
used for continuous optimization problems. Several important papers have
contributed to the understanding of the convergence properties of CMA-ES [15,
14, 16]. These works explore the convergence theory of CMA-ES under various
settings, including scenarios with limited function evaluations, large
population sizes, and even in the presence of noise, which is often
encountered in real-world optimization problems. As such, these methods are
particularly useful when solving optimization problems related to nonconvex
and nonsmooth objective functions. More recently, another class of ES
strategies has emerged, known as directional Gaussian smoothing (DGS) [55, 50,
54, 8, 53], that specifically averages the original objective function along
$d$ orthogonal directions. As such, the representation of the partial
derivatives of the smoothed function along these directions can be reduced to
one-dimensional integrals, as opposed to the more complex $d$-dimensional
integrals used in standard ES methods. Consequently, one can approximate the
averaged partial derivatives using deterministic [55, 50, 54] or adaptive [8]
Gauss-Hermite quadrature rules.

However, for increased accuracy, both ES and DGS approaches must expand the
size of the domain, and expend more effort approximating either the
$d$-dimensional integral or the integral within each individual direction. The
resulting explosion in computational effort is a symptom of the curse of
dimensionality. In order to combat this grand challenge, similar to [20, 31],
we numerically approximate the $d$-dimensional GSmoothGD nonlocal gradient
(1.3) with the use of Monte Carlo (MC) sampling (see, e.g., [12, 13, 3] and
the references therein) and provide a theory in which the iterates converge
regardless of the function smoothness and dimension. To the best of our
knowledge, this constitutes the inaugural in-depth analysis of MC-GSmoothGD
convergence rates in the context of high-dimensional non-convex problems.
Moreover, this work also addresses the calculation of the smoothing parameter
$\sigma$, with the details described in Section 4.2.

###  1.1. Paper organization

The paper is organized as follows. The remainder of Section 1 is focused on
describing an important connection between Gaussian smoothing (or homotopy
methods) and a class of partial differential equations (PDEs) known as the
heat equation [10], as well as providing an overview of previous works.
Section 2 introduces the notation and nomenclature used throughout. In
Sections 3.2 and 3.2, we first describe the simplicity of GSmoothGD and then
provide the first complete convergence analysis of such approaches for both
high-dimensional convex and non-convex functions. In Section 3.3, we provide a
thorough analysis of the relationship between minimizers and smoothed
minimizers. In Section 4, we describe various numerical approximation schemes
for Gaussian smoothing, including MC, variance of the gradient of the smoothed
function, and Gaussian homotopy. We also discuss the various strategies
employed to appropriately update the smoothing parameter $\sigma$. In Section
5, we numerically compare Gaussian smoothing with other smoothing-based
algorithms, as well as other conventional methods such as momentum-based
approaches, and classical gradient-based algorithms from numerical
optimization. In Section 6, we provide several concluding remarks and possible
future directions we are excited to pursue. Finally, Appendix A contains the
proofs of the background results from Section 2 and Appendix B contains the
proofs of the main convergence results from Sections 3.1, 3.2, 4.1.

###  1.2. Related works

Gaussian smoothing has been studied across many disciplines, which creates two
almost distinct paths of research. We divide the work that has been done so
far into these two areas of research, the first being from the perspective of
evolutionary strategies and the second being motivated by homotopy
continuation and partial differential equations (PDEs).

### Connections to evolutionary strategies

Motivated by [8], this effort can appropriately be classified in a category of
methods known as smoothing-based and even gradient-free optimization. The
development and analysis of such techniques are extensive, see, e.g., [34, 33,
29, 17, 32, 31, 30, 21, 9, 56, 20, 37, 36] and the references therein.
However, to date, this is the first detailed analysis of convergence rates of
GSmoothGD for general non-convex problems, given by (1.1), has been
unavailable in the current and existing literature. Several works have
enriched our comprehension of the convergence characteristics of CMA-ES, as
evidenced by studies such as [15, 14, 16, 44, 26, 6, 7]. These investigations
delve into the convergence theory of CMA-ES across a spectrum of scenarios,
encompassing limited function evaluations, large population sizes, and the
incorporation of noise, a common real-world optimization challenge. As a
result, these methodologies offer significant utility in the optimization of
non-convex and non-smooth objective functions.

The recent effort [50] investigates the convergence of directional Gaussian
smoothing (DGS), first introduced in [55, 54], in the very specific case when
the objective function consists of a convex component perturbed by oscillating
noise. The theory demonstrates that the DGS iterations exhibit exponential
convergence toward a narrowed region around the solution for strongly convex
functions. The extent of this region is defined by the wavelength of the
noise. Furthermore, they establish a connection between the optimal values of
the Gaussian smoothing radius and the noise wavelength. This connection
validates the benefits of employing a moderate or large smoothing radius in
this particular situation.

### Connections to Gaussian homotopy methods and PDEs

Recall that the heat equation is the initial value problem given by

$\left\\{\begin{array}[]{ll}u_{t}=\epsilon\Delta
u&(\bm{x},t)\in\mathbb{R}^{d}\times(0,\infty)\\\
u(\bm{x},0)=f(\bm{x})&\bm{x}\in\mathbb{R}^{d}\end{array}\right.$ (1.6)

The fundamental solution to the heat equation (HE-PDE) is given by

$u(\bm{x},t)=\mathbb{E}_{\bm{u}\sim\mathcal{N}(0,2\epsilon^{2}t\mathbb{I}_{d})}[f(\bm{u})].$
(1.7)

This means that the smoothing function $f_{2\sqrt{t}}(\bm{x})$ is a solution
to the heat equation as well. Explicitly, we have

$\frac{\partial}{\partial\sigma}f_{\sigma}(\bm{x})=\frac{\sigma}{2}\Delta_{\bm{x}}f_{\sigma}(\bm{x}).$
(1.8)

In other words, using the heat equation smoothes the initial value function.

The heat equation is a particular example of the viscous Hamilton-Jacobi PDE
which is given by

$\left\\{\begin{array}[]{ll}u_{t}=\epsilon\Delta u-H(\nabla
u)&(\bm{x},t)\in\mathbb{R}^{d}\times(0,\infty)\\\
u(\bm{x},0)=f(\bm{x})&\bm{x}\in\mathbb{R}^{d}\end{array}\right.$ (1.9)

In particular, when $H(\cdot)=0$ we recover the heat equation. In the case
that $\epsilon=0$, we have the standard Hamilton-Jacobi PDE (HJ-PDE), which
can be used to smooth functions as well. HJ-smoothing attempts to remove
narrow minima from $f$ regardless of depth, whereas HE-smoothing attempts to
remove shallow minima regardless of width.

Motivated by [43] and statistical physics, the effort [1] introduces
optimizing via local entropy loss, which favors minima with low eigenvalues in
Hessian (and hence wider minima). The authors also introduce Entropy-SGD and
compare numerical results on image classification problems (using RNNs and
CNNs) with heat equation smoothing, concluding this approach is very different
from local entropy and can introduce an artificial minimum between two nearby
sharp valleys which is detrimental to generalization. However, these
artificial minima do not persist when $\sigma\to 0$ (i.e., when finding the
minimum of $f$). For analysis of how the HE-smoothed minimizers relate to the
original minimizers, see Section 3.3. Furthermore, the work [5] shows that the
local entropy loss is a solution to the viscous HJ-PDE, and that viscous HJ-
PDE smoothing has much better empirical performance as well as improved
(theoretical) convergence rates compared to GD.

Inspired by [5], the effort [41] introduces Laplacian smoothing (LSGD), see
Algorithm 2, as $x_{k+1}=x_{k}-t_{k}A^{-1}_{\sigma}\nabla f_{i_{k}}(x_{k})$,
where $A_{\sigma}$ is the graph Laplacian of model weight graph and $\nabla
f_{i_{k}}$ is the SGD gradient using observation $i_{k}$ (that is, HJ-PDE with
$H(\cdot)=\frac{1}{2}\langle\cdot,A^{-1}_{\sigma}\cdot\rangle$). Modified
Laplacian smoothing gradient descent (mLSGD) is given in [24] where the
smoothing parameter is allowed to change between iterations, denoted by
$\sigma(k)$. The authors show that this approach is less susceptible to saddle
points and converges as fast as (and anecdotally faster than) GD. We remark
that there is no mathematical reason that the matrix, denoted $A_{\sigma(k)}$
for mLSGD, needs to be the graph Laplacian, in fact, any symmetric, positive
definite matrix will satisfy the HJ-PDE described in [41].

Algorithm 2 LSGD

1:$f:\mathbb{R}^{d}\to\mathbb{R}$, $\sigma\geq 0$, $x_{0}\in\mathbb{R}^{d}$,
$t>0$

2:for $k=1\to K$ do

3: $x_{k}=x_{k-1}-tA_{\sigma}^{-1}\left(\nabla f(x_{k-1})\right)$

4:end for

One major benefit of using HE-smoothing is that we do not need access to the
gradient of $f$ and instead can just use function evaluations to approximate
the gradient of $f_{\sigma}$. This cannot be done with HJ-smoothing, which is
why $\nabla f(x)$ is required for Algorithm 2.

In addition to the connection with PDEs, smoothing can be motivated from
optimization via homotopy continuation.111In this context, this method could
also be called Graduated Non-Convexity (see [2]). Optimization via homotopy
continuation, parameterized by $t$, creates a homotopy between the original
$f$ ($t=0$) and a smooth function ($t=1$). The method finds the minimizers of
the homotopy at $t$, starting at $t=1$ and iteratively reduces $t$ to 0. That
is, it starts by finding the minimizers of a nice function and repeats this
with less smooth functions until it arrives at the original function.
Explicitly, let $h:\mathbb{R}^{d}\times[0,T]\to\mathbb{R}$ where
$h(x,0)=h(x)$, $h(x,T)$ is “smooth”, and $h(x,t)$ is continuously
differentiable for $x\in\mathbb{R}^{d}$ and $t>0$. Denote the path of the
minimizer by $x(t)$, where for $t\geq 0$, $x(t)$ satisfies $\nabla
g(x(t),t)=0$ and is continuous. Obviously, such a path may not exist.
Furthermore, there’s not always a clear choice for how to construct the
homotopy. When the homotopy is created by convolving the function with a
Gaussian kernel (where $\sigma$ both acts as $t$ and controls the variance),
this method is called Gaussian Homotopy Continuation (see Algorithm 3). In
[31], they show that evolving the objective function using a Gaussian homotopy
provides optimal convexification of the function.

Algorithm 3 Optimization by Gaussian Homotopy Continuation

1:Input: $f:\mathbb{R}^{d}\to\mathbb{R}$, $\\{\sigma_{k}\\}_{k=1}^{K}$ s.t.
$0<\sigma_{k+1}<\sigma_{k}$, $x_{0}\in\mathbb{R}^{d}$

2:for $k=1\to K$ do

3: $x_{k}=$ local minimizer of $f_{\sigma_{k}}(x)$ initialized at $x_{k-1}$

4:end for

5:Output: $x_{K}$

In practice, this method leads to an algorithm with two loops, an outer loop
that decreases $\sigma_{k}$ and an inner loop that performs gradient descent
on $f_{\sigma_{k}}$. Motivated by the connection between the derivative with
respect to the smoothing parameter and the second space derivative given by
the heat equation, [20] propose a single loop Gaussian homotopy continuation
method (see Algorithm 4), which is a particular instance of GSmoothGD. In
[20], they prove that SLGH converges but require that both the objective
function and its derivative be Lipschitz, whereas we obtain similar
convergence results only requiring the derivative to be Lipschitz in the non-
convex case. In the convex case, we improve upon their results and we only
assume that either the function or its derivative is Lipschitz.

Algorithm 4 Deterministic Single Loop GH algorithm

1:Iteration number $T$, initial solution $x_{1}$, initial smoothing parameter
$\sigma_{1}$, step size $\beta$ for $x$, step size $\eta$ for $t$, decreasing
factor $\gamma\in(0,1)$, sufficient small positive value $\epsilon$

2:for $k=1\to T$ do

3: $x_{k+1}=x_{k}-\beta\nabla f_{\sigma_{k}}(x_{k})$

4: $\sigma_{k+1}=\left\\{\begin{array}[]{ll}\gamma\sigma_{k}\text{
(SLGH${}_{r}$)}\\\
\max\\{\min\\{\sigma_{k}-\eta\frac{\partial}{\partial\sigma}f_{\sigma_{k}}(x_{k}),\gamma\sigma_{k}\\},\epsilon\\}\text{
(SLGH${}_{d}$)}\end{array}\right.$

5:end for

##  2\. Background and preliminaries

Throughout this effort, we assume that
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$. As typical in optimization papers, we
often assume our functions are $L$-smooth and convex. We restate the
definitions here for the convenience of the reader.

######  Definition 2.1.

We say that $f$ is $M$-Lipschitz if for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$

$\|f(\bm{x})-f(\bm{y})\|\leq M\|\bm{x}-\bm{y}\|.$

We say that $f$ is $L$-smooth if for $\nabla f$ is $L$-Lipschitz.

Instead of using the definition of $L$-smoothness, the majority of the time,
we use the following well-known equivalent formulation (which we only state as
an implication of the definition).

######  Proposition 2.2.

If $f:\mathbb{R}^{d}\to\mathbb{R}$ is $L$-smooth, then for
$\bm{x},\bm{y}\in\mathbb{R}^{d}$

$\big{|}f(\bm{y})-f(\bm{x})-\langle\nabla
f(\bm{x}),\bm{y}-\bm{x}\rangle\big{|}\leq\frac{L}{2}\|\bm{y}-\bm{x}\|^{2}.$
(2.1)

######  Definition 2.3.

We say that $f:\mathbb{R}^{d}\to\mathbb{R}$ is convex if for all
$\bm{x},\bm{y}\in\mathbb{R}^{d}$ with $\bm{x}\not=\bm{y}$ and for all
$t\in(0,1)$ we have

$f\big{(}t\bm{x}+(1-t)\bm{y}\big{)}\leq tf(\bm{x})+(1-t)f(\bm{y}).$

If this inequality is strict, then we say $f$ is strictly convex.

Since we typically assume that $f$ is $L$-smooth, it is differentiable. When
$f$ is differentiable, the following equivalent definition is used.

######  Proposition 2.4.

If $f:\mathbb{R}^{d}\to\mathbb{R}$ is differentiable and convex, then for all
$\bm{x},\bm{y}\in\mathbb{R}^{d}$

$f(\bm{y})-f(\bm{x})\geq\langle\nabla f(\bm{x}),\bm{y}-\bm{x}\rangle.$

The remainder of this section will outline some new theoretical estimates that
are required to prove our main Theorems, given by Theorem 3.1 and 3.3.
Detailed proofs of theoretical results described thorough this section are
given in Appendix A. The first result, shows that smoothing $f$ maintains its
smoothness and convexity (these are found in [36]). Additionally, if $f$ is
Lipshitz, the smoothed derivative also becomes Lipschitz.

######  Lemma 2.5.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ and $\sigma>0$.

  1. (a)

If $f$ is $L$-smooth then $f_{\sigma}$ is also $L$-smooth.

  2. (b)

If $f$ is convex (and differentiable) then so is $f_{\sigma}$.

  3. (c)

If $f$ is $M$-Lipschitz then $f_{\sigma}$ is $M$-Lipschitz and
$\frac{M\sqrt{2d}}{\sigma}$-smooth.

######  Remark 2.6.

As discussed in the introduction, in practice, we do not need to have access
to the gradient of $f$ and instead rely on function evaluations to compute the
derivative of $f_{\sigma}$. In fact, even for the theory to hold we do not
always have to assume that the target function $f$ is differentiable
everywhere because we apply results like Proposition 2.2 and 2.4 on
$f_{\sigma}$ which will be differentiable even if $f$ is only differentiable
a.e. ($\forall\sigma>0$). For example, if $f$ is Lipschitz then it is
automatically differentiable a.e. or if $f$ is only $L$-smooth a.e. then
$f_{\sigma}$ is $L$-smooth $\forall\sigma>0$ (the set of measure 0 where $f$
is non-differentiable does not impact the proof of Lemma 2.5).

Since we are using smoothing to optimize a function, we need to know how the
values of the smoothing function relate to the values of the original
function. The following result shows that smoothing the function increases the
minimum values and, for convex functions, the output unless $f$ is constant.

######  Lemma 2.7.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ and $\sigma>0$.

  1. (a)

Suppose $f_{\sigma}(\bm{x})=f(\bm{x}^{\star})$ for some
$\bm{x}\in\mathbb{R}^{d}$, then $f$ is constant.

  2. (b)

If $f$ is non-constant and either $f(\bm{x})\geq m$ or $f(\bm{x})\leq M$, then
$f_{\sigma}(\bm{x})>m$ or $f_{\sigma}(\bm{x})<M$ (respectively).

  3. (c)

If $f$ is convex, then $f_{\sigma}(\bm{x})\geq f(\bm{x})$ whenever $f$ is
differentiable at $\bm{x}\in\mathbb{R}^{d}$.

Intuitively, smoothing an already smoothed function is the same as smoothing
the original function by some amount; the following result explicitly shows
this amount.

######  Lemma 2.8.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ and $\sigma,\tau>0$. Define
$\eta=\sqrt{\sigma^{2}+\tau^{2}},$ then
$(f_{\sigma})_{\tau}(\bm{x})=f_{\eta}(\bm{x})$ where $(f_{\sigma})_{\tau}$ is
the smoothing function of $f_{\sigma}$ with smoothing parameter $\tau$.

######  Remark 2.9.

Instead of the self-contained proof in the appendix, we could just appeal to
the “heat semigroup” as follows: Define

$(P_{t}f)(\bm{x})=u(\bm{x},t),$ (2.2)

where $u$ is the solution to the heat equation with initial value $f(\bm{x})$,
then

$P_{t_{1}}\circ P_{t_{2}}=P_{t_{1}+t_{2}}.$ (2.3)

Then in our case (as $\sigma=2\sqrt{t}$), for some
$\sigma_{1},\sigma_{2},\sigma\geq 0$, we have

$\frac{\sigma^{2}}{4}=t=t_{1}+t_{2}=\frac{\sigma_{1}^{2}}{4}+\frac{\sigma_{2}^{2}}{4}\Longrightarrow\sigma=\sqrt{\sigma_{1}^{2}+\sigma_{2}^{2}}.$
(2.4)

Our results rely on careful analysis of how much the smoothing changes the
output. We saw above how this relationship unfolds at the minimum, but we need
to more exactly how much the smoothed function can differ from the original
function.

######  Lemma 2.10.

Let $\tau\geq\sigma\geq 0$.

  1. (a)

If $f$ is $L$-smooth, then
$|f_{\tau}(\bm{x})-f_{\sigma}(\bm{x})|\leq(\tau^{2}-\sigma^{2})\nicefrac{{Ld}}{{4}}$.

  2. (b)

If $f$ is $M$-Lipschitz, then $|f_{\tau}(\bm{x})-f_{\sigma}(\bm{x})|\leq
M|\tau-\sigma|\sqrt{\nicefrac{{d}}{{2}}}$.

If $f$ is convex and we do not specify that $\sigma\leq\tau$, the first part
of the previous lemma becomes

$f_{\tau}(\bm{x})-f_{\sigma}(\bm{x})\leq\frac{Ld}{4}\max(0,\tau^{2}-\sigma^{2}),$
(2.5)

which is often the form in which we use the result.

One last result relating the smoothed function’s output to the original’s
output is needed. So far, we know that for a particular $\bm{x}$-value, the
change in output values is bounded by a function of $\sigma$. The same is true
when comparing the minimum of the smoothed function to the minimum of the
original function. This also means if we fix $\sigma$ and minimize
$f_{\sigma}$, then we know we are within some distance of the minimum of the
original function and that distance gets smaller as $\sigma$ does.

######  Corollary 2.11.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ and $\sigma\geq 0$. Let $\bm{x}^{\star}$
and $\bm{x}^{\star}_{\sigma}$ be any minimizers of $f$ and $f_{\sigma}$,
respectively.

  1. (a)

If $f$ is $L$-smooth, then $0\leq
f_{\sigma}(\bm{x}^{\star}_{\sigma})-f(\bm{x}^{\star})\leq\frac{1}{4}\sigma^{2}Ld$.

  2. (b)

If $f$ is $M$-Lipschitz, then $0\leq
f_{\sigma}(\bm{x}^{\star}_{\sigma})-f(\bm{x}^{\star})\leq
M\sigma\sqrt{\nicefrac{{d}}{{2}}}$.

Intuitively, one reason we want to smooth this way is to make the function
“more convex”. Unbounded, non-convex functions that have function values go to
$\infty$ and $-\infty$ in certain directions, e.g., $f(x)=x^{3}$, can only
become convex if flattened out entirely, which will not happen in finite time.
Even for bounded, non-convex functions, the following corollary shows that it
is not always possible to make the function convex. In particular, if you have
a bounded, non-convex function, then no amount of smoothing makes the function
convex. This result is a complement to the work of Mobahi (e.g., see [32]).

######  Corollary 2.12.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ so that $|f_{\sigma}(\bm{x})|\leq
Ae^{a\|x\|^{2}}$ for all $0\leq\sigma\leq S$ for some constants $A$ and $a$.

  1. (a)

If $f_{\sigma}$ is constant for some $\sigma\leq S$, then $f_{\eta}=f$ for all
$\eta>0$.

  2. (b)

If $g:\mathbb{R}^{d}\to\mathbb{R}$ satisfies $|g_{\sigma}(\bm{x})|\leq
Be^{b\|x\|^{2}}$ for all $0\leq\sigma\leq S$ for some constants $B$ and $b$
and $f_{\sigma}(\bm{x})=g_{\sigma}(\bm{x})$ for all $x\in\mathbb{R}^{d}$, then
$f=g$ a.e.

  3. (c)

If there exists $S\geq\sigma>0$ such that
$f_{\sigma}(\bm{x})=f_{\tau}(\bm{x})$ for all $\tau\geq\sigma$, then
$f=f_{\eta}$ a.e. for all $\eta>0$.

  4. (d)

If $f$ is non-convex and bounded, then $f_{\sigma}$ is non-convex for all
$\sigma\geq 0$.

Note that (a) and (b) follow from the uniqueness of solutions to the heat
equation (e.g., see Section 2.3 of [10]).

###### Proof of (c).

Let $\eta>0$ and set $\tau=\sqrt{\sigma^{2}+\eta^{2}}$. Then since
$\tau>\sigma$, using Lemma 2.7,

$\displaystyle(f_{\eta})_{\sigma}=f_{\tau}=f_{\sigma}.$ (2.6)

Then by part (b), we have that $f_{\eta}=f$ a.e. ∎

###### Proof of (d).

Since $f$ is bounded, $f_{\sigma}$ is bounded by Lemma 2.7. If $f_{\sigma}$
were convex, then it would be constant. By part (a), we would have that
$f_{\sigma}=f=0$. However, $f$ is non-convex, which means it cannot be
constant. As such, $f_{\sigma}$ must be non-convex. ∎

##  3\. Gaussian smoothing gradient descent (GSmoothGD)

Our work is primarily concerned with a complete convergence analysis of
Gaussian smoothing gradient descent (GSmoothGD) approaches governed by the
following update rule:

$\bm{x}_{k+1}=\bm{x}_{k}-t\,\nabla f_{\sigma_{k+1}}(\bm{x}_{k}).$ (3.1)

Here the standard gradient $\nabla f(\bm{x}_{k})$ is replaced with the
Gaussian smoothed surrogate $\nabla f_{\sigma_{k+1}}(\bm{x}_{k})$, given by
(1.3), with $\bm{x}_{k}$ and $\bm{x}_{k+1}$ being possible solutions to (1.4)
at iterations $k$ and $k+1$, $t$ is the step size or learning rate, and
$\sigma_{k}$ is the smoothing radius utilized during the $k$th step of (3.1).

###  3.1. Convergence of GSmoothGD for high-dimensional convex functions

We prove the following convergence estimate of GSmoothGD when applied to high-
dimensional convex functions. The detailed proof can be found in Section B.

######  Theorem 3.1 (Convergence of GSmoothGD for convex functions).

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ is convex and $L$-smooth and let
$(\sigma_{n})_{n=1}^{\infty}$ be a sequence of positive real numbers. Then,
after $k$ iterations of GSmoothGD, defined by (3.1), with a fixed step size
$0<t\leq\frac{1}{L}$, the solution $f(\bm{x}_{k})$ satisfies

$f(\bm{x}_{k})-f(\bm{x}^{\star})\leq\frac{\|\bm{x}_{0}-\bm{x}^{\star}\|^{2}}{2tk}+\frac{Ld}{4k}\left(\sum_{i=1}^{k}\sigma_{i}^{2}+\sum_{i=2}^{k}i\max(0,\sigma_{i}^{2}-\sigma_{i-1}^{2})\right),$
(3.2)

where $f(\bm{x}^{\star})$ is the optimal value.

######  Remark 3.2 (Constant smoothing radius).

If we further assume that $\sigma_{n}=\sigma>0$ for all $n$, then for
$t\leq\frac{1}{L}$, and with the use of Lemma 2.10 we get that

$\displaystyle\begin{split}0\leq
f(\bm{x}_{k})-f(\bm{x}^{\star})\leq\frac{\|\bm{x}_{0}-\bm{x}^{\star}\|^{2}}{2tk}+\frac{Ld\sigma^{2}}{4}.\end{split}$

Additionally, the same proof can be used to show a similar result for convex,
$M$-Lipschitz functions. In this case $L$-smooth is replaced with
$\frac{M\sqrt{2d}}{\sigma}$-smooth and $\frac{\sigma^{2}Ld}{4}$ is replaced
with $M\sigma\sqrt{\frac{d}{2}}$.

The proof of Theorem 3.1 is a modification of the proof that the standard GD
algorithm converges when used to minimize convex functions (see Section 1.2.3
of [37] for example). In order to generalize the theory of GD to include the
use of the gradient of the Gaussian smoothing of a convex function we exploit
several new results shown below. First, we show that the Gaussian smoothing
functions inherit convexity and $L$-smoothness from $f$ (Lemma 2.5). Second,
we detail how the function values of $f$ and $f_{\sigma}$ are related (Lemmas
2.7 and 2.10). Third, we show that the smaller the smoothing value, the closer
the Gaussian smoothing function is to the original function (at least when the
original function is convex) (Lemma 2.10).

###  3.2. Convergence of GSmoothGD for high-dimensional non-convex functions

In the setting of non-convex functions when a minimizer exists, we no longer
have that increasing the smoothing parameter also increases the smoothing
function. Hence, changing $\sigma_{i}$ between iterations increases the bound
on the gradient. This is the main result of this section, which is stated in
the following theorem.

######  Theorem 3.3 (Convergence of GSmoothGD for non-convex functions).

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ is non-convex, $L$-smooth, and
satisfies (1.3) and let $(\sigma_{n})_{n=1}^{\infty}$ be a sequence of
positive real numbers. Then, after $k$ iterations of GSmoothGD, defined by
(3.1), with a fixed step size $0<t\leq\frac{1}{L}$,

$\min_{i=1,...,k}\|\nabla
f(\bm{x}_{i})\|^{2}\leq\frac{4}{tk}\big{(}f_{\sigma_{1}}(\bm{x}_{1})-f_{\sigma_{k+1}}(\bm{x}_{k+1})\big{)}\\\
+\frac{Ld}{2tk}\sum_{i=1}^{k}|\sigma_{i+1}^{2}-\sigma_{i}^{2}|+\frac{L^{2}(6+d)^{3}}{4k}\sum_{i=1}^{k}\sigma_{i+1}^{2}$
(3.3)

######  Remark 3.4.

The requirement that $f$ satisfies (1.3), which just means we can interchange
the gradient and the expectation, comes from [38, Lemma 4], which we state
below for the convenience of the reader. In the convex case, we did not need
to assume this because we were able to bound $f(\bm{x}_{k})-f(\bm{x}^{\star})$
rather than the gradient. This requirement can be satisfied in a variety of
ways such as $f\in L^{1}(\mathbb{R}^{d})$, $f$ being bounded, $f$ having
compact support, or even the assumption that
$\sup_{\bm{x}\in\mathbb{R}^{d}}E_{\bm{u}}[|f(\bm{x}+\sigma\bm{u})|]<\infty$
from [20]. Practically, we can pick a large ball around the minimizer of $f$
and make $f$ constant outside of this ball, which would cause $f$ to be
bounded.

######  Lemma 3.5 ([38]).

If $f$ is $L$-smooth, then $\|\nabla f(\bm{x})\|^{2}\leq 2\|\nabla
f_{\sigma}(\bm{x})\|^{2}+\sigma^{2}\nicefrac{{L^{2}(d+6)^{3}}}{{4}}$.

######  Proposition 3.6.

Let $f$ be $L$-smooth and $(\sigma_{n})_{n=1}^{\infty}$ be square summable.
Then the complexity of GSmoothGD is
$O\left(\frac{1+d^{3}}{\epsilon^{2}}\right)$.

######  Remark 3.7.

If $\sigma_{n}=\sigma$ for all $n$ (similarly, if
$\sum_{i=0}^{\infty}\sigma_{i}^{2}$ diverges), then we can’t compute the
iterations in the same manner. In the constant case, we end up with:

$\min_{i=1,...,k}\|\nabla
f(\bm{x}_{i})\|^{2}\leq\frac{4}{tk}\big{(}f(\bm{x}_{0})-f(\bm{x}^{\star})\big{)}+\frac{L^{2}(6+d)^{3}\sigma^{2}}{4}.$
(3.4)

So if we want the derivative to be small, we have to make $\sigma$ small too
(but we could do this by taking a finite number of unique $\sigma_{n}$).

###  3.3. Relationship between minimizers and smoothed minimizers

In this section, we discuss the relationship between $\bm{x}^{\star}$ and
$\bm{x}^{\star}_{\sigma}$ for convex, $L$-smooth functions, given by (1.5).
Our motivation comes from the following question: if we can optimize $f$ (i.e.
$\bm{x}^{\star}$ exists), then can we optimize $f_{\sigma}$ for a fixed
$\sigma$ (i.e. does $\bm{x}^{\star}_{\sigma}$ exist)? The first result, which
is just the contrapositive of Corollary 2.11, says that if $f(\bm{x})$ is too
large then $\bm{x}$ cannot minimize $f_{\sigma}$ (Corollary 3.8). The second
result shows that if the set of minimizers is bounded, then for small enough
values of $\sigma$ we know that $\bm{x}^{\star}_{\sigma}$ exists (Proposition
3.11). This proof requires a technical bound on the smoothing functions (Lemma
3.9). Third, we show that if the set of minimizers of $f$ is bounded then for
small enough $\sigma$ that the smooth minimizer $\bm{x}^{\star}_{\sigma}$ is
close to some actual minimum $\bm{x}^{\star}$ (Proposition 3.14). Before we
show these results, we provide an example to show that if the set of
minimizers of $f$ is unbounded, then no minimizers of $f_{\sigma}$ for any
$\sigma>0$ may exist.

######  Example 1.

Let $f:\mathbb{R}\to\mathbb{R}$ be defined as

$f(x)=\left\\{\begin{array}[]{ll}-x&x<0\\\ 0&x\geq 0\end{array}\right..$ (3.5)

Then for all $x\in\mathbb{R}$

$\nabla
f_{\sigma}(x)=\frac{1}{\sqrt{\pi}}\int_{-\infty}^{-\nicefrac{{x}}{{\sigma}}}-e^{-u^{2}}\;du<0.$
(3.6)

This means that $f_{\sigma}$ has no minimum regardless of $\sigma$. So even
though $f(x)$ is minimized by any positive number, $f_{\sigma}(x)$ has no
minimum for any $\sigma>0$.

For the remainder of this section, for any $\epsilon\geq 0$, we will denote
the inverse image of $[f(\bm{x}^{\star}),f(\bm{x}^{\star})+\epsilon]$ as
$f^{\star}(\epsilon)$, defined by

$f^{\star}(\epsilon)=\\{\bm{x}\in\mathbb{R}^{d}:f(\bm{x})-f(\bm{x}^{\star})\leq\epsilon\\}.$
(3.7)

The following first result in this section allows us to limit the size of the
set of possible minimizers of $f_{\sigma}$ solely based on the output of the
original $f$.

######  Corollary 3.8.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be $L$-smooth and $\sigma\geq 0$. If

$|f(\bm{x})-f(\bm{x}^{\star})|>\frac{\sigma^{2}Ld}{4},$ (3.8)

then $\bm{x}$ is not a minimizer of $f_{\sigma}$. In particular, any minimizer
of $f_{\sigma}$ is in $f^{\star}(\nicefrac{{\sigma^{2}Ld}}{{4}})$.

We now focus on showing our second result with the technical lemma required in
the proof of Proposition 3.11.

######  Lemma 3.9.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be $L$-smooth and assume that a minimizer
$\bm{x}^{\star}$, given by (1.5), of $f$ exists. Let $\sigma>0$ and let
$\epsilon\geq\frac{4\sigma^{2}Ld}{3}$ then for $\bm{x}\in
f^{\star}\left(\frac{\sigma^{2}Ld}{4}\right)$

$f_{\sigma}(\bm{x})<f_{\sigma}(\bm{y})\qquad\forall\bm{y}\notin
f^{\star}(\epsilon).$ (3.9)

###### Proof.

Let $\bm{x}\in f^{\star}\left(\frac{\sigma^{2}Ld}{4}\right)$ and $\bm{y}\notin
f^{\star}(\epsilon)$ (that is, $f(\bm{y})>f(\bm{x}^{\star})+\epsilon$). Using
Lemma 2.10 to switch between $f_{\sigma}$ and $f$, we have

$\displaystyle\begin{split}f_{\sigma}(\bm{x})&\leq
f(\bm{x})+\frac{\sigma^{2}Ld}{4}\,\leq\,f(\bm{x}^{\star})+\frac{\sigma^{2}Ld}{2}=f(\bm{x}^{\star})+\frac{3\sigma^{2}Ld}{4}-\frac{\sigma^{2}Ld}{4}\\\
&\ \ \
<f(\bm{x}^{\star})+\epsilon-\frac{\sigma^{2}Ld}{4}<f(\bm{y})-\frac{\sigma^{2}Ld}{4}\leq
f_{\sigma}(\bm{y})\end{split}$ (3.10)

∎

######  Remark 3.10.

If $f$ is convex, the same result holds using
$\epsilon\geq\frac{\sigma^{2}Ld}{2}$ as in this case $f(\bm{y})\leq
f_{\sigma}(\bm{y})$.

We can now prove our second result that provides a sufficient condition on
when a minimizer of $f_{\sigma}$ can exist.

######  Proposition 3.11.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be $L$-smooth. Suppose
$f^{\star}(\epsilon)$ is bounded for some $\epsilon>0$. Let $\sigma>0$ with
$\sigma<\sqrt{\frac{4\epsilon}{3Ld}}$. Then $\bm{x}^{\star}_{\sigma}$ exists.

###### Proof.

Since $f$ is continuous, $f^{\star}(\epsilon)$ is also closed. By assumption,
$f^{\star}(\epsilon)$ is bounded, which means it is compact too. This
guarantees that $f_{\sigma}|_{f^{*}(\epsilon)}$ attains its minimum on
$f^{*}(\epsilon)$. Let

$\bm{x}_{\sigma}^{\epsilon}=\operatorname*{argmin}_{\bm{x}\in
f^{*}(\epsilon)}f_{\sigma}(\bm{x}).$ (3.11)

Since $\frac{\sigma^{2}Ld}{4}<\epsilon$,
$f^{\star}(\nicefrac{{\sigma^{2}Ld}}{{4}})\subseteq f^{\star}(\epsilon)$ and
so $f_{\sigma}(\bm{x}_{\sigma}^{\epsilon})\leq
f_{\sigma}(\bm{x})\;\;\forall\bm{x}\in
f^{\star}\left(\nicefrac{{\sigma^{2}Ld}}{{4}}\right)$. By Lemma 3.9,
$\displaystyle f_{\sigma}(\bm{x}_{\sigma}^{\epsilon})\leq
f_{\sigma}(\bm{y})\;\;\forall\bm{y}\notin f^{\star}(\epsilon),$ which means
that $\displaystyle f_{\sigma}(\bm{x}_{\sigma}^{\epsilon})\leq
f_{\sigma}(\bm{x})\;\;\forall\bm{x}\in\mathbb{R}^{d},$ making
$\bm{x}_{\sigma}^{\epsilon}$ a minimizer of $f_{\sigma}$. ∎

######  Remark 3.12.

If $f$ is convex, then we have the same result for
$\sigma<\sqrt{\frac{2\epsilon}{Ld}}$.

If $f$ is convex, then the set of minimizers being bounded means that the set
of points that output just a little more than the minimum is also bounded. On
the other hand, the following proposition does not necessarily hold for non-
convex functions. In fact for non-convex functions, it can be the case that
$f^{\star}(0)$ is bounded and for all $\epsilon>0$ $f^{\star}(\epsilon)$ is
unbounded. This can occur when there is a sequence
$(\bm{x}_{n})_{n=1}^{\infty}$ where $\|\bm{x}_{n}\|\to\infty$ and
$f(\bm{x}_{n})\to f(\bm{x}^{\star})$.

######  Proposition 3.13.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be convex and $L$-smooth with a bounded
minimizer set, $f^{\star}(0)$. Then there exists $\epsilon>0$ so that
$f^{\star}(\epsilon)$ is bounded too.

###### Proof.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be convex and $L$-smooth with a bounded
minimizer set, $f^{\star}(0)$. Suppose towards a contradiction that
$f^{\star}(\epsilon)$ is unbounded for all $\epsilon>0$. Since $f^{\star}(0)$
is bounded, there is an $M>0$ so that $f^{\star}(0)\subseteq
B(0,\frac{M}{2})$. Since $f^{\star}(\frac{1}{n})$ is unbounded for all
$n\in\mathbb{N}$, there exists $\bm{x}_{n}\in f^{\star}(\frac{1}{n})\cap
B(0,M)^{c}$. For any $0<t<1$, using the fact that $f$ is convex and the choice
of $x_{n}$, we have

$f(t\bm{x}^{\star}+(1-t)\bm{x}_{n})\leq
tf(\bm{x}^{\star})+(1-t)f(\bm{x}_{n})<f(\bm{x}^{\star})+\frac{1}{n}.$ (3.12)

For each $n\in\mathbb{N}$, there exists $t_{n}\in(0,1)$ so that

$\bm{y}_{n}=t_{n}\bm{x}^{\star}+(1-t_{n})\bm{x}_{n}\text{ and
}\|\bm{y}_{n}\|=M.$ (3.13)

This means $f(\bm{y}_{n})\to f(\bm{x}^{\star})$. Since
$\\{\bm{y}_{n}\\}_{n=1}^{\infty}$ is bounded, there is a convergent
subsequence $(\bm{y}_{n_{i}})_{i=1}^{\infty}$ to the point $\bm{y}_{0}$. Since
$\|\bm{y}_{n}\|=M$, $\|\bm{y}_{0}\|=M$ too. This would mean that
$\bm{y}_{0}\in f^{\star}(0)$, but since $f^{\star}(0)\subseteq
B(0,\frac{M}{2})$, this cannot be the case and we arrive at our contradiction.
Therefore, for some $\epsilon>0$, $f^{\star}(\epsilon)$ is bounded. ∎

Now we will justify the third result, which shows that the set of minimizers
of $f_{\sigma}$ grow in a continuous manor when $f$ is convex.

######  Proposition 3.14.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be $L$-smooth and
$(\sigma_{n})_{n=1}^{\infty}$ with $\sigma_{n}\geq 0$ and $\sigma_{n}\to 0$.
Suppose $f^{\star}(\delta)$ is bounded for some $\delta>0$. Then for all
$\epsilon>0$, there exists $N\in\mathbb{N}$ such that for all $n\geq N$

$d(\bm{x}^{\star}_{\sigma_{n}},f^{\star}(0))=\inf\left\\{\|\bm{x}^{\star}_{\sigma_{n}}-\bm{x}^{\star}\|:\bm{x}^{\star}\in
f^{\star}(0)\right\\}<\epsilon$ (3.14)

where $\bm{x}^{\star}_{\sigma_{n}}$ is any minimizer of $f_{\sigma_{n}}$.

###### Proof.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be $L$-smooth and
$(\sigma_{n})_{n=1}^{\infty}$ with $\sigma_{n}\geq 0$ and $\sigma_{n}\to 0$.
Since $\sigma_{n}\to 0$, there exists $N\in\mathbb{N}$ so that
$\sigma_{n}\leq\sqrt{\frac{4\delta}{3Ld}}$. By Proposition 3.11,
$\bm{x}^{\star}_{\sigma_{n}}$ exists for all $n\geq N$. Suppose, towards a
contradiction, that there is some $\epsilon>0$ so that for all
$i\in\mathbb{N}_{\geq N}$ there exists $n_{i}\geq i$ with
$d(\bm{x}^{\star}_{\sigma_{n_{i}}},f^{\star}(0))\geq\epsilon$. This means that
no subsequence of $(\bm{x}^{\star}_{\sigma_{n_{i}}})_{i=N}^{\infty}$ can
converge to a point in $f^{\star}(0)$. Since $\sigma_{n}\to 0$, we still have
that $\sigma_{n_{i}}\to 0$. By Corollary 2.11

$|f(\bm{x}^{\star}_{\sigma_{n_{i}}})-f(\bm{x}^{\star})|\leq\frac{\sigma_{n_{i}}^{2}Ld}{4}\leq\delta,$
(3.15)

so by Corollary 3.8 $\bm{x}^{\star}_{\sigma_{n_{i}}}\in f^{\star}(\delta)$ for
all $i\geq N$. Since $f^{\star}(\delta)$ is bounded, there exists a
subsequence $(\bm{x}^{\star}_{\sigma_{n_{i_{j}}}})_{j=1}^{\infty}$ that
converges to a point, say $\bm{x}_{0}$. Since

$|f(\bm{x}^{\star}_{\sigma_{n_{i_{j}}}})-f(\bm{x}^{\star})|\leq\frac{\sigma_{n_{i_{j}}}^{2}Ld}{4}\to
0$ (3.16)

(again using Corollary 2.11) and $f$ is continuous,
$f(\bm{x}_{0})=f(\bm{x}^{\star})$. However, this means that $\bm{x}_{0}\in
f^{\star}(0)$, which is a contradiction. ∎

######  Corollary 3.15.

Let $f:\mathbb{R}^{d}\to\mathbb{R}$ be convex and $L$-smooth with a unique
minimizer $\bm{x}^{\star}$. Then for any $\sigma_{n}\to 0$ with
$\sigma_{n}\geq 0$,

$\bm{x}^{\star}_{\sigma_{n}}\to\bm{x}^{\star},$ (3.17)

where $\bm{x}^{\star}_{\sigma_{n}}$ is any minimizer of $f_{\sigma_{n}}$.

###### Proof.

Let $\sigma_{n}\to 0$ with $\sigma_{n}\geq 0$ and $\epsilon>0$. Since $f$ is
convex, there exists $\delta>0$ so that $f^{\star}(\delta)$ is bounded. This
means there is an $N\in\mathbb{N}$ so that

$\|\bm{x}^{\star}_{\sigma_{n}}-\bm{x}^{\star}\|=d(\bm{x}^{\star}_{\sigma_{n}},f^{\star}(0))<\epsilon$
(3.18)

for all $n\geq N$. This shows $\bm{x}^{\star}_{\sigma_{n}}\to\bm{x}^{\star}$.
∎

##  4\. Numerical methods for GSmoothGD

In this section we describe various numerical approximation schemes for
Gaussian smoothing, including MC, variance of the gradient of the smoothed
function, and Gaussian homotopy. We also discuss the strategies employed to
appropriately update the smoothing parameter $\sigma$.

###  4.1. Monte Carlo GSmoothGD (MC-GSmoothGD)

In practice, we cannot evaluate $\nabla f_{\sigma}(\bm{x})$ exactly. Instead,
we can use one of the approximations from [38]. Define
$\delta_{\sigma}(\bm{x};\bm{u})$ as either of the finite difference schemes

$\frac{f(\bm{x}+\sigma\bm{u})-f(\bm{x})}{\nicefrac{{\sigma}}{{2}}}\quad\text{or}\quad\frac{f(\bm{x}+\sigma\bm{u})-f(\bm{x}-\sigma
u)}{\sigma}$ (4.1)

and

$\bm{g}_{\sigma}(\bm{x};N)=\frac{1}{N}\sum_{n=1}^{N}\delta_{\sigma}(\bm{x};\bm{u}_{n})\bm{u}_{n}$
(4.2)

where $\bm{u}_{n}$ are independent samples from the $e^{-\|\bm{u}\|^{2}}$
density. Regardless of the choice, both are unbiased estimates of $\nabla
f_{\sigma}(\bm{x})$. We will use the second choice for the MC-GSmoothGD
algorithm (Algorithm 5). Theorem 4.2 shows the convergence of this algorithm.

Algorithm 5 MC-GSmoothGD

1:$f:\mathbb{R}^{d}\to\mathbb{R}$, $N\in\mathbb{N}$, $\sigma>0$,
$\bm{x}_{0}\in\mathbb{R}^{d}$, $t>0$

2:for $k=1\to K$ do

3: Sample $\bm{u}_{n}\sim\mathcal{N}(0,\frac{1}{2})$ for $n=1,...,N$

4:
$\bm{g}_{k}=\displaystyle\frac{1}{N}\sum_{n=1}^{N}\frac{f(\bm{x}_{k-1}+\sigma\bm{u}_{n})-f(\bm{x}_{k-1}-\sigma\bm{u}_{n})}{\sigma}\bm{u}_{n}$

5: $\bm{x}_{k}=\bm{x}_{k-1}-t\bm{g}_{k}$

6:end for

######  Lemma 4.1.

Let $\delta_{\sigma}(\bm{x};\bm{u})$ and $\bm{g}_{\sigma}(\bm{x};N)$ be either
of the approximations of $\nabla f_{\sigma}(\bm{x})$ above. Then

$E(\|\bm{g}_{\sigma}(\bm{x};N)\|^{2})=\frac{1}{N}E\big{(}\delta_{\sigma}(\bm{x};\bm{u}_{1})^{2}\|\bm{u}_{1}\|^{2}\big{)}+\left(1-\frac{1}{N}\right)\|\nabla
f_{\sigma}(\bm{x})\|^{2}.$ (4.3)

######  Theorem 4.2.

Let $f$ be $L$-smooth and satisfy (1.3). Let $(\sigma_{n})_{n=1}^{\infty}$ be
a sequence of positive real numbers. Pick $0<t\leq\frac{1}{2L(d+4)}$. Let
$\delta_{\sigma}(\bm{x};\bm{u})$ be either of the differences in (4.1) and
$\bm{g}_{\sigma}(\bm{x};N)$ be the corresponding $N$-point Monte Carlo
approximation of $\nabla f_{\sigma}(\bm{x})$. Define

$\bm{x}_{k+1}=\bm{x}_{k}-t\bm{g}_{\sigma_{k+1}}(\bm{x}_{k};N).$ (4.4)

Then for $N\geq 1$,

$\min_{i=0,...,k-1}E(\|\nabla f(\bm{x}_{i})\|^{2})\\\
\leq\frac{1}{k}\left(\frac{N}{N-2Lt(d+4)}\right)\Bigg{(}\frac{4(f(\bm{x}_{0})-f_{\sigma_{k}}(\bm{x}_{k}))}{t}+\left(\frac{L^{3}t(d+6)^{3}}{4N}+\frac{2Ld}{t}\right)\sum_{i=1}^{k}\sigma_{i}^{2}\Bigg{)}.$
(4.5)

As with Theorem 3.3, we need to switch apply [38, Lemma 4] which is why we
require (1.3) to be satisfied and everything in Remark 3.4 still holds.

###  4.2. Updating the smoothing parameter

Regardless of how $\sigma$ is chosen or updated, the results that we have
shown here apply to any of the Gaussian smoothing algorithm we have mentioned.
In the homotopy continuation setting (Algorithm 3), for each $\sigma_{k}$, we
minimize (via gradient descent) $f_{\sigma_{k}}$. In the context of our
results, this corresponds to creating a sequence of smoothing parameters where
we repeat $\sigma_{k}$ as many times as the number of steps in the gradient
descent. Since the goal is to minimize $f_{\sigma_{k}}$, the double loop is
baked into this algorithm.

Instead of focusing on minimizing each $f_{\sigma_{k}}$, we can perform
gradient descent on the $\mathbb{R}^{d+1}$ function $f_{\sigma}(x)$. This is
what SLGH does by doing a gradient descent steps simultaneously in $\bm{x}$
and $\sigma$. We know that the minimum of $f_{\sigma}(\bm{x})$ over both
$\bm{x}$ and $\sigma$ occurs when $\sigma=0$ (see Lemma 2.7), so if SLGH finds
the global minimum of $f_{\sigma}(\bm{x})$ then it has found the global
minimum of $f$.

Without exception, the Gaussian smoothing algorithms we have discussed
(Algorithms 3 and 4) have all required $\sigma$ to decrease. The motivation
for this decrease is to force $\sigma\to 0$ so that the original function can
be minimized. In the context of homotopy continuation, if we trace the path of
minimums, then we can easily become trapped in a local minimum of $f_{\sigma}$
or $f$. This can happen even if we start at the global minimum of $f_{\sigma}$
for some $\sigma>0$. Note that restrictive assumptions can be made to stop
this from happening, but we want to avoid further restricting $f$. The
motivation for smoothing is to use smoothing to remove local minimums, but
this does not happen when $\sigma$ is small. So if we force $\sigma$ to
decrease and we become trapped in a local minimum, we are unlikely to escape
unless we increase $\sigma$ high enough that our gradient descent step moves
us away from this trap.

##  5\. Numerical experiments

In this section we compare smoothing-based optimization algorithms with other
conventional methods. We consider smoothing-based algorithms (MC-GSmoothGD,
DGS [54], LSGD [41], SLGH [20]), backpropagation-based algorithms (NAG [48],
Adam [23], RMSProp [19]), and classical gradient-based algorithms from
numerical optimization (BFGS [39], CG [39]).

Our experiments are performed in Python3.8 with the use of Numpy and Scipy
packages. In order to provide a uniform comparison between different algorithm
families, each of the smoothing-based and backpropagation-based algorithms is
implemented as a custom scipy.optimize method with the same gradient
estimation and stopping criteria. The experiments are performed on a consumer-
grade desktop and the source code is publicly available at
https://github.com/sukiboo/smoothing_based_optimization.

Our testbed consists of well-established multi-dimensional functions from the
Virtual Library of Simulation
Experiments222https://www.sfu.ca/~ssurjano/optimization.html. Specifically, we
use $100$-dimensional formulations of Ackley, Levy, Michalewicz, Rastrigin,
Rosenbrock, and Schwefel functions to test and compare the algorithms. For
Schwefel function we additionally take the absolute value to receive an
unconstrained optimization problem. We note that such a modification does not
change the function values or the position of minimizers on the intended
domain $[-500,500]^{100}$.

Each experiment is performed $10$ times with a series of initial guesses
(synchronized between different algorithms) that are randomly sampled from the
corresponding domain for each test function. For each algorithm and target
function we consider the following increasingly noisy settings:

  1. 1.

each target function evaluation is computed precisely;

  2. 2.

each target function evaluation is computed with $0.000001$% relative
perturbation;

  3. 3.

each target function evaluation is computed with $0.01$% relative
perturbation.

Results of our experiments are presented in Figure 1, where for each algorithm
the so1lid line indicates the median value across all $10$ experiments and the
shaded region denotes the area between $25$-th and $75$-th percentile.

###  5.1. Hyperparameters

For each algorithm and test function we perform a hyperparameter search for
learning rate $\lambda$ on the grid [1, $10^{-1}$, $10^{-2}$, $10^{-3}$,
$10^{-4}$, $10^{-5}$, $10^{-6}$]. For smoothing-based algorithms we
additionally perform a hyperparameter search for the value of the smoothing
parameter $\sigma$ on the grid [1, $10^{-1}$, $10^{-2}$, $10^{-3}$].

Hyperparameter searches are performed with the exact function evaluations and
the final values of hyperparameters for each algorithm and test function are
given in Tables 1 and 2.

For the smoothed gradient computation we use $1000$ Monte Carlo samples in MC-
GSmoothGD and $5$ Gauss–Hermite quadrature points in DGS across all
experiments. The value of the momentum in NAG is set to $\beta=0.5$ to offer a
reasonable compromise since there seems to be no conventional value and the
practical recommendations typically range between $0.1$ and $0.9$. All
unspecified hyperparameters are set to their default values selected by the
algorithm’s authors. Note that BFGS and CG use adaptive learning rates, thus
these algorithms are not listed in Table 1.

(a) Ackley function

(b) Levy function

(c) Michalewicz function

(d) Rastrigin function

(e) Rosenbrock function

(f) Schwefel function

Figure 1: Numerical experiments on $100$-dimensional test functions with various relative noise levels: no noise (left), $0.000001$% (middle), and $0.01$% (right).  | Target function
---|---
Algorithm | Ackley | Levy | Michalewicz | Rastrigin | Rosenbrock | Schwefel
MC-GSmoothGD | 1e-0 | 1e-1 | 1e-4 | 1e-3 | 1e-5 | 1e-0
DGS | 1e-1 | 1e-1 | 1e-4 | 1e-5 | 1e-5 | 1e-2
LSGD | 1e-1 | 1e-1 | 1e-5 | 1e-5 | 1e-5 | 1e-1
SLGH | 1e-0 | 1e-3 | 1e-6 | 1e-4 | 1e-5 | 1e-2
NAG | 1e-3 | 1e-4 | 1e-5 | 1e-5 | 1e-5 | 1e-3
Adam | 1e-4 | 1e-3 | 1e-4 | 1e-4 | 1e-1 | 1e-1
RMSProp | 1e-4 | 1e-3 | 1e-4 | 1e-4 | 1e-2 | 1e-1
Table 1: Values of the learning rate $\lambda$ for optimization algorithms on $100$-dimensional test functions. See Figure 1 for the performance of the corresponding algorithms. | Target function
---|---
Algorithm | Ackley | Levy | Michalewicz | Rastrigin | Rosenbrock | Schwefel
MC-GSmoothGD | 1e-0 | 1e-2 | 1e-2 | 1e-0 | 1e-0 | 1e-3
DGS | 1e-1 | 1e-1 | 1e-2 | 1e-3 | 1e-0 | 1e-3
LSGD | 1e-3 | 1e-2 | 1e-1 | 1e-3 | 1e-0 | 1e-0
SLGH | 1e-0 | 1e-1 | 1e-3 | 1e-2 | 1e-0 | 1e-3
Table 2: Values of the smoothing parameter $\sigma$ for the smoothing-based
optimization algorithms on $100$-dimensional test functions.

##  6\. Conclusions

This effort delves into the convergence analysis of a category of smoothing-
based gradient descent methods when applied to high-dimensional non-convex
optimization challenges. Gaussian smoothing is harnessed to define the
nonlocal gradient, which significantly aids gradient descent in navigating
away from local minima and enhances overall performance in non-convex
optimization tasks. Furthermore, this work provides rigorous theoretical error
estimates on the convergence rate of GSmoothGD iterates, taking into account
the influence of function convexity, smoothness, input dimension, and the
Gaussian smoothing radius. To address curse of dimensionality, we numerically
approximate the $d$-dimensional GSmoothGD nonlocal gradient using MC sampling,
backed by a theory that demonstrates convergence regardless of function
smoothness and dimensionality. To combat local minima’s influence, the paper
discusses strategies for updating the smoothing parameter, making global
minima more attainable. These methods, in their bid to alleviate high-
frequency noise, minor fluctuations, and rapid variations in the computation
of descent directions, replace conventional (local) gradients with (nonlocal)
approximations that aim to preserve the overall large-scale structure or
features of the loss landscape. In our investigation of optimization
techniques, we present empirical evidence that highlights the remarkable
stability of smoothing-based optimization when subjected to external
perturbations. Our findings reveal that algorithms employing Gaussian
smoothing mechanisms exhibit an extraordinary resilience to the presence of
noise, a characteristic that holds significant practical utility in real-world
applications. Finally, future endeavors will focus on extending the theory and
numerical approaches for Gaussian smoothing to improve other popular
approaches for high-dimensional non-convex optimization, including stochastic
gradient descent (GSmoothSGD), as well as stochastic variance reduced gradient
(GSmoothSVRG). These approaches aim at reducing noise and uncertainty in the
gradient approximation and, thereby, enhancing the effectiveness of SGD as
well as SVRG.

##  Appendix A Proofs of background results

### Proof of Lemma 2.5

For the proofs of Lemma 2.5(a) and (b) please see, e.g., [38, p. 533].

For the first part of (c), the fact that $f_{\sigma}$ is $M$-Lipschitz is
stated as the 2nd bullet on pg. 533 of [38]. To see the second half,

$\displaystyle\begin{split}\|\nabla f_{\sigma}(\bm{x})-\nabla
f_{\sigma}(\bm{y})\|&\leq\frac{2}{\sigma\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}|f(\bm{x}+\sigma\bm{u})-f(\bm{y}+\sigma\bm{u})|\|\bm{u}\|e^{-\|\bm{u}\|^{2}}\;d\bm{u}\\\
&\leq\frac{2M\|\bm{x}-\bm{y}\|}{\sigma\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\|\bm{u}\|e^{-\|\bm{u}\|^{2}}\;d\bm{u}\\\
&=\frac{M\sqrt{2d}}{\sigma}\|\bm{x}-\bm{y}\|\end{split}$ (A.1)

### Proof of Lemma 2.7

For the proof of (a), let $\sigma>0$ and suppose there is some
$\bm{x}_{0}\in\mathbb{R}^{d}$ so that
$f_{\sigma}(\bm{x}_{0})=f(\bm{x}^{\star})$. Then

$0=f_{\sigma}(\bm{x}_{0})-f(\bm{x}^{\star})=\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\Big{(}f(\bm{x}_{0}+\sigma\bm{u})-f(\bm{x}^{\star})\Big{)}e^{-\|\bm{u}\|^{2}}\;d\bm{u}.$
(A.2)

Since $(f(\bm{x}_{0}+\sigma\bm{u})-f(\bm{x}^{\star}))e^{-\|\bm{u}\|^{2}}\geq
0$ and $e^{-\|\bm{u}\|^{2}}\not=0$, we have
$f(\bm{x}_{0}+\sigma\bm{u})-f(\bm{x}^{\star})=0$ for all
$\bm{u}\in\mathbb{R}^{d}$. Further for any $\bm{x}\in\mathbb{R}^{d}$ we can
find a $\bm{u}\in\mathbb{R}^{d}$ so that $\bm{x}=\bm{x}_{0}+\sigma\bm{u}$,
which shows $f(\bm{x})=f(\bm{x}^{\star})$ for all $\bm{x}\in\mathbb{R}^{d}$.
Thus $f$ is constant. This same approach obviously holds for a maximizer of
$f$ as well.

For the proof of (b), since $f(\bm{x}+\sigma\bm{u})-m\geq 0$, we have

$f_{\sigma}(\bm{x})-m=\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\Big{(}f(\bm{x}+\sigma\bm{u})-m\Big{)}e^{-\|\bm{u}\|^{2}}\;d\bm{u}\geq
0.$ (A.3)

This means $f_{\sigma}(\bm{x})\geq m$. Repeating this for
$M-f(\bm{x}+\sigma\bm{u})\geq 0$, gives the other result.

Finally, for the proof of (c), let $\bm{x}\in\mathbb{R}^{d}$ and $\sigma>0$.
If $f$ is differentiable at $\bm{x}$, then

$\displaystyle\begin{split}f_{\sigma}(\bm{x})-f(\bm{x})&=\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\Big{(}f(\bm{x}+\sigma\bm{u})-f(\bm{x})\Big{)}e^{-\|\bm{u}\|^{2}}\;d\bm{u}\\\
&\geq\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\langle\nabla
f(\bm{x}),\sigma\bm{u}\rangle e^{-\|\bm{u}\|^{2}}\;d\bm{u}\\\ &=0.\end{split}$
(A.4)

Rearranging shows that $f_{\sigma}(\bm{x})\geq f(\bm{x})$.

### Proof of Lemma 2.8

We have that

$\displaystyle\begin{split}(f_{\sigma})_{\tau}(\bm{x})&=\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\left(\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}f((\bm{x}+\tau\bm{v})+\sigma\bm{u})e^{-\|\bm{u}\|^{2}}\;d\bm{u}\right)e^{-\|\bm{v}\|^{2}}\;d\bm{v}\\\
&=\frac{1}{\pi^{d}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}f(\bm{x}+\tau\bm{v}+\sigma\bm{u})e^{-\|\bm{u}\|^{2}+\|\bm{v}\|^{2}}\;d\bm{u}d\bm{v}.\end{split}$
(A.5)

Using the change of variables $\bm{s}=\sigma\bm{u}+\tau\bm{v}$ and
$\bm{t}=\tau\bm{u}-\sigma\bm{v}$ we end up with

$\displaystyle\begin{split}(f_{\sigma})_{\tau}(\bm{x})&=\frac{1}{\pi^{d}\eta^{2d}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}f(\bm{x}+\bm{s})e^{-\frac{1}{\eta^{2}}(\|\bm{s}\|^{2}+\|t\|^{2})}\;d\bm{t}d\bm{s}\\\
&=\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}f(\bm{x}+\eta\bm{w})e^{-\|\bm{w}\|^{2}}\;d\bm{w}\\\
&=f_{\eta}(\bm{x}),\end{split}$ (A.6)

which completes the proof.

### Proof of Lemma 2.10

First, let $f:\mathbb{R}^{d}\to\mathbb{R}$ be $L$-smooth. From Lemma 2.8, if
$\eta=\sqrt{\tau^{2}-\sigma^{2}}$, then
$f_{\tau}(\bm{x})=(f_{\sigma})_{\eta}(\bm{x}).$ So,

$\displaystyle\begin{split}|f_{\tau}(\bm{x})-f_{\sigma}(\bm{x})|=|(f_{\sigma})_{\eta}(\bm{x})-f_{\sigma}(\bm{x})|.\end{split}$
(A.7)

As such, it suffices to show

$|f_{\sigma}(\bm{x})-f(\bm{x})|\leq\frac{\sigma^{2}Ld}{4}.$ (A.8)

To this end, note that

$\displaystyle\begin{split}f_{\sigma}(\bm{x})-f(\bm{x})&=\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\Big{(}f(\bm{x}+\sigma\bm{u})-f(\bm{x})-\langle\nabla
f(\bm{x}),\sigma\bm{u}\rangle\Big{)}e^{-\|\bm{u}\|^{2}}d\bm{u}.\end{split}$
(A.9)

Therefore, since $f$ is $L$-smooth,

$\displaystyle\begin{split}|f_{\sigma}(\bm{x})-f(\bm{x})|&\leq\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\Big{|}f(\bm{x}+\sigma\bm{u})-f(\bm{x})-\langle\nabla
f(\bm{x}),\sigma\bm{u}\rangle\Big{|}e^{-\|\bm{u}\|^{2}}d\bm{u}\\\
&\leq\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\frac{L}{2}\|\sigma\bm{u}\|^{2}e^{-\|\bm{u}\|^{2}}d\bm{u}\\\
&=\frac{\sigma^{2}L}{2\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\|\bm{u}\|^{2}e^{-\|\bm{u}\|^{2}}d\bm{u}=\frac{\sigma^{2}L}{2\pi^{\frac{d}{2}}}\left(\frac{d\pi^{\frac{d}{2}}}{2}\right)=\frac{\sigma^{2}Ld}{4}.\end{split}$
(A.10)

To prove part (b), let $f$ be $M$-Lipschitz. Then

$|f_{\tau}(\bm{x})-f_{\sigma}(\bm{x})|\leq\frac{1}{\pi^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}|f(\bm{x}+\tau\bm{u})-f(\bm{x}+\sigma\bm{u})|e^{-\|\bm{u}\|^{2}}d\bm{u}\leq
M|\tau-\sigma|\sqrt{\frac{d}{2}}.$ (A.11)

### Proof of Corollary 2.11

Let $f:\mathbb{R}^{d}\to\mathbb{R}$. By Lemma 2.7, we have that
$f_{\sigma}(\bm{x}^{\star}_{\sigma})\geq f(\bm{x}^{\star}).$ Suppose $f$ is
$L$-smooth and $\sigma\geq 0$. Since $\bm{x}^{\star}_{\sigma}$ minimizes
$f_{\sigma}$ then using Lemma 2.10, we have

$\displaystyle f_{\sigma}(\bm{x}^{\star}_{\sigma})-f(\bm{x}^{\star})\leq
f_{\sigma}(\bm{x}^{\star})-f(\bm{x}^{\star})\leq\frac{\sigma^{2}Ld}{4}.$
(A.12)

If $f$ is $M$-Lipschitz instead, Lemma 2.10 again gives

$\displaystyle f_{\sigma}(\bm{x}^{\star}_{\sigma})-f(\bm{x}^{\star})\leq
f_{\sigma}(\bm{x}^{\star})-f(\bm{x}^{\star})\leq M\sigma\sqrt{\frac{d}{2}}.$
(A.13)

##  Appendix B Proofs of main convergence results

### Proof of Theorem 3.1

Suppose $f$ is convex and $L$-smooth. Let $L^{1}_{k}=L$ for all
$k\in\mathbb{N}$. By Lemma 2.5, $f_{\sigma_{k}}$ is $L^{1}_{k}$-smooth for
each $k\in\mathbb{N}$. As such, we have

$\displaystyle\begin{split}f_{\sigma_{k+1}}(\bm{x}_{k+1})&\leq
f_{\sigma_{k+1}}(\bm{x}_{k})+\langle\nabla
f_{\sigma_{k+1}}(\bm{x}_{k}),\bm{x}_{k+1}-\bm{x}_{k}\rangle+\frac{1}{2}L^{1}_{k+1}\|\bm{x}_{k+1}-\bm{x}_{k}\|^{2}\\\
&=f_{\sigma_{k+1}}(\bm{x}_{k})-t\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}+\frac{1}{2}L^{1}_{k+1}t^{2}\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}\\\ &\leq
f_{\sigma_{k+1}}(\bm{x}_{k})-\frac{1}{2}t\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}\end{split}$ (B.1)

We can combine (B.1) with Lemma 2.10 to see that

$f_{\sigma_{k}}(\bm{x}_{k})\leq f_{\sigma_{k}}(\bm{x}_{k-1})\leq
f_{\sigma_{k-1}}(\bm{x}_{k-1})+L_{k}^{2}$ (B.2)

where $L_{k}^{2}=\frac{Ld}{4}\max(0,\sigma_{k}^{2}-\sigma_{k-1}^{2})$ is the
bound from Lemma 2.10.

Using Lemma 2.5, as $f$ is convex, so is $f_{\sigma_{k}}$ for every $k$. This
means for any $\bm{x}$

$f_{\sigma_{k}}(\bm{x}^{\star})\geq f_{\sigma_{k}}(\bm{x})+\langle\nabla
f_{\sigma_{k}}(\bm{x}),\bm{x}^{\star}-\bm{x}\rangle,$ (B.3)

which can be rewritten as

$f_{\sigma_{k}}(\bm{x})\leq f_{\sigma_{k}}(\bm{x}^{\star})+\langle\nabla
f_{\sigma_{k}}(\bm{x}),\bm{x}-\bm{x}^{\star}\rangle.$ (B.4)

Define $L^{3}_{k}$ as $\frac{Ld\sigma_{k}^{2}}{4}$, which is from Lemma 2.10.
Then, combining the above, we have the following:

$\displaystyle\begin{split}0&\stackrel{{\scriptstyle\text{Lem
\ref{lem:fsigmagreaterthanf}}}}{{\leq}}f_{\sigma_{k+1}}(\bm{x}_{k+1})-f(\bm{x}^{\star})\\\
&=f_{\sigma_{k+1}}(\bm{x}_{k+1})-f_{\sigma_{k+1}}(\bm{x}^{\star})+f_{\sigma_{k+1}}(\bm{x}^{\star})-f(\bm{x}^{\star})\\\
&\stackrel{{\scriptstyle\text{Lem
\ref{lem:differentsmoothingvalues}}}}{{\leq}}f_{\sigma_{k+1}}(\bm{x}_{k+1})-f_{\sigma_{k+1}}(\bm{x}^{\star})+L_{k+1}^{3}\\\
&\stackrel{{\scriptstyle(\ref{eqn:quickproof2})}}{{\leq}}f_{\sigma_{k+1}}(\bm{x}_{k})-\frac{1}{2}t\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}-f_{\sigma_{k+1}}(\bm{x}^{\star})+L_{k+1}^{3}\\\
&\stackrel{{\scriptstyle(\ref{eqn:quickproof1})}}{{\leq}}\langle\nabla
f_{\sigma_{k+1}}(\bm{x}_{k}),\bm{x}_{k}-\bm{x}^{\star}\rangle-\frac{1}{2}t\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}+L_{k+1}^{3}.\end{split}$ (B.5)

Now, repeating the computation done in the proof of gradient descent, we have
the following:

$\displaystyle\begin{split}f_{\sigma_{k+1}}(\bm{x}_{k+1})-f(\bm{x}^{\star})&\leq\langle\nabla
f_{\sigma_{k+1}}(\bm{x}_{k}),\bm{x}_{k}-\bm{x}^{\star}\rangle-\frac{1}{2}t\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}+L_{k+1}^{3}\\\
&=\frac{1}{2t}\left(\|\bm{x}_{k}-\bm{x}^{\star}\|^{2}-\|\bm{x}_{k+1}-\bm{x}^{\star}\|^{2}\right)+L_{k+1}^{3}\end{split}$
(B.6)

Summing over the steps:

$\displaystyle\begin{split}\sum_{i=0}^{k-1}\left(f_{\sigma_{i+1}}(\bm{x}_{i+1})-f(\bm{x}^{\star})\right)&\stackrel{{\scriptstyle(\ref{eqn:quickproof4})}}{{\leq}}\frac{1}{2t^{*}}\sum_{i=0}^{k-1}\left(\|\bm{x}_{i}-\bm{x}^{\star}\|^{2}-\|\bm{x}_{i+1}-\bm{x}^{\star}\|^{2}\right)+\sum_{i=0}^{k-1}L_{i+1}^{3}\\\
&\leq\frac{1}{2t}\|\bm{x}_{0}-\bm{x}^{\star}\|^{2}+\sum_{i=0}^{k-1}L_{i+1}^{3}\\\
\end{split}$ (B.7)

By (B.2), for $k>i\geq 1$ we have

$f_{\sigma_{k}}(\bm{x}_{k})\leq
f_{\sigma_{k-1}}(\bm{x}_{k-1})+L_{k}^{2}\leq\cdots\leq
f_{\sigma_{k-i}}(\bm{x}_{k-i})+\sum_{j=1}^{i}L_{k-j+1}^{2}.$ (B.8)

This means we have (where $t_{k}^{*}=t$)

$\displaystyle\begin{split}k\left(f_{\sigma_{k}}(\bm{x}_{k})-f(\bm{x}^{\star})\right)&=(f_{\sigma_{k}}(\bm{x}_{k})-f(\bm{x}^{\star}))+\sum_{i=1}^{k-1}(f_{\sigma_{k}}(\bm{x}_{k})-f(\bm{x}^{\star}))\\\
&=\sum_{i=1}^{k}(f_{\sigma_{i}}(\bm{x}_{i})-f(\bm{x}^{\star}))+\sum_{i=1}^{k-1}iL_{i+1}^{2}\\\
&\leq\frac{1}{2t_{k}^{*}}\|\bm{x}_{0}-\bm{x}^{\star}\|^{2}+\sum_{i=0}^{k-1}L_{i+1}^{3}+\frac{Ld}{4}\sum_{i=1}^{k-1}iL_{i+1}^{2}.\end{split}$
(B.9)

Finally, applying Lemma 2.7 and dividing by $k$,

$f(\bm{x}_{k})-f(\bm{x}^{\star})\leq
f_{\sigma_{k}}(\bm{x}_{k})-f(\bm{x}^{\star})\leq\frac{1}{2t_{k}^{*}k}\|\bm{x}_{0}-\bm{x}^{\star}\|^{2}+\frac{1}{k}\left(\sum_{i=1}^{k}L_{i}^{3}+\sum_{i=2}^{k}iL_{i}^{2}\right),$
(B.10)

which completes the proof.

######  Remark B.1 ($f$ is convex and $M$-Lipschitz).

The above proof holds for $M$-Lipschitz instead of $L$-smooth with the
following modifications:

  * (i)

replace $t$ with $t_{k+1}$ in equations (B.1), (B.5), and (B.6);

  * (ii)

define $t_{k}^{*}=\min\\{t_{i}|i\in\\{1,...,k\\}\\}$ and replace $t$ with
$t_{k}^{*}$ in equations (B.7), (B.9), and (B.10);

  * (iii)

Define $L^{1}_{k}=\frac{M\sqrt{2d}}{\sigma_{k}}$,
$L^{2}_{k}=M\sqrt{(\frac{d}{2})\max(0,\sigma_{k}^{2}-\sigma_{k-1}^{2})}$, and
$L^{3}_{k}=M\sigma_{k}\sqrt{\frac{d}{2}}$; and

  * (iv)

if $f$ is not differentiable at $\bm{x}_{k}$, then we require
$f_{\sigma_{k}}(\bm{x}_{k})-f(\bm{x}^{\star})$ on the left-hand-side of (3.2).

### Proof of Theorem 3.3

From the proof of Theorem 3.1, since $f$ is $L$-smooth (regardless of
convexity)

$f_{\sigma_{k+1}}(\bm{x}_{k+1})\leq
f_{\sigma_{k+1}}(\bm{x}_{k})-\frac{t}{2}\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}.$ (B.11)

As expected, this means $f_{\sigma_{k+1}}(\bm{x}_{k})\geq
f_{\sigma_{k+1}}(\bm{x}_{k+1})$.

For $k\geq 1$,

$\displaystyle\begin{split}\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2}&\leq\frac{2}{t}\Big{(}f_{\sigma_{k+1}}(\bm{x}_{k})-f_{\sigma_{k+1}}(\bm{x}_{k+1})\Big{)}\\\
&=\frac{2}{t}\Big{(}f_{\sigma_{k}}(\bm{x}_{k})-f_{\sigma_{k+1}}(\bm{x}_{k+1})\Big{)}+\frac{Ld}{2t}|\sigma_{k+1}^{2}-\sigma_{k}^{2}|.\end{split}$
(B.12)

This means that

$\displaystyle\begin{split}&k\min_{i=1,...,k}\|\nabla f(\bm{x}_{i})\|^{2}\\\
&\qquad\leq\sum_{i=1}^{k}\|\nabla f(\bm{x}_{i})\|^{2}\\\ &\qquad\leq
2\sum_{i=1}^{k}\|\nabla
f_{\sigma_{i+1}}(\bm{x}_{i})\|^{2}+\frac{L^{2}(6+d)^{3}}{4}\sum_{i=1}^{k}\sigma_{i+1}^{2}\\\
&\qquad\leq\frac{4}{t}\sum_{i=1}^{k}\big{(}f_{\sigma_{i}}(\bm{x}_{i})-f_{\sigma_{i+1}}(\bm{x}_{i+1})\big{)}+\frac{Ld}{2t}\sum_{i=1}^{k}|\sigma_{i+1}^{2}-\sigma_{i}^{2}|+\frac{L^{2}(6+d)^{3}}{4}\sum_{i=1}^{k}\sigma_{i+1}^{2}\end{split}$
(B.13)

using Lemma 4 from [38] on the second inequality. Dividing both sides by $k$
gives the result.

### Proof of Proposition 3.6

Let $f$ be $L$-smooth, so that $f_{\sigma}$ is smooth for any $\sigma\geq 0$.
We assume nothing about the convexity of $f$. From the proof of Theorem 3.3,
we have that

$\displaystyle\frac{1}{k}\sum_{i=1}^{k}\|\nabla f(\bm{x}_{i})\|^{2}$
$\displaystyle\leq\frac{1}{k}\left[\frac{4}{t}\big{(}f(\bm{x}_{0})-f(\bm{x}^{\star})\big{)}+\left(\frac{Ld}{t}+\frac{L^{2}(6+d)^{3}}{4}\right)\sum_{i=1}^{k+1}\sigma_{i}^{2}\right]$
(B.14)
$\displaystyle=O\left(\frac{1+d^{3}\sum_{i=1}^{k+1}\sigma_{i}^{2}}{k}\right).$
(B.15)

This means for at least some $j$, $\|\nabla f(x_{j})\|^{2}$ is at most the LHS
of (B.14). Hence, if $(\sigma_{i})_{i=1}^{\infty}\in l^{2}(\mathbb{R}^{+})$
and we want $\|\nabla f(x_{j})\|<\epsilon$, we need at least

$\frac{1}{\epsilon^{2}}\left[\frac{4}{t}\big{(}f(\bm{x}_{0})-f(\bm{x}^{\star})\big{)}+\left(\frac{Ld}{t}+\frac{L^{2}(6+d)^{3}}{4}\right)\sum_{i=1}^{k+1}\sigma_{i}^{2}\right]=O\left(\frac{1+d^{3}}{\epsilon^{2}}\right)$
(B.16)

iterations, which completes the proof.

### Proof of Lemma 4.1

First, we have

$\text{Var}(\bm{g}_{\sigma}(\bm{x};N))=\frac{1}{N^{2}}\text{Var}\left(\sum_{n=1}^{N}\delta_{\sigma}(\bm{x};\bm{u}_{n})\bm{u}_{n}\right)=\frac{1}{N}\text{Var}(\bm{g}_{\sigma}(\bm{x};1)).$
(B.17)

Second, since $E(\bm{g}_{\sigma}(\bm{x};1))=\nabla f_{\sigma}(\bm{x})$,

$\displaystyle\begin{split}\text{Var}(\bm{g}_{\sigma}(\bm{x};1))&=E\Big{(}\big{(}\bm{g}_{\sigma}(\bm{x};1)-\nabla
f_{\sigma}(\bm{x}))\big{)}\big{(}\bm{g}_{\sigma}(\bm{x};1)-\nabla
f_{\sigma}(\bm{x}))\big{)}^{T}\Big{)}\\\
&=E\big{(}\bm{g}_{\sigma}(\bm{x};1)\bm{g}_{\sigma}(\bm{x};1)^{T}\big{)}-\nabla
f_{\sigma}(\bm{x})\nabla f_{\sigma}(\bm{x})^{T}\\\
&=E\big{(}\delta_{\sigma}(\bm{x};\bm{u}_{1})^{2}\bm{u}_{1}\bm{u}_{1}^{T}\big{)}-\nabla
f_{\sigma}(\bm{x})\nabla f_{\sigma}(\bm{x})^{T}.\end{split}$ (B.18)

So,

$\text{tr}(\text{Var}(\bm{g}_{\sigma}(\bm{x};1)))=E\big{(}\delta_{\sigma}(\bm{x};\bm{u}_{1})^{2}\|\bm{u}_{1}\|^{2}\big{)}-\|\nabla
f_{\sigma}(\bm{x})\|^{2}$ (B.19)

Finally,

$\displaystyle\begin{split}E(\|\bm{g}_{\sigma}(\bm{x};N)\|^{2})&=\text{tr}(\text{Var}(\bm{g}_{\sigma}(\bm{x};N)))+\|\nabla
f_{\sigma}(\bm{x})\|^{2}\\\
&=\frac{1}{N}E\big{(}\delta_{\sigma}(\bm{x};\bm{u}_{1})^{2}\|\bm{u}_{1}\|^{2}\big{)}+\left(1-\frac{1}{N}\right)\|\nabla
f_{\sigma}(\bm{x})\|^{2}.\end{split}$ (B.20)

### Proof of Theorem 4.2

This proof is a modification of the proof of Theorem 3.3.

First, if $\bm{x}\in\mathbb{R}^{d}$, $\sigma>0$, and
$\bm{x}^{\prime}=\bm{x}-t\bm{g}_{\sigma}(\bm{x};N)$, then since $f$ is
$L$-smooth

$\displaystyle\begin{split}f_{\sigma}(\bm{x}^{\prime})&\leq
f_{\sigma}(\bm{x})+\langle\nabla
f_{\sigma}(\bm{x}),\bm{x}^{\prime}-\bm{x}\rangle+\frac{L}{2}\|\bm{x}^{\prime}-\bm{x}\|^{2}\\\
&\leq f_{\sigma}(\bm{x})-t\langle\nabla
f_{\sigma}(\bm{x}),\bm{g}_{\sigma}(\bm{x};N)\rangle+\frac{Lt^{2}}{2}\|\bm{g}_{\sigma}(\bm{x};N)\|^{2}.\end{split}$
(B.21)

The expected value of the inner product in the second term is given by

$E(\langle\nabla
f_{\sigma}(\bm{x}),\bm{g}_{\sigma}(\bm{x};N)\rangle)=\langle\nabla
f_{\sigma}(\bm{x}),E(\bm{g}_{\sigma}(\bm{x};N))\rangle=\|\nabla
f_{\sigma}(\bm{x})\|^{2}.$ (B.22)

This means

$\displaystyle\begin{split}E(f_{\sigma}(\bm{x}^{\prime}))&\leq
f_{\sigma}(\bm{x})-tE(\langle\nabla
f_{\sigma}(\bm{x}),\bm{g}_{\sigma}(\bm{x};N)\rangle)+\frac{Lt^{2}}{2}E(\|\bm{g}_{\sigma}(\bm{x};N)\|^{2})\\\
&\leq f_{\sigma}(\bm{x})-t\|\nabla
f_{\sigma}(\bm{x})\|^{2}+\frac{Lt^{2}}{2}E(\|\bm{g}_{\sigma}(\bm{x};N)\|^{2}).\end{split}$
(B.23)

Applying the Lemma 4.1 shows

$\displaystyle\begin{split}E(f_{\sigma}(\bm{x}^{\prime}))&\leq
f_{\sigma}(\bm{x})-t\|\nabla
f_{\sigma}(\bm{x})\|^{2}+\frac{Lt^{2}}{2}E(\|\bm{g}_{\sigma}(\bm{x};N)\|^{2})\\\
&\leq f_{\sigma}(\bm{x})-\frac{t}{2}\|\nabla
f_{\sigma}(\bm{x})\|^{2}+\frac{Lt^{2}}{2N}E(\delta_{\sigma}(\bm{x};\bm{u})^{2}\|\bm{u}\|^{2}).\end{split}$
(B.24)

Rearranging gives

$\displaystyle\begin{split}\|\nabla
f_{\sigma}(\bm{x})\|^{2}&\leq\frac{2}{t}E\left(f_{\sigma}(\bm{x})-f_{\sigma}(\bm{x}^{\prime})\right)+\frac{Lt}{N}E(\delta_{\sigma}(\bm{x};\bm{u})^{2}\|\bm{u}\|^{2}).\end{split}$
(B.25)

Applying this to our gradient descent sequence, we have

$\displaystyle\begin{split}E(\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2})&\leq\frac{2}{t}E(f_{\sigma_{k+1}}(\bm{x}_{k})-f_{\sigma_{k+1}}(\bm{x}_{k+1}))+\frac{Lt}{N}E(\delta_{\sigma_{k+1}}(\bm{x}_{k};\bm{u})^{2}\|\bm{u}\|^{2}).\end{split}$
(B.26)

Applying Lemma 2.10

$E(\|\nabla
f_{\sigma_{k+1}}(\bm{x}_{k})\|^{2})\leq\frac{2}{t}E(f_{\sigma_{k}}(\bm{x}_{k})-f_{\sigma_{k+1}}(\bm{x}_{k+1}))\\\
+\frac{Lt}{N}E(\delta_{\sigma_{k+1}}(\bm{x}_{k};\bm{u})^{2}\|\bm{u}\|^{2})+\frac{Ld}{2t}|\sigma_{k+1}^{2}-\sigma_{k}^{2}|.$
(B.27)

From [38, Lemma 4], we have that

$\|\nabla f(\bm{x})\|^{2}\leq 2\|\nabla
f_{\sigma}(\bm{x})\|^{2}+\frac{\sigma^{2}L^{2}(d+3)^{3}}{16}.$ (B.28)

Combining this with our computation gives

$E(\|\nabla
f(\bm{x}_{k})\|^{2})\leq\frac{4}{t}E(f_{\sigma_{k}}(\bm{x}_{k})-f_{\sigma_{k+1}}(\bm{x}_{k+1}))+\frac{2Lt}{N}E(\delta_{\sigma_{k+1}}(\bm{x}_{k};\bm{u})^{2}\|\bm{u}\|^{2})\\\
+\frac{Ld}{t}|\sigma_{k+1}^{2}-\sigma_{k}^{2}|+\frac{\sigma_{k+1}^{2}L^{3}t(d+3)^{3}}{16N}.$
(B.29)

From Theorem 4 of [38], we have that for any $\bm{x}$

$E(\delta_{\sigma}(\bm{x};\bm{u})^{2}\|\bm{u}\|^{2})\leq\frac{L^{2}\sigma^{2}(d+6)^{3}}{16}+(d+4)\|\nabla
f(\bm{x})\|^{2}.$ (B.30)

This means

$E(\|\nabla
f(\bm{x}_{k})\|^{2})\leq\frac{4}{t}E(f_{\sigma_{k}}(\bm{x}_{k})-f_{\sigma_{k+1}}(\bm{x}_{k+1}))+\frac{L^{3}\sigma_{k+1}^{2}t(d+6)^{3}}{8N}\\\
+\frac{2Lt(d+4)}{N}E(\|\nabla
f(\bm{x}_{k})\|^{2})+\frac{Ld}{t}|\sigma_{k+1}^{2}-\sigma_{k}^{2}|+\frac{\sigma_{k+1}^{2}L^{3}t(d+3)^{3}}{16N}.$
(B.31)

So, with $\sigma_{0}=0$,

$k\left(1-\frac{2Lt(d+4)}{N}\right)\min_{i=0,...,k-1}E(\|\nabla
f(\bm{x}_{i})\|^{2})\leq\frac{4}{t}(f(\bm{x}_{0})-f_{\sigma_{k}}(\bm{x}_{k}))\\\
+\left(\frac{L^{3}t(d+6)^{3}}{8N}+\frac{L^{3}t(d+3)^{3}}{16N}\right)\sum_{i=1}^{k}\sigma_{i}^{2}+\frac{Ld}{t}\sigma_{1}^{2}+\frac{Ld}{t}\sum_{i=2}^{k}|\sigma_{i}^{2}-\sigma_{i-1}^{2}|.$
(B.32)

If $\frac{1}{2L(d+4)}>t$ and $N\geq 1$, then $1-\frac{2Lt(d+4)}{N}>0$. In
which case, after dividing by $k$,

$\min_{i=0,...,k-1}E(\|\nabla
f(\bm{x}_{i})\|^{2})\leq\frac{1}{k}\left(\frac{N}{N-2Lt(d+4)}\right)\Bigg{(}\frac{4(f(\bm{x}_{0})-f_{\sigma_{k}}(\bm{x}_{k}))}{t}\\\
+\left(\frac{L^{3}t(d+6)^{3}}{4N}+\frac{2Ld}{t}\right)\sum_{i=1}^{k}\sigma_{i}^{2}\Bigg{)}$
(B.33)

## References

  * [1] Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina.  Local entropy as a measure for sampling solutions in constraint satisfaction problems.  Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023301, 2016.
  * [2] Andrew Blake and Andrew Zisserman.  Visual reconstruction.  MIT press, 1987.
  * [3] R. E. Caflisch.  Monte Carlo and quasi-Monte Carlo methods.  Acta numerica, 1-49, Cambridge Univ. Press, 1998.
  * [4] Tingfeng Cao, Liang Chen, Dixiang Zhang, Tianxiang Sun, Zhengfu He, Xipeng Qiu, Xing Xu, and Hai Zhang.  Competition for gradient-free tuning of large language models: approaches, results, current challenges and future directions.  National Science Review, 10(6):nwad124, 05 2023.
  * [5] Pratik Chaudhari, Adam Oberman, Stanley Osher, Stefano Soatto, and Guillaume Carlier.  Deep relaxation: partial differential equations for optimizing deep neural networks.  Research in the Mathematical Sciences, 5:1–30, 2018.
  * [6] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E Turner, and Adrian Weller.  Structured evolution with compact architectures for scalable policy optimization.  International Conference on Machine Learning, pages 969–977, 2018\.
  * [7] Xiaodong Cui, Wei Zhang, Zoltán Tüske, and Michael Picheny.  Evolutionary stochastic gradient descent for optimization of deep neural networks.  NeurIPS, 2018.
  * [8] Anton Dereventsov, Clayton G Webster, and Joseph Daws.  An adaptive stochastic gradient-free approach for high-dimensional blackbox optimization.  In Proceedings of International Conference on Computational Intelligence: ICCI 2020, pages 333–348. Springer, 2022.
  * [9] John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono.  Optimal rates for zero-order convex optimization: The power of two function evaluations.  IEEE Transactions on Information Theory, 61(5):2788–2806, 2015\.
  * [10] Lawrence C Evans.  Partial differential equations, volume 19.  American Mathematical Society, 2010.
  * [11] Maryam Fazel, Rong Ge, Sham M Kakade, and Mehran Mesbahi.  Global convergence of policy gradient methods for the linear quadratic regulator.  Proceedings of the 35th International Conference on Machine Learning, 80:1467–01476, 2018.
  * [12] G.S. Fishman.  Monte Carlo.  Springer Series in Operations Research. Springer-Verlag, New York, 1996\.  Concepts, algorithms, and applications.
  * [13] M. Gunzburger, C. G. Webster, and G. Zhang.  Stochastic finite element methods for partial differential equations with random input data.  Acta Numerica, 23:521–650, 2014.
  * [14] N. Hansen.  The CMA evolution strategy: A tutorial.  arXiv preprint arXiv:1604.00772, 2016.
  * [15] Nikolaus Hansen.  The CMA evolution strategy: a comparing review.  In Towards a new evolutionary computation, pages 75–102. Springer, 2006.
  * [16] Nikolaus Hansen and Andreas Ostermeier.  Completely derandomized self-adaptation in evolution strategies.  Evolutionary computation, 9(2):159–195, 2001.
  * [17] Elad Hazan, Kfir Yehuda Levy, and Shai Shalev-Shwartz.  On graduated optimization for stochastic non-convex problems.  In International conference on machine learning, pages 1833–1841. PMLR, 2016.
  * [18] J. B. Heaton, N. G. Polson, and J. H. Witte.  Deep learning for finance: deep portfolios.  Applied Stochastic Models in Business and Industry, 33(1):3–12, 2017.
  * [19] Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky.  Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.  http://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf, 2012\.
  * [20] Hidenori Iwakiri, Yuhang Wang, Shinji Ito, and Akiko Takeda.  Single loop gaussian homotopy method for non-convex optimization.  Advances in Neural Information Processing Systems, 35:7065–7076, 2022.
  * [21] Chi Jin, Lydia T Liu, Rong Ge, and Michael I Jordan.  On the local minima of the empirical risk.  Advances in neural information processing systems, 31, 2018.
  * [22] Shauharda Khadka, Somdeb Majumdar, Tarek Nassar, Zach Dwiel, Evren Tumer, Santiago Miret, Yinyin Liu, and Kagan Tumer.  Collaborative Evolutionary Reinforcement Learning.  Proceedings of the 36th International Conference on Machine Learning, 2019.
  * [23] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [24] Lisa Maria Kreusser, Stanley J Osher, and Bao Wang.  A deterministic gradient-based approach to avoid saddle points.  European Journal of Applied Mathematics, pages 1–20, 2022.
  * [25] Jeffrey Larson, Matt Menickelly, and Stefan M. Wild.  Derivative-free optimization methods.  Acta Numerica, 28:287–404, 2019.
  * [26] Guoqing Liu, Li Zhao, Feidiao Yang, Jiang Bian, Tao Qin, Nenghai Yu, and Tie-Yan Liu.  Trust region evolution strategies.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4352–4359, 2019.
  * [27] Yue Liu, Tianlu Zhao, Wangwei Ju, and Siqi Shi.  Materials discovery and design using machine learning.  Journal of Materiomics, 3(3):159–177, 2017.  High-throughput Experimental and Modeling Research toward Advanced Batteries.
  * [28] Alvaro Maggiar, Andreas Wachter, Irina S Dolinskaya, and Jeremy Staum.  A derivative-free trust-region algorithm for the optimization of functions smoothed via gaussian convolution using adaptive multiple importance sampling.  SIAM Journal on Optimization, 28(2):1478–1507, 2018.
  * [29] Hossein Mobahi.  Closed form for some gaussian convolutions.  arXiv preprint arXiv:1602.05610, 2016.
  * [30] Hossein Mobahi.  Training recurrent neural networks by diffusion.  arXiv preprint arXiv:1601.04114, 2016.
  * [31] Hossein Mobahi and John W Fisher.  On the link between gaussian homotopy continuation and convex envelopes.  In Energy Minimization Methods in Computer Vision and Pattern Recognition: 10th International Conference, EMMCVPR 2015, Hong Kong, China, January 13-16, 2015. Proceedings 10, pages 43–56. Springer, 2015.
  * [32] Hossein Mobahi and John Fisher III.  A theoretical analysis of optimization by gaussian continuation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
  * [33] Hossein Mobahi and Yi Ma.  Gaussian smoothing and asymptotic convexity.  Coordinated Science Laboratory Report no. UILU-ENG-12-2201, DC-254, 2012.
  * [34] Hossein Mobahi, C Lawrence Zitnick, and Yi Ma.  Seeing through the blur.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 1736–1743. IEEE, 2012.
  * [35] Gregory Morse and Kenneth O. Stanley.  Simple evolutionary optimization can rival stochastic gradient descent in neural networks.  Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016), page 477–484, 2016.
  * [36] Y. Nesterov and V. Spokoiny.  Random gradient-free minimization of convex functions.  Foundations of Computational Mathematics, pages 1–40, 2015.
  * [37] Yurii Nesterov.  Introductory Lectures on Convex Optimization.  Springer US, 2004.
  * [38] Yurii Nesterov and Vladimir Spokoiny.  Random gradient-free minimization of convex functions.  Foundations of Computational Mathematics, 17(2):527–566, 2017.
  * [39] Jorge Nocedal and Stephen J Wright.  Numerical optimization.  Springer, 1999.
  * [40] Stanley Osher, Bao Wang, Penghang Yin, Xiyang Luo, Farzin Barekat, and Minh Pham.  Laplacian smooth gradient descent.  arXiv preprint arXiv:1806.06317, 2018.
  * [41] Stanley Osher, Bao Wang, Penghang Yin, Xiyang Luo, Farzin Barekat, Minh Pham, and Alex Lin.  Laplacian smoothing gradient descent.  Research in the Mathematical Sciences, 9(3):55, 2022.
  * [42] Luis Miguel Rios and Nikolaos V. Sahinidis.  Derivative-free optimization: a review of algorithms and comparison of software implementations.  J Glob Optim, 56:1247–1293, 2009.
  * [43] Levent Sagun, Leon Bottou, and Yann LeCun.  Eigenvalues of the hessian in deep learning: Singularity and beyond.  arXiv preprint arXiv:1611.07476, 2016.
  * [44] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever.  Evolution strategies as a scalable alternative to reinforcement learning.  arXiv preprint arXiv:1703.03864, 2017.
  * [45] Olivier Sigaud and Freek Stulp.  Robot skill learning: From reinforcement learning to evolution strategies.  Paladyn Journal of Behavioral Robotics, 4(1):49–61, 2013.
  * [46] F. P. Such, V. Madhavan, E. Conti, J. Lehman, K. O. Stanley, and J. Clune.  Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning.  arXiv preprint arXiv:1712.06567, 2017.
  * [47] Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuanjing Huang, and Xipeng Qiu.  BBTv2: Towards a gradient-free future with large language models.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 3916–3930, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
  * [48] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton.  On the importance of initialization and momentum in deep learning.  In International conference on machine learning, pages 1139–1147. PMLR, 2013.
  * [49] Van-Dai Ta, CHUAN-MING Liu, and Direselign Addis Tadesse.  Portfolio optimization-based stock prediction using long-short term memory network in quantitative trading.  Applied Sciences, 10(2), 2020.
  * [50] Hoang Tran, Qiang Du, and Guannan Zhang.  Convergence analysis for a nonlocal gradient descent method via directional gaussian smoothing, 2023.
  * [51] Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jurgen Schmidhuber.  Natural evolution strategies.  Journal of Machine Learning Research, 15:949–980, 2014.
  * [52] Junjie Zhan, Jing Li, Pai Liu, and Yangjun Luo.  A gradient-free topology optimization strategy for continuum structures with design-dependent boundary loads.  Symmetry, 13(11), 2021.
  * [53] Jiaxin Zhang, Sirui Bi, and Guannan Zhang.  A directional gaussian smoothing optimization method for computational inverse design in nanophotonics.  Materials & Design, 197:109213, 2021.
  * [54] Jiaxin Zhang, Hoang Tran, Dan Lu, and Guannan Zhang.  A novel evolution strategy with directional gaussian smoothing for blackbox optimization.  arXiv preprint arXiv:2002.03001, 2020.
  * [55] Jiaxing Zhang, Hoang Tran, and Guannan Zhang.  Accelerating reinforcement learning with a directional-gaussian-smoothing evolution strategy.  arXiv preprint arXiv:2002.09077, 2020.
  * [56] Yuchen Zhang, Percy Liang, and Moses Charikar.  A hitting time analysis of stochastic gradient langevin dynamics.  In Conference on Learning Theory, pages 1980–2022. PMLR, 2017.
  * [57] Zhong-Qiu Zhao, Peng Zheng, Shou tao Xu, and Xindong Wu.  Object detection with deep learning: A review, 2019.