非凸有限和问题中随机递归梯度的概率性保证
内容提要
本文综述随机递归梯度算法SARAH及其mini-batch、SARAH+、ZeroSARAH等改进版本，用于非凸经验损失最小化。这些方法在一般非凸和梯度主导函数下分别实现子线性与线性收敛，并扩展至分布式学习、复合优化和策略梯度，具有更优复杂度与实用性。
延伸解读
SARAH系列算法的演进脉络
文章梳理了SARAH算法从2017年提出到后续多个改进版本的发展历程。SARAH最初针对有限和问题，在强凸情况下具有线性收敛率；随后出现的mini-batch版本、SARAH+、ZeroSARAH等，分别针对非凸损失最小化、分布式学习和无需全梯度计算等场景进行了优化。这些改进在保持理论保证的同时，提升了算法的实用性和适用范围。
收敛性保证的差异与适用条件
文章指出，SARAH的mini-batch版本在一般非凸函数下可实现子线性收敛，而在梯度主导函数下则能达到线性收敛。这种差异意味着算法性能高度依赖于目标函数的性质。对于满足梯度主导条件的非凸问题，算法能获得更快的收敛速度；而对于一般非凸问题，收敛速度相对较慢，但仍有理论保证。
分布式与复合优化的扩展
SARAH的改进版本已扩展到分布式学习和复合优化领域。例如，ZeroSARAH在分布式学习中处理大量非凸函数的平均值时，无需计算全梯度即可实现最优复杂度；混合随机策略梯度算法（ProxHSPGA）则用于解决带约束或正则化的复合策略优化问题。这些扩展表明SARAH框架具有较好的通用性和灵活性。
实际应用中的权衡与验证
文章提到，部分改进算法（如SARAH++）已在多个数据集上进行数值实验，验证了其实际性能。同时，混合方差缩减近端梯度法通过减少每次迭代的随机梯度评估次数，在达到最优复杂度的同时降低了计算开销。这些实践表明，SARAH系列算法在理论优势之外，也注重实际可行性，但具体效果可能因问题规模和数据结构而异。
Q&A
SARAH算法主要用来解决什么问题？
SARAH算法用于解决非凸损失函数的经验损失最小化问题，即有限和优化问题。
SARAH算法在非凸和梯度主导函数下的收敛速度如何？
对于一般非凸函数，SARAH的mini-batch版本具有子线性收敛率；对于梯度主导函数，具有线性收敛率。
ZeroSARAH有什么特点？
ZeroSARAH是一种新的方差减少方法，用于分布式学习中处理大量非凸函数的平均值，可以在不需要计算全梯度的情况下实现，并在标准和分布式设置下取得新的最优结果。
SARAH+算法在什么情况下具有线性收敛速率？
SARAH+算法在强凸情况下具有线性收敛速率。
混合随机策略梯度算法ProxHSPGA用于解决什么问题？
ProxHSPGA用于解决复合策略优化问题，可以处理策略参数上的约束或规则化，并已在强化学习中的一些示例上进行了评估和验证。
随机平均梯度方法相比黑匣子随机梯度方法有什么优势？
随机平均梯度方法克服了黑匣子随机梯度方法的缺点，具有更快的收敛速度和更少的梯度评估数量，在许多情况下优于现有的随机梯度方法和确定性梯度方法，并且可以通过非均匀采样策略进一步提高表现。
