![[2602.05119] Unbiased Single-Queried Gradient for Combinatorial Objective](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.05119] Unbiased Single-Queried Gradient for Combinatorial Objective
Summary
This paper presents a novel stochastic gradient method for combinatorial optimization that requires only a single query, enhancing efficiency in gradient computation.
Why It Matters
The proposed method addresses a significant challenge in combinatorial optimization by reducing the number of required queries for gradient computation. This advancement could lead to more efficient algorithms in machine learning and optimization tasks, making it relevant for researchers and practitioners in these fields.
Key Takeaways
- Introduces an unbiased stochastic gradient method for combinatorial objectives.
- Reduces the need for multiple queries, enhancing computational efficiency.
- Builds on existing techniques like REINFORCE and importance sampling.
Computer Science > Machine Learning arXiv:2602.05119 (cs) [Submitted on 4 Feb 2026 (v1), last revised 16 Feb 2026 (this version, v2)] Title:Unbiased Single-Queried Gradient for Combinatorial Objective Authors:Thanawat Sornwanee View a PDF of the paper titled Unbiased Single-Queried Gradient for Combinatorial Objective, by Thanawat Sornwanee View PDF HTML (experimental) Abstract: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. Comments: Subjects: Machine Learning (cs.LG); Optimization and Control (math.OC) Cite as: arXiv:2602.05119 [cs.LG] (or arXiv:2602.05119v2 [cs.LG] for this version) https://doi.org/10.48550/arXiv.2602.05119 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Thanawat Sornwanee [view email] [v1] Wed, 4 Feb 2026 23:08:07 UTC (1,162 KB) [v2] Mon, 16 Feb 2026 04:14:16 UTC (1,162 KB) Full-text links: Access Paper: View a PDF of the paper titled Unbiased Single-Queried Gradient for Combinatorial Objective, by Thanawat Sor...