高效逃离非凸政策优化中的鞍点

Nov, 2023

Efficiently Escaping Saddle Points for Non-Convex Policy Optimization

Sadegh Khorasani, Saber Salehkaleybar, Negar Kiyavash, Niao He, Matthias Grossglauser

TL;DR我们提出了一种使用 Hessian 矩阵 - 向量积的方差约简二阶方法，其样本复杂度为～O (ε^(-3))，并收敛于近似二阶稳定点 (SOSP)。该方法通过使用 HVP 项在不使用 IS 权重的情况下改善了达到近似 SOSPs 的最佳已知样本复杂度的速率，实验结果表明该算法优于现有技术，并对随机种子变化更稳健。

Abstract

policy gradient (PG) is widely used in reinforcement learning due to its scalability and good performance. In recent years, several variance-reduced PG methods have been proposed with a theoretical guarantee of converging to an →

policy gradient variance-reduced pg methods approximate first-order stationary point variance reduction technique hessian vector products

发现论文，激发创造

策略梯度寻找二阶稳定点的样本复杂度

本研究提出一种基于强化学习的优化方法，并使用二阶导数的技术证明了其收敛到二阶稳定点，从而避免了算法陷入鞍点或局部最小值。

Dec, 2020

约束优化中逃离鞍点

本研究研究了非凸优化中的鞍点问题，提出了一个通用的框架，该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外，还将研究结果扩展到了随机情形下，以更好地适应实际问题。

Sep, 2018

随机方差减小策略梯度的收敛性改进分析

研究改进了 SVRPG 方法的收敛性和采样复杂度问题，并通过理论分析和实验验证了重要性采样权重和批量大小参数的影响

May, 2019

稳定 SVRG: 非凸优化的简单方差缩减

该研究使用改进的 SVRG 算法创新性地找到一个非凸函数的二阶稳定点，并提出了使用稳定性 SVRG 算法的方法。

May, 2019

具有递归方差降低的高效策略梯度方法

该研究旨在提高强化学习中采样效率，通过提出一种名为 SRVR-PG 的新型策略梯度算法，并对其进行了数值实验以验证其性能。

Sep, 2019

非凸随机梯度下降逃离鞍点的尖锐分析

本文将通过对随机梯度下降进行深入分析，证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时，SGD 能够在 O（ε^ -3.5）次随机梯度计算中逃离鞍点并找到（ε，O（ε^ 0.5））- 近似二阶稳定点，从而推翻了 SGD 至少需要 O（ε^ - 4）的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配，如 Nesterov 的动量加速，负曲率搜索，以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解，并可潜在地推广到广泛的随机优化算法类。

Feb, 2019

普通策略梯度的一般样本复杂性分析

本文使用最近为非凸优化分析 SGD 开发的工具，获得了 vanilla policy gradient（PG）的收敛性和样本复杂性保证。

Jul, 2021

如何高效地逃离鞍点

本文研究表明惯性梯度下降法可以在较短的迭代次数内收敛于二阶稳定点，收敛速率与梯度下降到一阶稳定点的收敛速率匹配，当所有鞍点都是非退化的时，所有的二阶稳定点都是局部最小值，该结果表明惯性梯度下降法几乎可以在无成本的情况下脱离鞍点，并可直接应用于许多机器学习应用中，包括深度学习。

Mar, 2017

鞍点问题的随机方差缩减方法

提出了一种新的随机优化算法，可以高效地解决凸 - 凹二次问题，并适用于更广泛类别的问题，该算法以局部更新的形式实现，可以使用非均匀采样来加速算法。

May, 2016

策略梯度方差减少方法的收敛和样本效率

本研究提出一种简单且有效的梯度截断机制，可用于加速政策梯度算法的变化减少技术，进而设计了一种名为 TSIVR-PG 的新方法，它不仅能够最大化累积奖励总和，还能在政策的长期访问分布上最大化一般效用函数，并对 TSIVR-PG 进行了理论分析。

Feb, 2021