# DBsurf: A Discrepancy Based Method for Discrete Stochastic Gradient Estimation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 7 Sep 2023.

## Builds on (most cited first, 24 of 24)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware](https://mlsanity.com/paper/1812.00332/) (2018)
- [NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search](https://mlsanity.com/paper/2001.00326/) (2020)
- [SNAS: Stochastic Neural Architecture Search](https://mlsanity.com/paper/1812.09926/) (2018)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search](https://mlsanity.com/paper/1907.05737/) (2019)
- [Searching for A Robust Neural Architecture in Four GPU Hours](https://mlsanity.com/paper/1910.04465/) (2019)
- [Implicit Reparameterization Gradients](https://mlsanity.com/paper/1805.08498/) (2018)
- [REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models](https://mlsanity.com/paper/1703.07370/) (2017)
- [DSNAS: Direct Neural Architecture Search without Parameter Retraining](https://mlsanity.com/paper/2002.09128/) (2020)
- [Few-shot Neural Architecture Search](https://mlsanity.com/paper/2006.06863/) (2020)
- [Estimating Gradients for Discrete Random Variables by Sampling without Replacement](https://mlsanity.com/paper/2002.06043/) (2020)
- [The Generalized Reparameterization Gradient](https://mlsanity.com/paper/1610.02287/) (2016)
- [DisARM: An Antithetic Gradient Estimator for Binary Latent Variables](https://mlsanity.com/paper/2006.10680/) (2020)
- [Generalizing Few-Shot NAS with Gradient Matching](https://mlsanity.com/paper/2203.15207/) (2022)
- [Gradient Estimation with Discrete Stein Operators](https://mlsanity.com/paper/2202.09497/) (2022)
- [ARMS: Antithetic-REINFORCE-Multi-Sample Gradient for Binary Variables](https://mlsanity.com/paper/2105.14141/) (2021)
- [Double Control Variates for Gradient Estimation in Discrete Latent Variable Models](https://mlsanity.com/paper/2111.05300/) (2021)

## Abstract (arXiv)

Computing gradients of an expectation with respect to the distributional parameters of a discrete distribution is a problem arising in many fields of science and engineering. Typically, this problem is tackled using Reinforce, which frames the problem of gradient estimation as a Monte Carlo simulation. Unfortunately, the Reinforce estimator is especially sensitive to discrepancies between the true probability distribution and the drawn samples, a common issue in low sampling regimes that results in inaccurate gradient estimates. In this paper, we introduce DBsurf, a reinforce-based estimator for discrete distributions that uses a novel sampling procedure to reduce the discrepancy between the samples and the actual distribution. To assess the performance of our estimator, we subject it to a diverse set of tasks. Among existing estimators, DBsurf attains the lowest variance in a least squares problem commonly used in the literature for benchmarking. Furthermore, DBsurf achieves the best results for training variational auto-encoders (VAE) across different datasets and sampling setups. Finally, we apply DBsurf to build a simple and efficient Neural Architecture Search (NAS) algorithm with state-of-the-art performance.