提出单次查询的无偏梯度方法，高效优化组合问题
Unbiased Single-Queried Gradient for Combinatorial Objective
- 用单次查询实现无偏梯度估计，避免多次评估
- 在超立方体优化中提升效率，兼容REINFORCE等方法
- 适合需快速梯度反馈的组合优化场景
在组合问题的概率重述中，常需在超立方体上进行优化，对应于原始问题中每个二值变量的伯努利概率参数。由于组合特性，精确梯度计算通常需要多次查询组合函数。本文提出一种仅需单次查询即可获得无偏梯度的随机梯度方法。该方法包含经典的REINFORCE（通过重要性采样实现），还扩展出一类新型随机梯度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。