Improving Computational Complexity in Statistical Models with
  Second-Order Information
  It is known that when the statistical models are singular, i.e., the Fisher
information matrix at the true parameter is degenerate, the fixed step-size
gradient descent algorithm takes polynomial number of steps in terms of the
sample size $n$ to converge to a final statistical radius around the true
parameter, which can be unsatisfactory for the application. To further improve
that computational complexity, we consider the utilization of the second-order
information in the design of optimization algorithms. Specifically, we study
the normalized gradient descent (NormGD) algorithm for solving parameter
estimation in parametric statistical models, which is a variant of gradient
descent algorithm whose step size is scaled by the maximum eigenvalue of the
Hessian matrix of the empirical loss function of statistical models. When the
population loss function, i.e., the limit of the empirical loss function when
$n$ goes to infinity, is homogeneous in all directions, we demonstrate that the
NormGD iterates reach a final statistical radius around the true parameter
after a logarithmic number of iterations in terms of $n$. Therefore, for fixed
dimension $d$, the NormGD algorithm achieves the optimal overall computational
complexity $\mathcal{O}(n)$ to reach the final statistical radius. This
computational complexity is cheaper than that of the fixed step-size gradient
descent algorithm, which is of the order $\mathcal{O}(n^{\tau})$ for some $\tau
> 1$, to reach the same statistical radius. We illustrate our general theory
under two statistical models: generalized linear models and mixture models, and
experimental results support our prediction with general theory.
