方差降低梯度下降的有限和复合优化
通过提出一种随机复合梯度下降 (SCGD) 算法来解决最小化一个包含期望值或两个期望值函数组合的非线性函数的问题;该算法可以令 SCGD 收敛于凸优化问题的最优解,并且可以加速收敛于平稳点来解决非凸问题,进而解决学习、估计、动态规划等实践中常见的关于期望值函数组合的随机优化问题。
Nov, 2014
本文提出了一种基于随机复合梯度法和增量方差缩减估计器的方法来最小化非凸函数的期望值和有限和,尽管丧失了复合梯度估计器的无偏性,但该方法达到了最佳已知一阶方法的复杂度,扩大了增量方差缩减方法在机器学习中的应用范围。
Jun, 2019
本文提出了一种新的随机组合减少方差的梯度算法来解决现有算法在算法设计中忽略凸性结构而导致的样本复杂度和实践问题,实验结果表明了该算法的有效性和效率。
Jun, 2018
本文提出了针对复合目标强凸的情况下,带有方差约束的随机梯度下降法,其收敛速度优于传统的随机梯度下降法,同时常数因子也更小,只与输入数据的方差有关。
Oct, 2016
本文介绍了一种用于解决随机函数组合的凸优化问题的无偏梯度仿真算法,并将其与两个方差减少算法相结合,得出该算法基于无偏梯度仿真展现出令人满意的收敛性能,最后为两个随机函数组合优化问题应用了该算法:最大化 Cox 部分似然模型和训练条件随机场。
Nov, 2017
本文提出一种使用归一化近端梯度求解多层组合优化问题的方法,其中包含一系列随机平滑映射,在嵌套随机方差约减的帮助下获得近似梯度,其期望样本复杂度为 O(ϵ^-3),在有限求和的情况下为 O(N+√Nϵ^-2),其中 N 是所有组合级别上的函数总数。与以前的方法相比,我们的总样本复杂度在组合级别数量上的依赖性是多项式的,而不是指数的。
Aug, 2019
本文提出了一种渐进协同优化梯度算法的统一视角,通过推广 Nesterov 引入的估计序列概念,覆盖了随机梯度下降法,SAGA 和 SVRG 等方法,并提出了具有同样保证的新的算法,并推导了使这些算法抗击随机噪声的通用策略,最终证明了该视角有助于得到新的加速算法。
May, 2019
通过统计学习理论的算法稳定性角度,本文提供了随机组合梯度下降算法的稳定性和泛化分析,包括引入组合均匀稳定性的概念、建立其与复合优化问题泛化性能的定量关系、针对两种常用的随机组合梯度下降算法 SCGD 和 SCSC 建立组合均匀稳定性结果,并通过权衡稳定性结果和优化误差,导出了 SCGD 和 SCSC 的维度无关的超额风险界限。据我们所知,这是第一次关于随机组合梯度下降算法稳定性和泛化分析的结果。
Jul, 2023
该论文研究了一种用于解决机器学习中优化非凸或凸组合测度 / 目标的随机算法,并提供了适用于非凸和凸目标的收敛分析。其中用到的算法是基于移动平均估计器的,且还提供了可以提高实现精度的新方法。
Feb, 2022