TY - GEN
T1 - Sampling s-concave functions
T2 - 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
AU - Chandrasekaran, Karthekeyan
AU - Deshpande, Amit
AU - Vempala, Santosh
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70350600103&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350600103&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03685-9_32
DO - 10.1007/978-3-642-03685-9_32
M3 - Conference contribution
AN - SCOPUS:70350600103
SN - 3642036848
SN - 9783642036842
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 420
EP - 433
BT - Approximation, Randomization, and Combinatorial Optimization
Y2 - 21 August 2009 through 23 August 2009
ER -