Philippe L. Toint – Optimization Online

Nonlinear Optimization, Unconstrained Optimization adaptive regularization methods, evaluation complexity, negative curvature, Newton's Method, nonconvex optimization

 A second-order algorithm is proposed for minimizing smooth nonconvex functions that alternates between regularized Newton and negative curvature steps. In most cases, the Hessian matrix is regularized with the square root of the current gradient and an additional term taking moderate negative curvature into account, a negative curvature step being taken only exceptionnally. As … Read more

Multilevel Objective-Function-Free Optimization with an Application to Neural Networks Training

Published: 2023/02/14

Alena Kopanicakova

Data Science Algorithms, Nonlinear Optimization, Nonlinear Systems and Least-Squares evaluation complexity, multilevel optimization, neural network training, OFFO methods

A class of multi-level algorithms for unconstrained nonlinear optimization is presented which does not require the evaluation of the objective function. The class contains the momentum-less AdaGrad method as a particular (single-level) instance. The choice of avoiding the evaluation of the objective function is intended to make the algorithms of the class less sensitive to … Read more

Convergence properties of an Objective-Function-Free Optimization regularization algorithm, including an $\mathcal{O}(\epsilon^{-3/2})$ complexity bound

Published: 2022/03/18

Nonlinear Systems and Least-Squares, Unconstrained Optimization adaptive regularization methods, evaluation complexity, nonlinear optimization, objective-function-free optimization

An adaptive regularization algorithm for unconstrained nonconvex optimization is presented in which the objective function is never evaluated, but only derivatives are used. This algorithm belongs to the class of adaptive regularization methods, for which optimal worst-case complexity results are known for the standard framework where the objective function is evaluated. It is shown in … Read more

OFFO minimization algorithms for second-order optimality and their complexity

Published: 2022/03/07

Unconstrained Optimization Adagrad, evaluation complexity, global rate of convergence, objective-function-free optimization (OFFO), second-order optimality

An Adagrad-inspired class of algorithms for smooth unconstrained optimization is presented in which the objective function is never evaluated and yet the gradient norms decrease at least as fast as O(1/\sqrt{k+1}) while second-order optimality measures converge to zero at least as fast as O(1/(k+1)^{1/3}). This latter rate of convergence is shown to be essentially sharp … Read more

Parametric complexity analysis for a class of first-order Adagrad-like algorithms

Published: 2022/03/07

Stochastic Programming, Unconstrained Optimization Adagrad, convergence bounds, evaluation complexity, first-order methods, noisy gradients, objective-function-free optimization

A class of algorithms for optimization in the presence of noise is presented, that does not require the evaluation of the objective function. This class generalizes the well-known Adagrad method. The complexity of this class is then analyzed as a function of its parameters, and it is shown that some methods of the class enjoy … Read more

First-Order Objective-Function-Free Optimization Algorithms and Their Complexity

Published: 2022/03/07

Unconstrained Optimization Adagrad, convergence bounds, evaluation complexity, first-order methods, objective-function-free optimization (OFFO), second-order models

A class of algorithms for unconstrained nonconvex optimization is considered where the value of the objective function is never computed. The class contains a deterministic version of the first-order Adagrad method typically used for minimization of noisy function, but also allows the use of second-order information when available. The rate of convergence of methods in … Read more

An adaptive regularization algorithm for unconstrained optimization with inexact function and derivatives values

Published: 2021/12/12

Nicholas I. M. Gould

Nonlinear Systems and Least-Squares, Unconstrained Optimization adaptive regularization, evaluation complexity, inexact functions and derivative values, nonconvex optimization

An adaptive regularization algorithm for unconstrained nonconvex optimization is proposed that is capable of handling inexact objective-function and derivative values, and also of providing approximate minimizer of arbitrary order. In comparison with a similar algorithm proposed in Cartis, Gould, Toint (2022), its distinguishing feature is that it is based on controlling the relative error between … Read more

Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques

Published: 2021/12/12

Nonlinear Systems and Least-Squares, Unconstrained Optimization evaluation complexity, finite-sum optimization, inexact functions and derivatives, probabilistic analysis, subsampling methods, trust-region methods

A trust-region algorithm is presented for finding approximate minimizers of smooth unconstrained functions whose values and derivatives are subject to random noise. It is shown that, under suitable probabilistic assumptions, the new method finds (in expectation) an epsilon-approximate minimizer of arbitrary order q > 0 in at most O(epsilon^{-(q+1)}) inexact evaluations of the function and … Read more

OPM, a collection of Optimization Problems in Matlab

Published: 2021/12/10