2024/02/19 by Ziyu Huang, Bo Jiang, Huang, Ziyu +3 · 2 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2402.11951
openalex publication_date 2024/02/19 · openalex created_date 2024/02/21 · openalex updated_date 2026/07/28
In this paper, we investigate the convergence behavior of the Accelerated Newton Proximal Extragradient (A-NPE) method when employing inexact Hessian information. The exact A-NPE method was the pioneer near-optimal second-order approach, exhibiting an oracle complexity of \TildeO(ε-2/7) for convex optimization. Despite its theoretical optimality, there has been insufficient attention given to the study of its inexact version and efficient implementation. We introduce the inexact A-NPE method (IA-NPE), which is shown to maintain the near-optimal oracle complexity. In particular, we design a dynamic approach to balance the computational cost of constructing the Hessian matrix and the progress of the convergence. Moreover, we show the robustness of the line-search procedure, which is a subroutine in IA-NPE, in the face of the inexactness of the Hessian. These nice properties enable the implementation of highly effective machine learning techniques like sub-sampling and various heuristics in the method. Extensive numerical results illustrate that IA-NPE compares favorably with state-of-the-art second-order methods, including Newton's method with cubic regularization and Trust-Region methods.