Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexity

In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order H"older smooth and uniformly convex functions. Specifically, for a function whose pth-order derivatives are H"older continuous with degree nu and parameter H, and that is uniformly convex with degree q and parameter σ, we focus on two asymmetric cases: (1) q > p + nu, and (2) q < p+nu. Given up to pth-order oracle access, we establish worst-case oracle complexities of Omegaleft( left( fracHσright)^frac23(p+nu)-2left( fracσεright)^frac2(q-p-nu)q(3(p+nu)-2)right) in the first case with an ℓ_∞-ball-truncated-Gaussian smoothed hard function and Omegaleft(left(fracHσright)^frac23(p+nu)-2+ loglogleft(left(fracσp+nuHqright)^frac1p+nu-qfrac1εright)right) in the second case, for reaching an ε-approximate solution in terms of the optimality gap. Our analysis generalizes previous lower bounds for functions under first- and second-order smoothness as well as those for uniformly convex functions, and furthermore our results match the corresponding upper bounds in this general setting.