A New Complexity Result for Strongly Convex Optimization with Locally $\alpha$-H{ö}lder Continuous Gradients

Abstract

In this paper, we present a new complexity result for the gradient descent method with an appropriately fixed stepsize for minimizing a strongly convex function with locally $\alpha$-H{ö}lder continuous gradients ($0<\alpha \le 1$). The complexity bound for finding an approximate minimizer with a distance to the true minimizer less than $\epsilon$ is $O(\log ({\epsilon }^{-1}){\epsilon }^{2\alpha -2})$, which extends the well-known complexity result for $\alpha =1$.