Timezone: »
Inference is typically intractable in hightreewidth undirected graphical models, making maximum likelihood learning a challenge. One way to overcome this is to restrict parameters to a tractable set, most typically the set of treestructured parameters. This paper explores an alternative notion of a tractable set, namely a set of “fastmixing parameters” where Markov chain Monte Carlo (MCMC) inference can be guaranteed to quickly converge to the stationary distribution. While it is common in practice to approximate the likelihood gradient using samples obtained from MCMC, such procedures lack theoretical guarantees. This paper proves that for any exponential family with bounded sufficient statistics, (not just graphical models) when parameters are constrained to a fastmixing set, gradient descent with gradients approximated by sampling will approximate the maximum likelihood solution inside the set with highprobability. When unregularized, to find a solution epsilonaccurate in loglikelihood requires a total amount of effort cubic in 1/epsilon, disregarding logarithmic factors. When ridgeregularized, strong convexity allows a solution epsilonaccurate in parameter distance with an effort quadratic in 1/epsilon. Both of these provide of a fullypolynomial time randomized approximation scheme.
Author Information
Justin Domke (NICTA)
More from the Same Authors

2015 Poster: Reflection, Refraction, and Hamiltonian Monte Carlo »
Hadi Mohasel Afshar · Justin Domke 
2014 Poster: Projecting Markov Random Field Parameters for Fast Mixing »
Xianghang Liu · Justin Domke 
2013 Poster: Structured Learning via Logistic Regression »
Justin Domke 
2013 Spotlight: Structured Learning via Logistic Regression »
Justin Domke 
2013 Poster: Projecting Ising Model Parameters for Fast Mixing »
Justin Domke · Xianghang Liu