The stochastic proximal gradient method is a powerful generalization of the
widely used stochastic gradient descent (SGD) method and has found numerous
applications in Machine Learning. However, it is notoriously known that this
method fails to converge in non-convex settings where the stochastic noise is
significant (i.e. when only small or bounded batch sizes are used). In this
paper, we focus on the stochastic proximal gradient method with Polyak
momentum. We prove this method attains an optimal convergence rate for
non-convex composite optimization problems, regardless of batch size.
Additionally, we rigorously analyze the variance reduction effect of the Polyak
momentum in the composite optimization setting and we show the method also
converges when the proximal step can only be solved inexactly. Finally, we
provide numerical experiments to validate our theoretical results.

该论文研究了在采用小型或有界批量大小时，在非凸设置中具有重要意义的随机近端梯度法，证明了该方法在非凸复合优化问题中达到最优的收敛速度，并且严格分析了 Polyak 动量在复合优化设置中的方差缩减效应，同时证明了在近似解决近端步骤的情况下，该方法仍然收敛，并通过数值实验验证了我们的理论结果。

使用 Polyak 动量的非凸随机复合优化

Non-Convex Stochastic Composite Optimization with Polyak Momentum

We consider a regularized expected reward optimization problem in the
non-oblivious setting that covers many existing problems in reinforcement
learning (RL). In order to solve such an optimization problem, we apply and
analyze the classical stochastic proximal gradient method. In particular, the
method has shown to admit an $O(\epsilon^{-4})$ sample complexity to an
$\epsilon$-stationary point, under standard conditions. Since the variance of
the classical stochastic gradient estimator is typically large which slows down
the convergence, we also apply an efficient stochastic variance-reduce proximal
gradient method with an importance sampling based ProbAbilistic Gradient
Estimator (PAGE). To the best of our knowledge, the application of this method
represents a novel approach in addressing the general regularized reward
optimization problem. Our analysis shows that the sample complexity can be
improved from $O(\epsilon^{-4})$ to $O(\epsilon^{-3})$ under additional
conditions. Our results on the stochastic (variance-reduced) proximal gradient
method match the sample complexity of their most competitive counterparts under
similar settings in the RL literature.

基于正则化预期奖励优化问题，我们应用分析了经典的随机近端梯度方法，在标准条件下表明该方法在收敛到 ε- 稳定点的样本复杂度为 O (ε^{-4})。考虑到经典随机梯度估计器的方差通常较大，导致收敛速度变慢，我们还应用了一种高效的随机方差缩减近端梯度方法与基于重要性采样的概率梯度估计器 (PAGE)。我们的分析结果表明，在附加条件下，样本复杂度可以从 O (ε^{-4}) 提高到 O (ε^{-3})。在强化学习文献中的类似设置下，我们的结果与竞争对手的随机 (方差减小) 近端梯度方法的样本复杂度相匹配。

关于随机（方差减少）近端梯度法在正则化期望回报优化中的应用

On the Stochastic (Variance-Reduced) Proximal Gradient Method for  Regularized Expected Reward Optimization

Majorization-minimization algorithms consist of iteratively minimizing a
majorizing surrogate of an objective function. Because of its simplicity and
its wide applicability, this principle has been very popular in statistics and
in signal processing. In this paper, we intend to make this principle scalable.
We introduce a stochastic majorization-minimization scheme which is able to
deal with large-scale or possibly infinite data sets. When applied to convex
optimization problems under suitable assumptions, we show that it achieves an
expected convergence rate of $O(1/\sqrt{n})$ after $n$ iterations, and of
$O(1/n)$ for strongly convex functions. Equally important, our scheme almost
surely converges to stationary points for a large class of non-convex problems.
We develop several efficient algorithms based on our framework. First, we
propose a new stochastic proximal gradient method, which experimentally matches
state-of-the-art solvers for large-scale $\ell_1$-logistic regression. Second,
we develop an online DC programming algorithm for non-convex sparse estimation.
Finally, we demonstrate the effectiveness of our approach for solving
large-scale structured matrix factorization problems.

本文提出了一种可扩展的随机主化最小化方案，能够应对大规模或可能无限的数据集，解决凸优化问题，并开发了几种基于此框架的有效算法，包括一个新的随机近端梯度方法，用于大规模 l1 逻辑回归的非凸稀疏估计的在线 DC 编程算法和解决大规模结构矩阵分解问题的有效性。