ترجمه فارسی مقاله مرزهای پایینی محکم تحت نرمی نگهدارنده مرتبه بالا نامتقارن و تحدب یکنواخت

چکیده

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)$ with a truncated-Gaussian smoothed hard function in the first case and $Ω\left(\left(\frac{H}σ\right)^\frac{2}{3(p+ν)-2}+ \log^2\left(\frac{σ^{p+ν}}{H^q}\right)^\frac{1}{p+ν-q}\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 the general setting.

چکیده به فارسی (ترجمه ماشینی)

در این مقاله ، ما مرزهای کمتری را برای پیچیدگی اوراکل به حداقل رساندن عملکردهای صاف و یکنواخت محدب Hölder با مرتبه بالا فراهم می کنیم.به طور خاص ، برای تابعی که $ p^{th} $-مشتقات سفارش Hölder با درجه $ ν $ و پارامتر $ H $ ، و این یکنواخت محدب با درجه $ q $ و پارامتر $ σ $ است ، ما روی دو تمرکز می کنیمموارد نامتقارن: (1) $ q> p + ν $ ، و (2) $ q