Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent
This work addresses computational efficiency in optimization for statistical learning, providing theoretical guarantees for faster convergence in non-convex settings, though it is incremental as it builds on existing Polyak step size theory.
The paper analyzes the Polyak step size gradient descent algorithm under generalized smoothness and Lojasiewicz conditions, showing it achieves a final statistical radius of convergence around the true parameter with a logarithmic number of iterations in sample size, which is computationally cheaper than fixed-step size methods when the population loss is not locally strongly convex.
We study the statistical and computational complexities of the Polyak step size gradient descent algorithm under generalized smoothness and Lojasiewicz conditions of the population loss function, namely, the limit of the empirical loss function when the sample size goes to infinity, and the stability between the gradients of the empirical and population loss functions, namely, the polynomial growth on the concentration bound between the gradients of sample and population loss functions. We demonstrate that the Polyak step size gradient descent iterates reach a final statistical radius of convergence around the true parameter after logarithmic number of iterations in terms of the sample size. It is computationally cheaper than the polynomial number of iterations on the sample size of the fixed-step size gradient descent algorithm to reach the same final statistical radius when the population loss function is not locally strongly convex. Finally, we illustrate our general theory under three statistical examples: generalized linear model, mixture model, and mixed linear regression model.