  Adaptive trust-region methods attempt to maintain strong convergence
guarantees without depending on conservative estimates of problem properties
such as Lipschitz constants. However, on close inspection, one can show
existing adaptive trust-region methods have theoretical guarantees with
severely suboptimal dependence on problem properties such as the Lipschitz
constant of the Hessian. For example, TRACE developed by Curtis et al. obtains
a $O(\Delta_f L^{3/2} \epsilon^{-3/2}) + \tilde{O}(1)$ iteration bound where
$L$ is the Lipschitz constant of the Hessian. Compared with the optimal
$O(\Delta_f L^{1/2} \epsilon^{-3/2})$ bound this is suboptimal with respect to
$L$. We present the first adaptive trust-region method which circumvents this
issue and requires at most $O( \Delta_f L^{1/2} \epsilon^{-3/2}) +
\tilde{O}(1)$ iterations to find an $\epsilon$-approximate stationary point,
matching the optimal iteration bound up to an additive logarithmic term. Our
method is a simple variant of a classic trust-region method and in our
experiments performs competitively with both ARC and a classical trust-region
method.
