conftrace_

2019 COLT COLT 2019

The Relative Complexity of Maximum Likelihood Estimation, MAP Estimation, and Sampling

Abstract

We prove that, for a broad range of problems, maximum-a-posteriori (MAP) estimation and approximate sampling of the posterior are at least as computationally difficult as maximum-likelihood (ML) estimation. By way of illustration, we show how hardness results for ML estimation of mixtures of Gaussians and topic models carry over to MAP estimation and approximate sampling under commonly used priors.

🐣 Hot Topic Early Bird - maximum likelihood

Authors

Christopher Tosh, Sanjoy Dasgupta

Topics

Artificial Intelligence > Bayesian & Probabilistic > Probabilistic Modeling Machine Learning > Optimization & Theory > Bayesian Inference Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Optimization & Theory > Theory Artificial Intelligence > Bayesian & Probabilistic > Bayesian Inference Machine Learning > Learning Types > Sampling

Keywords

posterior sampling computational complexity maximum likelihood maximum a posteriori maximum likelihood estimation approximate sampling gaussian mixture model topic model maximum a posteriori estimation mixture of gaussian

More from COLT 2019

All COLT 2019 papers →

Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression

Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches

Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint

Theoretical guarantees for sampling and inference in generative models with latent diffusions

Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds