Running a random walk in a convex body K⊆ℝn is a standard approach to sample approximately uniformly from the body. The requirement is that from a suitable initial distribution, the distribution of the walk comes close to the uniform distribution πK on K after a number of steps polynomial in n and the aspect ratio R/r (i.e., when rB2 ⊆ K ⊆ RB2). Proofs of rapid mixing of such walks often require the probability density η0 of the initial distribution with respect to πK to be at most poly(n): this is called a “warm start”. Achieving a warm start often requires non-trivial pre-processing before starting the random walk. This motivates proving rapid mixing from a “cold start”, wherein η0 can be as high as exp(poly(n)). Unlike warm starts, a cold start is usually trivial to achieve. However, a random walk need not mix rapidly from a cold start: an example being the well-known “ball walk”. On the other hand, Lovász and Vempala proved that the “hit-and-run” random walk mixes rapidly from a cold start. For the related coordinate hit-and-run (CHR) walk, which has been found to be promising in computational experiments, rapid mixing from a warm start was proved only recently but the question of rapid mixing from a cold start remained open.

We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for integer polytopes in terms of the length of the description of the polytope (in bits) and the minimum angle between facets of its polar. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure 1-o(1) and polynomial diameter. Both bounds rely on spectral gaps - of a certain Schrödinger operator in the first case, and a certain continuous time Markov chain in the second - which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.

In the present work, we give a solution to the following question from manifold learning. Suppose data belonging to a high dimensional Euclidean space is drawn independently, identically distributed from a measure supported on a low dimensional twice differentiable embedded manifold $M$, and corrupted by a small amount of gaussian noise. How can we produce a manifold $M’$ whose Hausdorff distance to $M$ is small and whose reach is not much smaller than the reach of $M$?

We propose a computationally efficient random walk on a convex body which rapidly mixes with respect to a fixed log-concave distribution and closely tracks a time-varying log-concave distribution. We develop general theoretical guarantees on the required number of steps; this number can be calculated on the fly according to the distance from and the shape of the next distribution. We then illustrate the technique on several examples. Within the context of exponential families, the proposed method produces samples from a posterior distribution which is updated as data arrive in a streaming fashion. The sampling technique can be used to track time-varying truncated distributions, as well as to obtain samples from a changing mixture model, fitted in a streaming fashion to data. In the setting of linear optimization, the proposed method has oracle complexity with best known dependence on the dimension for certain geometries. In the context of online learning and repeated games, the algorithm is an efficient method for implementing no-regret mixture forecasting strategies. Remarkably, in some of these examples, only one step of the random walk is needed to track the next distribution.

We consider the problem of optimizing an approximately convex function over a bounded convex set in \mathbbR^n using only function evaluations. The problem is reduced to sampling from an \emphapproximately log-concave distribution using the Hit-and-Run method, which is shown to have the same \mathcalO^* complexity as sampling from log-concave distributions. In addition to extend the analysis for log-concave distributions to approximate log-concave distributions, the implementation of the 1-dimensional sampler of the Hit-and-Run walk requires new methods and analysis. The algorithm then is based on simulated annealing which does not relies on first order conditions which makes it essentially immune to local minima. We then apply the method to different motivating problems. In the context of zeroth order stochastic convex optimization, the proposed method produces an ε-minimizer after \mathcalO^*(n^7.5ε^-2) noisy function evaluations by inducing a \mathcalO(ε/n)-approximately log concave distribution. We also consider in detail the case when the “amount of non-convexity” decays towards the optimum of the function. Other applications of the method discussed in this work include private computation of empirical risk minimizers, two-stage stochastic programming, and approximate dynamic programming for online learning.

The hypothesis that high dimensional data tends to lie in the vicinity of a low dimensional manifold is the basis of a collection of methodologies termed Manifold Learning. In this paper, we study statistical aspects of the question of fitting a manifold with a nearly optimal least squared error. Given upper bounds on the dimension, volume, and curvature, we show that Empirical Risk Minimization can produce a nearly optimal manifold using a number of random samples that is {\it independent} of the ambient dimension of the space in which data lie. We obtain an upper bound on the required number of samples that depends polynomially on the curvature, exponentially on the intrinsic dimension, and linearly on the intrinsic volume. For constant error, we prove a matching minimax lower bound on the sample complexity that shows that this dependence on intrinsic dimension, volume and curvature is unavoidable. Whether the known lower bound of $O(\frac{k}{\eps^2} + \frac{\log \frac{1}{\de}}{\eps^2})$ for the sample complexity of Empirical Risk minimization on $k-$means applied to data in a unit ball of arbitrary dimension is tight, has been an open question since 1997 \cite{bart2}. Here $\eps$ is the desired bound on the error and $\de$ is a bound on the probability of failure. We improve the best currently known upper bound \cite{pontil} of $O(\frac{k^2}{\eps^2} + \frac{\log \frac{1}{\de}}{\eps^2})$ to $O\left(\frac{k}{\eps^2}\left(\min\left(k, \frac{\log^4 \frac{k}{\eps}}{\eps^2}\right)\right) + \frac{\log \frac{1}{\de}}{\eps^2}\right)$. Based on these results, we devise a simple algorithm for $k-$means and another that uses a family of convex programs to fit a piecewise linear curve of a specified length to high dimensional data, where the sample complexity is independent of the ambient dimension.

We propose a computationally efficient random walk on a convex body which rapidly mixes to a time-varying Gibbs distribution. In the setting of online convex optimization and repeated games, the algorithm yields low regret and presents a novel efficient method for implementing mixture forecasting strategies.

Let K be a polytope in Rn defined by m linear inequalities. We give a new Markov Chain algorithm to draw a nearly uniform sample from K. The underlying Markov Chain is the first to have a mixing time that is strongly polynomial when started from a "central" point x0. If s is the supremum over all chords pq passing through x0 of (|p-x0|)/(|q-x0|) and ε is an upper bound on the desired total variation distance from the uniform, it is sufficient to take O(m n( n log (s m) + log 1/ε)) steps of the random walk. We use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately. More precisely, suppose Q = {z | Bz ≤ 1} contains a point z such that cT z ≥ d and r := supz ∈ Q |Bz| + 1, where B is an m x n matrix. Then, after τ = O(mn (n ln(mr/ε) + ln 1/δ)) steps, the random walk is at a point xτ for which cT xτ ≥ d(1-ε) with probability greater than 1-δ. The fact that this algorithm has a run-time that is provably polynomial is notable since the analogous deterministic affine algorithm analyzed by Dikin has no known polynomial guarantees.

We consider the question of averaging on a graph that has one sparse cut separating two subgraphs that are internally well connected. We exhibit a decentralized algorithm for such graphs that uses updates involving negative weights and has an averaging time that can be significantly shorter than the averaging time of known distributed averaging algorithms.

In recent times, a considerable amount of work has been devoted to the development and analysis of gossip algorithms in Geometric Random Graphs. In a recently introduced model termed "Geographic Gossip," each node is aware of its position but possesses no further information. We develop a new protocol for Geographic Gossip, in which counter-intuitively, we use "non-convex affinecombinations" as updates in addition to convex combinations to accelerate the averaging process.

We draw on the observation that the amount of heat diffusing outside of a heated body in a short period of time is proportional to its surface area, to design a simple algorithm for approximating the surface area of a convex body given by a membership oracle. Our method has a complexity of O*(n4), where n is the dimension, compared to O*( n8.5) for the previous best algorithm. We show that our complexity cannot be improved given the current state-of-the-art in volume estimation

One of the intuitions underlying many graph-based methods for clustering and semi-supervised learning, is that class or cluster boundaries pass through areas of low probability density. In this paper we provide some formal analysis of that notion for a probability distribution. We introduce a notion of weighted boundary volume, which measures the length of the class/cluster boundary weighted by the density of the underlying probability distribution. We show that sizes of the cuts of certain commonly used data adjacency graphs converge to this continuous weighted volume of the boundary. keywords: Clustering, Semi-Supervised Learning