Apr, 2023

基于平均二阶相似性的随机分布式优化：算法与分析

PDF
TL;DR本文研究了具有 n 个客户机的有限和分布式优化问题，针对流行的 δ- 相似性条件和 μ- 强凸性，提出了 SVRS 和 AccSVRS 两种新算法，其通信复杂度分别为 O (n+√(nδ/μ) ) 和 O (n+ n^(3/4)√(δ/μ) )，并显示了接近匹配的下界以验证其紧密性。
发现论文，激发创造
  • 网络中平滑且强凸分布式优化的最优算法

    该论文在两个设置中确定了强凸和光滑分布式优化的最优收敛速率：中央集权和去中心化通信。对于中央集权算法，作者表明分布式 Nesterov 加速梯度下降算法是最优的。对于基于流言蜚语 (gossip) 的去中心化算法，作者提供了第一个最优算法 MSDA 方法，并通过最小二乘回归和分类的逻辑回归问题验证了其效率。

    Feb, 2017

  • 具有加速收敛的方差缩减分散随机优化

    本文提出一种名为 GTVR 的随机分散算法框架，其基于本地方差缩减和全局梯度跟踪的技术，用于解决大规模，有可能无法集中处理私有数据的优化问题。我们在本文中重点研究了 GTVR 并介绍了两种算法 GT-SAGA 和 GT-SVRG，证明它们在解决光滑问题上呈现出线性收敛，并实现了在网络独立下的线性速度提升。

    Dec, 2019

  • 随机嵌套方差缩减非凸优化

    我们提出了一种基于嵌套方差降低的新随机梯度下降算法，可用于解决有限个数个、非凸函数的优化问题，并且在平滑非凸函数上具有比现有算法更好的梯度复杂度。

    Jun, 2018

  • 分散的非凸优化求和

    本文研究分散设置中的非凸函数求和最小化优化问题，提出了 PMGT-SVRG 算法的新的理论分析，证明了其方法的线性收敛性。然而，PMGT-SVRG 算法的收敛速度与条件数呈线性依赖关系，这对于病态问题而言是不理想的。为了解决这个问题，我们提出了一种结合加速、梯度跟踪和多共识混合技术的加速随机分散一阶算法，该方法的收敛速度与条件数呈平方根依赖关系。数值实验验证了我们提出算法在合成和真实数据集上理论保证的有效性。

    Feb, 2024

  • 高效的基于符号的优化：通过方差减少加速收敛

    本文介绍了 signSGD 方法及其收敛速率的改进，并引入了基于符号的随机方差缩减（SSVR）方法，通过引入方差缩减估计器来跟踪梯度并利用其符号进行更新；此外，还研究了分布式环境中的异构多数投票，引入了两种新算法以获得更好的收敛速率，通过数值实验验证了所提方法的有效性。

    Jun, 2024

  • 分布式随机梯度跟踪算法降低方差用于非凸优化

    本文提出了一种基于分布式随机算法的方差约简方法，以解决在多代理网络中进行大规模非凸有限和优化问题，提出了 GT-VR 算法，并证明了其收敛性和效率优于一些现有的一阶方法。

    Jun, 2021

  • 零阶异步双随机算法与方差缩减

    本文提出了一种使用方差缩减的异步双随机零阶优化算法 (AsyDSZOVR)，应用于光滑但不一定是凸函数的有限和问题，证明了该算法将收敛速度从 O（1 /√T）提高到了 O（1 / T），优于现有算法的最佳结果，并且也超越了顺序随机零阶优化算法的理论结果。

    Dec, 2016

  • 强凸优化的最优分布式随机镜像下降

    本文研究在多智能体网络中，基于 Bregman 散度作为距离测度函数，提出了两种高效的非欧几里德随机次梯度下降算法，用于求解非平滑和强凸函数的最小值，并在模拟实验中验证其收敛速度。

    Oct, 2016

  • 任意采样的 L-SVRG 和 L-Katyusha

    本篇研究提出了一种新的基于方差约减方法的优化算法，并使用预期平滑性条件来上界随机梯度估计的方差，以便于处理任意采样方案和非凸情况，此外还介绍了新的重要性采样，以在预期微型批量大小处实现线性加速，并建立期望平滑性参数与期望可分离过估计的联系，从而利用数据稀疏性。

    Jun, 2019

  • 分散优化中平滑强凸问题的最优实用算法

    本文提出了两种基于加速的前后向算法的分散优化新算法以解决存储在网络节点上的光滑强凸函数之和的最小化问题，并显示它们是最优的算法，具有复杂性的保证。

    Jun, 2020