Convex Optimization with Nonconvex Oracles
Oren Mangoubi1 and Nisheeth K. Vishnoi2

arXiv:1711.02621v1 [] 7 Nov 2017

1,2

École Polytechnique Fédérale de Lausanne (EPFL), Switzerland

November 8, 2017

Abstract
In machine learning and optimization, one often wants to minimize a convex objective function F but can only evaluate a noisy approximation F̂ to it. Even though F is convex, the
noise may render F̂ nonconvex, making the task of minimizing F intractable in general. As a
consequence, several works in theoretical computer science, machine learning and optimization
have focused on coming up with polynomial time algorithms to minimize F under conditions
on the noise F (x) − F̂ (x) such as its uniform-boundedness, or on F such as strong convexity.
However, in many applications of interest these conditions do not hold. Here we show that, if
the noise has magnitude αF (x) + β for some α, β > 0, then there is a polynomial time algorithm to find an approximate minimizer of F . In particular, our result allows for unbounded
noise and generalizes those of [1, 17] who proved similar results for the bounded noise case, and
that of [2] who assume that the noise grows in a very specific manner and that F is strongly
convex. Turning our result on its head, one may also view our algorithm as minimizing a nonconvex function F̂ that is promised to be related to a convex function F as above. Technically,
Markov chains, such as the stochastic gradient Langevin dynamics, are deployed to arrive at
approximate solutions to these optimization problems. For the class of noise we consider, no
single temperature allows such a Markov chain to both mix quickly and concentrate near the
global minimizer. Consequently, our algorithm, which is a “simulated annealing” modification
of the stochastic gradient Langevin dynamics, gradually decreases the temperature of the chain
to approach the global minimizer. Analyzing such an algorithm for the unbounded noise model
and a general convex function turns out to be challenging and requires several technical ideas
that might be of independent interest in deriving non-asymptotic bounds for other simulated
annealing based algorithms.

1

Contents
1 Introduction
1.1 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Short summary of techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Organization of the rest of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
5
6
7

2 Overview of Our Contributions

9

3 Preliminaries
3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Assumptions on the convex objective function and the constraint set . . . . . . . . .
3.3 A smoothed oracle from a non-smooth one . . . . . . . . . . . . . . . . . . . . . . . .

15
15
15
15

4 Our Contribution
16
4.1 Our Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Statement of Our Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5 Proofs
5.1 Assumptions about the smooth oracle . . . . . . . . . .
5.2 Conductance and bounding the Cheeger constant . . . .
5.3 Bounding the escape probability . . . . . . . . . . . . .
5.4 Comparing noisy functions . . . . . . . . . . . . . . . . .
5.5 Bounding the error and running time: The smooth case
5.6 The non-smooth case . . . . . . . . . . . . . . . . . . . .
5.7 Rounding the domain of the Markov Chain . . . . . . .
5.8 Proof of Main Result (Theorem 4.1) . . . . . . . . . . .

2

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

17
17
18
20
24
24
30
32
33

1

Introduction

A general problem that arises in machine learning, computational mathematics and optimization
is that of minimizing a convex objective function F : K → R, where K ⊆ Rd is convex, and one can
only evaluate F approximately. Let F̂ denote this “noisy” approximation to F . In this setting, even
though the function F is convex, we can no longer assume that F̂ is convex. However, if one does
not make any assumptions on the noise function, the problem of minimizing F can be shown to be
arbitrarily hard. Thus, in order to obtain algorithms for minimizing F with provable guarantees,
one must place some restrictions on the noise function.
A widely studied setting is that of “additively” bounded noise. Here, the noise N (x) := F (x) −
F̂ (x) is assumed to have a uniform bound on K: supx∈K |N (x)| ≤ β for some β ≥ 0. This model
was first considered by Applegate and Kannan in [1] and has received attention in a recent work
of Zhang, Liang and Charikar [17].
In practice, however, the strongest bound we might have for the noise may not be uniform
on K. One such noise model is that of “multiplicative” noise where one assumes that F̂ (x) =
F (x)(1 + ψ(x)), where |ψ(x)| ≤ α for all x ∈ K and some α ≥ 0. In other words, N (x) =
F̂ (x) − F (x) = F (x) × ψ(x), which motivates the name. One situation where multiplicative noise
arises is when F decomposes into a sum of functions that are easier to compute, but these component
functions are computed via Monte Carlo integration with stopping criteria that depend on the
computed value of the component function [5].1 For other natural settings where multiplicative
noise arises see [6, 9, 10].
More generally, one can model the noisy F̂ by decomposing it into additive and multiplicative
components, in the following sense:
Definition 1.1. We say that F̂ has both additive and multiplicative noise of levels (β, α) if there
exist functions ϕ : K → R and ψ : K → R and α, β ≥ 0 with |ϕ(x)| ≤ β and |ψ(x)| ≤ α for all
x ∈ K such that
F̂ (x) = F (x)(1 + ψ(x)) + ϕ(x)

∀x ∈ K.

(1)

To motivate this definition, we consider the problem of solving a system of noisy linear or nonlinear
black-box equations where one wishes to find a value of x such that hi (x) = 0 for each component
function hi [6]. Since each equation hi (x) = 0 must be satisfied simultaneously for a single value of
x, it is not enough to solve each equation individually. One way in which we may solve this system
of equations is by minimizing an objective function of the form
n

F (x) =

1X
(hi (x))2
n

(2)

i=1

since any value of x that minimizes F (x) also solves the system of equations hi (x) = 0 for every i,
provided that such a solution exists. In practice, rather than having access to an exact computation
oracle of hi (x) one may instead only have access to a perturbed function
ĥi (x) = hi (x) + Ni (x).
1

Note that a function with additive noise of level β can instead be modeled as having multiplicative noise of level
β if we replace the objective function F (x) with F (x) − F (x? ) + β and the corresponding noisy function F̂ (x) with
F̂ (x) − F (x? ) + β, where x? is the unique minimizer of F . Conversely, if an objective function F is bounded on its
domain K and its corresponding noisy function F̂ has multiplicative noise of level α, then the noise can instead be
modeled with the additive noise model, with additive noise of level β = α × supx∈K |F (x)|. Nevertheless, even though
it may be possible to represent a noisy function as either having additive or multiplicative noise of finite level, the
bound on the noise function N (x) implied by the noise model is different depending on the model we use.

3

Here Ni (x) is a noise term that may have additive or multiplicative noise (or both), that is, |Ni (x)| ≤
b + ahi (x) for some a, b ≥ 0. Hence, instead of minimizing Equation (2), one must try to minimize
a noisy function of the form
n

F̂ (x) =

1X
(ĥi (x))2 .
n

(3)

i=1

A straightforward calculation shows that the fact that |Ni (x)| ≤ b + ahi (x) for all i implies that
1
|F̂ (x) − F (x)| ≤ (2a + a2 + 2b + 2ab)F (x) + (b + ab) + b2 .
2
Thus, F̂ can be modeled as having additive noise of level β = 12 (b + ab) + b2 together with multiplicative noise of level α = 2a + a2 + 2b + 2ab. In particular, even if each component function only
has additive noise (that is, if a = 0), F̂ will still have nonzero multiplicative noise α = 2b. Thus we
arrive at the following general problem.
Problem 1. Let K ⊆ Rd be a convex body and F : K → R be a convex function. Let x? be a
minimizer of F in K. Given access to a noisy oracle F̂ for F that has additive and multiplicative
noise of levels (β, α). The problem is to find an approximate minimizer x̂ for F such that F (x̂) −
F (x? ) ≤ ε̂ for a given ε̂ > 0.
This problem was first studied (indirectly) by Applegate and Kannan [1] in the special case of
additive noise where α = 0. Specifically, they studied the related problem of sampling from the
canonical distribution
1
e−ξF̂ (x)
R
−ξ
F̂
(y)
dy
Ke
when F̂ is an additively noisy version of a convex function. Roughly, their algorithm discretized
K with a grid and ran a simple random walk on this grid. Using their Markov chain one can
solve Problem 1 in the special case of α = 0 for some error ε̂ = Õ(dβ) with running time that is
polynomial in d and various other parameters as well.
Recently, in Belloni et al. [2], Problem 1 was studied in a special case where the noise decreases to
zero near the global minimum2 and F is m-strongly convex. Specifically, they study the situation
where the noise is bounded by |N (x)| ≤ ckx − x? kp , for some 0 < p < 2 and some c > 0.
Roughly speaking, in this regime they show that one can obtain an approximate minimizer x̂
1
such that F (x̂) − F (x? ) ≤ O(( md ) 2−p ) in polynomial time. To find an approximate minimizer x̂,
they repeatedly run a simulated annealing Markov chain based on the “hit-and-run” algorithm.
They state that they are “not aware of optimization methods for such a problem” outside of their
work, and that “it is rather surprising that one may obtain provable guarantees through simulated
annealing” under noise with non-uniform bounds even in the special case of strong convexity.
Very recently, Problem 1 was also studied by Zhang, Liang and Charikar [17] in the special case
of additive noise (where α = 0 but β ≥ 0). The main component of their algorithm is the stochastic
gradient Langevin dynamics (SGLD) Markov chain that runs at a fixed “temperature” parameter
to find an approximate minimizer x̂. In particular, they show that one can solve Problem 1 in the
special case of α = 0 for some error ε̂ = Õ(dβ) with running time that is polynomial in d and β
and various smoothness parameters.
2

The authors of [2] also study separately the special case of purely additive noise, but not simultaneously in the
presence of a non-uniformly bounded noise component.

4

Extending these results to the general case when both α, β > 0, and F is not necessarily strongly
convex, has been an important and challenging problem. The difficulty arises from the fact that, in
this setting, the noise can become unbounded and the prior Markov chain approaches do not seem
to work. Roughly, the Markov chains of [1, 17] run at a fixed temperature and, due to the fact that
the noise can be very different at different levels of F , would either get stuck in local minimum
or never come close to the minimzer; see Figure 2 for an illustration. The Markov chain of [2] on
the other hand varies the temperature but the strong convexity of F makes the task of estimating
progress significantly simpler.

1.1

Our contributions

The main result of this paper is the first polynomial time algorithm that solves Problem 1 when
α, β > 0 without assuming that F is strongly convex. Our algorithm combines simulated annealing
(as in [2]) with the stochastic gradient Langevin dynamics (as in [17]). We assume that k∇F k ≤ λ
and that K is contained in a bounding ball of radius R > 0, and that K = K0 + B(0, r0 ) for some
r0 > 0, where “+” denotes the Minkowski sum. Note that, given bounds λ and R, one can deduce
an upper bound of λR on the value of F in K.
Theorem 1.2. [Informal; see Section 4.2 for a formal description] For any desired accuracy
level ε̂, additive noise level β = O(ε̂), and a multiplicative noise level α that is a sufficiently small
constant, there exists an algorithm that solves Problem 1 and outputs x̂ with high probability such
that F (x̂) − F (x? ) ≤ ε̂. The running time of the algorithm is polynomial in d, R, 1/r0 , and λ,
whenever α ≤ Õ( d1 ) and β ≤ Õ( dε̂ ).
In particular, our theorem recovers the result of [17] in the special case of no multiplicative noise
(α = 0). Importantly, when the multiplicative noise coefficient satisfies α ≤ Õ( d1 ), then one can
obtain an approximate minimizer x̂ such that F (x̂)−F (x? ) ≤ ε̂ for arbitrarily small ε̂ in polynomial
time. More generally, in the case where α ≤ Õ( d1 ) or β ≤ Õ( dε̂ ) may not be satisfied, then the
dβ

running time of our algorithm is roughly bounded by edα+ ε̂ .
The requirement that β ≤ Õ( dε̂ ) in order to get a polynomial running time can be shown to be
necessary using results from [3] (as done in [17]). If the additive noise β was required to be any
lower than Ω( dε̂ ), the algorithm would take an exponentially long time to escape the local minima
(Figure 1). We believe that the requirement that α ≤ Õ( d1 ) in order to get a polynomial running
time is also tight for a similar reason. This is because a sub-level set U of F of s height ε̂, i.e.,
U = {x ∈ K : F (x) ≤ ε̂}, will have a uniform bound on the noise of size supx∈U αF (x) ≤ αε̂ in the
presence of multiplicative noise of level α. This is equivalent to having additive noise of level Õ( dε̂ ),
which is required for the Markov chain to quickly escape the local minima of that sub-level set.
Establishing this formally is an interesting open problem. While our algorithm’s running time is
polynomial in various parameters, we believe that it is not tight and can be improved with a more
thorough analysis of the underlying Markov chain, perhaps using tools developed in [12]. In [17] a
version of Problem 1 is solved for a class of nonconvex functions F in the special case that α = 0
(i.e., only additive noise). It would therefore be interesting to see if we can solve Problem 1 for
this class of nonconvex functions F but under the more general noise model where we have both
additive and multiplicative noise. Finally, we note the following interpretation of our main result for
nonconvex functions: Suppose we are given oracle access to a nonconvex function F̂ with a promise
that there is a convex function F and functions ψ and ϕ such that F̂ (x) = F (x)(1 + ψ(x)) + ϕ(x)
(as in Definition 1.1), then there is an algorithm to minimize F̂ .

5

U F (x

U F (x

)+d

)+

x⇤

x

Figure 1: The local minimum at x◦ has “depth” β so, roughly speaking, there is a path of maximum
elevation F̂ (x◦ ) + β between it and the neighboring minimum at x? (which happens to be the global
◦
minimum in this example). However, the sub-level set U F̂ (x )+β has a very narrow bottleneck, so it
will take a long time for a Markov chain running at temperature β to escape the region of attraction
◦
around the local minimum at x◦ . On the other hand, the sub-level set U F̂ (x )+dβ does not have
a narrow bottleneck, so a Markov chain running at temperature dβ will quickly escape the local
minimum x◦ .

1.2

Short summary of techniques

To find an approximate global minimum of the objective function F , we must try to find an
approximate global minimum of the noisy approximation F̂ . One method of optimizing a nonconvex
or approximately convex function F̂ is to generate a Markov chain with stationary distribution
approximating the canonical distribution
1

π̂ (ξ) (x) := R
K

e−ξF̂ (y) dy

e−ξF̂ (x) ,

where ξ is thought of as an “inverse temperature” parameter. If the “temperature” ξ −1 is small,
then π̂ (ξ) concentrates near the global minima of F̂ . On the other hand, to escape local minima of
“depth” β > 0 in polynomial time, one requires the temperature ξ −1 to be at least Ω(β) (Figure
1). Now consider the random variable Z ∼ N (0, ξ −1 Id ) with
π (ξ) (x) := R

Rd

1
e

−ξ 12 kyk2

1

dy

2

e−ξ 2 kxk .

Then F (Z) concentrates near dξ −1 with high probability. This suggests that for a noisy function
F̂ where we are given a bound on the additive noise of level β > 0, the best we can hope to achieve
in polynomial time is to find a point x̂ such that
|F (x̂) − F (x? )| ≤ Õ(dβ),
since there may be sub-optimal local minima in the vicinity of x? that have depth O(β), requiring
the temperature ξ −1 to be at least Ω(β) (Figure 1).
6

As mentioned earlier, optimization of a noisy function under additive noise is studied in [17],
who analyze the stochastic gradient Langevin dynamics (SGLD) Markov chain. The SGLD chain
approximates the Langevin diffusion, which has stationary distribution π̂ (ξ) . They show that by
running SGLD at a single fixed temperature ξ one can obtain an approximate global minimizer x̂
of F such that |F (x̂) − F (x? )| < Õ(ε̂) with high probability with running time that is polynomial in
d, edβ/ε̂ , and various smoothness bounds on F . In particular, for the algorithm to get a polynomial
running time in d and β one must choose ε̂ = Ω(dβ). Thus, the SGLD algorithm returns an
approximate minimizer such that |F (x̂) − F (x? )| ≤ Õ(dβ) in polynomial time in the additive case.
More generally, if multiplicative noise is present one may have many local minima of very
different sizes, so our bound on the “depth” of the local minima is not uniform over K. In this case
the approach from [17] of using a single fixed temperature will lead to either a very long running
time or a very large error ε̂: If the temperature is hot enough to escape even the deepest the local
minima, then the Markov chain will not concentrate near the global minimum and the error ε̂
will be large (Figure 2(b)). If the temperature is chosen to be too cold, then the algorithm will
take a very long time to escape the deeper local minima (Figure 2(c)). Instead of using a fixed
temperature, we search for the global minimum by starting the Markov chain at a high temperature
and then slowly lowering the temperature at each successive step of the chain (Figure 2(d)). This
approach is referred to as “simulated annealing” in the literature [11].
The only non-asymptotic analysis we are aware of where the bound on the noise is not uniform
involves a simulated annealing technique based on the hit-and-run algorithm [2]. Specifically, the
authors of [2] show that if F is m-strongly convex, then one can compute an approximate global
1
minimizer x̂ such that |F (x̂) − F (x? )| < ( md ) 2−p with running time Õ(d4.5 ), as long as N (x) ≤ ckxkp
for some 0 < p < 2 and some c > 0. The algorithm used in [2] runs a sequence of subroutine Markov
chains. Each of these subroutine Markov chains is restricted to a ball B(yk , rk ) centered at the
point yk returned by the subroutine chain from the last epoch. Crucially, for this algorithm to
work, rk must be chosen such that B(yk , rk ) contains the minimizer x? at each epoch k. Towards
this end, the authors of [2] show that since the temperature is decreased at each epoch, F (yk ) is
much smaller than F (yk−1 ) at each epoch k. Since F is assumed to be strongly convex, the authors
of [2] show that this decrease in F implies a contraction in the distance kyk − x? k at each epoch k,
allowing one to choose a sequence of radii rk that contract as well at each step but still have the
property that x? ∈ B(yk , rk ).
One obstacle in generalizing the results of [2] to the non-strongly convex case is that we do not
have an oracle for the sub-level sets of F , but only for F̂ , whose sub-level sets may not even be
connected. Instead, we show that the SGLD Markov chain concentrates inside increasingly smaller
sub-level sets of F as the temperature parameter is decreased. To analyze the behavior of the
SGLD Markov chain at each temperature, we build several new tools and use some from [17]. Our
results make important contributions to the growing body of work on non-asymptotic analysis of
simulated annealing, Langevin dynamics and their various combinations [4, 12, 14, 16].

1.3

Organization of the rest of the paper

We start with a detailed but informal primer of the algorithm and the key steps and ideas involved in
the proof of Theorem 1.2 in Section 2. Subsequently, we present the notation and other preliminaries
in Section 3. This is followed by a formal presentation of the algorithm and the statement of the
main results in Sections 4.1 and 4.2. Section 5 contains the detailed mathematical proof of our
main theorem.

7

F
F
F̂
X0

F̂

X5

X4
X0

X4

X1

X1

X6
X7
X11

X8
X5

X9

X9

(a)

(b)
F

F
F̂

F̂
X0

X0

X5

X4
X1
X5

X6

X1

X4

X6
X8

X9
X7

(c)

X12

(d)

Figure 2: (a) Optimization of a convex function F (green) with noisy oracle F̂ (black) under
bounded additive noise. Since the gap between the noise bounds (dashed lines) is constant, the
Markov chain (red) can be run at a single temperature that is both hot enough to quickly escape
any local minimum but also cold enough so that the Markov chain eventually concentrates near
the global minimum. (b) and (c) Optimization of a convex function F (green) with noisy oracle F̂
(black) when both additive and multiplicative noise are present, if we run the Markov chain at single
a fixed temperature. If the temperature is hot enough to escape even the deepest local minima,
then it will not concentrate near the global minimum, leading to a large error. If instead the
Markov chain is run at a colder temperature, it will take a very long time to escape the deeper local
minima. (d) Optimization of a convex function F (green) with noisy oracle F̂ (black) under both
additive and multiplicative noise, when using a gradually decreasing temperature. If multiplicative
noise is present the local minima of F̂ are very deep for large values of F . To quickly escape the
deeper local minima, the Markov chain is started at a high temperature. As the Markov chain
concentrates in regions where F is smaller, the local minima become shallower, so the temperature
may be gradually decreased while still allowing the Markov chain to escape nearby local minima. As
the temperature is gradually decreased, the Markov chain concentrates in regions with successively
smaller values of F̂ .

8

2

Overview of Our Contributions

The model and the problem. Let K ⊆ Rd be the given convex body contained in a ball of
radius R > 0 and F : K → R the given convex function. We assume that F has gradient bounded
by some number λ > 0, and that K = K0 + B(0, r0 ) for some r0 > 0, where “+” denotes the
Minkowski sum and K0 is a convex body. Let x? be a minimizer of F over K. Recall that our goal
is to find an approximate minimizer x̂ of F on K, such that F (x̂) − F (x? ) ≤ ε̂ for a given ε̂ > 0.
We assume that we have access to a membership oracle for K and a noisy oracle F̂ for F . Recall
that in our model of noise, we assume that there exist functions ϕ : K → R and ψ : K → R and
numbers α, β ≥ 0, with |ϕ(x)| ≤ β and |ψ(x)| ≤ α for all x ∈ K, such that
F̂ (x) = F (x)(1 + ψ(x)) + ϕ(x)

∀x ∈ K.

(4)

We say that F̂ has “additive noise” ϕ of level β and “multiplicative noise” ψ of level α. To simplify
our analysis, we assume that F ≥ 0 and that F has minimizer x? ∈ K such that F (x? ) = 0 (if not,
we can always shift F and F̂ down by the constant F (x? ) to satisfy this assumption). That way,
the multiplicative noise ψ has the convenient property that it goes to zero as we approach x? .
We first describe our algorithm and the proof assuming that F̂ is smooth and we have access
to the gradient of F̂ . Specifically, we assume that k∇F̂ k is bounded from above by some number
λ̃ > 0 and that the Hessian of F̂ has singular values bounded above by L > 0. This simplifies the
presentation considerably and we explain how to deal with the non-smooth case at the end of this
section.
Our algorithm. To find an approximate minimizer of F , we would like to design a Markov chain
whose stationary distribution concentrates in a subset of K where the values of F are small. The
optimal choice of parameters for this Markov chain will depend on the amount of noise present.
Since the bounds on the noise are not uniform, the choice of these parameters will depend on
the current state of the chain. To deal with this fact, we will run a sequence of Markov chains in
different epochs, where the parameters of the chain are fixed throughout each epoch. Our algorithm
runs for kmax epochs, with each epoch indexed by k.
(k) max
In epoch k, we run a separate Markov chain {Xi }ii=1
over K for the same number of iterations
(imax . Each such Markov chain has parameters ξk and ηk that depend on k. We think of ξk−1 as
the “temperature” of the Markov chain and ηk as the step size. At the beginning of each epoch,
we decrease the temperature and step size, and keep them fixed throughout the epoch. We explain
quantitatively how we set the temperature a bit later, Each Markov chain also has an initial point
(k)
X0 ∈ K. This initial point is chosen from the uniform distribution on a small ball centered at the
point in the Markov chain of the previous epoch (k − 1) with the smallest value of F̂ . In the final
epoch, the algorithm outputs a solution x̂, where x̂ is chosen to be the point in the Markov chain
of the final epoch with the smallest value of F̂ .
Description of the Markov chain in a single epoch. We now describe how the Markov
(k)
(k)
chain, at the point Xi in the k-th epoch, chooses the next point Xi+1 . First, we compute the
(k)

0
gradient ∇F̂ (Xi ). Then we compute a “proposal” Xi+1
for the next point as follows
r
2ηk
(k)
(k)
0
Xi+1 = Xi − ηk ∇F̂ (Xi ) +
Pi ,
ξk

(5)

0
where Pi is sampled from N (0, Id ). If Xi+1
is inside the domain K, then we accept the proposal and
(k)

(k)

(k)

0 ; otherwise we reject the proposal and we set X
set Xi+1 = Xi+1
i+1 = Xi

9

– which is the old point.

The update rule in Equation (5) is called the Langevin dynamics. This is a version of gradient
descent injected with a random term. The amount of randomness is controlled by the temperature
ξk−1 and the step size ηk . This randomness allows the Markov chain to escape local minima when
F̂ is not convex. Although the stationary distribution of this Markov chain is not known exactly,
roughly speaking it is approximately proportional3 to e−ξk F̂ . This completes the description of our
algorithm in the smooth case and we now turn to explaining the steps involved in bounding its
running time for a given bound on the error ε̂.
Steps in bounding the running time. In every epoch, the algorithm makes multiplicative
1
progress so that the smallest value of F achieved by the Markov chain decreases by a factor of 10
.
M
To achieve an error ε̂, our algorithm therefore requires kmax = O(log ε̂ ) epochs, where M is the
maximum value of F̂ on K (M ≤ λR). The running time of our algorithm is given by the number of
epochs kmax multiplied by the number of steps imax taken by the Markov chain within each epoch.
For simplicity, we will run the Markov chain at each epoch for the same number of steps imax . For
1
the value of F to decrease by a factor of 10
in each epoch, we must set the number of steps imax
taken by the Markov chain during each epoch to be no less than the hitting time of the Markov
chain for epoch k to a sub-level set Uk ⊆ K of F , where the “height” of Uk is one-tenth the value
of F at the initial point in this Markov chain. By the height of a sub-level set, we mean the largest
value of F achieved at any point on that sub-level set, that is the sub-level set {y ∈ K : F (y) ≤ h}
has height h. Thus, bounding the hitting time will allow us to bound the number of steps imax for
which we must run each Markov chain. Specifically, we should choose imax to be no less than the
greatest hitting time in any of the epochs with high probability.
This approach was used in the simpler setting of additive noise and a non-iterative way by [17].
Thus, the running time is roughly the product of the number of epochs and the hitting time to the
sub-level set Uk , and having determined the number of epochs required for a given accuracy, we
proceed to bounding the hitting time.
Bounding the hitting time and the Cheeger constant. To bound the hitting time of the
Markov chain in a single epoch, we use the strategy of [17], who bound the hitting time of the
Langevin dynamics Markov chain in terms of the Cheeger constant. Since the Markov chain has
approximate stationary measure induced by e−ξk F̂ , we consider the Cheeger constant with respect
to this measure, defined as follows.
Given a probability measure µ on some domain, we consider the ratio of the measure of the
boundary of an arbitrary subset A of the domain to the measure of A itself. The Cheeger constant
of a set V is the infimum of these ratios over all subsets A ⊆ V (see Definition 5.1 in Section 5.2
for a formal definition). We use some of the results in [17] to show a bound on the hitting time
to the sub-level set Uk contained in a larger sub-level set Uk0 in terms of the Cheeger constant Cˆk ,
with respect to the measure induced by e−ξk F̂ (x) on Uk0 . Specifically, we set Uk0 to be the sub-level
(k)
(k)
1
set of height F̂ (X0 ) + ξk−1 d and Uk to be the sub-level set of height 10
F (X0 ) and show that for
a step size
(Cˆk )2
ηk =
,
d3 ((ξk λ̃)2 + ξk L)2
the hitting time to Uk is bounded by

R
qλ̃ξk +d ;
ηk ˆ
C
d k

see Section 5.5. Thus, to complete our bound on the

hitting time we need to bound the corresponding Cheeger constants.
3

By this we mean that the density of this measure is

1
R

e−ξk F̂

10

e−ξk F̂ .

Bounding the Cheeger constant. We would like to bound the Cheeger constant of the measure
induced by e−ξk F̂ (x) . However, F̂ is not convex, so we cannot directly apply the usual approach of
Lovasz and Simonovits [13] for convex functions. Instead, we first apply their result to bound the
Cheeger constant of the convex function F . We then bound the Cheeger constant of the nonconvex
function F̂ in terms of the Cheeger constant of the convex function F , using a very useful stability
property satisfied by the Cheeger constant.
Roughly speaking, we show that the Cheeger constant of Uk0 \Uk is bounded below by R1 (where
R is the radius of the bounding ball for K) as long as the inverse temperature satisfies
ξk ≥

d
(k)
1
10 F (X0 )

(see Lemma 5.3). However, the difficulty is that Uk0 may have sharp corners, the volume of Uk
might be so small that Uk would have much smaller measure than Uk0 \Uk , leading to a very small
Cheeger constant. To get around this problem, we instead consider a slightly “rounded” version
of K, where we take K to be the Minkowski sum of another convex body with a ball of very small
radius r0 . The roundness allows us to show that Uk contains a ball of even smaller radius r̂ such
that the measure is much larger on this ball than at any point in Uk0 \Uk . This in turn allows us
to apply the results of [13] to show that the Cheeger constant is bounded below by R1 (see Lemma
5.3). Note our Cheeger bound is more general (for convex functions) than that obtained in [17],
where the constraint set is assumed to be a ball.
The Cheeger constant has the following useful stability property that allows us to bound the
Cheeger constant of the nonconvex F̂ with respect to the convex F : if |F̂ (x) − F (x)| ≤ Nk for all
x ∈ Uk0 , then the Cheeger constant for the measures proportional to e−ξk F and e−ξk F̂ differ by a
factor of at most e−2ξk Nk . For our choice of Uk0 , we have
(k)

Nk ≈ α[F (X0 ) + ξk−1 d] + β.
We can then use the stability property to show that the Cheeger constants of F̂ and F differ by a
factor of at most e−2ξk Nk , allowing us to get a large bound for the Cheeger constant of F̂ in terms
of our bound for the Cheeger constant of F as long as the bound on the noise Nk on Uk0 is not too
large, namely we get that the Cheeger constant is bounded below by
!
1 −2ξk Nk
1
d
≈ exp −αd −
e
β
(k)
R
R
F (X )
0

if we choose ξk =

d
(k)
1
F (X0 )
10

.

At this point we mention the key difference between the approach of [17] and ours in bounding
the hitting time. As [17] assume a uniform bound on the noise they only consider the Cheeger
constant of K\Uk , where K is the entire constraint set and is assumed to be a ball. Since the noise
in our model depends on the “height” of the level sets, we instead need to bound the Cheeger
(k)
constant of Uk0 \Uk , where Uk0 is the level set of height F̂ (X0 ) + ξk−1 d and Uk is the level set of
(k)
1
height 10
F (X0 ).
In order to complete our bound for the Cheeger constant of F̂ , we still need to verify that we
can choose a temperature such that the Cheeger constant of F is large and the Cheeger constants
of F and F̂ are close at this same temperature.

11

Requirements on the temperature to bound the Cheeger constant. To get a large bound
for the Cheeger constant of F̂ , we need to use a temperature ξk−1 such that the following competing
requirements are satisfied:
1. We need the Cheeger constant of the convex objective function F to be not too small. This
requires the temperature to be low enough.
2. We need the Markov chain to stay inside a level set on which the upper bound Nk on the
noise is not too large, to show that the Cheeger constants of F and F̂ are close. That is, we
need to show that the ratio e−2ξk Nk of the Cheeger constants of F and F̂ is not to small. This
requires the temperature to be low enough.
3. We also need the temperature to be high enough to show that the ratio e−2ξk Nk is not to
small. This requires the temperature to be high enough.
At some epoch k, the value of F becomes too low for all three of these requirements on the
temperature to be satisfied simultaneously. At this point the Cheeger constant and hitting time
to Uk become very large no matter what temperature we use, so that the minimum value of F
obtained by the Markov chain no longer decreases by a large factor in imax steps.
Quantitative error and running time bounds. We now give a more quantitative analysis to
determine at what point F stops decreasing. The value of F at this point determines the error ε̂
of the solution returned by our algorithm. Towards this end, we set the inverse temperature to be
ξk = 1 d (k) and check to what extent all 3 requirements above are satisfied.
10

F (X0 )

1. We start by showing that if the temperature roughly satisfies ξk ≥
constant for F on Uk0 \Uk is bounded below by

1
R

d
(k)
1
F (X0 )
10

then the Cheeger

(see Lemma 5.3).

2. We then show that at each epoch the Markov chain remains with high probability in the level
(k)
set Uk0 of height F̂ (X0 )+ξk−1 d (Lemma 5.7). The fact that the noise satisfies |F̂ (x)−F (x)| ≤
αF (x) + β (note that we assume F ≥ 0), implies that the noise is roughly bounded above by
(k)
Nk = α[F (X0 ) + ξk−1 d] + β on this level set.
3. Since we chose the temperature to be ξk =

d
(k)
1
F (X0 )
10

ξk Nk ≈ αd +

, we have that

d
(k)

F (X0 )

β.

1 −2ξk Nk
Combing
≈
 these three facts
 we get that the Cheeger constant is bounded below by R e
(k)
1
d
(k) β . If we run the algorithm for enough epochs to reach F (X0 ) ≤ ε̂ for any
R exp −αd −
F (X0 )

1
d
R exp(−αd − ε̂ β).
2
ˆ
(Ck )
. Choosing
Rd3 ((ξk λ̃)2 +ξk L)2

desired error ε̂ > 0, the Cheeger constant will be roughly bounded below by
Recall that the hitting time is bounded by

R
qλ̃ξk +d ,
ηk ˆ
Ck
d

for stepsize ηk ≈

imax to be equal to our bound on the hitting time, and recalling that kmax = Õ(1), we get a running
time of roughly
"
#!
3
3
5 L
λ̃
d
,
Õ R 2 d5 3 + d 2 ] exp(c[αd + β
ε̂
ε̂
ε̂
for some c = Õ(1).
12

Therefore, for our choice of inverse temperature ξk =

d
(k)
1
F (X0 )
10

, the running time is polynomial

in d, R, λ and λ̃ whenever the multiplicative noise level satisfies α ≤ Õ( d1 ) and the additive noise
level satisfies β ≤ Õ( dε̂ ). As discussed in the introduction, the requirements that α ≤ Õ( d1 ) and
β ≤ Õ( dε̂ ) are not an artefact of the analysis or algorithm and are in fact tight.
Drift bounds and initialization. So far we have been implicitly assuming that the Markov
chain does not leave Uk0 , so that we could analyze the Markov chain using the Cheeger constant
on Uk0 . We now show that this assumption is indeed true with high probability. This is important
to verify, since there are examples of Markov chains where the Markov chain may have a high
probability of escaping a level set Uk0 , even if this level set contains most of the stationary measure,
provided that the Markov chain is started far from the stationary distribution.
(k)
To get around this problem, at each epoch we choose choose the initial point X0 from the
uniform distribution on a small ball of radius r centered at the point in the Markov chain of the
previous epoch k − 1 with the smallest value of F̂ . We then show that if the Markov chain is
initialized in this small ball, it has a low probability of leaving the level set Uk0 (see Propositions
5.5, 5.7 and Lemma 5.7).
Our method of initialization is another crucial difference between our algorithm and the algorithms in [17] and [2], since it allows us to effectively restrict the Markov chain to a sub-level set
of the objective function F , which we do not have direct oracle access to, rather than restricting
the Markov chain to a large ball as in [2] or the entire constraint set K as in [17] for which we have
an membership oracle. This in turn allows us to get a tighter bound on the multiplicative noise
than would otherwise be possible, since the amount of multiplicative noise depends, by definition,
on the sub-level set.
We still need to show that the chain X (k) does not leave the set Uk0 with high probability. To
bound the probability that X (k) leaves Uk0 , we would like to use the fact that most of its stationary
distribution is concentrated in Uk0 . However, the problem is that we do not know the stationary
distribution of X (k) . To get around this, we consider a related Markov chain Y (k) with known
stationary distribution. The chain Y (k) evolves according to the same update rules as X (k) , using
the same sequence of Gaussian random vectors P1 , P2 , . . . and the same starting point, except that it
performs a Metropolis “accept-reject” step that causes its stationary distribution to be proportional
to e−ξk F̂ . The fact that we know the stationary distribution of Y (k) is key to showing that Y (k)
stays in the subset Uk0 with high probability (see Proposition 5.6). We then argue that Y (k) = X (k)
with high probability, implying that X (k) also stays inside the set Uk0 with high probability (see
Lemma 5.7).
Another coupled toy chain. So far we have shown that the Markov chain X (k) stays inside the
set Uk0 with high probability. However, to use the stability property to bound the hitting time of the
Markov chain X (k) to the set Uk , we actually want the Markov chain to be restricted to the set Uk0
where the noise is not too large. In reality, however, the domain of X (k) is all of K, so we cannot
directly bound the hitting time of X (k) with the Cheeger constant of Uk0 \Uk . Instead, we consider
a Markov chain X̂ (k) that evolves according to the same rules as X (k) , except that it rejects any
proposal outside of Uk0 . Since X̂ (k) has domain Uk0 , we can use our bound on the Cheeger constant
of Uk0 \Uk to obtain a bound on the hitting time of X̂ (k) . Then, we argue that since X (k) stays in
Uk0 with high probability, and X̂ (k) and X (k) evolve according to the same update rules as long as
X (k) stays inside Uk0 , X̂ (k) = X (k) with high probability as well, implying a hitting time bound for
X (k) .
13

Rounding the sub-level sets. We must also show a bound on the roundness of the sets Uk0 , to
avoid the possibillty of the Markov chain getting stuck in “corners”. The authors of [17] take this
as an assumption about the constraint set. However, since we must consider the Cheeger constant
on sub-level sets Uk0 rather than just on the entire constraint set, we must make sure that these
sub-level sets are “round enough”. Towards this end we consider “rounded” sub-level sets where we
take the Minkowski sum of Uk0 with a ball of a small radius r0 . We then apply the Hanson-Wright
inequality to show that any Gaussian random variable with center inside this rounded sub-level set
and small enough covariance remains inside the rounded sub-level set with high probability (see
Lemma 5.14).
Smoothing a non-differentiable noisy oracle. Finally, so far we have considered the special
case where F̂ is smooth. However, F̂ may not be smooth or may not even be differentiable, so we
may not have access to a well-behaved gradient which we need to compute the Langevin dynamics
Markov chain (Equation 5). To get around this problem, we follow the approach of [7] and [17].
We define a smoothed function
f˜σ (x) := EZ [F̂ (x + Z)]
where Z ∼ N (0, σId ) and σ > 0 is a parameter we must fix. The smoothness of f˜σ comes from the
fact that f˜σ is a convolution of F̂ with a Gaussian distribution.
When choosing σ, we want σ to be small enough so that we get a good bound on the noise
˜
|fσ (x) − F (x)|. Specifically, we need



r β + ε̂α + ε̂/d
√
σ = Õ min √ ,
,
d
λ d
where λ is a bound on k∇F k. On the other hand, we also want σ not to be too small so that we
get a good bound on the smoothness of f˜σ .
Further, so far we have also assumed that we have access to the full gradient of F̂ , but in general
F̂ may not even have a gradient. Instead, we would like to use the gradient of f˜σ to compute the
proposal for the Langevin dynamics Markov chain (Equation (5)). However, computing the full
gradient of f˜σ can be expensive, since we do not even have direct oracle access to f˜σ . Instead, we
compute a projection g(x) of ∇f˜σ , where
Z
(F̂ (x + Z) − F̂ (x))
σ2
Since g has the property that E[g(x)] = ∇f˜σ , g is called a “stochastic gradient” of f˜σ . We use
this stochastic gradient g in place of the full gradient of F̂ when computing the proposal for the
Langevin dynamics Markov chain (Equation 5). This gives rise to the following Markov chain
proposal, also known as stochastic gradient Langevin dynamics (SGLD):
r
2ηk
(k)
(k)
0
Xi+1 = Xi − ηk g(Xi ) +
Pi .
ξk
To bound the running time of SGLD, we will need a bound on the magnitude of the gradient of f˜σ
(see Lemma 5.10), bounds on the Hessian and tails of f˜σ , which we obtain from [17] (see Lemma
5.12), and bounds on the noise of the smoothed function, |f˜σ − F (x)| (see Lemma 5.13).
g(x) =

Although in this technical overview we largely showed running time and error bounds assuming
access to a full gradient, in reality we prove Theorem 1.2 for the more general stochastic gradient
Langevin dynamics algorithm, where we only assume access to a stochastic gradient of a smooth
function. Therefore, the bounds on the noise and smoothness of f˜σ allow us to extend the error
and polynomial running time bounds shown in this overview to the more general case where F̂ may
not be differentiable.
14

3

Preliminaries

In this section we go over notation and assumptions that we use to state our algorithm and prove
our main result. We start by giving assumptions we make about the convex objective function F .
We then explain how to obtain an oracle for the gradient of the smoothed function f˜σ if we only
have access to the non-smooth oracle F̂ .

3.1

Notation

In this section we define the notation we use to prove our main result. For any set S ⊆ Rd and
t ≥ 0 define St := S + B(0, t) where “+” denotes the Minkowski sum. We denote the `2 -norm by
k · k, and the d × d identity matrix by Id . We denote by k · kop the operator norm of a matrix, that
is, its largest singular value. We define B(a, t) to be the closed Euclidean ball with center a and
radius t. Denote the multivariate normal distribution with mean m and covariance matrix Σ by
N (m, Σ). Let x? denote a minimizer of F on K.

3.2

Assumptions on the convex objective function and the constraint set

We make the following assumptions about the convex objective function F and K:
• K is contained in a ball, with K ⊆ B(c, R) for some c ∈ Rd .
• F (x? ) = 0.4
• There exists an r0 > 0 and a convex body K0 such that K = K0 + B(0, r0 ) for some convex
body. (This assumption is necessary to ensure that our convex body does not have “pointy”
edges, so that the Markov chain does not get stuck for a long time in a corner.)
• F is convex over Kr for some r > 0.
• k∇F (x)k ≤ λ for all x ∈ Kr , where λ > 0.

3.3

A smoothed oracle from a non-smooth one

In this section we show how to obtain a smooth noisy oracle for F if one only has access to a nonsmooth and possibly non-continuous noisy oracle F̂ . Our goal is to find an approximate minimum
for F on the constraint set K. (We consider the thickened set Kr only to help us compute a smooth
oracle for F on K). We assume that we have access to a noisy function F̂ of the form
F̂ (x) = F (x)(1 + ψ(x)) + ϕ(x),

(6)

where |ψ(x)| < α, and |ϕ(x)| < β for every x ∈ Kr , for some α, β ≥ 0. We extend F̂ to values
outside Kr by setting F̂ (x) = 0 for all x ∈
/ Kr . Since F̂ need not be smooth, as in [7, 17] we will
instead optimize the following smoothed function
f˜σ (x) := EZ [F̂ (x + Z)]

(7)

4
If F (x? ) is nonzero, we can define a new objective function F 0 (x) = F (x) − F (x? ) and a new noisy function
0
˜
f (x) = f˜(x) − F (x? ). The noise N 0 (x) = f˜0 (x) − F 0 (x) can then be modeled as having additive noise of level
β 0 = β + αF (x? ) and multiplicative noise of level α0 = α, if N (x) = f˜(x) − F (x) has additive noise of level β and
multiplicative noise of level α.

15

where Z ∼ N (0, σId ), for some σ > 0. The parameter σ determines the smoothness of f˜σ ; a larger
value of σ will mean that f˜σ will be smoother. The gradient of f˜σ (x) can be computed using a
stochastic gradient g(x), where

1 
g(x) ≡ gZ (x) := 2 Z F̂ (x + Z) − F̂ (x) ,
∇f˜σ (x) = EZ [g(x)].
σ

4
4.1

Our Contribution
Our Algorithm

In this section we state our simulated annealing algorithm (Algorithm 2) that we use to obtain a
solution to Problem 1. At each epoch, our algorithm uses the SGLD Markov chain as a subroutine,
which we describe first in Algorithm 1. The SGLD Markov chain we describe here is the same
algorithm used in [17], except that we allow the user to specify the initial point.
Algorithm 1 Stochastic gradient Langevin dynamics (SGLD)
input: Convex constraint set K̂ ⊆ Rd , inverse temperature ξ > 0, step size η > 0, parameters
imax ∈ N and D > 0, and a stochastic gradient oracle g for some f˜ : K → R.
input: Initial point X0 ∈ K̂.
1: for i = 0 to imax do
2: Sample Pi ∼ N (0, Id ).
q
3:

0
Set Xi+1
= Xi − ηg(Xi ) +

2η
ξ Pi .

0
0
Set Xi+1 = Xi+1
if Xi+1
∈ K̂ ∩ B(Xi , D). Otherwise, set Xi+1 = Xi .
5: end for
output: Xi? , where i? := argmini {F̂ (Xi )}

4:

Using Algorithm 1 as a subroutine, we define the following simulated annealing algorithm:
Algorithm 2 Simulated annealing SGLD
input: Convex constraint set K̂ ⊆ Rd , initial point x0 ∈ K̂, inverse temperatures ξ0 , ξ1 , . . . , ξkmax ,
step sizes η0 , η1 , . . . , ηkmax , parameters kmax , imax ∈ N, D > 0 and r > 0, and a stochastic gradient
oracle g for some f˜ : K̂ → R.
1: Sample y0 from the uniform distribution on B(x0 , r) ∩ K̂.
2: for k = 0 to kmax do
3: Run Algorithm 1 on K̂, inverse temperature ξ = ξk , and step size ηk , imax , the oracle g, and
the initial point X0 = yk . Let xk+1 be the output of Algorithm 1.
4: Sample yk+1 from the uniform distribution on B(xk+1 , r) ∩ K̂.
5: end for
output: xkmax

4.2

Statement of Our Main Theorem

We now formally state our main result, where we bound the error and running time when Algorithm
2 is used to solve Problem 1, assuming access to an oracle F̂ that may be non-smooth or even noncontinuous.
16

Theorem 4.1. (Main Theorem: Error bounds and running time for Algorithm 2) Let
F : K → R be a convex function, and K ⊆ Rd be a convex set that satisfy the assumptions stated in
Section 3.1. Let F̂ be a noisy oracle for F with multiplicative noise of level α ≤ O(1) and additive
noise of level β, as in Equation (6). Let ε̂ ≥ 75β and δ 0 > 0. Then there exist parameters imax ,
max
, and σ, such that if we run Algorithm 2 with a smoothed version f˜σ of the oracle
kmax , (ξk , ηk )kk=0
F̂ (as defined in Section 3.3), with probability at least 1 − δ 0 , the algorithm outputs a point x̂ such
that
F (x̂) − F (x? ) ≤ ε̂,
β

with running time that is polynomial in d, e(dα+d ε̂ )c , R, λ,
λ)).

1
r0 ,

β, 1ε̂ , and log δ10 , where c = O(log(R+

We give a proof of Theorem 4.1 in Section 5.8.
The precise values of the parameters in this theorem are quite involved and appear in the proofs at
the following places: ξk appears in (41), ηk here (43), imax here (42), and the expression for kmax
can be found here (40). Below we present their approximate magnitudes. The inverse temperature
parameter ξk , the smoothing parameter σ, and the number of epochs kmax satisfy:




 

1
d
d
(0)
k
≤ ξk ∼ Õ d · max
, F̂ (X0 ) · 10
≤ Õ
,
Ω̃
λR
ε̂
ε̂


1
r
β
,
√ ,q
σ = min 
2
1
λ(1 + α) d
log( ) + d
α

kmax ∼ log

R
.
ε̂

To make the expressions for ηk and imax understandable, assume that λR > 1, β, that r > βλ , d > ε̂,
and that R > λ. Then
ηk ∼

ε̂4
−d(α+ βε̂ )c0 −k
e
10
d9 R5 λ8 β 4

d6.5 11 6 d(α+ β )c0
ε̂
≤
R 2 λ βe
ε̂3


1 ≤ imax

1+c00 α
,

2

R
00
where c0 ∼ log rdδ min{ε̂/λ,r
0 } and c is a constant factor. In particular, the running time is given by
imax × kmax .

5
5.1

Proofs
Assumptions about the smooth oracle

We first show how to optimize F if one has access to a smooth noisy objective function f˜ : K → R
(Sections 5.2, 5.3, 5.5). Then, in Section 5.6, we show how one can obtain a smooth noisy objective
function from a non-smooth and possibly non-continuos noisy objective function F̂ . We will make
the following assumptions (we prove in Section 5.6 that these assumptions hold for a smoothed
17

version f˜σ of a non-smooth noisy objective function F̂ ). We assume the following noise model for
f˜:
f˜(x) = F (x)(1 + ψ(x)) + ϕ(x),
for all x ∈ K where |ψ(x)| ≤ α and |ϕ(x)| ≤ β. Note that, with a slight abuse of notation, in
Section 3.3 we also used the letters α and β to denote the noise levels of the non-smooth oracle F̂ ,
even though typically F̂ will have lower noise levels than f˜. In this section, as well as in Sections
5.2-5.5 where we assume direct access to a stochastic gradient for the smooth oracle f˜, we will
instead refer to the noise levels of F̂ by “α̂” and “β̂”. In Section 4.2, on the other hand, “α” and
“β” will be used exclusively to denote the noise levels of F̂ . We also assume that
α ≥ α̂

and β ≥ β̂.

(8)

We make the following assumptions about f˜:
• ψ(x) > −α† for some 0 ≤ α† < 1. This assumption is needed because if not we might have
ψ(x) = −1 for all x ∈ K, in which case f˜(x) would give no information about F .
• k∇f˜(x)k ≤ λ̃ for all x ∈ K.
• We assume that we have access to a stochastic gradient g such that ∇f˜(x) = E[g(x)] for every
x ∈ K. However, we do not assume that we have oracle access to f˜ itself.
Assumption 1. (Based on assumption A in [17]) Let f˜ : K → Rd be differentiable, and let
g ≡ gw : K → Rd be such that ∇f˜(x) = E[gW (x)] where W is a random variable. We will assume
that
1. There exists ζmax > 0 such that for every compact convex K̂ ⊆ Rd , every x ∈ K̂r0 , and every
0 ≤ ζ ≤ ζmax , the random variable Z ∼ N (x, 2ζId ) satisfies P(Z ∈ K) ≥ 13 . We prove this
assumption in Lemma 5.14.
2. There exists L > 0 such that |f˜(y) − f˜(x) − hy − x, ∇f˜(x)i| ≤

L
2 ky

− xk2

∀x, y ∈ K.

3. There exists bmax > 0 and G > 0 such that for any u ∈ Rd with kuk ≤ bmax the stochastic
2
2
2
gradient g(x) satisfies E[ehu,g(x)i |x] ≤ eG kuk .

5.2

Conductance and bounding the Cheeger constant

To help us bound the convergence rate, we define the Cheeger constant of a distribution, as well as
the conductance of a Markov chain. For any set K̂ and any function f : K̂ → R, define
e−f (x)
−f (x)
K̂ e

µK̂
f (x) := R

∀x ∈ K̂.

Definition 5.1. (Cheeger constant) For all V ⊆ K̂, define the Cheeger constant to be
CfK̂ (V ) := lim inf inf
ε↓0

K̂
µK̂
f (Aε ) − µf (A)

ε

A⊆V

recalling that Aε = A + B(0, ε).

18

K̂(A)

µf

.

For a Markov chain Z0 , Z1 , . . . on K̂ with stationary distribution µZ and transition kernel QZ , we
define the conductance on a subset V to be
R
QZ (x, K̂\A)µZ (x)dx
K̂
ΦZ (V ) := inf A
∀V ⊆ K̂
A⊆V
µZ (A)
and the hitting time
τZ (A) := inf{i : Zi ∈ A}

∀A ⊆ K̂.

Finally, we define the notion of two Markov chains being ε0 -close:
Definition 5.2. If W0 , W1 , . . . and Z0 , Z1 , . . . are Markov chains on a set K̂ with transition kernels
QW and QZ , respectively, we say that W is ε0 -close to Z with respect to a set U ⊆ K̂ if
QZ (x, A) ≤ QW (x, A) ≤ (1 + ε0 )QZ (x, A)
for every x ∈ K̂\U and A ⊆ K̂\{x}.
We now give a generalization of Proposition 2 in [17]:
Lemma 5.3. (Bounding the Cheeger constant) Assume that K̂ ⊆ K0 is convex, and that F
is convex and λ-Lipschitz on K̂r0 . Then for every ε > 0 and all ξ ≥
K̂

CξFr (K̂r0 \U ε ) ≥
0

ε
,r0 ))
4d log(R/ min( 2λ
ε

we have

1
.
R

ε
Proof. Let x̂? be a minimizer of F on K̂r0 . Let r̂ = min( 2λ
, r0 ). Then since K̂r0 = K̂ + B(0, r0 ), for
0
?
some a ∈ K there is a closed ball B(a, r̂) ⊆ K̂r0 , with x ∈ B(a, r̂). By the Lipschitz property, we
have

ε
sup{F (x) : x ∈ B(a, r̂)} ≤ F (x? ) + 2r̂λ ≤ F (x? ) + .
2
Therefore,
inf{

e−ξF (x)
: x ∈ B(a, r̂), y ∈ K0 \U ε )} ≥ eξε/2 .
e−ξF (y)

(9)

Then Equation (9) implies that
K̂

0

µξFr (K̂r0 \Uε )
K̂ 0
µξFr (Uε )

≤ e−ξε/2

Vol(B(c, R))
Vol(B(a, r̂))

R
= e−ξε/2 ( )d
r̂
−ξε/2+d log(R/r̂)
=e
1
≤ ,
2
which implies that
1
K̂ 0
µξFr (K̂r0 \Uε ) ≤ .
2
19

(10)

Then by Theorem 2.6 of [13] for all A ⊆ K̂r0 \U ε for any 0 < δ < 2R we have
K̂

0

δ
2 2R

K̂ 0
K̂ 0
min(µξFr (A), µξFr (K̂r0 \Aδ ))
δ
1 − 2R
δ
2 2R
K̂ 0
K̂ 0
≥
min(µξFr (A), µξFr (K̂r0 \Aδ ))
δ
1 − 2R
δ
2 2R
K̂ 0
K̂ 0
min(µξFr (A), 1 − µξFr (Aδ ))
=
δ
1 − 2R
δ
2 2R
K̂ 0
K̂ 0
K̂ 0
=
min(µξFr (A), 1 − µξFr (Aδ \A) − µξFr (A))
δ
1 − 2R
Eq. (10) 2 δ
1
K̂r0
K̂r0
2R
≥
1 min(µξF (A), 1 − µξF (Aδ \A) − 2 )
1 − 2R
δ
2 2R
1
K̂ 0
K̂ 0
min(µξFr (A), − µξFr (Aδ \A))
=
δ
2
1 − 2R
δ
2 2R
K̂ 0
=
µξFr (A),
δ
1 − 2R

µξFr (Aδ \A) ≥

provided that 0 < δ < ∆A for some small enough value ∆A > 0 that depends on A. Therefore for
every A ⊆ K̂r0 \Uε there exists ∆A > 0 such that
K̂

0

µξFr (Aδ \A)
K̂

≥

0

δµξFr (A)

1
2 2R

1−

δ
2R

∀0 < δ < ∆A .

Taking δ → 0, we get
K̂

CξFr (K̂r0 \U ε ) ≥

5.3

0

1
.
R

Bounding the escape probability

We will use the Lemma proved in this section (Lemma 5.7) to show that the SGLD chain X defined
in Algorithm 1 does not drift too far from its initial objective function value with high probability.
This will allow us to bound the noise, since the noise is proportional to the objective function F .
The organization of this section is as follows: we first define a “toy” algorithm and an associated
Markov chain Y that will allow us to prove Lemma 5.7 (and which we will later use to prove
Theorem 2). We then prove Propositions 5.5 and 5.6, and Lemma 5.7. Proposition 5.5 is used to
prove Proposition 5.6, which in turn is used to prove Lemma 5.7.
We begin by recalling the Metropolis-adjusted version of Algorithm 1 defined in [17], which defines a Markov chain Y0 , Y1 , . . . with stationary distribution µK
. Note that this is a“toy” algorithm
ξ f˜
which is not meant to be implemented; rather we state this algorithm only to define the Markov
chain Y0 , Y1 , . . ., which we will use as a tool to prove Lemma 5.7 and Theorem 2.

20

Algorithm 3 Lazy Metropolis-adjusted SGLD
input: Convex constraint set K̂ ⊆ Rd , inverse temperature ξ > 0, step size η > 0, parameters
imax ∈ N and D > 0, stochastic gradient oracle g for some f˜ : K → R,
input: Initial point Y0 ∈ Rd .
1: for i = 0 to imax do
2: Sample Pi ∼ N (0, Id ).
q
3:

0
Set Yi+1
= Yi − ηg(Yi ) +

2η
ξ Pi .

00 = Y 0
0
00 = Y .
Set Yi+1
Otherwise, set Yi+1
i
i+1 if Yi+1 ∈ K̂ ∩ B(Yi , D).


00 )k
00
1
−
+ηg(Yi+1
kY −Y
00 )
] f˜(Yi )−f˜(Yi+1
E[e 4η i i+1
000
00
. Otherwise, set
e
5: Set Yi+1 = Yi+1 with probability min 1,
− 1 kY 00 −Y +ηg(Y )k

4:

E[e

000
Yi+1

4η

i+1

i

i

]

= Yi .
000 if V = 1; otherwise,
6: Set Vi = 1 with probability 12 and set Vi = 0 otherwise. Let Yi+1 = Yi+1
i
let Yi+1 = Yi .
7: end for
output: xi? , where i? := argmini {f˜(xi )}.
We now define a coupling of three Markov chains. We will use this coupling to prove Lemma 5.7
and Theorem 2.
Definition 5.4. (Coupled Markov chains) Let X and X̂ be Markov chains generated by generated by Algorithm 1 with constraint set K and K̂r0 , respectively, where K̂ ⊆ K and K̂r0 =
K̂ + B(0, r0 ). Let Y be the Markov chain generated by Algorithm 3. We define a coupling of the
Markov chains X, X̂ and Y in the following way: Define recursively, t(0) = 0,
t(i + 1) = min{j ∈ N : j > i, Vj = 1}.
Let Q0 , Q1 , . . . ∼ N (0, Id ) be i.i.d. Let X0 = Y0 = X̂0 . Let Yi be the chain in Algorithm 3 generated
by setting Pi = Qi for all i ≥ 0 with constraint set K. Let X be the chain in Algorithm 3 generated
by setting Pi = Qt(i) for all i ≥ 0 with constraint set K. Let X̂ be the chain in Algorithm 3
generated by setting Pi = Qt(i) for all i ≥ 0 with constraint set K̂r0 .
We now bound the escape probability of the Markov chain Y from a sub-level set of a given height,
assuming that it is initialized from its stationary distribution conditioned on a small ball.
Proposition 5.5. (Escape probability from stationary distribution on a small ball) Let
r > 0 be such that r0 ≥ r > 0 and let ξ > 0. Let Y0 , Y1 , . . . be the Markov chain defined in
B(y,r)∩K
Algorithm 3 with stationary distribution π = µK
, and let Y0 be sampled from π0 := µξf˜
,
ξ f˜
where π0 is the distribution of π conditioned on B(y, r) ∩ K for some y ∈ K. Then for every i ≥ 0
we have
˜

P(f˜(Yi ) ≥ h) ≤ eξ[f (y)+λ̃r]−ξh+d log(

2R
)
r

∀h ≥ 0.

Proof. Fix h ≥ 0. Define S1 := B(y, r) ∩ K and S2 := {x ∈ K : f˜(x) ≥ h}. Let cπ =
be the normalizing constant of π. Since π is the stationary distribution of Y ,
P(Yi ∈ S2 ) ≤

π(S2 )
π(S1 )

∀ i ∈ {0, . . . , imax }

21

R

−ξ f˜(x) dx
Ke

(11)

But k∇ξ f˜k = kξ∇f˜k ≤ ξ λ̃, implying that
˜

π(S1 ) = π(B(y, r)) ≥ cπ e−[ξf (y)+ξλ̃r] × Vol(B(y, r) ∩ K)
1
˜
≥ cπ e−ξ[f (y)+λ̃r] × Vol(B(0, r)),
2

(12)

since B(y, r) ∩ K contains a ball of radius 21 r because r ≤ r0 . Also,
π(S2 ) = π({x : f˜(x) ≥ h}) ≤ cπ e−ξh Vol(K) ≤ cπ e−ξh Vol(B(0, R)).

(13)

Therefore,
Eq. (11)

P(Yi ∈ S2 )

≤

π(S2 )
π(S1 )

Eq. (12), (13)

≤

ξ[f˜(y)+λ̃r]−ξh

e

˜

= eξ[f (y)+λ̃r]−ξh+d log(

2R
)
r

×

R
1
2r

!d

.

We now extend our bound for the escape probability of the Markov chain Y (Proposition 5.5) to
the case where Y is instead initialized from the uniform distribution on a small ball:
Proposition 5.6. (Escape probability from uniform distribution on a small ball) Let
r > 0 be such that r0 ≥ r > 0 and let ξ > 0. Let ν0 be the uniform distribution on B(y, r) ∩ K for
some y ∈ K. Let Y0 , Y1 , . . . be the Markov chain defined in Algorithm 3 with stationary distribution
, and let Y0 be sampled from ν0 . Then for every i ≥ 0 we have
π = µK
ξ f˜
˜

P(f˜(Yi ) ≥ h) ≤ eξ[f (y)+λ̃r]−ξh+d log(

2R
)
r

+ 2rλ̃ξ

∀h ≥ 0.

(14)

Moreover, for every A ⊆ K, we have
ν0 (A) ≤ e2Rλ̃ξ+d log(

2R
)
r

π(A).

(15)

Proof. Since k∇ξ f˜(x)k ≤ ξ λ̃,
ξ f˜(x) −

sup
x∈B(y,r)∩K

inf

x∈B(y,r)∩K

ξ f˜(x) ≤ 2rλ̃ξ,

and hence
inf x∈B(y,r)∩K π(x)
≥ e−2rλ̃ξ .
supx∈B(y,r)∩K π(x)
B(y,r)∩K

Define π0 := µξf˜

(16)

to be the distribution of π conditioned on B(y, r) ∩ K̂0 . Let Z be sampled

(Y0 )
from the distribution π0 . Let Z 0 = Y0 with probability min( πν00(Y
, 1); otherwise let Z 0 = Z. Then
0)

Z 0 has distribution π0 . Moreover, by Equation (16), Z 0 = Y0 with probability at least e−2rλ̃ξ .
Therefore, by Proposition 5.5
˜

P(f˜(Yi ) ≥ h) ≤ eξ[f (y)+λ̃r]−ξh+d log(
22

2R
)
r

+ 1 − e−2rλ̃ξ

˜

≤ eξ[f (y)+λ̃r]−ξh+d log(

2R
)
r

+ 2rλ̃ξ

∀h ≥ 0.

This proves Equation (14). Now, since kξ∇f˜(x)k ≤ ξ λ̃ and K ⊆ B(c, R),
sup ξ f˜(x) − inf ξ f˜(x) ≤ 2Rλ̃ξ,
x∈K

x∈K

and so
inf x∈K π(x)
≥ e−2Rλ̃ξ .
supx∈K π(x)

(17)

Therefore, for every z ∈ K we have
π(z)
= Vol(B(y, r) ∩ K) × π(z)
ν0 (z)
1
≥ Vol(B(0, r)) × π(z)
2
1
1
inf x∈K π(x)
≥ Vol(B(0, r)) ×
2
Vol(B(0, 2R)) supx∈K π(x)
 −d
Eq. (17)
2R
≥
e−2Rλ̃ξ
r
= e−2Rλ̃ξ−dlog(

2R
)
r

(18)

.

Where the second inequality holds since r ≤ r0 . This proves Equation (15).
We are now ready to bound the escape probability of the SGLD Markov chain X defined in
Algorithm 1 when it is initialized from the uniform distribution on a small ball:
Lemma 5.7. (Escape probability for unadjusted SGLD chain) Let r > 0 be such that
r0 ≥ r > 0 and let ξ > 0. Let ν0 be the uniform distribution on B(y, r) ∩ K for some y ∈ K, and
let X0 be sampled from ν0 . Let X0 , X1 , . . . be the Markov chain generated by Algorithm 1 with
δ
constraint set K. Let δ ≤ 41 and let 0 < η ≤ imax ×16d(G
2 +L) then
˜

P(f˜(Xi ) ≥ h) ≤ eξ[f (y)+λ̃r]−ξh+d log(

2R
)
r

+ 2rλ̃ξ + δ

∀h ≥ 0.

Proof. Let Y0 , Y1 , . . . be the Markov chain generated by Algorithm 3, and let X0 , X1 , . . . be the
Markov chain defined in Algorithm 1, where both chains have constraint set K. Couple the Markov
chains X and Y as in Definition 5.4. By Claim 2 in the proof of Lemma 13 of [17], for each i ≥ 0
the rejection probability P(Yi+1 = Yi ) is bounded above by 1 − e−16ηd(G
Hence, for all 0 ≤ i ≤ imax we have
P(Xj = Yj ∀0 ≤ j ≤ i) ≥ (1 −

δ
imax

2 +L)

δ

≤ 1 − e− imax ≤

)i ≥ 1 − δ.

(19)

Thus,
P(f˜(Xi ) ≥ h) ≤ P(f˜(Yi ) ≥ h) + P(Xj 6= Yj for some 0 ≤ j ≤ i)
Eq. (19)

≤

P(f˜(Yi ) ≥ h) + δ

Proposition 5.6

≤

˜

∀h ≥ 0

eξ[f (y)+λ̃r]−ξh+d log(

23

2R
)
r

+ 2rλ̃ξ + δ

δ
imax .

∀h ≥ 0.

5.4

Comparing noisy functions

In this section we bound the ratio of F̂ to f˜. We use this bound to prove Theorem 2 in Section 5.5.
Lemma 5.8. (Bounding the ratio of two noisy objective functions) Fix x ∈ K and let
t ≥ 5β. Define Ĥ = max{f˜(x), t} and let Jˆ = max{F̂ (x), t}. Then,
1
Ĥ ≤ Jˆ ≤ 5Ĥ.
5
Proof. By our assumption in Equation (8), we have that
|F (x) − F̂ (x)| ≤ α̂F (x) + β̂ ≤ αF (x) + β.
Since α < 21 , we have,
F (x) ≤ 2F̂ (x) + 2β.

(20)

We also have that,
|f˜(x) − F (x)| ≤ αF (x) + β
implying that
f˜(x) ≤ 4F (x) + β.

(21)

Therefore, combining Equations (20) and (21), we have
f˜(x) ≤ 4F̂ (x) + 5β,

(22)

implying that
max(f˜(x), 5β) ≤ max(4F̂ (x) + 5β, 20β).

Thus,
max(f˜(x), 5β) ≤ 5 max(F̂ (x), 5β).
ˆ By a similar argument as above, we can also show that Jˆ ≤ 5Ĥ.
Thus, we have Ĥ ≤ 5J.

5.5

Bounding the error and running time: The smooth case

In this section we will show how to bound the error and running time of Algorithm 1, if we
assume that we have access to a stochastic gradient oracle g for a smooth noisy function f˜, which
approximates the convex function F . In particular, we do not assume access to the smooth function
f˜ itself, only to g. We also assume access to a non-smooth oracle F̂ , which we use to determine the
temperature parameter for our Markov chain based on the value of F̂ (Xk0 ) at the beginning of each
epoch. To prove the running time and error bounds, we will use the results of Sections 5.2 and 5.3.
Recall that in this section α and β refer exclusively to the multiplicative and additive noise
levels of f˜. We must first define parameters that will be needed to formally state and prove our
error and running time bounds:
24

• Fix 0 ≤ ε <

1
25

and δ > 0.

• Set parameters of Algorithms 1 and 2 as follows:
– Let y0 ∈ K and let H0 := f˜(y0 ).
– Fix D ≥ 1ε β. For every 0 ≤ k ≤ kmax , let Hk := f˜(xk ) and define Ĥk := max(Hk , D).
– Assume, without loss of generality, that r0 ≤

D 5
λ.

– For every 0 ≤ k ≤ kmax , let Jk := F̂ (xk ). Define Jˆk := max(Jk , D).
0 /D)
– Set the number of epochs to be kmax = d log(5J
e + 1.
log( 1 )
25ε

– At every k ≥ 0, set the temperature to be ξk =
ε
4d log(R/ min( 2λ
D,r0 ))
1
εD
25

– Set r =

ε
4d log(R/ min( 2λ
D,r0 ))
.
1 ˆ
εJk

Define ξ¯ :=

5

.

δ
.
ξ̄ λ̃

– Define


ω 2 b2max
1
η̄ := c min ζmax , d 2 ,
,
¯ 2 + ξL)
¯ 2
λ
d Rd3 ((ξG)
†

and

d log(2 Rr ) + δ + 1 + log( 1δ ) )
B :=
.
ε
2d log(R/ min( 2λ
D, r0 ))
0

– Set the number of steps imax for which we run the the Markov chain X in each epoch
to be


1
 150
1− ε α



¯ + log( 2Rλ̃ )) + 4 log( 1 )


8Rλ̃ξk + 4d(1 + log(1 + ξ)

δ
δ

 + 1.
imax =  


h
i

2
β
β
α
150d
ε
p


0
0


(3+εB + D )+ D log(R/ min( 2λ D,r ))
1
† /de− ε
1−α†
η̄


1536R


– Define B :=

(d log(2 Rr )+δ+log(imax +1)+log( 1δ )))
ε
2d log(R/ min( 2λ
D,r0 ))

.

– For every ξ > 0 define
h
i


β
β
α
ε
0
− 100d

2
2
† (3+εB+ D )+ D log(R/ min( 2λ D,r )) 2 
ε
1−α
(e
)
ω b
η(ξ) := c min ζmax , d 2 , max ,
,
3
2
2


λ
d
Rd ((ξG) + ξL)
where ω = εD, and c is the universal constant in Lemma 15 of [17].
¯
Set the step size at each epoch to be ηk = η(ξk ). Also define η̄ = η(ξ).
√
– Set D = 2η̄d.
We now state the error and running time bounds:
5
This is without loss of generality since if there exists a convex body K0 such that K0 + B(0, r0 ) = K, then for
every 0 < ρ ≤ r0 there must also exist a convex body K00 such that K00 + B(0, ρ) = K, namely K00 = K0 + B(0, r0 − ρ).

25

Theorem 5.9. (Error and running time bounds when using a smooth noisy objective
ε
function) Assume that α ≤ 32
. Then with probability at least 1 − 6δ(kmax + 1) Algorithm 2
returns a point x̂ = xkmax such that
1
(D + β),
1−α

F (x̂) − F (x? ) ≤

h

d

with running time that is polynomial in d, e ε/150
G, ζmax , bmax , and log( 1δ ).

α
1−α†

(3+εB0 + Dβ )+ Dβ

i

ε
log(R/ min( 2λ
D,r0 ))

, R, λ, λ̃, L,

Proof. Set notation as in Algorithms 1 and 2. Denote by X (k) the Markov chain generated by
Algorithm 1 as a subroutine in the k’th epoch of Algorithm 2 with constraint set K.
1
Set hk = Ĥk + ξk−1 d log( 2R
r ) + δ + log(imax + 1) + log( δ ) . Then by Lemma 5.7
P( sup

0≤i≤imax

2R
(k)
f˜(Xi ) ≥ hk ) ≤ (imax + 1) × [eξk [Ĥk +λ̃r]−ξk hk +d log( r ) + 2rλ̃ξk + δ]

≤ eξk Ĥk +δ−ξk hk +d log(

2R
)+log(imax +1)
r

(23)

+ 4δ]

= 5δ,
where the second inequality holds since r =

δ
ξ̄ λ̃

and ξk ≤ ξ¯ for all k.

(k)
But f˜(Xi ) ≥ hk if and only if
(k)

(k)

(k)

F (Xi )(1 + ψ(Xi )) + ϕ(Xi ) ≥ hk
if and only if
1

(k)

F (Xi ) ≥

1+

(k)

(k)
ψ(Xi )

(hk − ϕ(Xi )),

(k)

since 1 + ψ(Xi ) ≥ 0. Also,
1
1+
(k)

(k)

(k)
ψ(Xi )

(hk − ϕ(Xi )) ≤

1
(hk + β),
1 − α†

(k)

since ψ(Xi ) ≥ −α† > −1 and |ϕ(Xi )| < β.
Hence,


Eq. (23)
(k)
˜
5δ ≥ P
sup f (Xi ) ≥ hk
0≤i≤imax


1
(k)
≥P
sup F (Xi ) ≥
(hk + β) .
1 − α†
0≤i≤imax
1
0
0
Define K̂(k) := (K0 ∩ {x ∈ Rd : F (x) ≤ 1−α
† (hk + β) + λr }) + B(0, r ). Then


1
x ∈ K : F (x) ≤
(hk + β) ⊆ K̂(k) ,
1 − α†

since k∇F k ≤ λ. Thus, by Equations (24) and (25),


(k)
P Xi ∈ K̂(k) ∀0 ≤ i ≤ imax ≥ 1 − 5δ.
26

(24)

(25)

(26)

Also, for every x ∈ K̂(k) , since r0 ≤

D
λ,

we have

1
(hk + β) + 2λr0
1 − α†
1
≤
(hk + β) + 2D
1 − α† 



1
R
1
−1
=
Ĥk + ξk
d log(4 ) + δ + log(imax + 1) + log( ) + β + 2D
r
δ
1 − α†
!

R
1
1 ˆ d log(4 r ) + δ + log(imax + 1) + log( 1δ ) )
=
Ĥk + εJk
+ β + 2D
ε
5
2d log(R/ min( 2λ
D, r0 ))
1 − α†

Lemma 5.8
1 
Ĥ
+
ε
Ĥ
B
+
β
+ 2D.
≤
k
k
1 − α†

F (x) ≤

(27)

Thus, for every x ∈ K̂(k) ,
|N (x)| ≤ αF (x) + β
Eq. (27)

≤

α
1 − α†

(28)



Ĥk (1 + εB) + β + 2D + β := Nk .

00

(k)

K̂ (K̂(k) \U εĤk ) ≥
Define Ukε := {x ∈ K̂(k) : F (x) ≤ ε00 } for every ε00 > 0. Then by Lemma 5.3, C(ξF
k
)

for any ξ ≥

ε
4d log(R/ min( 2λ
Ĥk ,r0 )

εĤk

But by Lemma 5.8, ξk =

.

ε
4d log(R/ min( 2λ
D,r0 ))
1 ˆ
εJk

≥

ε
Ĥk ,r0 )
4d log(R/ min( 2λ

εĤk

5

K̂
C(ξ

(k)

˜ (K̂
kf )

(k)

1
R

\UkεĤk )

Eq. (28)

≥
≥

1 − 4d
ε
e
R

Lemma 5.8

≥

(k)

K̂
e−2ξk Nk C(ξ
(K̂(k) \UkεĤk )
kF )

Lemma 5.3

=

, so
(29)

1 −2ξk Nk
e
R
Nk
1 Jˆ
5 k

ε 1
D,r0 ))
log(R/ min( 2λ
5

1 − 4d
ε
e
R
α

Nk
1
25 Ĥk

ε
log(R/ min( 2λ
D,r0 ))

Ĥ (1+εB)+2D+β )+β
†( k

1−α
ε
D,r0 ))
log(R/ min( 2λ
1 − 4d
1
ε
25 Ĥk
= e
R
h
i
ε
1 − 100d α (3+εB+ Dβ )+ Dβ log(R/ min( 2λ
D,r0 ))
≥ e ε 1−α†
,
R

where the first inequality holds by the stability property of the Cheeger constant, and the last
inequality is true since Ĥk ≥ D by definition.
Recall that
h
i


β
β
α
ε
0
− 100d

2
2
† (3+εB+ D )+ D log(R/ min( 2λ D,r )) 2 
ε
1−α
ω b
(e
)
ηk = c min ζmax , d 2 , max ,
(30)


λ
d
Rd3 ((ξk G)2 + ξk L)2


K̂(k) (K̂(k) \U εĤk ))2 

(C
2
2
Eq. (29)
k
ω b
(ξ f˜)
≤ c min ζmax , d 2 , max , 3 k
,
2

λ
d
d ((ξk G) + ξk L)2 
27

where ω = εD.
Recall that X (k) is the subroutine Markov chain described in Algorithm 1 with inputs specified
by Algorithm 2 and constraint set K. Let X̂ (k) be the Markov chain generated by Algorithm 1
(k)
(k)
(k)
with constraint set K̂r0 and initial point X0 = X̂0 . Let Y (k) be the Markov chain generated by
(k)
Algorithm 3 with constraint set K̂r0 . Couple the Markov chains as in definition 5.4.
Write
(UkεĤk )ω/λ := (UkεĤk + B(0, ω/λ)) ∩ K̂(k)
as shorthand. Then by Lemma 15 of [17] and by Equation (30), the Markov chain X̂ (k) is ε0 -close
to Y (k) with ε0 ≤ 14 ΦY (K̂(k) \(UkεĤk )ω/λ ) and
1 p
εĤk
(k)
K̂(k)
)ω/λ )
ηk /dC(ξ
˜ (K̂ \(Uk
kf )
1536
h
i
β
β
Eq. (29)
α
ε
0
1 p
− 100d
† (3+εB+ D )+ D log(R/ min( 2λ D,r ))
ε
1−α
≥
ηk /de
.
1536R

ΦY (K̂(k) \(UkεĤk )ω/λ )) ≥

(31)

Recall that by Equation (15) of Proposition 5.6, for every A ⊆ K0 , we have
ν0 (A) ≤ e4Rλ̃ξk +dlog(

2R
)
r

(k)

µK̂
(A).
ξ f˜
k

Therefore, since X̂ (k) is ε0 -close to Y (k) , by Lemma 11 of [17], with probability at least 1 − δ we
have
τX̂ (k) ((UkεĤk )ω/λ ) ≤

4 log(e2Rλ̃ξk +dlog(

2R
)
r

/δ)

(32)

Φ2Y (K̂(k) \(UkεĤk )ω/λ )
1
8Rλ̃ξk + 4dlog( 2R
r ) + 4 log( δ )

Eq. (31)

≤



1
1536R

p
− 100d
ηk /de ε

h

α
1−α†

(3+εB+ Dβ )+ Dβ

i

ε
log(R/ min( 2λ
D,r0 ))

=

¯ + log( 2Rλ̃ )) + 4 log( 1 )
8Rλ̃ξk + 4d(log(ξ)
δ
δ
2
h
i
β
β
α
100d
ε
p
0
− ε
1
† (3+εB+ D )+ D log(R/ min( 2λ D,r ))
1−α
ηk /de
1536R

≤

¯ + log( 2Rλ̃ )) + 4 log( 1 )
8Rλ̃ξk + 4d(log(1 + ξ)
δ
δ
2
h
i
β
β
100d
α
ε
p
− ε
3+εB+ D )+ D log(R/ min( 2λ D,r0 ))
(
1
†
1−α
ηk /de
1536R

≤

¯ + log( 2Rλ̃ )) + 4 log( 1 )
8Rλ̃ξk + 4d(1 + log(1 + ξ)
δ
δ
2
h
i
β
β
100d
α
ε
p
0 ))
−
3+εB+
+
log(R/
min(
D,r
(
)
1
†
ε
D
D
2λ
1−α
η̄/de
1536R

≤

≤

2

¯ + log( 2Rλ̃ )) + 4 log( 1 )
8Rλ̃ξk + 4d(1 + log(1 + ξ)
δ
δ
1
1536R

p
− 150d
η̄ † /de ε

h

α
1−α†

(3+εB0 + Dβ )+ Dβ

i

ε
log(R/ min( 2λ
D,r0 ))− 75
α log(imax +1)
ε

2

¯ + log( 2Rλ̃ )) + 4 log( 1 )
8Rλ̃ξk + 4d(1 + log(1 + ξ)
150
δ
δ
× (imax + 1) ε α

h
i
2
α
ε
p
− 150d
D,r0 ))
(3+εB0 + Dβ )+ Dβ log(R/ min( 2λ
1
η̄ † /de ε 1−α†
1536R
28

≤ imax ,
where the first equality is true since r =

δ
,
ξ̄ λ̃

the fourth inequality is true by the definition of η̄, the

η̄ † ,

fifth inequality is true by the definition of
and the last inequality is true by our choice of imax .
(k)
(k)
But by Equation (26), Xi = X̂i with probability at least 1 − 5δ. Therefore, since Equation
(32) holds with probability at least 1 − δ, we have that
τX (k) ((UkεĤk )ω/λ ) ≤ imax .

(33)

with probability at least 1 − 6δ.
Therefore, by Equation (33), with probability at least 1 − 6δ for some 0 ≤ i◦k ≤ imax we have
(k)

Xi◦ ∈ (UkεĤk )ω/λ̃ and hence that
k

(k)

F (Xi◦ ) ≤ εĤk + λ̃ ×
k

ω
= εĤk + εD ≤ 2εĤk
λ̃

and therefore, since 0 ≤ α < 1,
Lemma 5.8
1˜
(k)
(k)
(k)
f (xk+1 )
≤
F̂ (xk+1 ) = min F̂ (Xi ) ≤ F̂ (Xi◦ ) ≤ 2F (Xi◦ ) + β ≤ 4εĤk + β ≤ 5εĤk .
k
k
0≤i≤imax
5

Hence, for every 0 ≤ k ≤ kmax we have
f˜(xk+1 ) = Hk+1 ≤ 25εĤk = 25ε max(Hk , D)
with probability at least 1 − 6δ.
Therefore, by induction on Equation (34), for every 0 ≤ k ≤ kmax , we have


Hk+1 ≤ 25ε × max (25ε)k H0 , D

(34)

(35)

with probability at least 1 − 6δ(k + 1).
0 /D)
0 /D)
By Lemma 5.8, we have kmax = d log(5J
e + 1 ≥ d log(H
e + 1. Then, with probability at least
log( 1 )
log( 1 )
1 − 6δ(kmax + 1),

25ε

25ε

f˜(xkmax ) − F (x? ) = f˜(xkmax )
= Hkmax
Eq. (35)

≤



kmax −1
25ε × max (25ε)
H0 , D

≤ 25ε × D
≤ D,
since 0 ≤ ε <
Hence,

1
25

implies that 0 ≤ 25ε < 1.
F (xkmax ) − F (x? ) = F (xkmax )
1
≤
(f˜(xkmax ) + β)
1−α
1
≤
(D + β),
1−α

where the first equality holds since F (x? ) = 0.
29

(36)

5.6

The non-smooth case

In this section we bound the gradient, supremum, and smoothness of the smoothed function fσ
obtained from F (Propositions 5.10 and 5.11 and Lemma 5.12), where fσ is defined in Equation
(7). We also bound the noise |F (x) − fσ (x)| of fσ (Lemma 5.13). We use these bounds in Section
5.8 to Prove our main result (Theorem 4.1).
Proposition 5.10. (Gradient bound for smoothed oracle)
For every x ∈ K we have
√
2d
k∇f˜σ (x)k ≤
(2λR(1 + 2α) + 2β).
σ
Proof.

1
kZk F̂ (x + Z) − F̂ (x)
σ2


1
≤ EZ
kZk max |F̂ (y2 ) − F̂ (y1 )|
y1 ,y2 ∈K
σ2


1
1
≤
max |F̂ (y2 ) − F̂ (y1 )|EZ
kZk
σ y1 ,y2 ∈K
σ


1
1
≤
max |F̂ (y2 ) − F̂ (y1 )|EZ
kZk
σ y1 ,y2 ∈K
σ
√ Γ( d+1
1
2 )
=
max |F̂ (y2 ) − F̂ (y1 )| 2
d
σ y1 ,y2 ∈K
Γ( 2 )
√
2d
≤
max |F̂ (y2 ) − F̂ (y1 )|
σ y1 ,y2 ∈K
√
2d
(2λR(1 + 2α) + 2β),
≤
σ

k∇f˜σ (x)k ≤ EZ



where the equality is true since σ1 kZk has χ distribution with d degrees of freedom, and the second√
Γ( d+1 )
to-last inequality is true since Γ( d2 ) ≤ d. The last ineqaulty is true because F is λ-Lipschitz,
2

and because of our assumption on the noise (Equation (6)).
Proposition 5.11. (maximum value of non-smooth noisy oracle) For every x ∈ Kr , we have
F̂ (x) ≤ (1 + α)2λ(R + r) + β.
Proof. Since F is λ-Lipschitz and by our assumption that F (x? ) = 0,
F (x) ≤ 2λ(R + r)

∀x ∈ Kr .

Thus,
F̂ (x) ≤ (1 + α)F (x) + β ≤ (1 + α)2λ(R + r) + β.

We recall the following Lemma from [17]:
30

(37)

Lemma 5.12. (Lemma 17 in [17]) Suppose that M̂ > 0 is a number such that 0 ≤ F̂ (x) ≤ M̂
for all x ∈ Kr then
1.
EZ [gZ (x)] = ∇f˜σ (x)

∀x ∈ K.

2. For every u ∈ Rd ,
2

EZ [ehu,gZ (x)i(2M̂ /σ) ] ≤ e

4M̂ 2
kuk2
σ2

.

3.
k∇2 f˜σ (x)kop ≤

2M̂
.
σ2

We show that the smoothed gradient is a good approximation of F for sufficiently small σ:
Lemma 5.13. (Noise of smoothed oracle) Let A ⊆ At ⊆ Kr for some A ⊆ Kr and some t > 0.
Let H 0 = supy∈A F (y). Then
√
t2 /σ 2 −d
|f˜σ (x) − F (x)| ≤ λσ(1 + α) d + H 0 × e− 8
+ αH 0 + β
for every x ∈ A.
Proof. Define N(x) := F̂ (x) − F (x). For any function h : Rd → R, define
h̃σ (x) := EZ [h(x + Z)],
where Z ∼ N (0, σ 2 Id ). Then for every x ∈ A we have,
|f˜σ (x) − F (x)| = |F̃σ (x) + Ñσ (x) − F (x)|
≤ |F̃σ (x) − F (x)| + |Ñσ (x)|
= EZ [|F (x + Z) − F (x)|] + |EZ [N(x + Z)]|
≤ EZ [|F (x + Z) − F (x)|] + EZ [α(H 0 + λkZk) + β]
≤ EZ [λkZk] + H 0 × P(kZk ≥ t) + EZ [α(H 0 + λkZk) + β]
= λ(1 + α)EZ [kZk] + H 0 × P(kZk ≥ t) + αH 0 + β
1
1
t
= λσ(1 + α)EZ [ kZk] + H 0 × P( kZk ≥ ) + αH 0 + β
σ
σ
σ
√
1
t
0
≤ λσ(1 + α) d + H × P( kZk ≥ ) + αH 0 + β
σ
σ
√
t2 /σ 2 −d
≤ λσ(1 + α) d + H 0 × e− 8
+ αH 0 + β,

where the second inequality holds because F is λ-Lipschitz on Kr and also since F is defined to
be zero outside Kr with x ∈ K ⊆ Kr . The third inequality holds by our assumption on the noise
(Equation (6)), and since F is defined to be zero outside Kr . The fourth inequality holds because
1
σ kzk is χ-distributed with d degrees of freedom. The last inequality holds by the Hanson-Wright
inequality (see for instance [8], [15]).
31

5.7

Rounding the domain of the Markov Chain

We now show that our constraint set K̂ is sufficiently “rounded”. This roundness property is used
to show that the Markov chain does not get stuck for a long time in corners of the constraint set.
0

r
)2 . Let K̂ ⊆ K0 be a
Lemma 5.14. (Roundness of constraint set) Let ζmax = ( 10√2(d+20)

convex set. Then for any ζ ≤ ζmax and any x ∈ K̂r0 the random variable W ∼ N (0, Id ) satisfies
P(

p
1
2ζW + x ∈ K̂r0 ) ≥ .
3

Proof. Without loss of generality, we may assume that x is the origin and that K̂r0 contains the ball
B(a, r0 ) where a = (r0 , 0, . . . , 0)> (since K̂r0 = K̂ + B(0, r0 ) implies that there is a ball contained in
K̂r0 that also contains x on its boundary. We can then translate and rotate K̂r0 to put x and a in
the desired position).
1
Since P( 10
≤ W1 ≤ 100) ≥ 0.45, with probability at least 0.45 we have that
1
≤ W1 ≤ 100
10
0

r
but ζmax = ( 10√2(d+20)
)2 , and hence, with probability at least 0.45,

But our choice of ζmax

√
2ζ
r0
√
.
(d
+
20)
≤
W
≤
1
r0
2ζ
q 02
implies that (r2ζ) − r 1 0 2 (d + 20) > 0, implying that
(r )
2ζ

s

s

0
0 )2
0 )2
(r
(r
r0
r
1
1
√ −
− q 0 2 (d + 20) ≤ W1 ≤ √ + 
− q 0 2 (d + 20) .
(r )
(r )
2ζ
2ζ
2ζ
2ζ
2ζ

But

√

a−

√t
a

≤

√

2ζ

a − t for every t ∈ [0, a), which implies
r0
√ −
2ζ

s

(r0 )2
r0
− (d + 20) ≤ W1 ≤ √ +
2ζ
2ζ

s

(r0 )2
− (d + 20).
2ζ

Therefore
r0 −

p
p
p
(r0 )2 − 2ζ(d + 20) ≤ 2ζW1 ≤ r0 + (r0 )2 − 2ζ(d + 20).

Hence,
p
( 2ζW1 − r0 )2 ≤ (r0 )2 − 2ζ(d + 20),
which implies that
p
( 2ζW1 − r0 )2 + 2ζ(d + 20) ≤ (r0 )2 .

(38)

But by the Hanson-Wright inequality
d
X
21
1
P(
Wj2 ≥ d + 20) ≤ e− 8 < .
10
j=2

32

(39)

Thus, Equations (39) and (38) imply that with probability at least 0.45 −
k

1
10

≥

1
3

we have

p
p
2ζW − ak = k 2ζW − (r0 , 0, . . . , 0)> k2
d
X
p
0 2
= ( 2ζW1 − r ) + 2ζ
Wj2
j=2

p
≤ ( 2ζW1 − r0 )2 + 2ζ(d + 20)
Eq. (38)

≤

(r0 )2 ,

implying that W ∈ B(a, r0 ) ⊆ K̂r0 with probability at least 31 .

5.8

Proof of Main Result (Theorem 4.1)

In this section, we prove Theorem 4.1. We do so by applying the bounds on the smoothness of fσ
of Section 5.6 to Theorem 5.9.
We note that in this section we will use “α” and “β” exclusively to denote the multiplicative
and additive noise levels of F . We will then set the smooth oracle f˜ to be f˜ = f˜σ , where f˜σ is the
smooth function obtained from F , defined in Equation (7). As an intermediate step in proving the
main result, we show that f˜σ has multiplicative noise level 2α and additive noise level 2β.
1
Proof. We will assume that α < 800
. This assumption is consistent with the statment of Theorem
4.1, which assumes that α = O(1).
Define the following constants: M = 2λR + 2β, M̂ = 6λR + β, L = 4σM̂2 , G = 2σM̂ , bmax = 1,

2
√
r0
ζmax = 10√2(d+20)
, and λ̃ = σ2d (2λR(1 + 2α) + 2β).
!

We set σ =

1
2

min

β √ q
r
,
1
λ(1+α) d
log( α
)+d

. Recall from Section 3.3 that σ determines the amount

of smoothness in f˜σ . A larger value of σ means that f˜σ will be smoother, decreasing the running
time of the algorithm. On the other hand, a smaller value of σ means that f˜σ will be a closer
approximation to F , and consequently lead to a lower error. We choose σ in such a way so that
the error ε̂ will be bounded by the desired value ε̂.
Set parameters of Algorithms 1 and 2 as follows:
• Fix ε =

1
50 .

• Let D = 23 ε̂.
• Define J0 := F̂ (x0 ) and set the number of epochs to be


log(5J0 /D)
+ 1.
kmax =
log(2)
• For every 0 ≤ k ≤ kmax , let Jk := F̂ (xk ), and define Jˆk := max(Jk , D).
• Fix δ =

δ0
6(kmax +1) .

33

(40)

• At every k ≥ 0, set the temperature to be
ξk =

ε
4d log(R/ min( 2λ
D, r0 ))
.
1 ˆ
εJk

(41)

5

Define ξ¯ :=
• Set r =

ε
4d log(R/ min( 2λ
D,r0 ))
.
1
εD
25

δ
.
ξ̄ λ̃

• Define


ω 2 b2max
1
η̄ := c min ζmax , d 2 ,
,
¯ 2 + ξL)
¯ 2
λ
d Rd3 ((ξG)
†

and

d log(2 Rr ) + δ + 1 + log( 1δ ) )
.
B :=
ε
2d log(R/ min( 2λ
D, r0 ))
0

• Set the number of steps imax for which we run the the Markov chain X in each epoch to be


1
 150
1− ε α



¯ + log( 2Rλ̃ )) + 4 log( 1 )


8Rλ̃ξk + 4d(1 + log(1 + ξ)

δ
δ
 + 1. (42)

imax =  


h
i

2
150d
α
p
0 + β + β log(R/ min( ε D,r 0 ))
−
3+εB


(
1
ε
D) D
2λ
† /de
1−α†
η̄


1536R


• Define B :=

(d log(2 Rr )+δ+log(imax +1)+log( 1δ )))
ε
2d log(R/ min( 2λ
D,r0 ))

.

• For every ξ > 0 define
h
i


β
β
α
ε
0
− 100d

2
2
† (3+εB+ D )+ D log(R/ min( 2λ D,r )) 2 
ε
1−α
)
(e
ω b
η(ξ) := c min ζmax , d 2 , max ,
,
3
2
2


λ
d
Rd ((ξG) + ξL)

(43)

where ω = εD, and c is the universal constant in Lemma 15 of [17]. We set the step size at
¯
each epoch k to be ηk = η(ξk ). We also define η̄ := η(ξ).
√
• Set D = 2η̄d.
We determine the constants for which f˜ =!f˜σ satisfies the various assumptions of Theorem 5.9.
Since σ =

1
2

min

β √
, q r
λ(1+α) d 8 log( 1 )+d
α

, by Lemma 5.13, we have that

|f˜σ (x) − F (x)| ≤ 2αF (x) + 2β

∀x ∈ K.

So, with a slight abuse of notation, we may state that f˜ = f˜σ has multiplicative noise of level 2α
and additive noise of level 2β, if we use “α” and “β” to denote the noise levels of F̂ .
Hence, M = 2λR + 2β ≥ supx∈K f˜σ (x). By Lemma 5.14, part 1 of Assumption 1 is satisfied
with constant ζmax . By Lemma 5.12 and Proposition 5.11, f˜σ satisfies parts 2 and 3 of Assumption
1 with constants L, G and bmax , (recall that we defined these constants at the beginning of this
34

proof). By Proposition 5.10, k∇f˜σ (x)k ≤ λ̃ for all x ∈ K. Therefore, applying Theorem 2 with the
above constants and the smoothed function fσ , we have,
F (x̂) − F (x? ) ≤

1
(D + 2β) ≤ ε̂,
1 − 2α
h

i

α
ε
8d
D,r0 ))
(3+εB0 + Dβ )+ Dβ log(R/ min( 2λ
, R, λ, λ̃, L, G,
with running time that is polynomial in d, e ε 1−α†
1
ζmax , bmax , and log( δ ). This completes the proof of the Theorem.

References
[1] David Applegate and Ravi Kannan. Sampling and integration of near log-concave functions.
In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages
156–163. ACM, 1991.
[2] Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. Escaping
the local minima via simulated annealing: Optimization of approximately convex functions.
In Conference on Learning Theory, pages 240–265, 2015.
[3] Avrim Blum and Ronald L Rivest. Training a 3-node neural network is np-complete. In
Advances in neural information processing systems, pages 494–501, 1989.
[4] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Finite-time analysis of projected Langevin
Monte Carlo. In Advances in Neural Information Processing Systems 28: Annual Conference
on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec,
Canada, pages 1243–1251, 2015.
[5] Ruobing Chen. Stochastic derivative-free optimization of noisy functions. Ph.D. Thesis, Lehigh
University, 2015.
[6] Ruobing Chen, Matt Menickelly, and Katya Scheinberg. Stochastic optimization using a trustregion method and random models. Mathematical Programming, pages 1–41, 2015.
[7] 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.
[8] David Lee Hanson and Farroll Tim Wright. A bound on tail probabilities for quadratic forms
in independent random variables. The Annals of Mathematical Statistics, 42(3):1079–1083,
1971.
[9] Mohamed Jebalia and Anne Auger. On Multiplicative Noise Models for Stochastic Search,
pages 52–61. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008.
[10] Mohamed Jebalia, Anne Auger, and Nikolaus Hansen. Log-linear convergence and divergence
of the scale-invariant (1 + 1)-ES in noisy environments. Algorithmica, 59(3):425–460, 2011.
[11] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science,
220(4598):671–680, 1983.
[12] Yin Tat Lee and Santosh S Vempala. Convergence rate of riemannian hamiltonian monte carlo
and faster polytope volume computation. arXiv preprint arXiv:1710.06261, 2017.
35

[13] László Lovász and Miklós Simonovits. Random walks in a convex body and an improved
volume algorithm. Random structures & algorithms, 4(4):359–412, 1993.
[14] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic
gradient Langevin dynamics: a nonasymptotic analysis. In Satyen Kale and Ohad Shamir,
editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings
of Machine Learning Research, pages 1674–1703, Amsterdam, Netherlands, 07–10 Jul 2017.
PMLR.
[15] Mark Rudelson and Roman Vershynin. Hanson-wright inequality and sub-Gaussian concentration. Electron. Commun. Probab, 18(82):1–9, 2013.
[16] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics.
In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages
681–688, 2011.
[17] Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient
Langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017,
Amsterdam, The Netherlands, 7-10 July 2017, pages 1980–2022, 2017.

36

