2016/02/10 by Tamir Hazan, Hazan, Tamir, Francesco Orabona +7
Computer Science · Mathematics · #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistical Methods and Inference #cs.IT #cs.LG #math.IT #stat.ML
paper · pdf · doi:10.48550/arxiv.1602.03571
47 pages, 10 figures, under review
openalex publication_date 2016/02/10 · arxiv created 2017/05/30 · arxiv updated 2017/06/01 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
This paper presents a new approach, called perturb-max, for high-dimensional statistical inference that is based on applying random perturbations followed by optimization. This framework injects randomness to maximum a-posteriori (MAP) predictors by randomly perturbing the potential function for the input. A classic result from extreme value statistics asserts that perturb-max operations generate unbiased samples from the Gibbs distribution using high-dimensional perturbations. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. However, when the perturbations are of low dimension, sampling the perturb-max prediction is as efficient as MAP optimization. This paper shows that the expected value of perturb-max inference with low dimensional perturbations can be used sequentially to generate unbiased samples from the Gibbs distribution. Furthermore the expected value of the maximal perturbations is a natural bound on the entropy of such perturb-max models. A measure concentration result for perturb-max values shows that the deviation of their sampled average from its expectation decays exponentially in the number of samples, allowing effective approximation of the expectation.