Solving convex programs by random walks

By Dimitris J. Bertsimas, Santosh Srinivas Vempala. 2004

275 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computer Graphics and Computer-Aided Design, Numerical Analysis

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 Numerical Analysis

Citations in the corpus

Near-Optimal Evasion of Convex-Inducing Classifiers (2010, methodology): “We use a randomized polynomial algorithm of Bertsimas and Vempala (2004) to minimize the cost given an initial x− ∈ X− f .”
The Geometry of Logconcave Functions and Sampling Algorithms ∗ (2003, background): “A different proof for the special case when f is uniform over a convex body is given in [2].”
Random Gradient-Free Minimization of Convex Functions (2015, unknown): “, [3]).”
Classifier Evasion: Models and Open Problems (2010, background): “In the case of convex X − f , the best known algorithm is a randomized ellipsoid approach ( cf. (cid:6) (cid:7) [2]) that ﬁnds a near-optimal instance with high probability using O ∗ D 5 queries (ignoring logarithmic terms).”
Behavior of Machine Learning Algorithms in Adversarial Environments (2010, methodology): “Instead, we rescale X implicitly using a technique described by Bertsimas and Vempala [2004]. We maintain a set Q of sufficiently many uniform samples from the body P(s) and in the hit-and-run algorithm (Algorithm 6.”
Stochastic Convex Optimization with Bandit Feedback (2011, background): “Using random walk ideas [6] to improve the dependence on d is an interesting question for future research.”
Lower Bounds for Higher-Order Convex Optimization (2017, unknown): “, 2015) and random-walk (Bertsimas and Vempala, 2004; Kalai and Vempala, 2006; Lovász and Vempala, 2006) based methods.”
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, unknown): “9”
Online convex optimization in the bandit setting: gradient descent without a gradient (2004, methodology): “from an oracle that evaluates the function, in theory one can use the ellipsoid [11] or more recent randomwalk based approaches [4].”
Convex Optimization: Algorithms and Complexity (2014, background): “This idea was proposed and developed in Bertsimas and Vempala [2004]. We give below a condensed version of the main ideas of this paper. Assuming that one can draw independent points X1, . . . , XN uniformly at random from the current set St, one could replace ct by ĉt = 1 N ∑N i=1Xi. Bertsimas and ”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “However, we show that the approximate center-of-gravity method introduced by Bertsimas and Vempala [11] and approximate computation of the inertial ellipsoid (Lov´asz and Vempala [65]) suf ﬁ ce for our purposes.”
Geometric Random Walks: a Survey (2007, methodology): “The next lemma (from [35]; see [6] for the case of f arising from convex bodies) states that its maximum must be bounded.”
Simulated annealing in convex bodies and an O*(n4) volume algorithm (2006, unknown): “A convenient way to use this is the following corollary (formulated in [3]).”