TY - UNPB
T1 - Adaptive Regularization for Nonconvex Optimization Using Inexact Function Values and Randomly Perturbed Derivatives
AU - Bellavia, Stefania
AU - Gurioli, Gianmarco
AU - Morini, Benedetta
AU - TOINT, Philippe
N1 - ArXiv:2005.04639 (May 2020)
PY - 2020/5/13
Y1 - 2020/5/13
N2 - A regularization algorithm allowing random noise in derivatives and inexact function values is proposed for computing approximate local critical points of any order for smooth unconstrained optimization problems. For an objective function with Lipschitz continuous p-th derivative and given an arbitrary optimality order q <= p, it is shown that this algorithm will, in expectation, compute such a point in at most O((min_{j=1,...,q}epsilon_j)^{-(p+1)/(p-q+1)}) inexact evaluations of f and its derivatives whenever q in {1,2}, where \epsilon_j is the tolerance for j-th order accuracy. This bound becomes at most O((min_{j=1,...,q}epsilon_j)^{-(q(p+1))/(p)}) inexact evaluations if q>2 and all derivatives are Lipschitz continuous. Moreover these bounds are sharp in the order of the accuracy tolerances. An extension to convexly constrained problems is also outlined.
AB - A regularization algorithm allowing random noise in derivatives and inexact function values is proposed for computing approximate local critical points of any order for smooth unconstrained optimization problems. For an objective function with Lipschitz continuous p-th derivative and given an arbitrary optimality order q <= p, it is shown that this algorithm will, in expectation, compute such a point in at most O((min_{j=1,...,q}epsilon_j)^{-(p+1)/(p-q+1)}) inexact evaluations of f and its derivatives whenever q in {1,2}, where \epsilon_j is the tolerance for j-th order accuracy. This bound becomes at most O((min_{j=1,...,q}epsilon_j)^{-(q(p+1))/(p)}) inexact evaluations if q>2 and all derivatives are Lipschitz continuous. Moreover these bounds are sharp in the order of the accuracy tolerances. An extension to convexly constrained problems is also outlined.
KW - evaluation complexity
KW - regularization methods
KW - lnexact functions and derivatives
KW - stochastic analysis
M3 - Working paper
VL - 2005.04639
BT - Adaptive Regularization for Nonconvex Optimization Using Inexact Function Values and Randomly Perturbed Derivatives
PB - Arxiv
ER -