Simulated annealing in convex bodies and an O*(n4) volume algorithm

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

295 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computer Graphics and Computer-Aided Design, 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 Applied Mathematics

In Computer Graphics and Computer-Aided Design

In Statistics and Probability

Citations in the corpus

Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “This step takes time polynomial in p with additional polylog factor in 1r where r > 0 is the diameter of the largest ball we can fit inside C (See [35] and [23]).”
Query Strategies for Evading Convex-Inducing Classifiers (2010, methodology): “4 The RoundingBody algorithm described by Lov´asz and Vempala (2003) uses O ∗ D membership queries to transforms the convex body into a near-isotropic position.”
Near-Optimal Evasion of Convex-Inducing Classifiers (2010, methodology): “The RoundingBody algorithm described by Lovász and Vempala (2003) uses O∗ ( D4 ) membership queries to make the convex body near-isotropic.”
Geometric Random Walks: a Survey (2007, background): “3 are both based on the following property of logconcave functions proved in [37].”
Hit-and-run from a corner (2004, methodology): “This class of density functions is interesting for other reasons as well—these are the functions used in “simulated annealing” and in the fastest volume algorithm [13].”
Protecting Locations with Differential Privacy under Temporal Correlations (2014, unknown): “Theorem 5.2 ([38, 50]).”
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, unknown): “9”
Private Empirical Risk Minimization, Revisited (2014, background): “This step takes time polynomial in p with additional polylog factor in 1r where r > 0 is the diameter of a p-dimensional ball contained in C (See [32] and [20]).”
Tractability of Multivariate Problems (2008, result): “This result was improved several times and the main result of the paper by Lovász and Vempala [180] is the following.”
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm (2014, background): “…and Subject Descriptors F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms; G.3 [Probability and Statistics]: Probabilistic Algorithms General Terms Algorithms, Theory Keywords Volume Computation; Sampling; Geometric random walks; Functional Analysis; Simulated Annealing”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “It is based on the random walk techniques of Kalai and Vempala [54] and Lov´asz and Vempala [64].”
Online convex optimization in the bandit setting: gradient descent without a gradient (2004, methodology): “[18] L. Lovasz and S. Vempala.”
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow (2014, background): “However, this result is generally considered to be only of theoretical interest as the universal barrier function is defined as the volume of certain polytopes, a problem which in full-genearality is NPhard and can only be computed approximately in O(n) for some large constant c [23].”