Improving Computational Complexity in Statistical Models with Second-Order Information
This work addresses computational efficiency for researchers and practitioners using statistical models with singularities, offering a method to reduce iteration counts in parameter estimation, though it is incremental as it builds on existing gradient descent variants.
The paper tackles the slow convergence of gradient descent in singular statistical models by proposing normalized gradient descent (NormGD), which uses second-order information to scale step sizes, achieving logarithmic iteration complexity and optimal overall computational complexity of O(n) to reach a final statistical radius, compared to polynomial complexity for fixed step-size gradient descent.
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^τ)$ for some $τ> 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.