Variance reduction technique improves learning from black-box feedback
Variance-Optimal Control Variates for Learning with Black-box Feedback
Machine Learning
Summary
Sometimes computer programs learn by getting feedback from tools or people whose inner workings are hidden. The authors found that using a common method to reduce noise in this feedback isn’t always the best way. They discovered a better way to reduce this noise by adjusting how the learning updates are calculated, making the learning process more stable and efficient. Their new method works well across various tasks and can be computed without extra calls to the feedback source.
What this means in practice
- •For machine learning engineers: Improve model training stability and speed when using feedback from external oracles with hidden mechanisms.
- •For optimization software developers: Reduce variance in gradient estimates when integrating black-box solvers into learning systems to enhance performance.
Authors
Zihao Zhao, Shuhan Zhang, Kai Wang
Abstract
Modern models increasingly learn through black-box oracles such as humans, optimization solvers, and external tools that provide feedback without exposing their internal mechanisms. A common remedy is to learn an (action-)value function as a control variate. In this paper, we first observe that even an exact action-value function can be arbitrarily far from variance-optimal. We show that this gap arises because the value function minimizes the noise in each action's own gradient term, while an action can still affect the rest of the gradient estimator through shared parameters. A simple unbiased correction, at no extra oracle cost, can still reduce its variance by an arbitrarily large factor. Motivated by this, we then prove that the residual variance can be decomposed exactly by actions with no cross terms. This decomposition yields a closed-form variance-minimizing correction for neural-network parameters, which can be computed by a simple projection. Empirically, our correction consistently reduces the variance left by the value function and improves learning across all tasks. The source code for all experiments is available at https://github.com/Zihao-Kevin/black_box_opt.