  A parametric class of trust-region algorithms for unconstrained nonconvex
optimization is considered where the value of the objective function is never
computed. The class contains a deterministic version of the first-order Adagrad
method typically used for minimization of noisy function, but also allows the
use of (possibly approximate) second-order information when available. The rate
of convergence of methods in the class is analyzed and is shown to be identical
to that known for first-order optimization methods using both function and
gradients values, recovering existing results for purely-first order variants
and improving the explicit dependence on problem dimension. This rate is shown
to be essentially sharp. A new class of methods is also presented, for which a
slightly worse and essentially sharp complexity result holds. Limited numerical
experiments show that the new methods' performance may be comparable to that of
standard steepest descent, despite using significantly less information, and
that this performance is relatively insensitive to noise.
