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

arXiv: https://arxiv.org/abs/2005.06083 · HTML: https://mlsanity.com/paper/2005.06083/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2020.

## Built on by (most cited first, 4 of 4)

- [A Data-Driven State Aggregation Approach for Dynamic Discrete Choice Models](https://mlsanity.com/paper/2304.04916/) (2023)
- [Deep PQR: Solving Inverse Reinforcement Learning using Anchor Actions](https://mlsanity.com/paper/2007.07443/) (2020)
- [SMILE: Evaluation and Domain Adaptation for Social Media Language Understanding](https://mlsanity.com/paper/2307.00135/) (2023)
- [High-dimensional Inference and FDR Control for Simulated Markov Random Fields](https://mlsanity.com/paper/2202.05612/) (2022)

## Abstract (arXiv)

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 [Schmidtet 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.