Examples of slow convergence for adaptive regularization optimization methods are not isolated

• 成果类型: Article; Early Access
• 署名作者: Toint, Philippe L.
• 署名单位: University of Namur
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02286-1
• 发表日期: 2025
• 关键词: cubic-regularization; trust-region; evaluation complexity; NORM

摘要

The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in [7, 20] to require, under standard assumptions, at most O(& varepsilon;(3/(3-q))) evaluations of the objective function and its derivatives of degrees one and two to produce an & varepsilon;-approximate critical point of order q is an element of{1,2}. This bound was shown to be sharp in [5, 6] for q=1 and in [11] for arbitrary q is an element of{1,2}. This note revisits these results and shows that the example for which slow convergence is exhibited is not isolated, but that this behaviour occurs for a subset of univariate functions of nonzero measure.