Consider a simple case of optimization of a system implementing a gradient descent method. This is a particular example of a class of learning algorithms called "stochastic approximation methods". We motivate our research with a real life problem in telecommunications flow control, and then study the general model.

The learning algorithm requires updating the control variables using certain feedback functions. In real systems that operate under uncertainty, even when a model is used, closed formulas for the feedback often require certain quantities or parameters that are unknown and must be estimated. For our example in telecommunications, the arrival rates (demand) are random and not known in advance.

For such scenarios, so called quasi-static optimization methods were proposed three decades ago, replacing the values of the the parameters by their estimates in the formulas. However, unless the formulas for the feedback are linear (which they rarely are), replacing an estimate inside the formula yields a biased estimator.

In this work we explore a statistical correction that provably reduces such bias. In our examples we observe also the benefit of variance reduction, although the conditions required for this reduction are hard to verify in the general setting.