# Unbiased Single-Queried Gradient for Combinatorial Objective

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 4 Feb 2026.

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

- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Gradient Estimation Using Stochastic Computation Graphs](https://mlsanity.com/paper/1506.05254/) (2015)
- [Backpropagation through the Void: Optimizing control variates for black-box gradient estimation](https://mlsanity.com/paper/1711.00123/) (2017)
- [DisARM: An Antithetic Gradient Estimator for Binary Latent Variables](https://mlsanity.com/paper/2006.10680/) (2020)
- [When Simple is Near Optimal in Security Games](https://mlsanity.com/paper/2402.11209/) (2024)
- [DEFT: Differentiable Automatic Test Pattern Generation](https://mlsanity.com/paper/2512.23746/) (2025)
- [Differentiable Integer Linear Programming is not Differentiable & it's not a mere technical problem](https://mlsanity.com/paper/2601.17800/) (2026)

## Abstract (arXiv)

In a probabilistic reformulation of a combinatorial problem, we often face an optimization over a hypercube, which corresponds to the Bernoulli probability parameter for each binary variable in the primal problem. The combinatorial nature suggests that an exact gradient computation requires multiple queries. We propose a stochastic gradient that is unbiased and requires only a single query of the combinatorial function. This method encompasses a well-established REINFORCE (through an importance sampling), as well as including a class of new stochastic gradients.