Complexity of Adagrad and other first-order methods for nonconvex
    optimization problems  with bounds and convex constraints

                S. Gratton, S. Jerad and Ph. L. Toint
                         July 2024

A parametric class of trust-region algorithms for constrained
nonconvex optimization is analyzed, where the objective function is
never computed. By defining appropriate first-order stationarity
criteria, we are able to extend the Adagrad method to the newly
considered problem and retrieve the standard complexity rate of the
projected gradient method that uses both the gradient and objective
function values. Furthermore, we propose an additional
iteration-dependent scaling with slightly inferior theoretical
guarantees. In both cases, the bounds are essentially sharp, and
curvature information can be used to compute the stepsize. The
adaptation of the algorithm to the convex constrained case is
discussed, and initial experimental results for noisy
bound-constrained instances illustrate the benefits of the
objective-free approach.

Keywords: First-order methods, objective-function-free optimization
(OFFO), Adagrad, convergence bounds, evaluation complexity, second-order models.