ترجمه فارسی مقاله پیچیدگی کمینه‌سازی توابع گرادیان تصویر شده با اوراکل‌های تصادفی مرتبه اول

چکیده

This work investigates the performance limits of projected stochastic first-order methods for minimizing functions under the $(α,τ,mathcal{X})$-projected-gradient-dominance property, that asserts the sub-optimality gap $F(mathbf{x})-min_{mathbf{x}’in mathcal{X}}F(mathbf{x}’)$ is upper-bounded by $τcdot|mathcal{G}_{η,mathcal{X}}(mathbf{x})|^α$ for some $αin[1,2)$ and $τ>0$ and $mathcal{G}_{η,mathcal{X}}(mathbf{x})$ is the projected-gradient mapping with $η>0$ as a parameter. For non-convex functions, we show that the complexity lower bound of querying a batch smooth first-order stochastic oracle to obtain an $ε$-global-optimum point is $Ω(ε^{-{2}/α})$. Furthermore, we show that a projected variance-reduced first-order algorithm can obtain the upper complexity bound of $mathcal{O}(ε^{-{2}/α})$, matching the lower bound. For convex functions, we establish a complexity lower bound of $Ω(log(1/ε)cdotε^{-{2}/α})$ for minimizing functions under a local version of gradient-dominance property, which also matches the upper complexity bound of accelerated stochastic subgradient methods.

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

این کار محدودیت های عملکرد روشهای مرتبه اول پیش بینی شده برای به حداقل رساندن توابع تحت $ (α ، τ ، Mathcal {x}) $-خاصیت پیش بینی شده-کلاس-تقاضا را بررسی می کند ، که ادعا می کند شکاف زیر حد مطلوب $ f (Mathbf {x})- min _ { mathbf {x} ‘ in mathcal {x}}} f ( mathbf {x}’) $ با $ τ τ cdot | mathcal {g} _} _} _. Mathcal {x}} ( mathbf {x}) $ نقشه برداری از کلاس پیش بینی شده با $ η> 0 $ به عنوان یک پارامتر است.برای توابع غیر کنفکس ، ما نشان می دهیم که پیچیدگی پایین تر از پرس و جو یک دسته از اوراکل تصادفی مرتبه اول صاف برای به دست آوردن یک نقطه ε $ -global-optimum $ $ (ε^{-{2}/α}) $ $ است.بشرعلاوه بر این ، ما نشان می دهیم که یک الگوریتم پیش بینی شده با واریانس مرتبه اول می تواند پیچیدگی بالایی از $ Mathcal {O} (ε^{-{2}/α}) $ را بدست آورد ، و مطابق با مرز پایین باشد.برای توابع محدب ، ما پیچیدگی پایین تر از $ ω ( log (1/ε) cdotε^{-{2}/α}) $ را برای به حداقل رساندن توابع تحت یک نسخه محلی از خاصیت دامنه شیب ایجاد می کنیم ، که مطابقت دارد.مرز پیچیدگی بالایی روشهای زیر بخش تصادفی شتاب.