English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the complexity of optimizing highly smooth convex functions. For apositive integer $p$, we want to find an $\epsilon$-approximate minimum of aconvex function $f$, given oracle access to the function and its first $p$derivatives, assuming that the $p$th derivative of $f$ is Lipschitz.  Recently, three independent research groups (Jiang et al., PLMR 2019;Gasnikov et al., PLMR 2019; Bubeck et al., PLMR 2019) developed a new algorithmthat solves this problem with $\tilde{O}(1/\epsilon^{\frac{2}{3p+1}})$ oraclecalls for constant $p$. This is known to be optimal (up to log factors) fordeterministic algorithms, but known lower bounds for randomized algorithms donot match this bound. We prove a new lower bound that matches this bound (up tolog factors), and holds not only for randomized algorithms, but also forquantum algorithms.

Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness