随机鞍点问题的泛化界
研究用于找到凸凹函数鞍点的随机一阶方法的性能。我们提出了一种简单有效的正则化技术,稳定迭代并提供有意义的性能保证,即使域和梯度噪声与迭代的大小成线性关系(可能是无界的)。此外,我们还将算法应用于强化学习中的特定问题,在无偏扩展的平均奖励 MDP 中,即使没有先验知识,也能找到接近最优策略的性能保证。
Feb, 2024
本研究研究了非凸优化中的鞍点问题,提出了一个通用的框架,该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外,还将研究结果扩展到了随机情形下,以更好地适应实际问题。
Sep, 2018
本文研究计算马尔科夫决策过程中随机最短路径问题中,学习合理策略的采样复杂度,得到在有选项模型的情况下,学习合理策略的采样下界,并提出一种能够匹配界限的算法。同时,探讨在没有选项模型的情况下学习最佳策略识别问题中的高效学习可能性,并证明在一些假设下是实现可能的。
Oct, 2022
本文针对非凸非光滑问题提出新的算法稳定性度量方法,同时建立它们与梯度之间的量化关系,并使用采样确定算法导出了随机梯度下降算法和其自适应变种的误差界。
Jun, 2022
本论文研究了具有线性函数逼近的随机最短路径问题,提出了一种使用 Hoeffding 类型置信度集的新算法,能够实现次线性后悔保证。同时,对于在 $c_{min}=0$ 的情况,可以保证近似次立方的后悔保证。此外,通过设计改进的贝恩斯坦置信度集,改进的算法能够保证近乎最优的后悔保证。
Oct, 2021
本文从凸优化的角度研究了已知和未知环境中的随机最短路径问题,回顾了已知参数情况下的结果,并通过不同的证明发展了理解。其后专注于未知参数情况,在此基础上研究了扩展值迭代算子,包括现有算子和定义了其他算子。本文表明了 EVI 算子与凸规划的关系及其对偶形式,同时提出了一些进一步研究的问题。
Jul, 2022
本文探讨了深度学习模型的一种优化方法 —— 随机梯度下降在泛化能力上的稳定性,提出了一种基于梯度方差的稳定性指标,并在此基础上分别分析了常规非凸损失函数、梯度主导性损失函数和带强凸规则化器的问题,得到了一系列改进的泛化误差界。
Feb, 2018
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
本文提出了两个理论,分别使用稳定性和 PAC-Bayesian 结果的非渐进离散时间分析,研究了 Stochastic Gradient Langevin Dynamics(SGLD)在非凸目标下的泛化误差,其边界没有隐含依赖于参数的维数、规范或其他容量测量,优美地刻画了非凸设置中 “快速训练保证泛化” 的现象
Jul, 2017