基于条件梯度的Adam分布式在线优化算法

本文主要考虑带有约束的分布式在线优化问题。在分布式环境下,节点间通过相互信息通信对实时数据流进行决策优化,因此每个节点的成本函数是时变的。为有效克服带有约束的优化问题通常要涉及到代价昂贵的投影运算,本文提出一种新的基于条件梯度的Adam分布式在线优化算法(DFWAdam)。Adam算法是随机梯度下降算法的扩展,其通过计算局部成本函数梯度的一阶矩估计和二阶矩估计,能有效提高算法收敛速度。算法收敛性分析表明:当代价函数为凸时,算法具有O (T~(3/4))的遗憾(Regret)界。利用合成数据集和真实数据集分别进行了数值实验,验证了DFWAdam算法的有效性,且其具有较快的收敛速度。

在线分布式优化研究进展

在线分布式优化是通过多智能体之间有效的协调合作以实现实时优化的任务,其在多无人系统实时编队跟踪、大规模分布式机器学习、传感器网络的动态参数估计等领域中有着广泛的应用。分别从决策空间、性能指标、信息反馈模型等角度对近年来国内外在线分布式优化的代表性研究工作进行了梳理和总结,着重从算法设计思路和收敛性结果两个角度进行了剖析,同时也指出不同算法的优势和不足。最后,对在线分布式优化算法的应用进行了简单讨论并对全文进行了总结和展望。

具有隐私保护的无投影分布式在线学习算法

本文研究了一个具有差分隐私性的无投影分布式在线条件梯度优化问题。针对这一问题,提出了一种分布式在线条件梯度(D-OCG)算法作为期望的变体,该方法通过使用线性最小化步骤来避免投影操作。此问题的网络模型是一个五个节点的平衡无向图。我们在理论证明中知道,该算法对于一般凸局部代价函数的期望遗憾界是O(√T),其中T是时间范围。我们的结果与最后的理论遗憾,可以实现最先进的算法。最后,通过仿真验证了算法的有效性。

基于Bandit反馈的分布式在线对偶平均算法

为解决梯度信息难以获取的分布式在线优化问题,提出了一种基于Bandit反馈的分布式在线对偶平均(DODA-B)算法。首先,该算法对原始梯度信息反馈进行了改进,提出了一种新的梯度估计,即Bandit反馈,利用函数值信息去近似原损失函数的梯度信息,克服了求解复杂函数梯度存在的计算量大等问题。然后,给出了该算法的收敛性分析,结果表明,Regret界的收敛速度为O(Tmax{k,1-k}),其中T是最大迭代次数。最后,利用传感器网络的一个特例进行了数值模拟计算,计算结果表明,所提算法的收敛速度与现有的分布式在线对偶平均(DODA)算法的收敛速度接近。与DODA算法相比,所提出算法的优点在于只考虑了函数值信息,使其更适用于梯度信息获取困难的实际问题。