Fast finite-sum optimization via cyclically-sampled Hessian averaging methods

• 成果类型: Article; Early Access
• 署名作者: O'Leary-Roseberry, Thomas; Bollapragada, Raghu
• 署名单位: University System of Ohio; Ohio State University; University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02354-0
• 发表日期: 2026-04-07
• 关键词: Adaptive Sampling; Hessian averaging; subsampled Newton; superlinear convergence; cyclic sampling; TRUST-REGION ALGORITHMS; newton; CONVERGENCE

摘要

We consider minimizing finite-sum objective functions via Hessian-averaging based subsampled Newton methods. These methods allow for gradient inexactness and have fixed per-iteration Hessian approximation costs. The recent work (Na et al. 2023) demonstrated that Hessian averaging can be utilized to achieve fast Ologkk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}\left( \sqrt{ frac{\log k}{k}} ight) $$\end{document} local superlinear convergence for strongly convex functions in high probability, while maintaining fixed per-iteration Hessian costs. These methods, however, require gradient exactness and strong convexity, which poses challenges for their practical implementation. To address this concern we consider Hessian-averaged methods that allow gradient inexactness via norm condition based adaptive-sampling strategies. Furthermore, to better control the error in the subsampled Hessian approximations, we utilize Hessian averaging with deterministic cyclic sampling techniques instead of random sampling, which leads to fast local superlinear convergence. We develop a comprehensive convergence theory, including global linear and sublinear convergence rates for strongly convex and nonconvex functions, respectively. Additionally, we establish an improved local superlinear convergence rate of O1k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}\left( frac{1}{k} ight) $$\end{document}. Our analysis introduces novel techniques that differ from previous probabilistic approaches. We investigate the performance of these methods on logistic regression problems, demonstrating significant improvements in convergence over similar Hessian-averaging methods that utilize stochastic sampling.