Summary: We derive lower bounds on the black-box oracle complexity of large-scale smooth convex minimization problems, with emphasis on minimizing smooth (with Hölder continuous, with a given exponent and constant, gradient) convex functions over high-dimensional \(\| \cdot \|_p\)-balls, \(1 \leq p \leq \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 \(\| \cdot \|_\infty\)-balls and their matrix analogies-spectral norm balls in the spaces of square matrices.