On Measure Concentration of Random Maximum A-Posteriori Perturbations
This work addresses a computational bottleneck in high-dimensional inference and learning, offering incremental improvements for researchers in machine learning and statistics.
The paper tackles the computational inefficiency of generating unbiased samples from the Gibbs distribution using MAP perturbations by developing new measure concentration inequalities that bound the number of samples needed to estimate expected values, potentially leading to a more efficient algorithm.
The maximum a-posteriori (MAP) perturbation framework has emerged as a useful approach for inference and learning in high dimensional complex models. By maximizing a randomly perturbed potential function, MAP perturbations generate unbiased samples from the Gibbs distribution. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. More efficient algorithms use sequential sampling strategies based on the expected value of low dimensional MAP perturbations. This paper develops new measure concentration inequalities that bound the number of samples needed to estimate such expected values. Applying the general result to MAP perturbations can yield a more efficient algorithm to approximate sampling from the Gibbs distribution. The measure concentration result is of general interest and may be applicable to other areas involving expected estimations.