For the problem of UBSR optimization, we propose a stochastic gradient algorithm, and derive non-asymptotic bounds on its performance. Stochastic gradient (SG) methods have a long history, and non-asymptotic analysis of such schemes has garnered a lot of attention over the last decade, see [1]} for a survey.
Unlike in a classic SG setting, the UBSR optimization problem involves biased function measurements, which presents some technical challenges. Specifically, the UBSR estimation scheme is biased, in the sense that the estimation error does not have zero expectation. This is unlike in the classical SG settings, where the estimation error is assumed to be zero mean. In our setting, even though the estimation error is not zero-mean, the error can be reduced by increasing the batch size used for estimation.
For the purpose of gradient estimation, we leverage the UBSR sensitivity formula derived in [2]}, and use a natural estimator of this quantity based on i.i.d. samples. By controlling the batch size, we are able to derive a \(O(1/n)\)  rate for the SG algorithm to optimize the UBSR.
