Improving the convergence rates of forward gradient descent with repeated sampling

Abstract Forward gradient descent (FGD) has been proposed as a biologically more plausible alternative of gradient descent as it can be computed without backward pass. Considering the linear model with $d$ parameters, previous work has found that the prediction error of FGD is, however, by a factor $d$ larger than the prediction error of stochastic gradient descent. In this paper, we show that performing $\ell$ FGD updates per training sample reduces the suboptimality factor to $\max (1,d/\ell ).$ Consequently, the convergence rate becomes optimal once $\ell \gtrsim d$. We also show that FGD with repeated sampling can adapt to low-dimensional structure in the input distribution. The main mathematical challenge lies in controlling the dependencies arising from the repeated sampling process.