Complexity and performance  for two classes
       of noise-tolerant first-order algorithms
 
       S. Gratton, S. Jerad and Ph. L. Toint

Two classes of algorithms for optimization in the presence of noise
are presented, that do not require the evaluation of the objective
function.  The first generalizes the well-known Adagrad method. Its
complexity is then analyzed as a function of its parameters, and it is
shown that some methods of the class enjoy a better asymptotic
convergence rate than previously known. A second class of algorithms
is then derived whose complexity is at least as good as that of the
first class.  Initial numerical experiments on finite-sum problems
arsing from deep-learning applications suggest that that methods of
the second class often outperform those of the first.