随机镜像下降方法在非光滑非凸优化中的收敛速率
该论文重新审视了当今非凸优化设置中随机镜像下降(Stochastic Mirror Descent,SMD)的收敛性。通过支持一般距离生成函数(distance generating function,DGF)的新的非凸 SMD 收敛分析,该论文克服了先前结果对于具有光滑连续的梯度的可微性 DGF 的限制,并仅依赖于标准假设。此外,该论文通过 Bregman 前向 - 后向包络建立了收敛性,该包络是比常用的梯度映射的平方范数更强的度量。进一步,该论文将结果扩展到在次高斯噪声下的高概率收敛和在广义 Bregman Proximal Polyak-Lojasiewicz 条件下的全局收敛。此外,通过利用非光滑 DGFs,我们展示了改进的 SMD 理论在各种非凸机器学习任务中的优势。值得注意的是,在非凸差分隐私(differentially private,DP)学习的背景下,我们的理论提供了一个(几乎)维度无关的效用界算法。对于训练线性神经网络的问题,我们开发了可证明收敛的随机算法。
Feb, 2024
本篇论文介绍了一种新的随机算法 ——Stochastic Block Mirror Descent(SBMD)方法,用于解决大规模非光滑和随机优化问题,其通过加入块状坐标分解和增量式块状平均方案到经典(随机)镜像下降法中,以显著降低后者算法的每次迭代成本。我们建立了 SBMD 方法的收敛速率及其相关的大偏差结果,用于解决一般的非光滑和随机优化问题。此外,我们还介绍了此方法的不同变体,并建立了它们用于解决强凸,平滑,复合和某些非凸优化问题的收敛速率。据我们所知,所有这些 SBMD 方法的发展都是随机优化文献中的新成果。此外,我们的一些结果对于块状坐标下降方法中的确定性优化也是新的。
Sep, 2013
本文研究在多智能体网络中,基于 Bregman 散度作为距离测度函数,提出了两种高效的非欧几里德随机次梯度下降算法,用于求解非平滑和强凸函数的最小值,并在模拟实验中验证其收敛速度。
Oct, 2016
本研究主要探讨过参数模型中采用 stochastic mirror descent 方法,在足够小的步长下,通过初始化接近全局最小值,其可以收敛和迭代到一种接近 Bregman 散度且具有更好泛化性能的解决方案,并探究该方法中不同的隐式正则化方式对结果表现的影响。
Jun, 2019
本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题,本文提出快速的随机算法,可获得常数迷你批量的收敛性。本文还使用这些算法的变种,证明了比批量近端梯度下降更快的收敛性,并在非凸、非光滑函数的一个子类中证明全局线性收敛率。
May, 2016
本文研究了凸函数和 Lipschitz 目标的随机镜像下降法的优化误差,提供了新的尾部界限,并将其扩展到更重尾噪声的情况。研究了最后一次迭代和迭代平均值的优化误差,并在指数尾和多项式尾两种重要情况下实例化了结果。我们的结果的一个显著特点是不需要对定义域的直径设置上界。最后,我们通过示例实验证明在重尾噪声情况下迭代平均值与最后一次迭代的行为的比较。
Dec, 2023
本文中,我们提出了两种新算法:相对随机坐标下降(relRCD)和相对随机梯度下降(relSGD),通过从随机凸优化领域中借鉴思想,以更快的速度最小化相对平滑函数,这两种方法可以看作是随机镜像下降算法的一种特例。其中,relRCD 对应于带有线性收敛速率的第一种随机变体的镜像下降算法。
Mar, 2018
本文研究了一类具有一致性属性的非单调问题中,优化镜像下降法(OMD)的收敛性和优化方式。分析表明,OMD 可以解决这些问题并推广了先前的结果,为建立凸凹博弈以外的收敛性提供了具体进展。在一系列 GAN 模型上的数值实验结果验证了分析的可行性。
Jul, 2018
通过对 Shor 子梯度分析的推广,我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中,确定性投影子梯度算法的全局 O(1/√T)收敛速度。我们还表明,对于具有最多二次增长的凸函数,随机投影子梯度方法的收敛速度为 O(1/√T),在强凸性或较弱的二次下限条件下,该速度可进一步提高至 O (1/T)。
Dec, 2017