This project develops and analyzes multilevel and regularized Newton-type methods for large-scale optimization problems, with a focus on fast convergence, scalability, and applications in machine learning and deep learning.
This project focuses on the theoretical analysis and practical development of second-order methods for large-scale optimization. The central aim is to design Newton-type algorithms that retain the fast convergence properties of classical second-order methods while reducing their computational cost through multilevel, subspace, randomized, and regularized techniques.
A major part of the project concerns multilevel methods for self-concordant and strongly self-concordant minimization. This includes the development of a multilevel Newton-type method that addresses important limitations in the theory of randomized Newton methods, including the lack of superlinear convergence with global convergence guarantees and the lack of scale-invariant analysis. This line of work also extends to non-convex optimization, showing improved practical behavior, including faster escape from saddle points and flat regions compared with standard first-order methods.
The project also studies regularized Newton-type methods for convex and non-convex problems. In this direction, the goal is to establish sharp global convergence rates and to understand how multilevel regularization can achieve state-of-the-art complexity guarantees while remaining suitable for large-scale problems. A related part of the work investigates the improved local behavior of Newton's method for strongly self-concordant functions, showing that stronger structural assumptions can lead to faster convergence and larger regions of local convergence.
The project further addresses the question of when an optimization algorithm should switch from a cheaper but slower method to a more expensive second-order method with fast local convergence. This leads to the development of adaptive multilevel Newton methods with provable quadratic local convergence. Overall, the project contributes to a broader research program on scalable second-order optimization, with potential applications in machine learning, deep learning, and scientific computing.
Journal Articles
- A multilevel method for self-concordant minimization, N. Tsipinakis and P. Parpas, J. Optim. Theory Appl., 203(3):2509–2559, 2024, https://doi.org/10.1007/s10957-024-02509-z
- Multilevel regularized Newton methods with fast convergence rates, N. Tsipinakis and P. Parpas, SIAM J. Sci. Comput., pp. S232–S257, 2025, https://doi.org/10.1137/24M1677307
- A multilevel low-rank Newton method with super-linear convergence rate and its application to non-convex problems, N. Tsipinakis, P. Tigkas, and P. Parpas, Trans. Mach. Learn. Res., 2026, https://openreview.net/forum?id=PKakPzVVja
Preprints / Submitted Papers
- Simba: A scalable bilevel preconditioned gradient method for fast evasion of flat areas and saddle points, N. Tsipinakis and P. Parpas, arXiv preprint arXiv:2309.05309, Sep. 2023, Submitted for publication, https://doi.org/10.48550/arXiv.2309.05309
- Convergence rates of Newton's method for strongly self-concordant minimization, N. Tsipinakis and P. Parpas, arXiv preprint arXiv:2507.23558, Jul. 2025, Submitted for publication, https://doi.org/10.48550/arXiv.2507.23558
- Adaptive Multilevel Newton: A quadratically convergent optimization method, N. Tsipinakis, P. Parpas, and M. Voigt, arXiv preprint arXiv:2510.24967, Oct. 2025, Submitted for publication, https://doi.org/10.48550/arXiv.2510.24967
