TY - GEN
T1 - Accelerating Stochastic Newton Method via Chebyshev Polynomial Approximation
AU - Sha, Fan
AU - Pan, Jianyu
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - To solve large scale optimization problems arising from machine learning, stochastic Newton methods have been proposed for reducing the cost of computing Hessian and Hessian inverse, while still maintaining fast convergence. Recently, a second-order method named LiSSA [12] was proposed to approximate the Hessian inverse with Taylor expansion and achieves (almost) linear running time in optimization. The approach is very simple yet effective, but still could be further accelerated. In this paper, we resort to Chebyshev polynomial and its variants to approximate the Hessian inverse. Note that Chebyshev polynomial approximation is broadly acknowledged as the optimal polynomial approximation in the deterministic setting, in this paper we introduce it into the stochastic setting of Newton optimization. We provide a complete convergence analysis and the experiments on multiple benchmarks show that our proposed algorithms outperform LiSSA, which validates our theoretical insights.
AB - To solve large scale optimization problems arising from machine learning, stochastic Newton methods have been proposed for reducing the cost of computing Hessian and Hessian inverse, while still maintaining fast convergence. Recently, a second-order method named LiSSA [12] was proposed to approximate the Hessian inverse with Taylor expansion and achieves (almost) linear running time in optimization. The approach is very simple yet effective, but still could be further accelerated. In this paper, we resort to Chebyshev polynomial and its variants to approximate the Hessian inverse. Note that Chebyshev polynomial approximation is broadly acknowledged as the optimal polynomial approximation in the deterministic setting, in this paper we introduce it into the stochastic setting of Newton optimization. We provide a complete convergence analysis and the experiments on multiple benchmarks show that our proposed algorithms outperform LiSSA, which validates our theoretical insights.
KW - Chebyshev Polynomial
KW - Condition Number
KW - Hessian inverse
KW - Stochastic Newton Method
UR - https://www.scopus.com/pages/publications/85163381548
U2 - 10.1007/978-3-031-33377-4_40
DO - 10.1007/978-3-031-33377-4_40
M3 - 会议稿件
AN - SCOPUS:85163381548
SN - 9783031333767
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 523
EP - 534
BT - Advances in Knowledge Discovery and Data Mining - 27th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2023, Proceedings
A2 - Kashima, Hisashi
A2 - Ide, Tsuyoshi
A2 - Peng, Wen-Chih
PB - Springer Science and Business Media Deutschland GmbH
T2 - 27th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2023
Y2 - 25 May 2023 through 28 May 2023
ER -