2022/03/03 by S. Gratton, Sadok Jerad, Gratton, S. +3 · 2 citations
Computer Science · Engineering · Mathematics · #49N30 #90C15 #90C26 #90C30 #90C60 #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Control Systems and Identification #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #Iterative Methods for Nonlinear Equations #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2203.01647
openalex publication_date 2022/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A parametric class of trust-region algorithms for unconstrained nonconvex\noptimization is considered where the value of the objective function is never\ncomputed. The class contains a deterministic version of the first-order Adagrad\nmethod typically used for minimization of noisy function, but also allows the\nuse of (possibly approximate) second-order information when available. The rate\nof convergence of methods in the class is analyzed and is shown to be identical\nto that known for first-order optimization methods using both function and\ngradients values, recovering existing results for purely-first order variants\nand improving the explicit dependence on problem dimension. This rate is shown\nto be essentially sharp. A new class of methods is also presented, for which a\nslightly worse and essentially sharp complexity result holds. Limited numerical\nexperiments show that the new methods' performance may be comparable to that of\nstandard steepest descent, despite using significantly less information, and\nthat this performance is relatively insensitive to noise.\n