mlsanityData to 7 Oct 2026

SIMPLE: A Gradient Estimator for k-Subset Sampling

arXiv 2210.01941 ↗First posted 4 Oct 2022cs.LG cs.AIcited by 34

Not on the map. Why?

Abstract (arXiv)

k-subset sampling is ubiquitous in machine learning, enabling regularization and interpretability through sparsity. The challenge lies in rendering k-subset sampling amenable to end-to-end learning. This has typically involved relaxing the reparameterized samples to allow for backpropagation, with the risk of introducing high bias and high variance. In this work, we fall back to discrete k-subset sampling on the forward pass. This is coupled with using the gradient with respect to the exact marginals, computed efficiently, as a proxy for the true gradient. We show that our gradient estimator, SIMPLE, exhibits lower bias and variance compared to state-of-the-art estimators, including the straight-through Gumbel estimator when k = 1. Empirical results show improved performance on learning to explain and sparse linear regression. We provide an algorithm for computing the exact ELBO for the k-subset distribution, obtaining significantly lower loss compared to SOTA.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). Builds on 39 of its 66 references that are in the map. First posted on arXiv 4 Oct 2022.

Builds on

39 of 66 references.

References · 39

  1. 2017Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layercited by 3,413
  2. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,708
  3. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,135
  4. 2019Neural Probabilistic Logic Programming in DeepProbLogcited by 389
  5. 2016From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classificationcited by 337
  6. 2016Rationalizing Neural Predictionscited by 281
  7. 2017A Semantic Loss Function for Deep Learning with Symbolic Knowledgecited by 267
  8. 2018Learning to Explain: An Information-Theoretic Perspective on Model Interpretationcited by 248
  9. 2019Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacementcited by 205
  10. 2020Fast Differentiable Sorting and Rankingcited by 196
  11. 2019Sparse Sequence-to-Sequence Modelscited by 167
  12. 2019Adaptively Sparse Transformerscited by 154
27 more
  1. 2014A* Samplingcited by 150
  2. 2016Discrete Variational Autoencoderscited by 124
  3. 2019Learning with Fenchel-Young Lossescited by 117
  4. 2019Differentiable Ranks and Sorting using Optimal Transportcited by 113
  5. 2019Stochastic Optimization of Sorting Networks via Continuous Relaxationscited by 111
  6. 2017Backpropagation through the Void: Optimizing control variates for black-box gradient estimationcited by 104
  7. 2022Semantic Probabilistic Layers for Neuro-Symbolic Learningcited by 103
  8. 2018Neural Nearest Neighbors Networkscited by 98
  9. 2021Implicit MLE: Backpropagating Through Discrete Exponential Family Distributionscited by 97
  10. 2021PySINDy: A comprehensive Python package for robust sparse system identificationcited by 88
  11. 2020Deep Graph Matching via Blackbox Differentiation of Combinatorial Solverscited by 81
  12. 2017REBAR: Low-variance, unbiased gradient estimates for discrete latent variable modelscited by 78
  13. 2019Reparameterizable Subset Sampling via Continuous Relaxationscited by 69
  14. 2020Gradient Estimation with Stochastic Softmax Trickscited by 66
  15. 2018SparseMAP: Differentiable Sparse Structured Inferencecited by 62
  16. 2018Differentiable Dynamic Programming for Structured Prediction and Attentioncited by 58
  17. 2019Optimizing Rank-based Metrics with Blackbox Differentiationcited by 58
  18. 2022Neuro-Symbolic Entropy Regularizationcited by 27
  19. 2019Structured Prediction with Projection Oraclescited by 21
  20. 2020Efficient Marginalization of Discrete and Structured Latent Variables via Sparsitycited by 21
  21. 2021Learning with Algorithmic Supervision via Continuous Relaxationscited by 21
  22. 2018Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencodercited by 19
  23. 2020LP-SparseMAP: Differentiable Relaxed Optimization for Sparse Structured Predictioncited by 17
  24. 2022Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Modelscited by 12
  25. 2019Efficient Search-Based Weighted Model Integrationcited by 11
  26. 2020Scaling up Hybrid Probabilistic Inference with Logical and Arithmetic Constraints via Message Passingcited by 11
  27. 2021Leveraging Unlabeled Data for Entity-Relation Extraction through Probabilistic Constraint Satisfactioncited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 12; 2024: 10; 2025: 7; 2026: 5.

34 papers.

Sort:

By area:

  1. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  2. 2023Graph Deep Learning for Time Series Forecastingcited by 26
  3. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  4. 2024Scaling Tractable Probabilistic Circuits: A Systems Perspectivecited by 23
  5. 2023A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraintscited by 21
  6. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  7. 2023Semantic Strengthening of Neuro-Symbolic Learningcited by 12
  8. 2024Controllable Generation via Locally Constrained Resamplingcited by 11
  9. 2023A Unified Approach to Count-Based Weakly-Supervised Learningcited by 9
  10. 2023GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networkscited by 7
  11. 2023Collapsed Inference for Bayesian Deep Learningcited by 6
  12. 2023Adaptive Computation Modules: Granular Conditional Computation For Efficient Inferencecited by 6
22 more
  1. 2023Graph State-Space Models and Latent Relational Inferencecited by 4
  2. 2025Tractable Representation Learning with Probabilistic Circuitscited by 4
  3. 2023Differentiable Random Partition Modelscited by 3
  4. 2024Semantic Loss Functions for Neuro-Symbolic Structured Predictioncited by 3
  5. 2024SPHINX: Structural Prediction using Hypergraph Inference Networkcited by 3
  6. 2025Learning with Local Search MCMC Layerscited by 2
  7. 2024Revisiting Score Function Estimators for k-Subset Samplingcited by 1
  8. 2025FedGrAINS: Personalized SubGraph Federated Learning with Adaptive Neighbor Samplingcited by 1
  9. 2025Deep Generative Models with Hard Linear Equality Constraintscited by 1
  10. 2025Zero-Variance Gradients for Variational Autoencoderscited by 1
  11. 2026Differentiable Knapsack and Top-k Operators via Dynamic Programmingcited by 1
  12. 2023Learning to Simplify Spatial-Temporal Graphs in Gait Analysiscited by 0
  13. 2024A Complexity Map of Probabilistic Reasoning for Neurosymbolic Classification Techniquescited by 0
  14. 2024Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithmscited by 0
  15. 2024Learning Predictive Checklists with Probabilistic Logic Programmingcited by 0
  16. 2024Discrete Subgraph Sampling for Interpretable Graph based Visual Question Answeringcited by 0
  17. 2025Exploiting the Potential Supervision Information of Clean Samples in Partial Label Learningcited by 0
  18. 2025Beyond Softmax: A Natural Parameterization for Categorical Random Variablescited by 0
  19. 2026GraIP: A Benchmarking Framework For Neural Graph Inverse Problemscited by 0
  20. 2026Learning to Approximate Uniform Facility Location via Graph Neural Networkscited by 0
  21. 2026ProbMoE: Differentiable Probabilistic Routing for Mixture-of-Expertscited by 0
  22. 2026Propensity Straight-Through Gradients for Discrete Stochastic Systemscited by 0