Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 1: Basic ARC Reaches ‖g‖ ≤ ε in O(ε^(−2)) IterationsResearch Paper
Methods for smooth unconstrained minimization, , are compared by how many evaluations of and of its gradient they need, in the worst case, to reach an approximately first-order critical point, an iterate with . For steepest descent with a Lipschitz gradient the answer is (Nesterov, Int…