Stochastic Learning for Sparse Discrete Markov Random Fields with Controlled Gradient Approximation Error

Sinong Geng, Zhaobin Kuang, Jie Liu, Stephen Wright, David Page
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:155-165, 2018.

Abstract

We study the L1-regularized maximum likelihood estimator/estimation (MLE) problem for discrete Markov random fields (MRFs), where efficient and scalable learning requires both sparse regularization and approximate inference. To address these challenges, we consider a stochastic learning framework called stochastic proximal gradient (SPG; Honorio 2012a, Atchade et al. 2014, Miasojedow and Rejchel 2016). SPG is an inexact proximal gradient algorithm [Schmidt et al., 2011], whose inexactness stems from the stochastic oracle (Gibbs sampling) for gradient approximation – exact gradient evaluation is infeasible in general due to the NP-hard inference problem for discrete MRFs [Koller and Friedman, 2009]. Theoretically, we provide novel verifiable bounds to inspect and control the quality of gradient approximation. Empirically, we propose the tighten asymptotically (TAY) learning strategy based on the verifiable bounds to boost the performance of SPG.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-geng18a, title = {Stochastic Learning for Sparse Discrete {M}arkov Random Fields with Controlled Gradient Approximation Error}, author = {Geng, Sinong and Kuang, Zhaobin and Liu, Jie and Wright, Stephen and Page, David}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {155--165}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/geng18a/geng18a.pdf}, url = {https://proceedings.mlr.press/r16/geng18a.html}, abstract = {We study the L1-regularized maximum likelihood estimator/estimation (MLE) problem for discrete Markov random fields (MRFs), where efficient and scalable learning requires both sparse regularization and approximate inference. To address these challenges, we consider a stochastic learning framework called stochastic proximal gradient (SPG; Honorio 2012a, Atchade et al. 2014, Miasojedow and Rejchel 2016). SPG is an inexact proximal gradient algorithm [Schmidt et al., 2011], whose inexactness stems from the stochastic oracle (Gibbs sampling) for gradient approximation – exact gradient evaluation is infeasible in general due to the NP-hard inference problem for discrete MRFs [Koller and Friedman, 2009]. Theoretically, we provide novel verifiable bounds to inspect and control the quality of gradient approximation. Empirically, we propose the tighten asymptotically (TAY) learning strategy based on the verifiable bounds to boost the performance of SPG.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Stochastic Learning for Sparse Discrete Markov Random Fields with Controlled Gradient Approximation Error %A Sinong Geng %A Zhaobin Kuang %A Jie Liu %A Stephen Wright %A David Page %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-geng18a %I PMLR %P 155--165 %U https://proceedings.mlr.press/r16/geng18a.html %V R16 %X We study the L1-regularized maximum likelihood estimator/estimation (MLE) problem for discrete Markov random fields (MRFs), where efficient and scalable learning requires both sparse regularization and approximate inference. To address these challenges, we consider a stochastic learning framework called stochastic proximal gradient (SPG; Honorio 2012a, Atchade et al. 2014, Miasojedow and Rejchel 2016). SPG is an inexact proximal gradient algorithm [Schmidt et al., 2011], whose inexactness stems from the stochastic oracle (Gibbs sampling) for gradient approximation – exact gradient evaluation is infeasible in general due to the NP-hard inference problem for discrete MRFs [Koller and Friedman, 2009]. Theoretically, we provide novel verifiable bounds to inspect and control the quality of gradient approximation. Empirically, we propose the tighten asymptotically (TAY) learning strategy based on the verifiable bounds to boost the performance of SPG. %Z Reissued by PMLR on 04 October 2026.
APA
Geng, S., Kuang, Z., Liu, J., Wright, S. & Page, D.. (2018). Stochastic Learning for Sparse Discrete Markov Random Fields with Controlled Gradient Approximation Error. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:155-165 Available from https://proceedings.mlr.press/r16/geng18a.html. Reissued by PMLR on 04 October 2026.

Related Material