Lower complexity bounds for minimizing regularized functions

In this paper, we establish lower bounds for the oracle complexity of the first-order methods minimizing regularized convex functions. We consider the composite representation of the objective. The smooth part has Hölder continuous gradient of degree $$\nu \in [0, 1]$$ and is accessible by a black-box local oracle. The composite part is a power of a norm. We prove that the best possible rate for the first-order methods in the large-scale setting for Euclidean norms is of the order $$O(k^{- p(1 + 3\nu ) / (2(p - 1 - \nu ))})$$ for the functional residual, where k is the iteration counter and $$p > 2$$ is the power of regularization. Our formulation covers several cases, including computation of the Cubically regularized Newton step by the first-order gradient methods, in which case the rate becomes $$O(k^{-6})$$ . It can be achieved by the fast gradient method. Thus, our result proves the latter rate to be optimal. We also discover lower complexity bounds for non-Euclidean norms.