In this note we propose a new variant of the hybrid variance-reduced proximal
gradient method in [7] to solve a common stochastic composite nonconvex
optimization problem under standard assumptions. We simply replace the
independent unbiased estimator in our hybrid- SARAH estimator introduced in [7]
by the stochastic gradient evaluated at the same sample, leading to the
identical momentum-SARAH estimator introduced in [2]. This allows us to save
one stochastic gradient per iteration compared to [7], and only requires two
samples per iteration. Our algorithm is very simple and achieves optimal
stochastic oracle complexity bound in terms of stochastic gradient evaluations
(up to a constant factor). Our analysis is essentially inspired by [7], but we
do not use two different step-sizes.

提出了一种新的混合方差缩减近端梯度法，它使用随机梯度评估来代替早期方法中的 $SARAH$，从而实现每次迭代少使用一个随机梯度，在达到了随机梯度评估的最优随机预测复杂度界限的同时很简单。

一种最优混合方差减小算法用于随机复合非凸优化

An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite  Nonconvex Optimization

In this paper, we introduce a simplified and unified method for finite-sum
convex optimization, named \emph{Variance Reduction via Accelerated Dual
Averaging (VRADA)}. In both general convex and strongly convex settings, VRADA
can attain an $O\big(\frac{1}{n}\big)$-accurate solution in $O(n\log\log n)$
number of stochastic gradient evaluations which improves the best-known result
$O(n\log n)$, where $n$ is the number of samples. Meanwhile, VRADA matches the
lower bound of the general convex setting up to a $\log\log n$ factor and
matches the lower bounds in both regimes $n\le \Theta(\kappa)$ and $n\gg
\kappa$ of the strongly convex setting, where $\kappa$ denotes the condition
number. Besides improving the best-known results and matching all the above
lower bounds simultaneously, VRADA has more unified and simplified algorithmic
implementation and convergence analysis for both the general convex and
strongly convex settings. The underlying novel approaches such as the novel
initialization strategy in VRADA may be of independent interest. Through
experiments on real datasets, we show the good performance of VRADA over
existing methods for large-scale machine learning problems.

本文介绍了一种名为 VRADA 的简化和统一的有限和凸优化方法，其中改进了现有方法，匹配了一些更强的下界，并在实际数据集上证明了其具有良好的性能。