  In this article we introduce an algorithm for mitigating the adverse effects
of noise on gradient descent in variational quantum algorithms. This is
accomplished by computing a {\emph{regularized}} local classical approximation
to the objective function at every gradient descent step. The computational
overhead of our algorithm is entirely classical, i.e., the number of circuit
evaluations is exactly the same as when carrying out gradient descent using the
parameter-shift rules. We empirically demonstrate the advantages offered by our
algorithm on randomized parametrized quantum circuits.
