  


Adaptive regularization algorithms with inexact evaluations for nonconvex optimization
Stefania Bellavia (stefania.bellaviaunifi.it) 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 betaH\"{o}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 qth 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^{(p+beta)/(pq+beta}) iterations and at most O(log(epsilon)epsilon^{(p+\beta)/(pq+beta}) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimize in O(log(epsilon)+epsilon^{(p+\beta)/(pq+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 boundconstrained first and secondorder cases. The deterministic complexity results are finally extended to the stochastic context, yielding adaptive samplesize rules for subsampling methods typical of machine learning. Keywords: evaluation complexity, regularization methods, inexact functions and derivatives, subsampling methods, machine learning Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Category 2: Applications  Science and Engineering (DataMining ) Category 3: Nonlinear Optimization (Unconstrained Optimization ) Citation: Download: [PDF] Entry Submitted: 11/09/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  