Total: 1
In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order Hölder smooth and uniformly convex functions. Specifically, for a function whose pth-order derivatives are Hölder continuous with degree ν and parameter H, and that is uniformly convex with degree q and parameter σ, we focus on two asymmetric cases: (1) q>p+ν, and (2) q<p+ν. Given up to pth-order oracle access, we establish worst-case oracle complexities of Ω((Hσ)23(p+ν)−2(σϵ)2(q−p−ν)q(3(p+ν)−2)) with a truncated-Gaussian smoothed hard function in the first case and Ω((Hσ)23(p+ν)−2+log2(σp+νHq)1p+ν−q) 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 the general setting.