Sub-sampled Trust-Region Methods with Deterministic Worst-Case Complexity Guarantees

Abstract

In this paper, we develop and analyze sub-sampled trust-region methods for solving finite-sum optimization problems. These methods employ subsampling strategies to approximate the gradient and Hessian of the objective function, significantly reducing the overall computational cost. We propose a novel adaptive procedure for deterministically adjusting the sample size used for gradient (or gradient and Hessian) approximations. Furthermore, we establish worst-case iteration complexity bounds for obtaining approximate stationary points. More specifically, for a given ${\epsilon }_g,{\epsilon }_H\in (0,1)$, it is shown that an ${\epsilon }_g$-approximate first-order stationary point is reached in at most $\mathcal{O}({{\epsilon }_g}^{-2})$ iterations, whereas an $({\epsilon }_g,{\epsilon }_H)$-approximate second-order stationary point is reached in at most $\mathcal{O}(\max \{{\epsilon }_g^{-2}{\epsilon }_H^{-1},{\epsilon }_H^{-3}\})$ iterations. Finally, numerical experiments illustrate the effectiveness of our new subsampling technique.