613. Convergence Analysis of Modified Cubic-Regularized Newton Method
Invited abstract in session TB-13: Numerical Methods and Applications I, stream Numerical Methods and Applications.
Tuesday, 10:30-12:30Room: B100/6009
Authors (first author is the speaker)
| 1. | Vladislav Ryspayev
|
| Machine Learning, MBZUAI |
Abstract
This paper presents a convergence analysis of a modified cubic-regularized Newton method for unconstrained optimization problems, considering the minimization of a twice-differentiable function with Lipschitz continuous Hessian and bounded eigenvalues. Our modification replaces the exact Hessian with a block diagonal matrix structure that combines a scaled identity matrix in one block and the original Hessian in another, effectively integrating first-order and second-order information. We derive explicit formulas for the step direction and size, establish a sufficient decrease property, and provide detailed convergence rates in different gradient regimes: for small gradient norms, we prove O(N^(-1/2)) convergence, while for large gradient norms, we achieve the faster O(N^(-2/3)) rate, with an overall global convergence guarantee of O(N^(-1/2)) in the general mixed regime. The analysis reveals how the algorithm's behavior adapts to different problem characteristics, making the method particularly attractive for large-scale applications where full Hessian computations are expensive. Our experiments on matrix factorization problems demonstrate the method's practical efficiency in settings where partial second-order information can be advantageously combined with first-order approaches.
Keywords
- Complexity and efficiency of algorithms
- Computational mathematical optimization
- Second- and higher-order optimization
Status: accepted
Back to the list of papers