Hit-and-run from a corner

By L. Lov'asz, Santosh Srinivas Vempala. 2004

305 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Mathematical Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Fair Algorithms for Infinite and Contextual Bandits (2016, methodology): “We use the following lemma from Lovász and Vempala [2006] to upper-bound the mixing time hit-and-run requires to approach a near-uniform distribution in its walk over C t .”
Near-Optimal Evasion of Convex-Inducing Classifiers (2010, background): “Under the appropriate conditions (see Section 3.2.2), hit-and-run generates a sample uniformly from the convex body after O∗ ( D3 ) steps2 (Lovász and Vempala, 2004).”
Mathematical Aspects of Mixing Times in Markov Chains (2006, background): “Albeit combinatorial, a non-discrete estimation problem which received significant devotion, both by way of algorithms and analytical techniques, is that of (approximately) computing the volume of a high-dimensional convex body (see [52, 53] and references therein).”
Geometric Random Walks: a Survey (2007, background): “This phenomenon is in fact general as shown by the following theorem, proved recently in [38].”
Protecting Locations with Differential Privacy under Temporal Correlations (2014, background): “For instance, a hit-and-run algo-rithm [37] only takes O ( log 3 (1 /δ )) time where δ is an error parameter.”
Log-concave sampling: Metropolis-Hastings algorithms are fast! (2018, methodology): “A few popular examples of zeroth order algorithms include Metropolized random walk (MRW) [28, 42], Ball Walk [24, 14, 25] and the Hit-and-run algorithm [1, 22, 23, 26, 27].”
Multiple Imputation of Missing or Faulty Values Under Linear Constraints (2014, background): “Lovász and Vempala (2006) proved that the H&R sampler mixes fast, and that mixing time does not depend on the choice of starting points.”
The Markov chain Monte Carlo revolution (2008, background): “Three of my favorite papers (which will lead the reader into the heart of this rich literature) are the [63] analysis of the hit-and-run algorithm, the [52] analysis of the problem of approximating permanents and the [70] analysis of knapsack problems.”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “The current best dependence on d is d4 for the first random point and d3 for all subsequent points [LV06b].”
Behavior of Machine Learning Algorithms in Adversarial Environments (2010, methodology): “2), the hit-and-run random walk generates a sample uniformly from the convex body after O∗ ( D3 ) steps9 [Lovász and Vempala, 2004].”
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm (2014, background): “Since then researchers have improved the complexity of volume computation and sampling for convex bodies considerably, to O∗(n4) for volume estimation and for obtaining the first random sample [21, 19] and to O∗(n3) per sample for subsequent samples [19, 20].”
Theoretical guarantees for approximate sampling from smooth and log‐concave densities (2014, background): “To the best of our knowledge, first computable bounds on the constants that are involved in the geometric convergence of Markov chains were derived in Meyn and Tweedie (1994); see also the subsequent work Rosenthal (2002), Douc et al. (2004) and Roberts and Rosenthal (2004).”
Simulated annealing in convex bodies and an O*(n4) volume algorithm (2006, methodology): “Under these assumptions, the main result of [19] says that the total variation distance of the output distribution from f is less than .”
Query by Committee Made Real (2005, background): “Current proofs [9, 14] show that (cid:6)(cid:7) (cid:8)(cid:6)(cid:9)(cid:10) steps are needed for the random walk to mix.”