Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry
verfasst von : Karthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Efficient sampling, integration and optimization algorithms for logconcave functions [BV04, KV06, LV06a] rely on the good isoperimetry of these functions. We extend this to show that − 1/(
n
− 1)-concave functions have good isoperimetry, and moreover, using a characterization of functions based on their values along every line, we prove that this is
the largest class
of functions with good isoperimetry in the spectrum from concave to quasi-concave. We give an efficient sampling algorithm based on a random walk for − 1/(
n
− 1)-concave probability densities satisfying a smoothness criterion, which includes heavy-tailed densities such as the Cauchy density. In addition, the mixing time of this random walk for Cauchy density matches the corresponding best known bounds for logconcave densities.