Submitted to the Annals of Applied Probability

arXiv:0911.3950v4 [] 15 Nov 2015

RANDOMIZED INTERIOR POINT METHODS FOR
SAMPLING AND OPTIMIZATION
By Hariharan Narayanan
Department of Statistics and Department of Mathematics
University of Washington, Seattle, 98105, USA
harin@uw.edu
We present a Markov Chain, “Dikin walk”, for sampling from a
convex body equipped with a self-concordant barrier. This Markov
Chain corresponds to a natural random walk with respect to a Riemannian metric defined using the Hessian of the barrier function.
For every convex set of dimension n, there exists a self-concordant
barrier whose self-concordance parameter is O(n). Consequently, a
rapidly mixing Markov Chain of the kind we describe can be defined
(but not always be efficiently implemented) on any convex set. We
use these results to design an algorithm consisting of a single random walk for optimizing a linear function on a convex set. Using
results of Barthe [2] and Bobkov and Houdré [5], on the isoperimetry
of products of weighted Riemannian manifolds, we obtain sharper
upper bounds on the mixing time of a Dikin walk on products of
convex sets than the bounds obtained from a direct application of
the Localization Lemma. The results in this paper generalize previous results of [12] from polytopes to spectrahedra and beyond, and
improve upon those results in a special case when the convex set is a
direct product of lower dimensional convex sets. This Markov Chain
like the chain described in [12] is affine-invariant.

MSC classification: 65C40, 90C30
Keywords: Random walks, Interior point methods
1. Introduction. The task of sampling from distributions supported in
high dimensional Euclidean space arises frequently in Statistics. In particular, the question of sampling from a nearly uniform distribution supported
on high dimensional convex set arises naturally in the task of computing the
volume [6] of the latter. Markov Chains that are rapidly mixing are a tool
for sampling. The usual strategy for sampling from distributions supported
on high dimensional Euclidean space is to design a rapidly mixing Markov
Chain whose stationary distribution is the desired distribution, run it for
sufficiently long and then pick the final point as a sample.
Previous sampling algorithms were applicable to convex sets specified in
the following way. The input consists of an n-dimensional convex set K
1
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

2

circumscribed around, and inscribed in, balls of radius r and R respectively.
The algorithm has access to an oracle which when supplied with a point in
Rn answers “yes” if the point is in K and “no” otherwise. If these balls are
not provided, the convex set could be either extremely small or extremely
large, making it impossible to sample the convex set in any fixed time frame.
The first polynomial time algorithm for sampling convex sets appeared
in [6]. It did a random walk on a sufficiently dense grid. The dependence of
its mixing time on the dimension was O∗ (n23 ). It resulted in the first randomized polynomial time algorithm to approximate the volume of a convex
set. A long series of works directed to improving the complexity culminated
in the work of Lovász and Vempala, who achieve a mixing time of O∗ (n4 )
in [19]. Another random walk for sampling convex sets, known as the ball
walk, does the following. Suppose the current point is xi . A point y is chosen
uniformly at random from a ball of radius δ centered at xi . If y ∈ K, xi+1
is set to y; otherwise xi+1 = xi . After many successive improvements over
several papers, it was shown in [11] that if δ < √rn a ball walk mixes in
2

O∗ (n Rδ2 ) steps from a warm start (i. e. a distribution whose density with respect to the uniform measure is bounded above by a universal constant). A
third random walk analyzed more recently by Lovász and Vempala
is known

R
as Hit-and-Run [17, 20]. This walk mixes in O n3 ( Rr )2 ln d
steps from a
point at a distance d from the boundary [20], where  is the desired variation
distance to stationarity.
There has been previous work converting sampling algorithms into algorithms for optimization, notably the work of Bertsimas and Vempala [4, 33].
Their algorithm can be be viewed as a randomized analogue of Vaidya’s algorithm [32], wherein the role of the analytic center is played by the center
of mass. In our work, we instead borrow the central idea of Karmarkar’s
algorithm, namely projective rescaling, to obtain a randomized algorithm
for convex optimization. We need to perform this step just once, although
affine rescaling occurs at every step. Generalizing prior work with Kannan
on polytopes [12], in Theorem 1 we present a Markov Chain for sampling
from a convex body defined by logarithmic, hyperbolic and self-concordant
barriers (see Section 3). When restricted to the case of polytopes, the bounds
we present imply, up to universal constants, the bounds in [12]. In our case,
the “Dikin random walk” uses Gaussian steps having ellipsoidal covariance
to make its individual steps, and is described in Section 5.1.
There is also work on sampling lattice points in polytopes based on sampling real points from the normalized Lebesgue measure in a polytope [13].
We believe that in cases where the solution is NP-hard, for example integer programming, randomized algorithms hold promise. While we are not
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

3

aware of any advantage that our method possesses for the task of minimizing a linear form over a convex set over using an interior point algorithm
associated with the barrier, we believe in the utility of our randomized optimization scheme for integer programming. Huang and Mehrotra [10] have
used a variety of geometric random walks for integer programming, including our random walk. The Dikin random walk (and a long-step variant of it)
were implemented alongside the so-called ball walk and Hit-and-Run random
walks by the authors of [10]. In several cases our methods are competitive.
In their approach instead of rounding the solution of an LP, they round the
result of a biased random walk. Although deterministic algorithms perform
better for solving LPs, it seems conceivable that the randomized algorithms
produce better starting points for heuristics for solving integer programs.
Another application of geometric random walks that we have not discussed
is volume computation. The results of Huang and Mehrotra suggest that
integer programming, or more generally, non-convex optimization are areas
that could benefit from the use of geometric random walks.
In joint work with Alexander Rakhlin, we used the Dikin walk to obtain
a low regret algorithm for online convex optimization (see [23]). A property
of the Dikin walk that was crucially used in that paper was that the bound
on the conductance is ”scale-free”, when a metropolis rule is overlayed for
sampling from exponential distributions. This feature is not known to be
shared by other random walks on convex sets, although the conductance of
Hit-and-Run is known to be scale-free by the work of Lovász and Vempala
[20] when sampling from the uniform distribution.
A self-concordant barrier F (see [31]) on a convex set K, is a convex
function whose domain is the interior of K, that tends to infinity as one approaches its boundary, and whose second derivative at a point along any unit
direction is large in a suitable sense compared to its first and third derivatives
along the same vector. In order to convey the basic idea of Theorem 1, let
D2 F (x) be the Hessian matrix of F at x. We define the transition measure
Px corresponding to x to be roughly
a Gaussian whose covariance matrix
−1
2
is a fixed multiple of D F (x)
. The properties of the barrier function
cause the random walk to avoid the boundary, but at the same time cause it
to take relatively large steps. For example, let K be the 2-dimensional Euclidean ball {x : kxk ≤ R} and F (x) := − ln(R2 − kxk2 ) be a self-concordant
barrier for it. Then, for x ∈ K, up to constants, the expected magnitude
of the component of a step in the radial direction is R − kxk, while the expected
magnitude of the component in the transverse direction is roughly
p
R2 − kxk2 . It can be shown that the mixing time from 0 is independent
of the diameter 2R, and that the size and typical orientation of a step vary
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

4

according to the local geometry.
In Theorem 3 we use this random walk to design an algorithm for optimization, which essentially consists of doing such a random walk on a
projectively transformed version of K. This transformation preferentially
dilates regions corresponding to a larger objective value, causing them to
occupy more space and hence become the target of a random walk. In the
case of polytopes, a slightly different version of this appeared in [12]. The
Markov Chain considered in [12] was ergodic, while the one we use here is
not. The analysis of the non-ergodic Markov Chain hinges upon the fact that
it can be viewed as a limit of ergodic Markov Chains. Suppose K is defined
by a semidefinite constraint of rank at most νh and at most m additional
linear constraints, i. e.
X

xi Ai  B},
K := x Ax ≤ b ∩ {x
i

where x := (x1 , . . . , xn )T , A is an m × n matrix, and each Ai is a νh ×
νh symmetric positive definite matrix, as is B. The symbol  indicates
domination in the symmetric positive definite cone. Our results specialize to
the following statement.
Let s ≥ |p|
|q| for any chord pq of K passing through a point x ∈ K. Let ρt
stand for the density of the tth point xt of the Dikin walk. Then, after



1
t = O n(m + nνh ) n ln((m + nνh )s) + ln

steps are taken by a Dikin walk starting at x, the total variation distance
and the L2 distance of the density ρt (·) of the point to the uniform density
are less than .
One technical contribution of this paper is a family of lower bounds (see
Theorem 8) for the isoperimetric constants of weighted Riemannian manifolds on which interior point methods perform a kind of steepest descent.
While the results in [12] used the isoperimetric properties of the “Hilbert
metric,” we use a Riemannian metric. It is not clear whether the Hilbert
metric can be used to obtain the results in this paper, because we consider
convex sets defined by a combination of three barriers of increasingly general type - logarithmic, hyperbolic and self-concordant. These barriers are
defined in Section 3. The logarithmic, hyperbolic and self-concordant barriers give rise to metrics possessing progressively weaker regularity properties.
The net metric that we are (seemingly) forced to use is a weighted sum of
the three metrics, where the weights take care of this progressively weakening regularity. It is unclear how the somewhat disparate issues that arise
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

5

from the use of a combination of these different kinds of metrics could be
dealt with in a unified way if one directly used the Hilbert metric. The proof
of our mixing bounds follows the broad outline of most results on mixing
in geometric random walks. We first prove a purely geometric isoperimetric
inequality for a “Dikin manifold”. We then obtain a bound on the probabilistic distance between the one-step densities starting from two nearby
points.
We end this section with an outline of the paper. Section 2 describes past
work on sampling convex sets. Section 3 describes self-concordant barriers,
which are needed to define the Dikin walk. Section 4 defines the oracle
model that will form the framework of our algorithm. Section 5 describes
the three main theorems, Theorem 1, Theorem 2 and Theorem 3. Section 6.1
introduces a “Hessian metric” based on a self-concordant barrier. Section 7
describes the proof of Theorem 1. Section 8 describes the proof of Theorem 2.
Section 9 describes the proof of Theorem 3. We have provided the proofs of
lemmas in the Appendix.
2. Comparison with related work. We begin with some definitions
that are used in related work.
Definition 1 (Warm start). Let ρ0 be a starting distribution for a
Markov Chain x0 , x1 , . . . whose stationary distribution is the uniform distribution µ on a convex set K. We say ρ0 is a warm start for the chain if
there is a fixed universal constant C such that
sup
A

ρ0 (A)
< C,
µ(A)

where the supremum is taken over all measurable subsets A.
Definition 2 (Mixing time). Let ρ0 be a starting distribution for a
Markov Chain x0 , x1 , . . . whose stationary distribution is the uniform distribution µ on a convex set K. Let ρt be the distribution of the tth point
of the Dikin walk. We define the mixing time in total variation distance
TT V (, ρ0 ) to be the smallest t such that the total variation distance of ρt (·)
to the uniform distribution on K is less thanq.
R
2
For every bounded f , let kf k2,µ denote
K f (x) dµ(x). Let ft (x) :=
ρt (x) − (vol(K))−1 . We define the mixing time in L2 distance T2 (, ρ(x0 ))
to be the smallest t such that
kft k2,µ < .
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

6

Let B(x, τ ) be defined to be the n−dimensional Euclidean ball of radius
τ centered at x and suppose K is an n-dimensional convex set such that
B(0, r) ⊆ K ⊆ B(0, R). The Markov Chain known as the “Ball walk” [18],
[11] is defined as follows. If the random walker is at a point xi in a convex
body K at time step i, a random point z is picked in B(xi , O( √1n )), and
xi+1 is set to z if it lies in K, otherwise the move is rejected and xi+1 is set
to xi . The mixing time of this walk from a warm startin order
 to achieve a
n2 R2
∗
constant total variation distance to stationarity is O
(where O∗ (T )
r2
is synonymous with T logO(1) T ). More recently, a random walk known as
Hit-and-Run, was analyzed in [17] and [20]. If the random walker is at a
point xi in a convex body K at time step i, a vector is picked from the
uniform distribution on the sphere and through xi , and xi+1 is chosen from
the uniform measure on the chord {xi + lv l ∈ R} ∩ K. Unlike the Ball
walk, this walk provably mixes rapidly from any interior point, with a weak
(logarithmic) dependence on the distance of the starting point from

 2 the
2
,
boundary. From a warm start, the mixing time of Hit-and-Run is O n rR
2
and its mixing time from a fixed point at a distance d from the boundary is
O n3 ( Rr )2 ln Rd .
The mixing time of the Dikin walk in two cases of interest are as follows
(details are provided in Theorem 1). Let x ∈ K and for all chords pq passing
n
through x, |p−x|
|q−x| ≤ s. We will call such a point x, s−central. Suppose K ∈ R
is
1. the intersection of an n−dimensional affine subspace (identified with
Rn ) with the semidefinite cone S νh ×νh of νh × νh matrices endowed
with the hyperbolic barrier F (x) = − ln det x or
2. the intersection of m = ν2h ellipsoids, A1 B ∩ A2 B ∩ · · · ∩ Am B where Ai
are non-singular affine transformations and B is
Pthe Euclidean Ball.
2
In this case, the hyperbolic barrier is F (x) = − ln(1 − kA−1
i (x)k ).
Then we define the complexity parameter of the barriers as ν = nνh and
the mixing time starting at x is O(nν(n ln(νs) + ln 1 )). Whether or not the
bodies are in isotropic position, in the above cases 1. and 2. corresponding
to semidefinite and quadratic programs, when νh = O(n1− ) [and so ν =
O(n2− ) and the mixing time from a warm start is O(n3− )], the mixing
time bounds are an improvement over the existing bound for Hit-and-Run
√
[20], which is O(n3 ) (assuming R/r = Ω( n)) .
Lovász [17] proved a lower bound of Ω(n2 p2 ) on the mixing time of Hitand-Run in a cylinder Bn × [−p, p] from a warm start, where Bn is the unit
ball in n−dimensions. Dikin walk has a mixing time of O(n2 ) from a warm
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

7

start. Thus for a cylinder with p = ω(1), the lower bound on the number of
steps needed for Hit-and-Run to mix (without rescaling the body) is larger
than the upper bound on the number of steps for Dikin walk.
In the specific case where the constraints are either semidefinite or linear,
we can compare the upper bounds on the number of arithmetic operations
needed for one step in Hit-and-Run and Dikin walk. This has been done in
Section 10.
3. Self-concordant barriers. Let K be a convex subset of Rn that is
not contained in any n − 1-dimensional affine subspace and int(K) denote
its interior. For any function F on int(K) having continuous derivatives of
order k, for vectors h1 , . . . , hk ∈ Rn and x ∈ int(K), for k ≥ 1, we recursively
define
Dk F (x)[h1 , . . . , hk ] :=
Dk−1 F (x + hk )[h1 , . . . , hk−1 ] − Dk−1 F (x)[h1 , . . . , hk−1 ]
,
→0

lim

where D0 F (x) := F (x). Following Nesterov and Nemirovskii [27], we call
a real-valued function F : int(K) → R, a regular self-concordant barrier if
it satisfies the conditions stated below. For convenience, if x 6∈ int(K), we
define F (x) = ∞.
1. (Convex, Smooth) F is a convex thrice continuously differentiable
function on int(K).
2. (Barrier) For every sequence of points {xi } ∈ int(K) converging to a
point x 6∈ int(K), limi→∞ f (xi ) = ∞.
3. (Differential Inequalities) For all h ∈ Rn and all x ∈ int(K), the
following inequalities hold.
(a) D2 F (x)[h, h] is 2-Lipschitz continuous with respect to the local
norm, which is equivalent to
3

D3 F (x)[h, h, h] ≤ 2(D2 F (x)[h, h]) 2 .
4. F (x) is ν-Lipschitz continuous with respect to the local norm defined
by F ,
|DF (x)[h]|2 ≤ νD2 F (x)[h, h].
We call the smallest non-negative real number ν for which this holds for
all h ∈ Rn and x in the interior of K, the self-concordance parameter
of the barrier.

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

8

It follows from these conditions that if F is a self-concordant barrier for
K and A is a non-singular affine transformation, then FA (x) := F (A−1 x)
is a self-concordant barrier for AK. This fact is responsible for the affineinvariance of Dikin walk. Some examples of convex sets for which explicit
barriers are known are
1. Convex sets defined by hyperbolic constraints. This set includes sections of semidefinite cones. Polytopes and the intersections of ellipsoids
can be expressed as sections of semidefinite cones.
2. Convex sets defined by the epigraphs of matrix norms (see page 199
of [27]).
For other examples and methods of constructing barriers for new convex
sets by combining existing barriers, see Chapter 5 of [27].
3.1. Generic self-concordant barrier. We refer by Fs to a generic selfconcordant barrier.
3.2. Hyperbolic barriers.
Definition 3. A homogenous polynomial p : Cn → C is called hyperbolic with respect to a direction d ∈ Rn if p(d) 6= 0 and there exists a constant
t0 ∈ R such that p(x + itd) 6= 0 if x ∈ Rn and t < t0 .
Associated with such a polynomial is a cone of hyperbolicity (see [9]). The
function
Fh (x) = − log p(x)
is called a hyperbolic barrier.
For the concrete applications in this paper, it suffices to note that on the
semidefinite cone S m×m , − ln det x is a hyperbolic barrier with parameter m,
and that on the intersection of ellipsoids, A1 B∩A2 B∩· · ·∩Am B where
P Ai are
non-singular affine transformations and B is the Euclidean Ball, − ln(1 −
2
kA−1
i (x)k ) is a hyperbolic barrier with self-concordance parameter m.
Lemma 1 (Theorem 4.2, Güler [9]).

If F is a hyperbolic barrier,

2
|D4 F (x)[h, h, h, h]| ≤ 6 D2 F (x)[h, h] .
3.3. Logarithmic barrier of a polytope. Given any set of linear constraints
{aTi x ≤ 1}m
i=1 , the logarithmic barrier is a real valued function defined on

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

9

the intersection of the halfspaces defined by these constraints, and is given
by
m
X

F` (x) = −
ln 1 − aTi x .
i=1

3.4. Dikin Ellipsoids. Around point x ∈ K, given a self-concordant barrier F the Dikin ellipsoid of radius r is defined to be
Dx := {y : D2 F (x)[x − y, x − y] ≤ r2 }.
Dikin ellipsoids are affine invariants in that, if the Dikin ellipsoid of radius
r around a point x ∈ K is Dxr and T is a non-singular affine transformation
of K, the Dikin ellipsoid of radius r centered at the point T x for T (K) is
T (Dxr ), as long as the new barrier that is used is H(y) := F (T −1 y).
The following fact will be used in the proof of Lemma 17 and Lemma 18.
Fact 1.

For any y such that
D2 F (x)[x − y, x − y] = r2 < 1,

for any vector h ∈ Rn ,
(1 − r)2 D2 F (x)[h, h] ≤ D2 F (y)[h, h] ≤

1
D2 F (x)[h, h].
(1 − r)2

Also, the Dikin ellipsoid centered at x, having radius 1, is contained in K.
This has been shown in Theorem 2.1.1 of Nesterov and Nemirovskii [27].
The following was proved in a more general context by Nesterov and Todd
in Theorem 4.1, [28].
Fact 2 (Nesterov-Todd). Let pq be a chord of a polytope P and x, y
be interior points on it so that p, x, y, q are in order. Let Dx be the Dikin
ellipsoid of unit radius at x with respect to a point x. Then z ∈ Dy implies
that p + |p−x|
|p−y| (z − p) ∈ Dx .
4. Oracle model. There are two standard information models for convex sets in the operations research literature, the separation model and the
(self-concordant) barrier model (see Freund [7], page 2). Existing work on
sampling convex sets, with the exception of Kannan and Narayanan [12] has
focussed on the separation model and a weaker model known as the membership oracle model. The self-concordant barrier model we will consider is
the following.
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

10

1. We are guaranteed that the origin belongs to K and that K has a
self-concordant barrier F (see Section 3).
2. We are given a real number s such that for any chord pq of K such
|p|
that |p|
|q| ≥ 1 through the origin, |q| ≤ s (see Figure 1).
n
3. On querying a point x ∈ R , we are returned a positive semidefinite
matrix corresponding to the Hessian of F at x, if x ∈ K and returned
“No” if x 6∈ K.
4.1. Presentation of the convex set K. For the definitions of logarithmic,
hyperbolic and self-concordant barriers, we refer to Section 3. We will assume
that the convex set K is specified as the set of points that satisfy a family
of constraints
m
\
K :=
{Fi (x) < ∞}
i=1

where the Fi are either logarithmic, hyperbolic or arbitrary self-concordant
functions. Without loss of generality, we may aggregate these barriers and
may assume that K := K` ∩ Kh ∩ Ks , where K` is a polytope with m faces
accompanied by the logarithmic barrier F` , Kh is a convex set accompanied by a hyperbolic barrier Fh with self-concordance parameter νh , and
Ks is a convex set accompanied by a self-concordant barrier Fs whose selfconcordance parameter is νs . Although their intersection is bounded, each
of these convex sets may be unbounded.
Definition 4.
barrier function

Given F` , Fh , Fs as above, we define the self-concordant
F := F` + nFh + n2 Fs ,

and define
(1)

ν := m + nνh + (nνs )2

to be the complexity parameter of F (which is different from its self-concordance
parameter the latter being bounded above by m + nνh + n2 νs ).
Let C be a sufficiently large universal constant. We define the radius of a
Dikin step, r to be 1/C. For a point x ∈ K and v ∈ Rn , we define
kvk2x := D2 F (x)[v, v].
The random walk we use here is a variation of the Dikin walk defined in
[12]. Instead of picking the next point from a Dikin ellipsoid, here we pick
it from a Gaussian having that covariance.
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

11

5. Main Results. In this section we present our main results. Theorem 1 shows that given a convex body accompanied with a barrier, it is
possible to use the Hessian of the barrier to define a rapidly mixing random walk. This allows us to efficiently pick a nearly random point from the
uniform measure on the convex set.
Theorem 2 shows that in a special case where the convex set is a direct
product of convex sets, the mixing time is governed by the worst factor.
While we are not aware of any algorithmic application of this result, since
it is easy to sample from a direct product, given samples from the factors,
this illustrates that one can do better than to apply the Localization Lemma
([18]) in a natural special case.
The mixing results can be adapted to give a random walk based polynomialtime Las Vegas algorithm for optimizing a linear function cT x on certain
convex sets K. The complexity of this algorithm is roughly the same as that
of the sampling algorithm. This is the content of Theorem 3.
5.1. Sampling through Dikin Walk. For x ∈ int(K), let Gx denote the
Gaussian density function given by


 n n
nkx − yk2x
2
Gx (y) :=
exp −
+ V (x) ,
πr2
r2
where

to

 
1
V (x) =
ln det D2 F (x).
2

Let r be a sufficiently small absolute constant (asymptotically less or equal
√1 ) so that the following tail estimate for the Gaussian holds.
2
Fact 3.

Suppose x → z is a transition of the Dikin walk given by


 n n
nkx − zk2x
2
Gx (z) :=
exp
−
+
V
(x)
,
πr2
r2

then,


1
P kx − zkx ≤
≥ 1 − 10−3 .
2
The Dikin Walk Algorithm is given below.
We prove the following in Subsection 7.3.
Theorem 1 (Sampling). Let K 3 0 be an n−dimensional convex set
accompanied by a barrier F as in Subsection 4.1, with complexity parameter
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

12

Q
O
P

K
Fig 1. A chord pq in a convex body K

Dikin Walk Algorithm
Let 0 = x0 ∈ int(K). For i ≥ 1, given xi−1 ,
1. Toss a fair coin. If Heads let xi := xi−1 .
2. Else
(a) Choose z from the density Gxi−1 .
(b) If z ∈ K, let
(
xi :=

z,
xi−1


with probability min 1,

Gz (xi−1 )
Gxi−1 (z)



otherwise.

(c) If z 6∈ K, let xi := xi−1 .

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

13
|p|
ν. Let s ≥ |p|
|q| for any chord pq of K containing the origin, with |q| ≥ 1. Let
e be the time of the first non-trivial move of the Markov chain. Then, the
number of steps xt after e, before both the distances – total variation distance
and the L2 distance of the density ρt
(x) of xt to the uniform density – are
1
less than  is O nν n ln(νs)
+
ln
. The number of steps needed from


1
a warm start is O nν ln  . The time of the first non-trivial move e has a
geometric distribution whose mean is bounded above by a universal constant.

In particular, suppose K is
(S) a slice of the semidefinite cone S νh ×νh of νh × νh matrices with F (x) =
− ln det x or
(Q) the intersection of ν2h ellipsoids, A1 B ∩ A2 B ∩ · · · ∩ Aνh /2 B where Ai
are non-singular affine P
transformations and B is the Euclidean Ball.
2
In this case, F (x) = − ln(1 − kA−1
i (x)k ).
In each case the complexity parameter ν is nνh and the mixing time from a 
1
fixed “s−central”
 point or a warm start, respectively, are O nν n ln(νs) + ln 
1
and O nν ln  .
The mixing bounds in this paper are obtained by relating the Markov
Chain to the metric of a Riemannian manifold studied in operations research [26] and [29], rather than the Hilbert metric [12] and [17]. The aforementioned Riemannian metric possesses several potentially useful characteristics. For example, when the convex set is a direct product of convex
sets, this metric factors in a natural way into a product of the metrics
corresponding to the individual convex sets, which is not the case for the
Hilbert metric. Using results of Barthe [2] and Bobkov and Houdré [5] on the
isoperimetry on product manifolds, this leads to an improved upper bound
on the mixing time when K is a direct product of convex sets, and opens
up the future possibility of using differential-geometric techniques for proving isoperimetric bounds, in addition to relying on the Localization Lemma,
which underlies the analysis of all Markov Chains on convex sets ever since
it was introduced in (Lovász and Simonovits [18]). Even if K is a direct
product of convex sets, the Dikin Markov Chain itself does not factor into
a product of Dikin Markov Chains and Theorem 2 does not follow from a
direct use of the Localization Lemma.
Theorem 2. If an n−dimensional convex set K := K1 × · · · × Kh is the
direct product of convex sets Ki , each of which individually has a function
Fi with a complexity parameter (defined in Equation 1) at most ν, then,
the mixing
P time of Dikin walk from a warm start on K defined using the
function hi=1 Fi is O(νn).
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

14

x4
x3
x1

x2
x0

O

K
Fig 2. Trajectory of a Dikin walk for optimizing a linear function on a convex set

When there are h = Ω(n) factors, each of which is a polytope with κ
faces, the total number of faces of K is ν` = Ω(nκ). In this case, the results
of [12] give a bound of O(nν` ) while Theorem 2 gives a bound of O(ν` ).
5.2. Convex programming. Our algorithm for convex optimization in this
paper is a Las Vegas algorithm rather than a Monte Carlo algorithm (as was
the case in [12]). It is also different from [12] in that the Markov Chain used
here does not depend on , the error tolerance.
We will consider convex programs specified as follows. Suppose we are
given a convex set K containing the origin as an interior point and a linear
objective c, such that
Q := K ∩ {y : cT y ≤ 1}
is bounded, for any chord pq of Q passing through the origin,

|p|
|q|

≤ s and

 > 0 (if B(0, r) ⊆ K ⊆ B(0, R), then s ≤ Rr ). Then, the algorithm is
required to do the following. If ∃ x ∈ K such that cT x ≥ 1, output x0 ∈ K
such that cT x0 ≥ 1 − .
Let T : Q → Rn be defined by
T (x) =

x
,
1 − cT x

and let F̂ be a barrier for K̂ := T (Q). Such a barrier can be easily constructed from F ; details appear in Section 5.2.1.
5.2.1. Constructing barriers. Let T : Q → Rn be defined by T (x) =
and K̂ be the projective image T Q of Q as defined in Section 5.2.

x
1−cT x

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

15

The construction in [25], provides us with a barrier F̂s on K̂. The barrier F̂s
is given by
  3 !2  


y
1
8
7 2
T
√ + √
Fs
F̂s (y) :=
+ 2νs ln(1 + c y) ,
1 + cT y
3 3 2 νs 3
√
whose self-concordance parameter is ≤ (3.08 ν + 3.57)2 . If Fh = − ln p(x)
where p is a hyperbolic polynomial of degree νh , F̂h is defined simply by


y
+ νh ln(1 + cT y),
F̂h (y) := Fh
1 + cT y
and has the same self-concordance parameter νh . This applies to the special
case of the logarithmic barrier as well. For any point x ∈ int(K̂), we use
the Hessian matrix D2 F̂ to define a norm
ˆ := (v T D2 F̂ v) 12 .
kvk
x


2
 n n
\
nkx − ykx
2
Ĝx (y) :=
exp −
+ V̂ (x) ,
πr2
r2
where

 
1
ln det D2 F̂ (x).
V̂ (x) =
2

For x 6∈ int(K̂), for any y 6= x, Ĝx (y) := 0. Let
|p|
,
pq3O |q|

s := sup

where the supremum is taken over all chords of K containing the origin.
Our algorithm for convex optimization consists simply of doing a modified
Dikin walk (see Figure 2) on K̂ for a sufficient number of steps that depends
on the desired accuracy  and confidence 1 − δ. Note that we define Ĝt using
F̂ in the same way that Gt was defined using F .
5.2.2. Las Vegas Algorithm. We state the Las Vegas Algorithm below.
Theorem 3. Let K, F and s be as in Theorem 1. In the cases where F
is a ν-barrier or a hyperbolic
barrier with parameter ν, let τ (, δ) be set to

T x ≥ 1} ∩ K is nonempty and x , x , . . . is
O nν ln 1δ + n ln snν
.
If
{c
0 1

the modified Dikin walk in Las Vegas Algorithm, then


P ∀i > τ (, δ), cT xi ≥ 1 −  ≥ 1 − δ.
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

16
Las Vegas Algorithm for Optimization
Let x0 = 0. While cT xi−1 < 1 − ,
1. Toss a fair coin. If Heads, set xi := xi−1 .
2. Else,
(a) Choose z from the density ĜT (xi−1 ) .
(b) If z ∈ K̂, let
xi :=




T −1 (z),



xi−1


with probability min 1,

Ĝz (T (xi−1 ))
ĜT (x
) (z)



i−1

otherwise.

(c) If z 6∈ K̂, let xi := xi−1 .

We remind the reader that for a Las Vegas algorithm, correctness is guaranteed, but there are no absolute bounds on the run time. Consider the
stopping rule under which the random walk is terminated the first time that
it reaches cT xi ≥ 1 − . The following corollary shows that the resulting
algorithm is a Las Vegas algorithm.
Corollary 4 (Las Vegas algorithm for optimization).
with probability 1,
1−κ
lim ei (1 − cT xi ) = 0.

For any κ > 0,

i→∞

6. Isoperimetry.
6.1. Metric defined by a barrier. The isoperimetric properties of a certain
metric measure space govern the mixing bounds in the present work. In this
section, we provide preliminary definitions and properties needed in our
proofs.
For any smooth strictly convex function G, the Hessian D2 G is positive
definite.
Definition 5. Given the barrier F , for every x ∈ supp(F ) and u, v ∈
√
Rn , D2 F (x)[u, v] is bilinear, and <F u, u >x is a norm. We define
√
1. <F u, v >x := D2 F (x)[u, v] and kF ukx := <F u, u >x ,
√
2. <` u, v >x := D2 F` (x)[u, v] and k` ukx := <` u, u >x ,
√
3. <h u, v >x := D2 Fh (x)[u, v] and kh ukx := <h u, u >x and
√
4. <s u, v >x := D2 Fs (x)[u, v] and ks ukx := <s u, u >x .

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

17

Definition 6.

We define
Z
kF dΓkz dz

dF (x, y) = inf
Γ

z

where the infimum is taken over all rectifiable paths Γ from x to y. d` , dh
and ds are defined analogously in terms of the respective norms k` · k, kh · k
and ks · k, which we refer to as Dikin norms.
R
1. d` (x, y) = inf Γ Rz k` dΓkz dz.
2. dh (x, y) = inf Γ R z kh dΓkz dz.
3. ds (x, y) = inf Γ z ks dΓkz dz.
Where F is clear from context, the subscript F will be skipped.
Let M be the metric space associated with F whose point set is K and
metric is dF .
The following lemma is needed to relate the Riemannian metric ds (x, y)
to the Dikin norm ks x − yk.
Lemma 2 (Nesterov-Todd (Lemma 3.1 [29])).

If ks x − ykx < 1 then,

ks x − ykx − ks x − yk2x ≤ ds (x, y) ≤ − ln(1 − ks x − ykx ).
Since any logarithmic or hyperbolic barrier is also a self-concordant barrier, this implies that if kF x − ykx < 1 then,
kF x − ykx − kF x − yk2x ≤ dF (x, y) ≤ − ln(1 − kF x − ykx ).
While some of the presented bounds can be obtained from the isoperimetric
bounds for the “Hilbert metric” (Theorem 7) proved by Lovász, we can prove
stronger results for sampling certain classes of convex sets such as the direct
product of an arbitrary number of convex sets, by using results of Barthe
[2] and Bobkov and Houdré [5] on the isoperimetry of product spaces, which
do not seem to follow directly from the Hilbert metric. In particular, for a
direct product of an arbitrary number of polytopes, each defined by O(κ)
constraints, this allows us to show an upper bound on the mixing time from
a warm start of O(κn). The bound obtained using the Hilbert metric in the
obvious way is O(κn2 ), since the Hilbert metric on a direct product does
not decompose conveniently into factors as does the Riemannian metric.
Riemannian metrics defined in this way have been studied because of their
importance in convex optimization, for example, by Nesterov and Todd in
[29] and by Nesterov and Nemirovski in [26], and Karmarkar studied the
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

18

properties of a related metric [15] that underlay his celebrated algorithm [14].
For other work on sampling Riemannian manifolds motivated by statistical
applications, see [16] and [22], and Chapter 8 of [21] and the references
therein.
6.2. Results on Isoperimetry. Let M be a metric space endowed with
distance function d and µ be a probability measure on it. We term (S1 , M \
(S1 ∪ S2 ), S2 ) a δ-partition of M, if
δ ≤ d(S1 , S2 ) :=

inf

x∈S1 ,y∈S2

d(x, y),

where S1 , S2 are measurable subsets of M. Let Pδ be the set of all δpartitions of M. The isoperimetric constant βfat (δ, M, µ) is defined as
inf
Pδ

µ(M \ (S1 ∪ S2 ))
.
µ(S1 )µ(S2 )

Given interior points x, y in int(K), suppose p, q are the ends of the chord
in K containing x, y and p, x, y, q lie in that order.
Definition 7.

Denote by dH the Hilbert (projective) metric defined by


|x − y||p − q|
.
dH (x, y) := ln 1 +
|p − x||q − y|

Definition 8.

For x ∈ K and a vector v, |v|x is defined to be
sup{x ± αv ∈ K}.
α

Let βfat := βfat (δ, M, µ), where δ =

√1 .
n

Theorem 5 (Theorem 2.3.2 (iii), [27]). Let F be a self-concordant barrier whose self-concordance parameter is νs as defined in Section 3. Then,
for all h ∈ Rn and x ∈ int(K)
|h|x ≤ ks hkx ≤ 2(1 + 3νs )|h|x .
The following result is implicit in [9].
Theorem 6 (Güler, [9]). Let − ln p(x) be a hyperbolic barrier for K,
where p has degree νh . Then, for all h ∈ Rn and x ∈ int(K),
p
√
|h|x ≤ D2 Fh (x)[h, h] ≤ νh |h|x .
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

19

Lemma 3.
1. ds (x, y) ≤ 2(1 + 3νs )dH (x, y).
√
2. dh (x, y) ≤ νh dH (x, y).
√
3. d` (x, y) ≤ mdH (x, y).
√
4. dF (x, y) ≤ O( ν)dH (x, y).
Proof. For any z on the segment xy, dH (x, z) + dH (z, y) = dH (x, y).
Therefore it suffices to prove the result infinitesimally. By Lemma 2
dF (x, y)
= 1,
y→x kF x − ykx
lim

and a direct computation shows that
lim

y→x

dH (x, y)
≥ 1.
|x − y|x

Parts 1 and 2 of Lemma 3 follow from Theorems 5 and 6. Part 3 is a special
case of part 2. Part 4 follows from adding up parts 1 to 3.
Theorem 7 (Lovász, [17]). Let S1 and S2 be measurable subsets of K.
Let µ be the uniform probability measure on K. Then,


µ(K \ (S1 ∪ S2 )) ≥ edH (S1 ,S2 ) − 1 µ(S1 )µ(S2 ).
Theorem 8. If F is a self-concordant barrier of K with complexity parameter ν, presented in the format of Section 4.1, then


1
βfat = Ω √
.
nν
Proof. Theorem 8 follows from Theorem 7 and Lemma 3.
7. Analysis of the mixing time.
7.1. Preliminaries. We denote the conditional distribution of xi+1 given
xi = x by Px . Lemma 4 is a statement about the concentration of derivatives
of odd order in high dimension. It will be used in the proof of Lemma 6,
which relates the Riemannian distance between two points x and y to the
total variation distance between Px and Py . Lemma 5 states that if the unit
Dikin ellipsoid around a point contains the unit ball, then the points at
which a random line through x chosen from the distribution induced by the
uniform measure on the unit sphere intersects the boundary are, with high
√
probability, at a distance Ω∗ ( n) from x.
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

20

Lemma 4 (Concentration bound). Let h be chosen uniformly at random
from the unit sphere S n = {v | kvk = 1}. Then, for any odd k,
"
#


−n2
k
k
P D F (x)[h, . . . , h] > k sup D F (x)[v, . . . , v] ≤ exp
.
2
kvkx ≤1
If F is a self-concordant barrier, and
∀v, kvk2 ≥ D2 F (x)[v, v]
when k = 3, this simplifies to


P D3 F (x)[h, h, h] > 3 ≤ exp



−n2
2


.

Proof. The “Bernstein inequality” of Gromov (Section 8.5, [8]) which
applies to multivariate polynomials restricted to S n , states that for any
polynomial p on S n of degree k,
sup kgrad p(h)k ≤ k sup |p(h)|.
h∈S n

h∈S n

For any fixed x, Dk F (x)[h, . . . , h] is a polynomial in h of degree k. Therefore
Dk F (x)[h, . . . , h]
k supkvkx ≤1 Dk F (x)[v, . . . , v]
is 1-Lipschitz on S n . If k is odd, Dk F (x)[h, . . . , h] = −Dk F (x)[−h, . . . , −h],
and therefore its median with respect to the uniform measure σ on the unit
sphere is 0. The first part of the lemma follows from the measure concentration properties of Lipschitz functions on the sphere (page 44 in [1]); namely,
if f is an 1-Lipschitz function on the unit sphere and M is its median, then
σ (p > M + ) ≤ e−

(2)

n2
2

.

When F is a self-concordant barrier, the second statement follows because
sup D3 F (x)[v, v, v] ≤ sup D3 F (x)[v, v, v] ≤ 1.
kvk≤1

kvkx ≤1

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

21

Lemma 5. Let P be a polytope and x a point in it. Let the Dikin ellipsoid
at x with respect to the logarithmic barrier at x contain the unit ball. Let v
be chosen uniformly at random from the unit ball centered at x and ` be the
line through x and v, and p and q be the two points of intersection of ` with
the boundary ∂P . Then, for any constant α ≥ 0,


r
n
P min(kpk, kqk) ≤
≤ 2e−α .
2(α + 2 ln n)
Proof. Without loss of generality, we may assume x to be the origin.
TheTunit ball is contained in the Dikin ellipsoid and so P can be expressed
T
as m
i=1 {ai x ≤ 1}, where
I

(3)

m
X

ai aTi .

i=1

Examining the trace and the norm on both sides of (3), we obtain
∀i, kai k ≤ 1
and

m
X

kai k2 ≤ n.

i=1

We note that

min(kpk, kqk) =

−1

min |aTi x|
i

.

Thus, it is sufficient to show that


2(α + 2 ln n)
T 2
P ∃i (ai v) ≥
≤ 2e−α ,
n
which we proceed to do. Let S be the subset of [m] := {1, . . . , m}, consisting
of those i for which kai k ≥ √1n . Clearly, if for some i, (aTi v)2 ≥ 2(α+2n ln n) ,
then i ∈ S. By (3), |S| ≤ n2 . Thus, by the union bound,




2(α + 2 ln n)
2(α + 2 ln n)
T 2
2
T 2
P ∃i∈S (ai v) ≥
≤ n sup P (ai v) ≥
.
n
n
i∈S
We note that, by (2), for any vector w with norm less or equal to 1,
"
#
r
2(α
+
2
ln
n)
e−α
P aTi w ≥
≤ 2 ,
n
n
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

22

and so


2(α + 2 ln n)
≤ 2e−α .
P ∃i (aTi v)2 ≥
n

In order to obtain mixing time bounds, we will first prove in Lemma 6
that if two points x and y are nearby in that d(x, y) ≤ O( √1n ), then the
total variation distance between the corresponding distributions Px and Py
is < 1 − Ω(1).
For x 6= y,



Gy (z) Gz (x) Gz (y)
1 − dT V (Px , Py ) = Ez min 1,
,
,
,
Gx (z) Gx (z) Gx (z)
where the expectation is taken over a random point z from the density Gx
and


Gy (z) Gz (x) Gz (y)
,
,
min 1,
Gx (z) Gx (z) Gx (z)
is defined to be 0 if z 6∈ K.
We will use the following fact (see Section 2.2, [24]) with Dk F in the place
of M .
Fact 4.

Let M [h1 , . . . , hk ] be a symmetric k-linear form on Rn . Then,
M [h1 , . . . , hk ] ≤ kh1 kkh2 k . . . khk k sup M [v, . . . , v].
kvk≤1

Fact 5. Let the eigenvalues of the covariance matrix of an n−dimensional
Gaussian g be bounded above by λ. Let < ·, · > be an inner product and
v ∈ Rn Then, E[< v, g >2 ] ≤ λ < v, v >.
7.2. Relating the Markov Chain to the manifold. In this section, we find
an upper bound on the total variation distance between the distributions of
one-step transition probabilities corresponding at two points at a Rieman√
nian distance of O(1/ n). We also describe two results used in the proof of
Theorem 1. We will frequently make statements of the form
P[g(x) > O(f (x))] ≤ c.
By this we mean, there exists a universal constant C such that
P[g(x) > Cf (x)] ≤ c.
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

23

Finally, we will frequently make use of the facts from (Theorem 2.1.1,
[27]) stated below that Dikin ellipsoids vary smoothly, and that they are
contained in the convex set.
• Given any self-concordant barrier F , for any y such that
D2 F (x)[x − y, x − y] = r2 < 1,
for any vector h ∈ Rn ,
(4)(1 − r)2 D2 F (x)[h, h] ≤ D2 F (y)[h, h] ≤

1
D2 F (x)[h, h].
(1 − r)2

• The Dikin ellipsoid centered at x, having radius 1, is contained in K.
For two probability distributions Px and Py , let dT V (Px , Py ) represent the
total variation distance between them. Without loss of generality, let x be the
origin 0 (which is achievable by translation), and for any v, let D2 F (0)[v, v] =
kvk2 (which is achievable by an affine transformation of K).
Lemma 6 (Relating d to Markov Chain).
then dT V (Px , Py ) = 1 − Ω(1).

If x, y ∈ K and d(x, y) ≤

1
√
,
C n

Proof. Without loss of generality, we may assume that Fh , F` and Fs
are strictly convex. In case any one is not, we can add the strictly convex
logarithmic barrier of a sufficiently large cube, thereby making an arbitrarily
small change to its second, third and if it is not Fs , fourth order derivatives
uniformly over K. Due to affine invariance, without loss of generality, let
< u, v >x :=< u, v >, the usual dot product. As defined in Section 5.1, for
any z ∈ K,
1
V (z) = det D2 F.
2
By Lemma 2, it suffices to prove that there is an absolute constant C such
1
that if x, y ∈ K and kx − ykx ≤ C √
, then dT V (Px , Py ) = 1 − Ω(1). Without
n
loss of generality, we assume x is the origin and we drop this subscript at
times to simplify notation.



Gy (z) Gz (x) Gz (y)
,
,
,
1 − dT V (Px , Py ) = Ez min 1,
Gx (z) Gx (z) Gx (z)
where the expectation is taken over a random point z having density Gx .
Thus, it suffices to prove the existence of some absolute constant c such that




Gy (z) Gz (x) Gz (y)
P min
,
,
> c = Ω(1).
Gx (z) Gx (z) Gx (z)
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

24

This translates to



P max nky − zk2y − r2 V (y), nkzk2z − r2 V (z), nkz − yk2z − r2 V (z) − nkzk2 < O(r2 )
= Ω(1).
Now we use the following lemmas whose proofs are in the Appendix.
Lemma 7.

−V (y) < O(1)

Lemma 8.
P [−V (z) < O(1)] >

(5)

9
.
10

Lemma 9.



199
1
2
2
2
2
.
P max ky − zky , kzkz , kz − ykz − kzk < O( ) >
n
1000
Substituting the statements of the last three lemmas into the preceding
expression of probability completes the proof.
The following two results are needed in the proof of Theorem 1. Lemma 10
is proved in the Appendix and the proof is based on that of a theorem in
[17].
Lemma 10 (Bound on Conductance). Let µ be the uniform distribution
on K. The conductance
R
S1 Px (K \ S1 )dµ(x)
Φ := inf
µ(S1 )
µ(S1 )≤ 12
of the Markov Chain in Dikin Walk Algorithm is Ω(βfat ).
Theorem 9 (Lovász-Simonovits [18]). Let µ0 be the initial distribution
for a lazy reversible ergodic Markov Chain whose conductance is Φ and
stationary measure is µ, and µk be the distribution of the k th step. Let
0 (S)
M := supS µµ(S)
where the supremum is over all measurable subsets S of
qR
2
K. For every bounded f , let kf k2,µ denote
K f (x) dµ(x). For any fixed
R
f , let Ef be the map that takes x to K f (y)dPx (y). Then,
1. for all S,
|µk (S) − µ(S)| ≤

√


M

1−

Φ2
2

k
.

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

25

2. If

R
K

f (x)dµ(x) = 0,


k

kE f k2,µ ≤

Φ2
1−
2

k
kf k2,µ .

7.3. Proof of Theorem 1.
Proof of Theorem 1. We first
 a summary of the proof. By Theo give
rem 8, βf at is bounded below by Ω √1nν . Lemma 10 states that the conductance Φ of the Markov Chain is bounded below by Ω (βf at ). We substitute
this in Theorem 9 to recover the fact that the mixing time from a warm
start is O nν ln 1 .
To recover the fact that the mixing time from an “s−central” point is
 

1
O nν n ln(νs) + ln
,

We first get a bound of exp(n ln(νs)) on the L2 norm of the starting density,
which we then use in Theorem 9. This concludes our summary – we now
proceed with the proof.
Let e be the first time the Markov Chain escapes x0 = 0. Thus e is an
integer valued random variable defined by the event that ye is the first point
in y1 , . . . that is not equal to y0 . Let the density of ye be ρe . We know that
∀t, P[e ≥ t + 1|e ≥ t] ≤ 1 − Ω(1), therefore
sup
x

ρe (x)
G0 (x)

= O(1).

Let µ(S) denote the measure assigned by the uniform probability measure
on K on a measurable set S. Therefore
Z
(vol(K)ρe (x))2 dµ(x) = exp (O(n ln(sν))) .
K

To see the last step, consider a linear transformation that maps the Dikin ellipsoid at the origin to the unit ball. Then the convex set is contained inside
 2 2 n/2
a ball of radius O(sν), making (vol(K)) bounded above by O(sn ν )
be

2 ) n/2
cause the volume of a ball in n−dimensions of radius R is O(R
. Also,
n
ρe is bounded above in sup-norm by exp((n/2) ln(O(n))), because G0 (x) is
so bounded. Therefore
Z
Z
2
ρe (x) dx < sup ρe (x)
ρe (x)dx < (O(n))n/2 .
K

K

K

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

26

This concludes our explanation.
qR
2
For every bounded f , let kf k2,µ denote
K (vol(K)f (x)) dµ(x). Let
fe (x) := ρe (x) − (vol(K))−1 . We then see from the above computation that
(6) kfe k2,µ ≤ kρe (x)k2,µ + k (vol(K))−1 1K k2,µ < exp (O(n ln(sν))) .
Theorem 9 states that
∀S, |µk (S) − µ(S)| ≤

√

M


k
Φ2
1−
.
2

Therefore, if
q
   
ln M
1
2

 = O ln
nν ,
k>
Φ2

− ln 1 − 2
then,
∀S, |µk (S) − µ(S)| ≤ .
This completes the proof of mixing from a warm start i. e. when M = O(1).
To recover the proof of mixing from a s−central point, we see by Theorem 9, Lemma 10 and (6) that
(7)
(8)

k

kE fe k2,µ


k
Φ2
≤
1−
kfe k2,µ
2

k
1
≤
1 − Ω( ) exp (O(n ln(sν))) .
nν

Therefore for k = Ω(nν(ln(1/) + n ln(sν))), we have kE k fe k2,µ ≤ . This
completes the proof of Theorem 1.
8. Mixing in a direct product of convex sets.
8.1. Preliminaries. Our analysis of mixing in a direct product of convex
sets in Theorem 2 hinges upon a lower bound on the Cheeger constant βfat ,
which is obtained by comparing the isoperimetry of the weighted manifold
M obtained by equipping K with the metric from the Hessian of F , with
the isoperimetry of the Dikin metric on the h−dimensional
cube [− π2 , π2 ]h ,
P
with respect to the barrier F (x1 , . . . , xh ) := − i ln cos(xi ) (see Section
6.2, [29]).

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

27

For a manifold N equipped with a measure µ and metric d, let the
Minkowski outer measure of a (measurable) set A be defined as
µ+ (A) := lim inf
→0+

µ(A ) − µ(A)
,


where A := {x|dM (x, A) < }.
Definition 9.
ifold (N , µ) is

The (infinitesimal) Cheeger constant of the weighted man-

βN =

inf

A⊂M,µ(A)≤ 12

µ+ (A)
,
µ(A)

where the infimum is taken over measurable subsets.
The isoperimetric function of µ is the largest function Iµ such that µ+ (A) ≥
Iµ (µ(A)) holds for all Borel sets.
h
Let the h−fold product space N × · · · × N be denoted
pPN , where the
2
distance between points (x1 , . . . , xh ) and (y1 , . . . , yh ) is
i d(xi , yi ) .
We will need the following theorem of Bobkov and Houdré (Theorem 1.1
[5]).

Theorem 10.

For any triple (N , d, µ) as above,
1
Iµ⊗h ≥ √ Iµ .
2 6

(9)

We will also need the following theorem, which is a modification of Barthe
(Theorem 10, [2]), obtained by scaling the metric on R by √1ν .
Theorem 11. Let k ≥ 2 be an integer. For i = 1, . . . , k, let (Xi , di , µi )
be a Riemannian manifold, with its geodesic distance and an absolutely continuous Borel measure of probability and let λi be a probability measure on
I
R with even log-concave density. If Iµi ≥ ηλi for i = 1, . . . , k, then
Iµ1 ⊗···⊗µk ≥

Iλ1 ⊗···⊗λk
.
η

The following lemma allows us to relate the “fat” Cheeger constant βfat
with the infinitesimal version βM .
Lemma 11.

Let A, B ⊆ M and dM (A, B) ≥ δM . Then,

µ(M \ {A ∪ B}) ≥ 2 min(µ(A), µ(B))(e

β M δM
2

− 1).

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

28

Proof. We will consider two cases.
First, suppose that max(µ(A), µ(B)) < 21 . Without loss of generality, we
assume that µ(A) ≤ µ(B). Then, let
δ1 :=

sup

δ.

µ(Aδ )< 21

We proceed by contradiction to show that
 β M δM

µ(M \ {A ∪ B}) ≥ 2µ(A) e 2 − 1 .
Suppose for some β < βM ,
(10)

∃δ ∈ [0, δ1 ), µ(Aδ ) < eβδ µ(A).

Let δ 0 be the infimum of such δ. Note that since µ(Aδ ) is a monotonically
increasing function of δ,
0

µ(Aδ0 ) ≥ eβδ µ(A).
However, we know that
µ+ (∂Aδ0 ) := lim inf
→0+

µ(A ) − µ(A)
≥ βM ,


which contradicts the fact that in any right neighborhood of δ 0 , there is a δ
for which (10) holds. This proves that for all δ ∈ [0, δ1 ), µ(Aδ ) ≥ eδβM µ(A).
We note that Aδ1 ∩ BδM −δ1 = ∅, therefore µ(BδM −δ1 ) ≤ 21 . So the same
argument tells us that
(11)

µ(BδM −δ1 \ B) ≥ (eβM (δM −δ1 ) − 1)µ(B).

Thus, µ(M \ {A ∪ B}) ≥ µ(A)(eβM (δM −δ1 ) + eβM δ1 − 2). This implies that
 β M δM

µ(M \ {A ∪ B}) ≥ 2µ(A) e 2 − 1 .
Next, consider the second case; suppose µ(B) ≥ 21 . We then set δ1 := δM ,
and see that the arguments from (10) to (11) carry through verbatim. Thus,

in this case, µ(M \ {A ∪ B}) ≥ µ(A)(eβM δM − 1) ≥ 2µ(A) e

β M δM
2

−1 .

This immediately leads to the following corollary:
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

29

Corollary 12.


βfat = Ω

βM
√
n


.

Nesterov and Todd show in (Lemma 4.1, [29]) that P
the Riemannian metric
M on the direct product of convex sets induced by hi=1 Fi is the same as
the direct product of the Riemannian metrics Mi induced by individual Fi
on the respective convex sets Ki .
Theorem 2 illustrates the utility of using the Riemannian metric in proving isoperimetric bounds in one specific case, namely when the convex set of
interest is a product of convex sets having smaller dimension. A large number of combinatorial optimization questions can be viewed as optimizing a
non-convex quadratic function over a unit cube. This is one scenario where
we hope the improved bounds on the mixing time may lead to interesting
results in the future.
8.2. Proof of Theorem 2.
Proof. In order to show that the mixing time is O(nν), by Theorem 9,
it suffices to show that the conductance Φ is bounded below by Ω( √1nν ). By
Lemma 10, it is in turn enough to bound βf at from below by
lary 12, it suffices to show that βM =

Ω( √1ν ).

√1 .
nν

By Corol-

We will show this using The-

π π h
orem 11 and Theorem 10. Consider the h−dimensional cube [−
P2 , 2 ] , and
the metric from the Hessian of the barrier F (x1 , . . . , xh ) := − i ln cos(xi )
(see Section 6.2, [29]). The map

ψ : (x1 , . . . , xh ) 7→ (ln(sec(x1 ) + tan(x1 )), . . . , ln(sec(xh ) + tan(xh ))),
maps the cube with the Hessian metric isometrically onto Euclidean space,
and the push-forward of the uniform density on the cube is a density φ ⊗
· · · ⊗ φ on Rh , where

 x 
−1
cos 2 arctan eex +1
φ(x) =
,
π
and

d2 ln φ
4e2x
=
−
< 0,
dx2
(1 + e2x )2

and the density is even (thus meeting the conditions of Theorem 11). In the
1−dimensional case, it is easy to check that the barrier is 1−self-concordant
(Section 6.2 [29]). Therefore, in the 1−dimensional case, Iφ is bounded above
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

30

and below by fixed constants. This, together with Theorem 8 implies that for
each Mi and the uniform measure µi (on Ki ), the isoperimetric profile Iµi of
(Mi , µi ) satisfies Iµi ≥ Ω( √1ν )Iφ . Now applying Theorem 11 and Theorem 10
in succession, we see that






1
1
1
Iµ1 ⊗···⊗µh ≥ Ω √
Iφ⊗···⊗φ ≥ Ω √
Iφ = Ω √
1,
ν
ν
ν
where 1 is the constant function taking the value 1. Therefore,
1
βM = Ω( √ ).
ν

9. Analysis of Las Vegas Algorithm.
Proof of Theorem 3. Note that this Markov Chain is not ergodic and
has no stationary probability distribution. We will analyze its behavior
up to time t by relating this to the limiting behavior of Dikin walks on
a family of convex sets {K̂ j }j≥1 each contained in the next, such that
K̂ j = K̂ ∩ {x|cT x ≤ j}. Note that for any fixed j, our mixing results
from Theorem 1 apply since K̂ j is bounded. Let F̂j = F̂ + ln(j − cT x).
By known properties of barriers ([27]), the self-concordance parameter of F̂j
is at most 1 more than that of F̂ . As j tends to ∞, D2 F̂j converges uniformly to D2 F̂ in the `n2 → `n2 operator norm on Hessian matrices on any
compact subset of K̂. Therefore, for any t, the distribution of the t-tuple
(T (x0 ), T (x1 ), . . . , T (xt )) is the limit in total variation distance of the distributions of t-tuples (T (xj0 ), T (xj1 ), . . . , T (xjt )), where (xj0 , . . . , xjt ) is a random
walk on K̂ j starting at 0.
We will now give an upper bound for P[cT (xi ) ≤ 1 − ]. Let yi := T (xi ).
Let e be the first time the Markov Chain y0 , y1 , . . . escapes y0 . Thus e is an
integer valued random variable defined by the event that ye is the first point
in y1 , . . . that is not equal to y0 . Let the density of ye be ρe . ∀t, we know
from Lemma 6 (applied when y → x ) that P[e ≥ t + 1|e ≥ t] ≤ 1 − Ω(1),
therefore
sup
x

ρe (x)
Ĝ0 (x)

= O(1).

Without loss of generality, in the rest of this proof, we assume that for all
v, D2 F̂ (0)[v, v] = kvk2 .

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

31

Therefore
Z
(12)

Z
ρe (x) dx = O(
2

Ĝ0 (x)2 dx)

Rn

K̂

(13)

= exp (O(n ln(n))).

Let ρt (x) be the density of xt . Then, by Theorem 1 and the fact that as far
as total variation distance is concerned, a random walk on K̂ can be viewed
as the limit of random walks on the K̂ j as j → ∞,
R
ρ (x)2 dx
Φ2 t
R K̂ t
(14)
=
O((1
−
) ).
2
2
K̂ ρe (x) dx

By Lemma 10, this is less than exp −tΩ(βfat 2 ) , using the fact that 1−x ≤
e−x .
The following lemma is proved in the Appendix.
Lemma 12. Let K̂ = T (K ∩{cT x ≤ 1−}). Let ρ be a density supported
on K̂ such that
Z
ρ(x)dx ≥ δ.
K̂

Then,


 sν 
.
ρ(x)2 dx ≥ δ 2 exp −O n ln

K̂


Using (13), (14), and Lemma 12, if P cT xt ≤ 1 −  = δ, we have that
there exists an absolute constant C > 0 such that

δ 2 exp −C n ln sν
2

< e−t(βf at ) /C .
exp(C(n ln n))
Z

Therefore,
 
 nsν 



P cT xt ≤ 1 −  ≤ exp C n ln
− (t(βfat )2 )/C .

 T

This gives the desired upper bound on P c xt ≤ 1 −  . We next proceed
to get an expression for τ (, δ). We have
 
 nsν 

X


P (∃t ≥ τ ) cT xτ ≤ 1 −  ≤
exp C n ln
− t(βfat 2 )/C

t≥τ


2
exp C n ln nsν
)/C
−
τ
(β
fat


≤
.
1 − exp − (βfat )2 /C
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

32



Therefore, for any δ, P (∃t ≥ τ ) cT xτ ≤ 1 −  < δ for



1 
1
nsν 
0
ln + n ln
,
τ >C
(βfat )2
δ

for a universal constant C 0 . Together with the fact that βf at = Ω
(from Theorem 8) this completes the proof.



√1
nν



10. Implementing the barrier oracle in the linear and semidefinite cases. The most frequently encountered barrier functions are the logarithmic barrier for polytopes and the log det barrier for convex sets defined
by semidefinite constraints (See Section 3). We discuss the implementation
of the barrier oracle for the logarithmic barrier below, in the case where x
is in the set. Let K` be the set of points satisfying the system of inequalities
Ax ≤ 1. Then, H(x) = AT D(x)2 A where D(x) is the diagonal matrix whose
ith diagonal entry dii (x) = 1−a1T x .
i

By results of Baur and Strassen [3], the complexity of solving linear equations and of computing the determinant of an n × n matrix is O(nγ ) where
γ < 2.377 is the exponent for matrix multiplication. The computation of
AT D(x)2 A can be achieved using mnγ−1 arithmetic operations, by partitioning a padded extension of AT D into ≤ m+n−1
square matrices. Thus,
n
the complexity of the barrier oracle is O(mnγ−1 ) arithmetic operations.
In case the convex set is defined by a semidefinite constraint of rank ν, the
log det barrier is a hyperbolic barrier and has a self-concordance parameter of
ν and a complexity parameter (defined in 1) of nν. the number of arithmetic
steps needed for computing the Hessian of the log det barrier is O(n2 ν 2 +
nν γ ), (see Section 11.3, [24]. We have replaced an exponent 3 in [24] with
γ). Given the Hessian, it can be inverted in (nγ ) arithmetic steps. This
is needed to implement one step of the Dikin walk. Suppose K, as above,
is a convex set that is defined by m linear constraints and additionally,
semidefinite constraints of total rank νh (which can be as low as O(1), e. g.
for the intersection of a constant number of ellipsoids). Then, the number
of arithmetic steps for implementing one Dikin step is

O mnγ−1 + n2 νh2 + nνhγ .
For Hit-and-Run, the number of arithmetic steps needed to make one move
in a naive implementation is

O∗ log(R/r)(mn + nνh2 + νhγ ) ,
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

33

(since the natural way of certifying positive semidefiniteness is to take a
Cholesky factorization, which has a complexity O(νhγ ), computing the new
semidefinite matrix after one step has a complexity n(νh2 ) (Section 11.3,
[24]) and testing containment in the region defined by linear constraints
takes O(nm) operations). We see that
1. If m < nνh2 + νhγ , then the ratio between the number of arithmetic
steps for one move of Dikin walk and one move of Hit-and-Run is not
more than O∗ (n).
2. If m ≥ nνh2 + νhγ , then the ratio between the number of arithmetic
steps for one move of Dikin walk and one move of Hit-and-Run is not
more than O∗ (nγ−2 ) < O∗ (n0.38 ).
Combining the arithmetic complexity of implementing one step of Hit-andRun with the mixing time, the ratio between the number of arithmetic steps
needed to produce one random point using Dikin walk to the number of
arithmetic
steps needed for producing one random
point


 using Hit-and-Run
(m+νh n)r2
(m+νh n)r2
γ
∗
∗
2
is O
if m < nνh + νh and O
if m ≥ nνh2 + νhγ .
R2
R2 n0.62
10.1. Implementing one Dikin step. If K is defined by semidefinite constraints, from a point x ∈ K, one step for Hit-and-Run requires Ω(log(R/d))
membership operations, each of which requires testing the semidefiniteness
of a ν ×ν matrix (which takes O(ν γ ) arithmetic steps), where R is the radius
of a circumscribing ball, and d is the distance of x to the boundary of K.
Convex sets defined by semidefinite programs can be very ill-conditioned,
and the best possible a priori upper bound on log Rd is not less than eL where
L is the total bit-length of rational data defining K and the point [30]. In the
general setting, the number of arithmetic operations needed for implementing a Dikin step would be independent of R/r, but would depend on two
affine-invariant quantities - the parameter associated with the barrier and
log s, where the starting point is s−central. In ill-conditioned semidefinite
programs, log s can be exponential in the bitlength, but for special points it
can be much smaller; for example, for the center of mass and or the analytic
center, it is O(log n) and O(log ν) respectively.
11. Concluding Remarks. We developed randomized analogues of
barrier-based interior point methods, and demonstrated their use in sampling convex sets and optimizing a linear function over a convex set. One
potential application of these methods is to integer programming as shown
by Huang and Mehrotra [10]. It remains to be seen whether a more efficient
algorithm for computing the volume of a polytope can be constructed using
Dikin walk.
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

34

12. Acknowledgements. I thank Robert Freund and Ravi Kannan for
stimulating conversations and Partha Niyogi for insights that motivated the
view of Dikin walk as a random walk on a manifold. I thank the anonymous
referee for a careful reading and many critical and insightful comments,
which I hope have led to an improvement in the readability of this paper.
APPENDIX A: PROOFS OF LEMMAS
Proof of Lemma 7. Let F̃˘ := F −F` . For w ∈ K, let X(w) := D2 F` (w)−
D2 F` (0). By Lemma 12 in [12], for any point w ∈ K, the gradient of TrX
√
at w measured using k` · kw is ≤ 2 n. Therefore, the gradient of TrX
√
at 0 measured using k` · k is ≤ O( n). X(0) = 0, therefore, |TrX(y)| ≤
√
√
O(kyk n) = O(1), since kyk = O(1/ n). For the same reason, kX(y)k =
√
O(supkwk≤kyk kD3 F` (w)[y, ·, ·]k) = O(1/ n).
For w ∈ K, let Y (w) := D2 F̃˘ (w) − D2 F̃˘ (0). Then
kY (y)k = D2 F̃˘ (y) − D2 F̃˘ (0) = O( sup kD3 F̃˘ (w)[y, ·, ·]k) = O(1/n).
kwk≤kyk

Therefore, |TrY (y)| = O(1).
−V (y) = − ln det(I + X + Y )
= −Tr(X + Y + R),
where R is a matrix whose k · k → k · k norm kRk is bounded above by
O(max(kXk2 , kY k2 )) = O(1). Thus, |V (y)| = O(1), and Lemma 7 is proved.
Proof of Lemma 8. We need to show that
P [−V (z) < O(1)] >

9
.
10

Let F̃˘ := F − F` . For w ∈ K, let W (w) := D2 F` (w), and let Z(w) :=
D2 F̃˘ (w).
−V (z) =
=
=
+

−1
ln det(W (z) + Z(z))
2
−1
(Tr ln(W (z) + Z(z))) with probability ≥ 1 − 10−3 (i. e. if kW (z) + Z(z) − Ik < 1)
2
−1
(Tr(W (z) − W (0)) + Tr(Z(z) − Z(0)))
2

1
Tr (W (z) + Z(z) − I)2
4


− O

Tr (I − (W (z) + Z(z)))3

expanding by power series.

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

35

This holds with probability ≥ 1 − 10−3 . The lemma is a consequence of
the following lemmas:
Lemma 13.
P [−(Tr(Z(z) − Z(0))) ≤ O(1)] ≥

99
.
100

Lemma 14.
P [Tr(−(W (z) − W (0))) ≤ O(1)] ≥

99
.
100

Lemma 15.

The following two probabilistic inequalities hold.
h
i
99
.
P Tr (I − (W (z) + Z(z)))3 ≤ O(1) ≥
100

h
i
99
P Tr (I − (W (z) + Z(z)))2 ≤ O(1) ≥
.
100

Proof of Lemma 9. Since kyk < O( √1n ) and kzk <
greater than

P max

1 − 10−3 ,

kzk2y

2

kyky and kykz are

− kzk , < y, z

>y , kzk2z

O( √1n ).
2

1
3

with probability

So it suffices to show that

− kzk , < y, z >z




1
< O( ) >
n

2
.
10

This fact follows from the following three lemmas and the union bound. The
4
proof of Lemma 16 would go through if 10
were replaced by 12 − Ω(1).
Lemma 16.



1
2
2
2
2
P max k` zky − k` zk , <` y, z >y , k` zkz − k` zk , <` y, z >z < O( ) >
n

4
.
10

Lemma 17.



1
2
2
2
2
P max kh zky − kh zk , <h y, z >y , kh zkz − kh zk , <h y, z >z < O( 2 ) >
n
Lemma 18.



1
P max ks zk2y − ks zk2 , <s y, z >y , ks zk2z − ks zk2 , <s y, z >z < O( 3 ) >
n
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

9
.
10

9
.
10

36

Proof of Lemma 10. Let S1 be a measurable subset of K such that
µ(S1 ) ≤ 21 and S2 := K \ S1 be its complement. For any x 6= y ∈ K,
dPy
(x) =
dµ

dPx
(y).
dµ

Let S10 = S1 ∩ {x Px (S2 ) = o(1)} and S20 = S2 ∩ {y Py (S1 ) = o(1)}. By the
reversibility of the chain, which is easily checked,
Z
Z
Px (S2 )dµ(x) =
Py (S1 )dµ(y).
S1

S2

If x ∈ S10 and y ∈ S20 then


Z
dPy
dPx
dT V (Px , Py ) := 1 −
min
(w),
(w) dµ(w) = 1 − o(1).
dµ
dµ
K
Lemma 6 states that for an absolute constant C, if d(x, y) ≤
dT V (Px , Py ) = 1 − Ω(1). Therefore Theorem 8 implies that

1
√
,
C n

then

µ((K \ S10 ) \ S20 ) ≥ Ω(βfat ) min(µ(S10 ), µ(S20 )).
First suppose µ(S10 ) ≥ (1 − Ω(1))µ(S1 ) and µ(S20 ) ≥ (1 − Ω(1))µ(S2 ). Then,
Z
Px (S2 )dµ(x) ≥ µ((K \ S10 ) \ S20 )
S1

≥ Ω(βfat )µ(S10 )
≥ Ω(βfat ) min(µ(S10 ), µ(S20 ))
and we are done. Otherwise, without loss of generality, suppose µ(S10 ) ≤
(1 − Ω(1))µ(S1 ). Then
Z
Px (S2 )dµ(x) ≥ Ω(µ(S1 ))
S1

and we are done.
Proof of Lemma 12. We remind the reader that we are given a convex
set K containing the origin as an interior point and a linear objective c, such
that
Q := K ∩ {y : cT y ≤ 1}
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

37

is bounded, for any chord pq of Q passing through the origin,
 > 0. Also, T : Q → Rn is defined by
T (x) =

|p|
|q|

≤ s and

x
.
1 − cT x

Let K be K ∩ {cT x ≤ 1 − } and K̂ := T K . Given four collinear points
0 0
a, b, c, d, (a : b : c : d) := (a−c)·(b−d)
(a−d)·(b−c) is called the the cross ratio. Let p q 3 0
be a chord of K̂ , and p = T −1 (p0 ) and q = T −1 (q 0 ). If cT p0 ≤ cT q 0 , then
|p|
|p0 |
T 0
T 0
|q 0 | ≤ |q| ≤ s. On the other hand, if c p ≥ c q , let r be the intersection of
pq with {x : cT x = 1}. By the projective invariance of the cross ratio (see
for example, Lemma 14 in [12])
(∞ : 0 : p0 : q 0 ) = (r : 0 : p : q).
Therefore
|p0 |
|q 0 |





|p|
|q − r|
=
|q|
|p − r|


s+1
≤ (s)
.


Thus
sup ln

(15)

p0 q 0 30

 s
|p0 |
,
=
O
ln
|q 0 |


where the supremum is taken over all chords of K containing the origin. By
(15) and Theorem 5 and Theorem 6, it follows that
  sν 
sup ln khk ≤ O ln
,

h∈K̂
and therefore
(16)


 sν 
.
ln volK̂ ≤ O n ln


Let ρ be a density supported on K̂ such that
Z
ρ(x)dx ≥ δ.
K̂

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

38

Then,
Z
Z
ρ(x)2 dx ≥
K̂

≥

ρ(x)2 dx

K̂
δ2

by convexity of the squared function and Jensen’s inequality


 sν 
≥ δ 2 exp −O n ln
, by (16).

volK̂

Proof of Lemma 13. Let Zh (w) := D2 Fh (w) and Zs = D2 Fs (w).
Then, Z(w) = nZh + n2 Zs . Next,
TrZh (z) − TrZh (0) = DTrZh (0)[z] +

(17)

D2 TrZh (z 0 )[z, z]
,
2

for some z 0 ∈ [0, z].
!!
|DTrZh (0)[z]| ≤ O n

with probability ≥ 1 − 10−3

sup |D3 Fh [v, v, v]|
kvk=1

!!
3

≤ O n

sup √ |D Fh [v, v, v]|

with probability ≥ 1 − 10−3

kh vk=1/ n

√
≤ O(1/ n) with probability ≥ 1 − 10−3 .
Applying Lemma 4, we see that
P[−DTrZh (0)[z] < O(1/n)] >

(18)

998
.
1000

Next,
(19)

D2 TrZ(z 0 )[z, z] = D2 TrD2 (nFh + n2 Fs )(z 0 )[z, z].

In order to bound (19), let A be an invertible matrix such that Z(z 0 ) =
√
AT Z(0)A. Such a matrix A exists for which kA − Ik = O(1/ n) with prob√
ability ≥ 1−10−3 because kh z 0 k = O(1/ n) with probability ≥ 1−10−3 . Let
DA be the differential operator whose action on a function G is determined
by the relation
∀v ∈ Rn , DA G(w)[v] := DG(w)[Av].
2 F (z 0 ) = Z (0). Now,
Thus DA
h
h

(20)

kh uk = O(1) ⇒ ∀kh vk = 1, D4 Fh (z 0 )[u, u, v, v] ≤ O(1).
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

39



2
D2 TrZh (z 0 ) [z, z] = D2 TrDA
Fh (0) [z, z]
≤ n sup O(D4 F (z 0 )[v, v, z, z]) with probability ≥ 1 − 10−3
kAvk=1

≤ n

2

sup √ D4 F (z 0 )[v, v, v, v]kh zk2

(by Fact 4)

kh vk=1/ n

(21)

= O(1/n)

with probability ≥ 1 − 10−3 .

The last line here uses Lemma 1.
Therefore, by Equations 17, 18 and 21, we have
P [− (TrZh (z) − TrZh (0)) < O(1/n)] >

997
.
1000

Also with probability ≥ 1−10−3 , ks zk = O(1/n). Therefore with probability
≥ 1 − 10−3 ,
(22)

TrZs (z) − TrZs (0) = O(TrZs (0)ks zk)
= O(1/n2 ).

(23)

The statement follows from the last two sentences, since Z = nZh + n2 Zs .

Proof of Lemma 14.


D2 TrW (z 0 )[z, z]
(24) − TrW (z) + TrW (0) = − DTrW (0)[z] +
,
2
√
for some z 0 ∈ [0, z]. Lemma 12 in [12] shows that k` ∇TrW k ≤ 2 n. Since for
√
all vectors v, kvk ≥ k` vk, this implies that k∇TrW k ≤ 2 n. By Lemma 4,
this implies that
P [|DTrW (0)[z]| < O(1)] ≥ 1 − 10−3 .
By Lemma 13 in [12],

−D2 TrW (z 0 )
2

≤ 0, thereby completing the proof.

Proof of Lemma 15. Recall that W (0) + Z(0) = I.
In order to prove that
h
i
99
P Tr (I − (W (z) + Z(z)))3 ≤ O(1) ≥
,
100
it suffices to show that
h
i
(25)
P k(W (z) − W (0))k ≤ O(n−1/3 ) ≥ 1 − 10−3
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

40

and that
h
i
P k(Z(z) − Z(0))k ≤ O(n−1/2 ) ≥ 1 − 10−3 .

(26)

From Lemma 5 and Fact 2, we obtain (25). We obtain (26) from (4).
In order to prove that
h
i
99
P Tr (I − (W (z) + Z(z)))2 ≤ O(1) ≥
,
100
it suffices to show that


(27)
P Tr(W (z) − W (0))2 k ≤ O(1) ≥ 1 − 10−3
and that

(28)



P Tr(Z(z) − Z(0))2 ≤ O(1) ≥ 1 − 10−3 ,

since by Cauchy-Schwartz,


|Tr(W (z)−W (0))(Z(z)−Z(0))|2 ≤ Tr (W (z) − W (0))2 Tr (Z(z) − Z(0))2 .
The above inequality (28) follows from (26). We will prove (27) below. We
have



 2
X

1
Tr (W (z) − W (0))2 = Tr 
ai aTi
−1 
T z)2
(1
−
a
i
i≤m

2
X
≤ Tr 
ai aTi ((2aTi z) + O(|aTi z|2 ))
i≤m






XX
5
≤ O Tr 
(ai aTi )(aj aTj )((2aTi z)(2aTj z) + O(n− 4 ))
i

≤

XX
i

j
5

(ai aTj )2 ((2aTi z)(2aTj z) + O(n− 4 )).

j

(The last three lines above are true with probability > 1−10−4 .) We proceed
to obtain a bound on
XX
5
E
(ai aTj )2 ((2aTi z)(2aTj z) + O(n− 4 ))
i

j

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

41

and then the lemma follows from Markov’s inequality.
E

XX
i

5

(ai aTj )2 ((2aTi z)(2aTj z) + O(n− 4 ))

j

is less or equal to
q
XX
XX
5
(ai aTj )2 ( E((aTi z)2 )E((aTj z)2 ) + O(n− 4 )) ≤
(ai aTj )2 (O(1/n))
i

j

i

j

= O(1/n)Tr

X

ai aTi

i

X
j

= O(1).

Proof of Lemma 16. Fixing an orthonormal basis with respect to
< ·, · >,
m
X
ai aTi  I,
i=1

where X  Y signifies that Y dominates X in the semidefinite cone.
Recall that for any v such that kvk = 1, E(< v, z >2 ) = r2 < 1/C for
some sufficiently large constant C. It suffices to prove the following two
inequalities.
Lemma 19.



1
2
2
P max k` zky − k` zk , <` y, z >y , <` y, z >z < O( ) >
n

19
.
20

Lemma 20.

P

k` zk2z

1
− k` zk < O( )
n
2


>

9
.
20

Proof of Lemma 17. We will prove upper bounds on each of (a) kh zk2y −
kh zk2 , (b) < y, z >y , (c) kh zk2z − kh zk2 and (d) <h y, z >z that hold with
constant probability, and then use the union bound. We will repeatedly use
the observation (that holds from Fact 1) that for any point w such that
kh wk = o(1),
 
1
−1/2
(29)
kh ykw ≤ O(n
kyk) ≤ O
n
imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

aj aTj

42

and with probability ≥ 1 − 10−3
√
kh zkw ≤ O(n−1/2 kzk) ≤ O(1/ n).

(30)
(a)

kh zk2y − kh zk2 = D2 Fh (y)[z, z] − D2 Fh (0)[z, z]
= D3 Fh [w][y, z, z],
for some w on the line segment [0, y].
By Fact 4,


3

P D Fh (w)[y, z, z] < O(n

−2




1
2
) ≥ P kh ykw (kh zkw ) ≤ O( 2 ) .
n

Since kzk2 = k` zk2 + nkh zk2 + n2 ks zk2 , we have
√
kh zkw = O(kzkw / n).
√
Also, kh wk = O(kyk/ n) = O(1/n), and so with probability ≥ 1 −
10−3 ,
√
√
O(kh zkw ) = O(kzk/ n) = O(1/ n).
Thus,
(31)



1
P kh ykw kh zkw ≤ O( √ ) ≥ 1 − 10−3 .
n n

and

1
P kh ykw (kh zkw ) ≤ O( 2 ) ≥ 1 − 10−3 .
n


(32)

2

(b)
<h y, z >y = <h y, z > +(<h y, z >y − <h y, z >)
= <h y, z > +D3 Fh (w)[y, y, z] (for w ∈ [0, y])
kh yk
(34)
= O(
) + O(kh yk2w kh zkw ) with probability > 99/100.
n
In going from (33) to (34), we used Fact 4 and Fact 5. In the above
calculation, to ensure that w is well-defined, we take it to be the candidate with the least norm. Thus by Equations (31), (32) and (34),



 
1
kh ykkh zk
1
2
√
P (<h y, z >y ) < O( ) ≥ P
+ kh ykw kh zkw = O
n
n
n
> 98/100.
(33)

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

43

(c) For some w ∈ [0, z],
|kh zk2z − kh zk2 − D3 Fh (0)[z, z, z]| ≤
D4 Fh (w)[z, z, z, z]
sup
2
w∈[0,y]

(35)
(36)
By Lemma 4,
"

P D3 Fh (0)[z, z, z] = O

supkh vk≤1 D3 Fh (0)[v, v, v]kh zk3
√
n

!#
> 99/100.

√
P[kh zk = O(1/ n)] > 99/100, therefore, each term in (36) is O(1/n2 )
99
with probability 100
by Lemma 1, and so


98
1
2
2
P kh zkz − kh zk < O( 2 ) >
.
n
100
(d)
<h y, z >z = <h y, z > +(<h y, z >z − <h y, z >)
≤ <h y, z > + sup

D3 Fh (w)[y, z, z]

w∈[0,z]

= O(

kh yk
) + 2kh ykw kh zk2w with probability > 99/100.
n

By Equations (29) and (30),

 
1
kh yk
2
P
+ kh ykw kh zkw = O
> 99/100.
n
n2
Therefore,


1
P (<h y, z >z ) < O( 2 ) >
n

98
.
100

Proof of Lemma 18. We trace the same steps involved in the proof
of the last lemma, the only difference being that of scale. We proceed to
prove upper bounds of O(1/n3 ) on each of the terms (a) ks zk2y − ks zk2 (b)
<s y, z >y , (c) ks zk2z − kzk2 and (d) <s y, z >z that hold with constant
probability separately, and then use the union bound. We will repeatedly

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

44

use the observation (that holds from Fact 1) that for any point w such that
ks wk = o(1),


1
−1
√
(37)
ks ykw ≤ O(n kyk) ≤ O
n n
and with probability ≥ 1 − 10−3
ks zkw ≤ O(n−1 kzk) ≤ O(1/n).

(38)
(a)

ks zk2y − ks zk2 = D2 Fs (y)[z, z] − D2 Fs (0)[z, z]
= D3 Fs (w)[y, z, z],
for some w on the line segment [0, y].
D3 Fs (w)[y, z, z] ≤ ks ykw ks zk2w
≤ (n

−3/2

)(n

by Fact 4

−1 2

)

with probability > 1 − 10−3

(b)
<s y, z >y = <s y, z > +(<s y, z >y − <s y, z >)
= <s y, z > +D3 Fs (w)[y, y, z]



ks yk
√
+ O kyk2w kzkw with probability > 99/100.
= O
n n

(39)
(40)

In going from (39) to (40), we used Fact 4 and Fact 5. We see that

 
ks yk
1
P √ + 2ks yk2w ks zkw = O
> 99/100,
n3
n n
Therefore,



1
P (<s y, z >y ) < O( 3 ) >
n

98
.
100

(c)
ks zk2z − ks zk2 = D2 Fs (z)[z, z] − D2 Fs (0)[z, z]
= D3 Fs (w)[z, z, z]
for some w on the line segment [0, z]. By Fact 4,
D3 Fs (w)[z, z, z] ≤ 2ks zkw ks zk2w
 
1
≤ O
with probability ≥ 1 − 10−3 .
n3

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

45

(d)
<s y, z >z = <s y, z > +(<s y, z >z − <s y, z >)
≤ <s y, z > + sup D3 Fs (w)[y, z, z]
w∈[0,z]

ks yk
= O( √ ) + 2ks ykw ks zk2w with probability > 99/100.
n n
By Equations (37) and (38),

 
ks ykks zk
1
2
√
P
+ 2ks ykw ks zkw = O
> 99/100.
n3
n
Therefore,



1
P (<s y, z >z ) < O( 3 ) >
n

Proof of Lemma 19.

98
.
100

(a)

k` zk2y − k` zk2 = D2 F` (y)[z, z] − D2 F` (0)[z, z]
= D3 F` (w)[y, z, z],
√
for some w ∈ [0, y] and consequently k` wk = O(1/ n) and hence
D3 F` (w)[y, z, z] = D3 F` (0)[y, z, z] + D4 F` (w1 )[y, y, z, z].
The term D4 F` (w1 )[y, y, z, z] is bounded above O(1/n) with probability 1 − 10−3 . We apply Cauchy-Schwartz below.

!2 
!
m
m
X
X
X
T
T
T
T
T
2
T
2
E
(y ai ai z)(ai z)  ≤ E
(y ai ai z)
(ai z)
i=1

i=1

i

!
≤ E

X

k(ai aTi )yk2 kzk4 /n

i

(41)

= O(1/n2 ), since k

X

(ai aTi )2 k ≤ 1.

i

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

46

Therefore,
" m
#
X
 3

P D F` (0)[y, z, z] < O(1/n) = P 2
(aTi y)(aTi z)2 < O(1/n)
i=1





≥ 1 − O  n2 E 

(42)

m
X

!2 
(y T ai aTi z)(aTi z)



i=1
−3

≥ 1 − 10

(43)

rescaling y by a universal constant.

(b) Proceeding to the next term,
P [<` y, z >y = O(1/n)] = P [<` y, z > +(<` y, z >y − <` y, z >) = O(1/n)] .
Also,
<` y, z >y − <` y, z >= O(kzk/n)
by (4), and
E[<` y, z >2 ] ≤ O(1/n2 ),

(44)

so by Markov’s inequality we obtain
P [<` y, z >y = O(1/n)] > 1 − 10−3 .

(45)

(c) Finally, we obtain a probabilistic upper bound
(46)

P[<` y, z >z − <` y, z >< O(1/n)] > 1 − 10−3 ,

as follows. Note that
(47)

<` y, z >z − <` y, z >= y T

X
i


ai aTi z
T
−
a
z
.
i
(1 − aTi z)2

This is equal to
X
i

yaTi



2(aTi z)2 − (aTi z)3
(1 − aTi z)2


.

Let the ai be listed in order of non-increasing
length. For i = 1 to n, the
√
1
− 14
T
−
n/2
probability
that |ai z| ≥ n
is O(e
). For i > n, |aTi z| ≥ n− 4 is
√
O(e− i/2 ). It is true with probability 1 − 10−3 that ∀i |aTi z| is ≤ kaTi kr,
which is less than 21 . Therefore with probability > 1 − 10−3 every term
2
T
3
2(aT
i z) −(ai z)
T
2
(1−ai z)

is bounded above by 3(aTi z)2 .

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

47

X

yaTi

i



2(aTi z)2 − (aTi z)3
(1 − aTi z)2


< kyk

X


ai

i

2(aTi z)2 − (aTi z)3
(1 − aTi z)2



Next, we apply the Semidefinite Cauchy-Schwartz inequality from [12]
and take operator norms on both sides. With probability > 1 − 10−3 ,

X
i


ai

2(aTi z)2 − (aTi z)3
(1 − aTi z)2



2

!
≤k

X

ai aTi k

X

i

9(aTi z)4

X
≤O
(aTi z)4

i

i

Next

 
P
4
X
1
T 4
i kai k
=O
.
E[ (ai z) ] = O
n2
n
i
P
The last step uses the fact that each kai k ≤ 1 and i kai k2 ≤ n. Thus
"
#


X
2(aTi z)2 − (aTi z)3
T
P
yai
< O(1/n) > 1 − 10−3 .
T
2
(1 − ai z)
i
It follows that
(48)

P [<` y, z >z − <` y, z >= O(1/n)] > 1 − 10−3 .

Lemma 19 follows.
Proof of Lemma 20. In order to prove that


1
2
2
P k` zkz − k` zk < O( ) >
n

9
,
20

it suffices to show that



1
2
2
2
P k` zkz + k` zk−z /2 < k` zk + O( ) >
n

9
,
10

because the distribution of z is symmetric about the origin.



X  (aT z)2
X
(aTi z)2
1 + (aTi z)2
T 2
i
+
=
(ai z)
T z)2
T z)2
2(1
−
a
2(1
+
a
(1 − (aTi z)2 )2
i
i
i
i

X
3(aTi z)4 − (aTi z)6
T 2
=
(ai z) +
(1 − (aTi z)2 )2
i
(49)

= k` zk2 +

X 3(aT z)4 − (aT z)6
i

i

i

(1 − (aTi z)2 )2

.

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

.

48

Let the ai be listed in order of non-increasing
length. For i = 1 to n,
√
T z| ≥ n− 14 is O(e− n/2 ). For i > n, |aT z| ≥ n− 14
the probability
that
|a
i
i
√
is O(e− i/2 ). It is true with probability 1 − 10−3 that ∀i |aTi z| is ≤ kaTi kr,
which is less than 21 . This allows us to write with probability ≥ 1 − 10−3

E

3(aTi z)4 − (aTi z)6
(1 − (aTi z)2 )2

which is O(k` ai k4 /n2 ). Since
P
2
i k` ai k ≤ n.
Therefore,

P



T
i ai ai

P

k` zk2z + k` zk2−z /2 > k` zk2 + O


= 3E[(aTi z)4 ](1 + o(1)),



 I, therefore, ∀i, k` ai k ≤ 1 and

100
n

"



X 3(aT z)4 − (aT z)6
i

= P

i

≤ n

X

i

(1 − (aTi z)2 )2

#
> O 102 /n

k` ai k4 /(100n2 )

i

≤

X

k` ai k2 /(100n)

i

≤ 1/100.

REFERENCES
[1] K. M. Ball, “An elementary introduction to modern convex geometry. In S. Levy
(Ed.),” Flavors of Geometry, Number 31 in MSRI Publications, pp. 158, New York:
Cambridge U. Press, 1997.
[2] F. Barthe, “Log-concave and spherical models in isoperimetry,” GAFA, Vol. 12
(2002), 32–55.
[3] W. Baur and V. Strassen, “The Complexity of Partial Derivatives,” Theoretical Computer Science, 22 (1983) 317-330.
[4] D. Bertsimas and S. Vempala, “Solving convex programs by random walks,” Journal
of the ACM (JACM), 2004, 51(4), 540–556.
[5] S. G. Bobkov and C. Houdré, “Isoperimetric constants for product probability measures,” The Annals of Probability, (1997), Vol. 25, No. 1, 184–205.
[6] M. Dyer, A. Frieze and R. Kannan, “A random polynomial time algorithm for approximating the volume of convex sets,” 1991, Journal of the Association for Computing
Machinary, 38, pp. 1-17.
[7] R. Freund and J. Vera, “Equivalence of convex problem geometry and computational
complexity in the separation oracle model,” Mathematics of Operations Research,
Vol. 34, No. 4, November 2009, pp. 869–879.
[8] M. Gromov, “Isoperimetry of waists and concentration of maps,” Geom. Funct. Anal.
13, 2003, No. 1, pp. 178-215.

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015



49
[9] O. Güler, “Hyperbolic polynomials and interior point methods for convex programming,” Mathematics of Operations Research, May 1997, v.22 n.2, pp. 350-377.
[10] K. Huang and S. Mehrotra, “An Empirical Evaluation of Walk-and-Round Heuristics
for Mixed-Integer Linear Programs,”Computational Optimization and Applications
July 2013, Volume 55, Issue 3, pp 545-570.
[11] R. Kannan, L. Lovász and M. Simonovits, “Random walks and an O∗ (n5 ) volume algorithm for convex bodies,” Random Structures and Algorithms, August 1997, 11(1),
pp. 1-50.
[12] R. Kannan and H. Narayanan, “Random walks on polytopes and an affine interior
point algorithm for linear programming,” Proceedings of the ACM Symposium on
Theory of Computing, 2009, pp. 561-570.
[13] R. Kannan, S. Vempala, “Sampling Lattice points,” Proceedings of the ACM Symposium on Theory of Computing, (1997), 696–700.
[14] N. K. Karmarkar, “A new polynomial-time algorithm for linear programming,” Combinatorica, 1984, 4, 373–395.
[15] N. K. Karmarkar, “On the Riemannian Geometry underlying interior point methods,” Mathematical Developments Arising from linear programming. Contemporary
Mathematics, Amer. Math. Soc., 1990, 144, 51–75.
[16] G. Lebeau, L. Michel, “Semiclassical analysis of a random walk on a manifold,” Ann.
Probab. Volume 38, Number 1 (2010), 277-315.
[17] L. Lovász, “Hit-and-run mixes fast,” Math. Programming, series A, 1999, 86, pp.
443-461.
[18] L. Lovász and M. Simonovits, “Random walks in a convex body and an improved
volume algorithm,” Random structures and algorithms, 4 (1993), 359–412.
[19] L. Lovász and Vempala, “Simulated annealing in convex bodies and an O ∗ (n4 )
volume algorithm.” J. Comput. Syst. Sci. 72(2), (2006) 392–417
[20] L. Lovász and S. Vempala, “Hit-and-run from a corner,” SIAM J. Comput., 2006, 4,
pp. 985-1005.
[21] H. Narayanan, “Diffusion in Computer Science and Statistics,” Ph.D thesis, University of Chicago, August 2009
[22] H. Narayanan and P. Niyogi, “Sampling Hypersurfaces through Diffusion,” 12th Intl.
Workshop on Randomization and Computation (RANDOM), August 2008, 535–548.
[23] H. Narayanan and A. Rakhlin, “Random Walk Approach to Regret Minimization,”
Advances in Neural Information processing Systems, 2010, 1777–1785.
[24] A. Nemirovski, “Interior Point Polynomial Time Methods in Convex Programming
(Lecture notes),” http://www2.isye.gatech.edu/~nemirovs/Lect_IPM.pdf (1994).
[25] Y. Nesterov, “Constructing Self-concordant Barriers for Convex Cones,” CORE Discussion Paper No. 2006/30, March 2006.
[26] Y. Nesterov and A Nemirovski, “Primal Central Paths and Riemannian Distances
for Convex Sets,” Foundations of Computational Mathematics 8(5), 533-560 (2008).
[27] Y. E. Nesterov and A. S. Nemirovski, “Interior point polynomial algorithms in convex
programming,” SIAM Publications. SIAM, Philadelphia, USA, 1994.
[28] Y. E. Nesterov and M. J. Todd, “Self-Scaled Barriers and Interior-Point Methods for
Convex Programming,” Mathematics of Operations Research, Vol. 22, No. 1, (Feb
1997), pp. 1-42.

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

50
[29] Y. E. Nesterov and M.J. Todd, “On the Riemannian geometry defined by selfconcordant barriers and interior-point methods,” Foundations of Computational
Mathematics, 2 (2002), 333–361.
[30] M. V. Ramana, An exact duality theory for semidefinite programming and its complexity implications. Mathematical Programming, 1997, 77, 129-162.
[31] J. Renegar, “A polynomial-time algorithm, based on Newton’s method, for linear
programming,” Mathematical Programming, 1988, 40, pp. 59-93.
[32] P. M. Vaidya, “A new algorithm for minimizing convex functions over convex sets,”
Mathematical Programming, 1996, 73, 291-341.
[33] S. Vempala, “Geometric Random Walks: A Survey,”, Combinatorial and Computational Geometry, MSRI Publications Volume 52, 2005, 573–612.

imsart-aap ver. 2012/08/31 file: dikin_nov14.tex date: November 17, 2015

