A Multilevel Method for Self-Concordant Minimization

Abstract: The analysis of second-order optimization methods based either on sampling, randomization or sketching has two serious shortcomings compared to the conventional Newton method. The first shortcoming is that the analysis of the iterates is not scale-invariant, and even if it is, restrictive assumptions are required on the problem structure. The second shortfall is that the fast convergence rates of second-order methods have only been established by making assumptions regarding the input data. In this paper, we close the theoretical gap between the theoretical analysis of the conventional Newton method and randomization-based second-order methods. We propose a Self-concordant Iterative-minimization - Galerkin-based Multilevel Algorithm (SIGMA) and establish its super-linear convergence rate using the well-established theory of self-concordant functions. Our analysis is global and entirely independent of unknown constants such as Lipschitz constants and strong convexity parameters. Our analysis is based on the connections between multigrid optimization methods, and the role of coarse-grained or reduced-order models in the computation of search directions. We take advantage of the insights from the analysis to significantly improve the performance of second-order methods in machine learning applications. We report encouraging initial experiments that suggest SIGMA significantly outperforms the state-of-the-art sub-sampled/sketched Newton methods for both medium and large-scale problems.

This page was built for publication: A Multilevel Method for Self-Concordant Minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504556)