  A regularization algorithm allowing random noise in derivatives and inexact
function values is proposed for computing approximate local critical points of
any order for smooth unconstrained optimization problems. For an objective
function with Lipschitz continuous $p$-th derivative and given an arbitrary
optimality order $q \leq p$, it is shown that this algorithm will, in
expectation, compute such a point in at most
$O\left(\left(\min_{j\in\{1,\ldots,q\}}\epsilon_j\right)^{-\frac{p+1}{p-q+1}}\right)$
inexact evaluations of $f$ and its derivatives whenever $q\in\{1,2\}$, where
$\epsilon_j$ is the tolerance for $j$th order accuracy. This bound becomes at
most
$O\left(\left(\min_{j\in\{1,\ldots,q\}}\epsilon_j\right)^{-\frac{q(p+1)}{p}}\right)$
inexact evaluations if $q>2$ and all derivatives are Lipschitz continuous.
Moreover these bounds are sharp in the order of the accuracy tolerances. An
extension to convexly constrained problems is also outlined.
