  We construct a family of functions suitable for establishing lower bounds on
the oracle complexity of first-order minimization of smooth strongly-convex
functions. Based on this construction, we derive new lower bounds on the
complexity of strongly-convex minimization under various inaccuracy criteria.
The new bounds match the known upper bounds up to a constant factor, and when
the inaccuracy of a solution is measured by its distance to the solution set,
the new lower bound exactly matches the upper bound obtained by the recent
Information-Theoretic Exact Method, thereby establishing the exact oracle
complexity for this class of problems.
