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）生成近似最优解的序列，改进了有限和最小化问题的复杂度。

高效连续有限和最小化

Efficient Continual Finite-Sum Minimization

Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD)
without replacement, is a popular and theoretically grounded method for
finite-sum minimization. We propose two new algorithms: Proximal and Federated
Random Reshuffing (ProxRR and FedRR). The first algorithm, ProxRR, solves
composite convex finite-sum minimization problems in which the objective is the
sum of a (potentially non-smooth) convex regularizer and an average of $n$
smooth objectives. We obtain the second algorithm, FedRR, as a special case of
ProxRR applied to a reformulation of distributed problems with either
homogeneous or heterogeneous data. We study the algorithms' convergence
properties with constant and decreasing stepsizes, and show that they have
considerable advantages over Proximal and Local SGD. In particular, our methods
have superior complexities and ProxRR evaluates the proximal operator once per
epoch only. When the proximal operator is expensive to compute, this small
difference makes ProxRR up to $n$ times faster than algorithms that evaluate
the proximal operator in every iteration. We give examples of practical
optimization tasks where the proximal operator is difficult to compute and
ProxRR has a clear advantage. Finally, we corroborate our results with
experiments on real data sets.

本篇论文提出两种新的优化算法：ProxRR 和 FedRR，应用于分布式问题的改进。这些算法在收敛性和计算复杂度方面具有明显优势，并在重要的最优化任务中发挥出色。

近端和联邦随机重洗

Proximal and Federated Random Reshuffling

Decentralized solutions to finite-sum minimization are of significant
importance in many signal processing, control, and machine learning
applications. In such settings, the data is distributed over a network of
arbitrarily-connected nodes and raw data sharing is prohibitive often due to
communication or privacy constraints. In this article, we review decentralized
stochastic first-order optimization methods and illustrate some recent
improvements based on gradient tracking and variance reduction, focusing
particularly on smooth and strongly-convex objective functions. We provide
intuitive illustrations of the main technical ideas as well as applications of
the algorithms in the context of decentralized training of machine learning
models.

本文综述了基于梯度追踪和方差减少的去中心化随机一阶优化方法，介绍了这些算法在去中心化机器学习模型训练中的应用。

分散随机优化与梯度追踪简介

An introduction to decentralized stochastic optimization with gradient  tracking

We consider variants of trust-region and cubic regularization methods for
non-convex optimization, in which the Hessian matrix is approximated. Under
mild conditions on the inexact Hessian, and using approximate solution of the
corresponding sub-problems, we provide iteration complexity to achieve $
\epsilon $-approximate second-order optimality which have shown to be tight.
Our Hessian approximation conditions constitute a major relaxation over the
existing ones in the literature. Consequently, we are able to show that such
mild conditions allow for the construction of the approximate Hessian through
various random sampling methods. In this light, we consider the canonical
problem of finite-sum minimization, provide appropriate uniform and non-uniform
sub-sampling strategies to construct such Hessian approximations, and obtain
optimal iteration complexity for the corresponding sub-sampled trust-region and
cubic regularization methods.

本文研究了基于 Hessian 矩阵近似的非凸优化中信任域和立方正则化方法的变体。通过对不精确 Hessian 矩阵的渐进解和相应子问题的近似解，提供了迭代复杂度，以实现达到二阶最优条件的近似解，并且在现有文献中条件松弛。