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 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 for the functional residual, where k is the iteration counter and 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. 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.