Jun, 2014

关于时变有向图上强凸函数的随机梯度推进

PDF
TL;DR本文研究了分布式优化中最近提出的 subgradient-push 方法在时变有向图上的收敛速度，并证明在强凸函数和具有 Lipschitz 梯度的情况下，即使只有随机梯度样本可用，其收敛速度为 O ((ln t)/t)，这比先前已知的（一般）凸函数的 O ((ln t)/√t) 更快。
distributed optimizationsubgradient-push methodconvergence ratetime-varying directed graphsstochastic gradient samples
发现论文，激发创造
  • 时变有向图上的分布式优化

    本文研究了通过节点之间的交流来进行分布式优化的问题，提出了一种基于广播的算法，即 subgradient-push algorithm, 计算其收敛速率.

    Mar, 2013

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

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

    Oct, 2016

  • 非 Lipschitz 连续情况下的确定性与随机次梯度方法的收敛速度

    通过对 Shor 子梯度分析的推广，我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中，确定性投影子梯度算法的全局 O（1/√T）收敛速度。我们还表明，对于具有最多二次增长的凸函数，随机投影子梯度方法的收敛速度为 O（1/√T），在强凸性或较弱的二次下限条件下，该速度可进一步提高至 O (1/T)。

    Dec, 2017

  • 非凸分布式优化

    该研究分析分布式非凸优化问题，针对多智能体网络模型，利用一些技术假设证明分布式推送算法在目标函数的临界点处收敛，并利用扰动动力学证明扰动过程的几乎肯定收敛性。

    Dec, 2015

  • 分布式优化在时变图上实现几何收敛

    本文考虑基于动态图的分布式优化问题，提出了 DIGing 和 Push-DIGing 算法来解决无向和有向图的问题，同时证明了在强凸性假设下，这些算法以几何级数的速率收敛。

    Jul, 2016

  • 异步梯度推送

    本文提出了一种异步多代理分布式优化算法，每个代理都有一个局部的强凸平滑函数，共同目标是达成对将代理的局部函数之和最小化的参数进行共识。实验结果表明，与同步一阶方法相比，Asynchronous Gradient-Push 算法收敛速度更快，更具鲁棒性，并且随着网络规模的增大，它的扩展性更好。

    Mar, 2018

  • 去中心化在线随机非凸优化的收敛分析改进

    本文研究了节点网络上的去中心化在线随机非凸优化。通过将梯度跟踪技术集成到去中心化随机梯度下降中，我们证明了该算法具有一定的优势，并分析了其有效性和性能。同时，对于满足 Polyak-Lojasiewics 条件的全局非凸函数，我们确定了 GT-DSGD 的线性收敛性，并且在几乎每条路径上具有最优的全局亚线性收敛速度。

    Aug, 2020

  • Polyak 学习率的随机梯度下降

    本文提出将 Subgradient 方法中的 Polyak 步长推广到随机梯度下降中，并证明了该算法可以在非渐进情况下以更好的速率收敛于优化解，该算法在训练深度神经网络等问题上表现良好。

    Mar, 2019

  • 强生长条件下随机梯度下降的快速收敛

    本文考虑优化一个平滑凸函数，该函数是一组可微函数的平均数，在每个梯度的范数受到平均梯度范数的线性约束的假设下，证明了基本的随机梯度方法具有 O (1/k) 的收敛速度，并且在强凸条件下具有线性收敛速度。

    Aug, 2013

  • 用于网络分布式优化的推拉梯度方法

    本文介绍了一种新的分布式梯度方法，称为 “推 - 拉梯度方法”，利用两种不同的图形实现代理之间的信息交换，并在同步和异步随机传递的情况下，线性地收敛于重要的自治网络。

    Oct, 2018