论文标题
关于最小化凸有限总和的复杂性，而无需使用单个函数的索引
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions
论文作者
论文摘要
最小化$ l $ -smooth $ $ $ $ $ $ $ -Sronglongly凸的最小化方法的最新进展已达到$ \ tilde {o}（（（n+\ sqrt {n+\ sqrt {n l/μ}）） $μ> 0 $和$μ= 0 $，$ n $表示单个功能的数量。与增量方法不同，有限总和的随机方法不依赖于每次迭代中正在解决哪些单个函数的明确知识，因此必须至少执行$ω（n^2）$迭代以获得$ O（1/n^2）$ - 最佳解决方案。在这项工作中，我们利用有限总和的有限噪声结构来得出匹配的$ O（n^2）$ - 在全球甲骨文模型下的上限，表明该下限确实很紧。遵循类似的方法，我们提出了一种新颖的SVRG适应，它既与随机的oracles}兼容，并达到$ \ tilde {o}的复杂性界限（（（（n^2+n \ n \ sqrt {l/μ}） $μ> 0 $和$μ= 0 $。我们的界限保持W.H.P.并部分匹配$ \tildeΩ（n^2+\ sqrt {nl/μ} \ log（1/ε）））$和$ \tildeΩ（n^2+\ sqrt {nl/ε}）$的部分现有下限。
Recent advances in randomized incremental methods for minimizing $L$-smooth $μ$-strongly convex finite sums have culminated in tight complexity of $\tilde{O}((n+\sqrt{n L/μ})\log(1/ε))$ and $O(n+\sqrt{nL/ε})$, where $μ>0$ and $μ=0$, respectively, and $n$ denotes the number of individual functions. Unlike incremental methods, stochastic methods for finite sums do not rely on an explicit knowledge of which individual function is being addressed at each iteration, and as such, must perform at least $Ω(n^2)$ iterations to obtain $O(1/n^2)$-optimal solutions. In this work, we exploit the finite noise structure of finite sums to derive a matching $O(n^2)$-upper bound under the global oracle model, showing that this lower bound is indeed tight. Following a similar approach, we propose a novel adaptation of SVRG which is both \emph{compatible with stochastic oracles}, and achieves complexity bounds of $\tilde{O}((n^2+n\sqrt{L/μ})\log(1/ε))$ and $O(n\sqrt{L/ε})$, for $μ>0$ and $μ=0$, respectively. Our bounds hold w.h.p. and match in part existing lower bounds of $\tildeΩ(n^2+\sqrt{nL/μ}\log(1/ε))$ and $\tildeΩ(n^2+\sqrt{nL/ε})$, for $μ>0$ and $μ=0$, respectively.
