Simulated annealing in convex bodies and an O*(n/sup 4/) volume algorithm

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

76 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

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.”
A Polynomial Number of Random Points Does Not Determine the Volume of a Convex Body (2009, background): “Starting from the 1980s, several works have been made in the area of finding a fast algorithm for computing the volume of a convex body (see, for example, [1–3, 8, 9], and references therein).”
Behavior of Machine Learning Algorithms in Adversarial Environments (2010, background): “Analysis of reverse engineering: Lowd and Meek [2005b] observe that the attacker need not model the classifier explicitly, but only find lowest-attacker-cost instances as in the setting of Dalvi et al.”
Submodular maximization by simulated annealing (2010, background): “[2] for general convergence results, [26, 19] for applications to volumes estimation and optimization over convex bodies, and [31, 3] for applications to counting problems).”
Logarithmic regret algorithms for online convex optimization (2006, methodology): “Using recent random walk analyses of Lov¶asz and Vempala [LV03a, LV03b ], m samples from such a distribution can be computed in time ~ O(n4 + mn3).”
Online convex optimization in the bandit setting: gradient descent without a gradient (2004, methodology): “Finally, we can use existing algorithms [18] to reshape the body so R/r ≤ d to get the final results.”