OPTAMI: global superlinear convergence of high-order methods
Kamzolov, Dmitry Agafonov, Artem Pasechnyuk, Dmitry Gasnikov, Alexander Takac, Martin
Kamzolov, Dmitry
Agafonov, Artem
Pasechnyuk, Dmitry
Gasnikov, Alexander
Takac, Martin
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Second-order methods for convex optimization outperform first-order methods in terms of theoretical iteration convergence, achieving rates up to O(k−5) for highly-smooth functions. However, their practical performance and applications are limited due to their multi-level structure and implementation complexity. In this paper, we present new results on high-order optimization methods, supported by their practical performance. First, we show that the basic high-order methods, such as the Cubic Regularized Newton Method, exhibit global superlinear convergence for µ-strongly star-convex functions, a class that includes µ-strongly convex functions and some non-convex functions. Theoretical convergence results are both inspired and supported by the practical performance of these methods. Secondly, we propose a practical version of the Nesterov Accelerated Tensor method, called NATA. It significantly outperforms the classical variant and other high-order acceleration techniques in practice. The convergence of NATA is also supported by theoretical results. Finally, we introduce an open-source computational library for high-order methods, called OPTAMI. This library includes various methods, acceleration techniques, and subproblem solvers, all implemented as PyTorch optimizers, thereby facilitating the practical application of high-order methods to a wide range of optimization problems. We hope this library will simplify research and practical comparison of methods beyond first-order. © 2025 13th International Conference on Learning Representations, ICLR 2025. All rights reserved.
Citation
D. Kamzolov, A. Agafonov, D. Pasechnyuk, A. Gasnikov, and M. Takáč, “OPTAMI: Global Superlinear Convergence of High-order Methods,” International Conference on Representation Learning, vol. 2025, pp. 99926–99955, May 2025
Source
13th International Conference on Learning Representations, ICLR 2025
Conference
13th International Conference on Learning Representations, ICLR 2025
Keywords
Subjects
Source
13th International Conference on Learning Representations, ICLR 2025
Publisher
International Conference on Learning Representations, ICLR