2018/11/14 by Stefania Bellavia, Bellavia, Stefania, Nataša Krejić +3 · 3 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1811.05730
openalex publication_date 2018/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper deals with the minimization of large sum of convex functions by\nInexact Newton (IN) methods employing subsampled functions, gradients and\nHessian approximations. The Conjugate Gradient method is used to compute the\ninexact Newton step and global convergence is enforced by a nonmonotone line\nsearch procedure. The aim is to obtain methods with affordable costs and fast\nconvergence. Assuming strongly convex functions, R-linear convergence and\nworst-case iteration complexity of the procedure are investigated when\nfunctions and gradients are approximated with increasing accuracy. A set of\nrules for the forcing parameters and subsample Hessian sizes are derived that\nensure local q-linear/superlinear convergence of the proposed method.\n The random choice of the Hessian subsample is also considered and convergence\nin the mean square, both for finite and infinite sums of functions, is proved.\nFinally, global convergence with asymptotic R-linear rate of IN methods is\nextended to the case of sum of convex function and strongly convex objective\nfunction. Numerical results on well known binary classification problems are\nalso given. Adaptive strategies for selecting forcing terms and Hessian\nsubsample size, streaming out of the theoretical analysis, are employed and the\nnumerical results showed that they yield effective IN methods.\n