Given a sequence of functions $f_1,\ldots,f_n$ with $f_i:\mathcal{D}\mapsto
\mathbb{R}$, finite-sum minimization seeks a point ${x}^\star \in \mathcal{D}$
minimizing $\sum_{j=1}^n f_j(x)/n$. In this work, we propose a key twist into
the finite-sum minimization, dubbed as continual finite-sum minimization, that
asks for a sequence of points ${x}_1^\star,\ldots,{x}_n^\star \in \mathcal{D}$
such that each ${x}^\star_i \in \mathcal{D}$ minimizes the prefix-sum
$\sum_{j=1}^if_j(x)/i$. Assuming that each prefix-sum is strongly convex, we
develop a first-order continual stochastic variance reduction gradient method
($\mathrm{CSVRG}$) producing an $\epsilon$-optimal sequence with
$\mathcal{\tilde{O}}(n/\epsilon^{1/3} + 1/\sqrt{\epsilon})$ overall first-order
oracles (FO). An FO corresponds to the computation of a single gradient $\nabla
f_j(x)$ at a given $x \in \mathcal{D}$ for some $j \in [n]$. Our approach
significantly improves upon the $\mathcal{O}(n/\epsilon)$ FOs that
$\mathrm{StochasticGradientDescent}$ requires and the $\mathcal{O}(n^2 \log
(1/\epsilon))$ FOs that state-of-the-art variance reduction methods such as
$\mathrm{Katyusha}$ require. We also prove that there is no natural first-order
method with $\mathcal{O}\left(n/\epsilon^\alpha\right)$ gradient complexity for
$\alpha < 1/4$, establishing that the first-order complexity of our method is
nearly tight.

提出了一种称为连续有限和最小化的方法，通过使用第一阶段随机方差减少梯度法（CSVRG）生成近似最优解的序列，改进了有限和最小化问题的复杂度。