High Dimensional Inference With Random Maximum A-Posteriori Perturbations

DOI10.1109/TIT.2019.2916805MaRDI QIDQ5211460zbMATH OpenOpenAlexWikidataFDO

Authors Tamir Hazan, Francesco Orabona, Anand Dilip Sarwate, Subhransu Maji, Tommi S. Jaakkola

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.03571

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Computational methods in Markov chains (60J22) Statistics of extreme values; tail inference (62G32) Multivariate analysis (62H99) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: 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.

Cited in

(8)

• In defense of the indefensible: a very naïve approach to high-dimensional inference
• High-dimensional inference using the extremal skew-\(t\) process
• Randomized incomplete \(U\)-statistics in high dimensions
• A Randomized Maximum A Posteriori Method for Posterior Sampling of High Dimensional Nonlinear Bayesian Inverse Problems
• scientific article; zbMATH DE number 7219341 (Why is no real title available?)
• Ancestral Gumbel-top-k sampling for sampling without replacement
• Approximating posteriors with high-dimensional nuisance parameters via integrated rotated Gaussian approximation
• Markov Neighborhood Regression for High-Dimensional Inference

This page was built for publication: High Dimensional Inference With Random Maximum A-Posteriori Perturbations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211460)