The Geometry of Logconcave Functions and Sampling Algorithms ∗

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

How researchers see this paper

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

Citations in the corpus

Efficient Representations for Lifelong Learning and Autoencoding (2014, background): “, [18]), the above procedure will be successful and learn the target functions with much fewer labeled examples in total than by learning each function separately.”
Efficient Robust Proper Learning of Log-concave Distributions (2016, background): “5 in [LV07], and the discrete case follows similarly.”
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm (2014, unknown): “The following lemma, based on results in [22], is useful.”
Hit-and-run from a corner (2004, methodology): “Third, we define α(x) (as in [12]) as the smallest s ≥ 3 for which a hit-and-run step y from x satisfies P(f(y) ≥ sf(x)) ≤ 1 16 .”
Bandit Algorithms (2020, background): “Mirror descent was first developed by Nemirovski [1979] and Nemirovski and Yudin [1983] for classical optimization while ‘follow the regularized leader’ appears first in the work by Shalev-Shwartz [2007], ShalevShwartz and Singer [2007]. An implicit form of regularization is to add a perturbation of”
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].”
Active and passive learning of linear separators under log-concave distributions (2012, background): “t includes the gaussian distribution and uniform distribution over any convex set, and which has played an important role in several areas including sampling, optimization, integration, and learning (Lovasz and Vempala, 2007). We also consider active learning, a major area of research of modern mach”
Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices (2019, background): “logconcave, there are many sampling algorithms with provable rapid convergence; these include the ball walk and hit-and-run [37, 43, 44, 42] (which give truly polynomial algorithms), various discretizations of the overdamped or underdamped Langevin dynamics [21, 22, 24, 8, 26] (which have polynomial”
Log-Concavity and Strong Log-Concavity: a review (2014, methodology): “For other pointwise bounds on log-concave densities themselves, see Devroye (1984), Dümbgen and Rufibach (2009) and Lovász and Vempala (2007).”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “, as in [LV07]) can be adapted to nearlogconcave functions with an additional factor of O(1) in the mixing time.”