A consistently adaptive trust-region method

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(Deltaf L3/2 ε-3/2) + tildeO(1) iteration bound where L is the Lipschitz constant of the Hessian. Compared with the optimal O(Deltaf L1/2 ε-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( Deltaf L1/2 ε-3/2) + tildeO(1) iterations to find an ε-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.