广义数据上,具有二次限制的随机线性优化从不过拟合
考虑由 Markovian 噪声驱动的线性随机逼近算法的动态特性,通过考虑适当选择的 Lyapunov 函数的漂移,获得常数步长算法的有限时间误差的二次矩的有限时间界限。我们还对逼近误差 2 范数的平方的矩进行了全面的处理。
Feb, 2019
本文研究了凸函数和 Lipschitz 目标的随机镜像下降法的优化误差,提供了新的尾部界限,并将其扩展到更重尾噪声的情况。研究了最后一次迭代和迭代平均值的优化误差,并在指数尾和多项式尾两种重要情况下实例化了结果。我们的结果的一个显著特点是不需要对定义域的直径设置上界。最后,我们通过示例实验证明在重尾噪声情况下迭代平均值与最后一次迭代的行为的比较。
Dec, 2023
本研究研究了随机梯度下降(SGD)这种普遍使用的随机优化方法的泛化特性,提供了依赖于在 SGD 计算的迭代路径上评估的随机梯度的本地统计信息的泛化误差的理论上限,其关键因素是梯度的方差及目标函数沿 SGD 路径的局部光滑性以及损失函数对最终输出的扰动敏感度和信息理论泛化界限等。
Feb, 2021
本研究主要探讨过参数模型中采用 stochastic mirror descent 方法,在足够小的步长下,通过初始化接近全局最小值,其可以收敛和迭代到一种接近 Bregman 散度且具有更好泛化性能的解决方案,并探究该方法中不同的隐式正则化方式对结果表现的影响。
Jun, 2019
研究了最小二乘线性回归的问题,其中数据点依赖于并从马尔可夫链中采样。在不同的噪声设置下,建立了关于底层马尔可夫链混合时间 $\tau_{mix}$ 的尖锐信息理论极小值下界来解决此问题。我们发现,与独立数据的优化相比,具有马尔可夫数据的优化通常更加困难,一个只在大约 $ ilde {\Theta}(\tau_{mix})$ 个样本中工作的平凡算法 (SGD-DD) 是极小化最优的。此外,我们还研究了实践中出现的结构化数据集,例如高斯自回归动态,它们能否拥有更高效的优化方案。令人惊讶的是,即使在这个特定的自然环境下,具有一定步长的随机梯度下降法与常数并没有比 SGD-DD 算法更好。相反,我们提出了一种基于体验复盘的算法 —— 一种流行的强化学习技术 —— 它可以实现更好的误差率。我们的改进速率是第一个在有趣的马尔可夫链上优于 SGD-DD 的算法之一,也为在实践中支持使用经验回放提供了首个理论分析。
Jun, 2020
本文提供基于生成函数的优化算法收敛性分析技巧,研究了梯度下降以及随机梯度下降在二次函数上的有限时间收敛性,证明了在有随机噪声的情况下,延迟对算法的影响可以被忽略,且在分布式优化问题上,加入延迟不会影响性能,且可和同步方法相媲美。
Jun, 2018
该论文讨论在数据过度参数化时,第一阶段优化方案(如随机梯度下降)的性质。作者发现,当损失函数在初始点的最小邻域内具有某些属性时,迭代会以几何速率收敛于全局最优解,会以接近直接的路线从初始点到达全局最优解,其中,通过引入一个新的潜力函数来作为证明技术的一部分。对于随机梯度下降(SGD),作者开发了新的鞅技巧,以保证 SGD 绝不会离开初始化的小邻域。
Dec, 2018
该论文研究了随机镜像下降法在非凸优化中的非渐近稳态收敛性,特别关注了一类非凸非光滑的随机优化问题,其中目标函数可以分解为一个相对弱凸函数(可能是非 Lipschitz)和简单的非光滑凸规则化函数。论文证明,SMD 算法在收敛速率为 $O(1/√t)$ 的同时,无需使用小批量就能保证收敛到一个稳定点。
Jun, 2018
本文研究了一类具有一致性属性的非单调问题中,优化镜像下降法(OMD)的收敛性和优化方式。分析表明,OMD 可以解决这些问题并推广了先前的结果,为建立凸凹博弈以外的收敛性提供了具体进展。在一系列 GAN 模型上的数值实验结果验证了分析的可行性。
Jul, 2018
使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题,证明了在 T 步随机梯度下降后,最终迭代的误差高概率为 O (log (T)/T);同时构造了一个函数,证明了在确定性梯度下降中,最终迭代的误差为 Ω(log (T)/T);然后证明了在采用后缀平均法的情形下,它的高概率误差界是优化函数相关类别中的最优界(O (1/T));最后证明了对于 Lipschitz 和凸函数 class,使用随机梯度下降解决此问题后,最终迭代的误差高概率为 O (log (T)/sqrt (T))
Dec, 2018