Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity

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 $p^{th}$-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 $p^{th}$-order oracle access, we establish worst-case oracle complexities of $Ω\left( \left( \frac{H}σ\right)^\frac{2}{3(p+ν)-2}\left( \fracσε\right)^\frac{2(q-p-ν)}{q(3(p+ν)-2)}\right)$ in the first case with an $\ell_\infty$-ball-truncated-Gaussian smoothed hard function and $Ω\left(\left(\frac{H}σ\right)^\frac{2}{3(p+ν)-2}+ \log\log\left(\left(\frac{σ^{p+ν}}{H^q}\right)^\frac{1}{p+ν-q}\frac{1}ε\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.