Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization

Abstract

A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is $\beta$-Hölder continuous. It features a very flexible adaptive mechanism for determining the inexactness which is allowed, at each iteration, when computing objective function values and derivatives. The complexity analysis covers arbitrary optimality order and arbitrary degree of available approximate derivatives. It extends results of Cartis, Gould and Toint (2018) on the evaluation complexity to the inexact case: if a $q$th order minimizer is sought using approximations to the first $p$ derivatives, it is proved that a suitable approximate minimizer within $\epsilon$ is computed by the proposed algorithm in at most $O({\epsilon }^{-\frac{p+\beta }{p-q+\beta }})$ iterations and at most $O(|\log (\epsilon )|{\epsilon }^{-\frac{p+\beta }{p-q+\beta }})$ approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in $O(|\log (\epsilon )|+{\epsilon }^{-\frac{p+\beta }{p-q+\beta }})$ evaluations.While the proposed framework remains so far conceptual for high degrees and orders, it is shown to yield simple and computationally realistic inexact methods when specialized to the unconstrained and bound-constrained first- and second-order cases. The deterministic complexity results are finally extended to the stochastic context, yielding adaptive sample-size rules for subsampling methods typical of machine learning.

32 pages

References in corpus (7)

• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• A Stochastic Line Search Method with Convergence Rate Analysis
• Inexact Non-Convex Newton-Type Methods
• Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales
• Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
• Bernstein Concentration Inequalities for Tensors via Einstein Products
• Minimizing convex quadratic with variable precision conjugate gradients

Cited by in corpus (6)

• Inexact Restoration for Minimization with Inexact Evaluation both of the Objective Function and the Constraints
• Bernstein Concentration Inequalities for Tensors via Einstein Products
• Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
• A note on solving nonlinear optimization problems in variable precision
• High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms
• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity