# Efficient Marginalization of Discrete and Structured Latent Variables via Sparsity

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2020.

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

- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Sparsity-Constrained Optimal Transport](https://mlsanity.com/paper/2209.15466/) (2022)
- [Sparse Graph Learning from Spatiotemporal Time Series](https://mlsanity.com/paper/2205.13492/) (2022)
- [Sparse Continuous Distributions and Fenchel-Young Losses](https://mlsanity.com/paper/2108.01988/) (2021)
- [Storchastic: A Framework for General Stochastic Automatic Differentiation](https://mlsanity.com/paper/2104.00428/) (2021)
- [Exploring Social Posterior Collapse in Variational Autoencoder for Interaction Modeling](https://mlsanity.com/paper/2112.00298/) (2021)
- [Constraint-Free Structure Learning with Smooth Acyclic Orientations](https://mlsanity.com/paper/2309.08406/) (2023)
- [DAG Learning on the Permutahedron](https://mlsanity.com/paper/2301.11898/) (2023)
- [Learning from Executions for Semantic Parsing](https://mlsanity.com/paper/2104.05819/) (2021)
- [Evidential Softmax for Sparse Multimodal Distributions in Deep Generative Models](https://mlsanity.com/paper/2110.14182/) (2021)
- [On Finding the K-best Non-projective Dependency Trees](https://mlsanity.com/paper/2106.00780/) (2021)
- [Reranking Laws for Language Generation: A Communication-Theoretic Perspective](https://mlsanity.com/paper/2409.07131/) (2024)
- [Sparse Communication via Mixed Distributions](https://mlsanity.com/paper/2108.02658/) (2021)
- [Scaling Structured Inference with Randomization](https://mlsanity.com/paper/2112.03638/) (2021)
- [Learning Discrete Structured Variational Auto-Encoder using Natural Evolution Strategies](https://mlsanity.com/paper/2205.01324/) (2022)
- [Efficient Learning of Discrete-Continuous Computation Graphs](https://mlsanity.com/paper/2307.14193/) (2023)
- [Reconciling the Discrete-Continuous Divide: Towards a Mathematical Theory of Sparse Communication](https://mlsanity.com/paper/2104.00755/) (2021)
- [SLM: End-to-end Feature Selection via Sparse Learnable Masks](https://mlsanity.com/paper/2304.03202/) (2023)
- [NeuralPDR: Neural Differential Equations as surrogate models for Photodissociation Regions](https://mlsanity.com/paper/2506.14270/) (2025)
- [Distillation of a tractable model from the VQ-VAE](https://mlsanity.com/paper/2509.01400/) (2025)

## Abstract (arXiv)

Training neural network models with discrete (categorical or structured) latent variables can be computationally challenging, due to the need for marginalization over large or combinatorial sets. To circumvent this issue, one typically resorts to sampling-based approximations of the true marginal, requiring noisy gradient estimators (e.g., score function estimator) or continuous relaxations with lower-variance reparameterized gradients (e.g., Gumbel-Softmax). In this paper, we propose a new training strategy which replaces these estimators by an exact yet efficient marginalization. To achieve this, we parameterize discrete distributions over latent assignments using differentiable sparse mappings: sparsemax and its structured counterparts. In effect, the support of these distributions is greatly reduced, which enables efficient marginalization. We report successful results in three tasks covering a range of latent variable modeling applications: a semisupervised deep generative model, a latent communication game, and a generative model with a bit-vector latent representation. In all cases, we obtain good performance while still achieving the practicality of sampling-based approximations.