Unbiased Single-Queried Gradient for Combinatorial Objective
This work addresses a bottleneck in probabilistic reformulations of combinatorial problems, offering a more efficient gradient computation method for researchers and practitioners in optimization and machine learning.
The paper tackles the problem of computing gradients for combinatorial optimization problems by proposing a stochastic gradient method that is unbiased and requires only a single query of the combinatorial function, encompassing REINFORCE and introducing new classes of stochastic gradients.
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.