  We derive lower bounds on the black-box oracle complexity of large-scale
smooth convex minimization problems, with emphasis on minimizing smooth (with
Holder continuous, with a given exponent and constant, gradient) convex
functions over high-dimensional ||.||_p-balls, 1<=p<=\infty. Our bounds turn
out to be tight (up to logarithmic in the design dimension factors), and can be
viewed as a substantial extension of the existing lower complexity bounds for
large-scale convex minimization covering the nonsmooth case and the 'Euclidean'
smooth case (minimization of convex functions with Lipschitz continuous
gradients over Euclidean balls). As a byproduct of our results, we demonstrate
that the classical Conditional Gradient algorithm is near-optimal, in the sense
of Information-Based Complexity Theory, when minimizing smooth convex functions
over high-dimensional ||.||_\infty-balls and their matrix analogies -- spectral
norm balls in the spaces of square matrices.
