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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recent advances in randomized incremental methods for minimizing $L$-smooth$\mu$-strongly convex finite sums have culminated in tight complexity of$\tilde{O}((n+\sqrt{n L/\mu})\log(1/\epsilon))$ and $O(n+\sqrt{nL/\epsilon})$,where $\mu>0$ and $\mu=0$, respectively, and $n$ denotes the number ofindividual functions. Unlike incremental methods, stochastic methods for finitesums do not rely on an explicit knowledge of which individual function is beingaddressed at each iteration, and as such, must perform at least $\Omega(n^2)$iterations to obtain $O(1/n^2)$-optimal solutions. In this work, we exploit thefinite noise structure of finite sums to derive a matching $O(n^2)$-upper boundunder the global oracle model, showing that this lower bound is indeed tight.Following a similar approach, we propose a novel adaptation of SVRG which isboth \emph{compatible with stochastic oracles}, and achieves complexity boundsof $\tilde{O}((n^2+n\sqrt{L/\mu})\log(1/\epsilon))$ and$O(n\sqrt{L/\epsilon})$, for $\mu>0$ and $\mu=0$, respectively. Our bounds holdw.h.p. and match in part existing lower bounds of$\tilde{\Omega}(n^2+\sqrt{nL/\mu}\log(1/\epsilon))$ and$\tilde{\Omega}(n^2+\sqrt{nL/\epsilon})$, for $\mu>0$ and $\mu=0$,respectively.

On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions