  The analysis of second-order optimization methods based either on
sub-sampling, randomization or sketching has two serious shortcomings compared
to the conventional Newton method. The first shortcoming is that the analysis
of the iterates has only been shown to be scale-invariant only under specific
assumptions 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 propose a randomized
Newton method for self-concordant functions to address both shortfalls. We
propose a Self-concordant Iterative-minimization-Galerkin-based Multilevel
Algorithm (SIGMA) and establish its super-linear convergence rate using the
theory of self-concordant functions. 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 theanalysis to significantly improve the performance of
second-order methods in machine learning applications. We report encouraging
initial experiments that suggest SIGMA outperforms other state-of-the-art
sub-sampled/sketched Newton methods for both medium and large-scale problems.
