基于零梯度之和策略的定向网络分布式在线序列学习

《Neurocomputing》：Distributed online sequential learning for directed networks via zero-gradient-sum strategy

　　谢进|严薇薇|高伟峰|李鸿|王凌 西安电子科技大学数学与统计学院，中国西安710071

摘要：为解决分布式在线优化中实时性能、收敛效率以及减少原始数据暴露等问题，本文提出了一种分布式在线序列学习算法。该算法将离散时间零梯度求和共识机制与在线序列学习相结合，适用于强连通的权重平衡有向网络。算法包括通过本地训练和零梯度求和迭代进行参数共识的初始化阶段，以及利用辅助变量和伍德伯里公式实现增量学习与全局收敛的序列学习阶段。此外，基于代数图论和凸优化的严格理论分析表明，该算法的节点参数会以指数速度收敛到相应的批量全局最优解。最后，通过六组真实数据集的实验验证了所提算法在在线回归和时间序列预测任务中的有效性。

引言：随着大数据时代的到来，机器学习理论及其算法实现已达到前所未有的成熟度。基于观测数据训练的模型如今已被广泛应用于医学、社会学、自然科学和模式识别等多个领域。然而，随着数据量的持续增长，计算复杂度和存储压力也急剧上升。面对如此庞大的数据量，传统的集中式学习算法难以取得理想效果，给数据处理带来了新的挑战。目前，解决这些问题的主流方法包括在线学习算法和分布式优化算法——这两种方法是大数据处理和分析的两大核心范式。

在线学习算法主要用于动态的实时数据处理。在金融市场交易、网页搜索点击分析以及物联网传感器监控等实际应用中，数据往往以高速流的形式持续涌入。为应对这一问题，在线学习摒弃了传统批量学习方式，后者需要预先存储整个数据集。在线学习则是按顺序处理数据：对于每个新到的样本或小批量数据，模型会立即做出预测并更新自身。例如，弗罗因德和沙皮尔提出的Hedge算法为在线学习奠定了早期基础，而津克维奇后来则 formalized了在线凸优化理论，为基于梯度的算法如在线梯度下降提供了核心支撑。这类算法的主要目标是 minimizing连续决策过程中的累积遗憾。这种范式具有内存开销低、模型更新速度快以及能适应数据分布变化等优点，因此特别适合对实时性要求较高的场景。不过，传统在线学习通常假设数据集中在单个处理节点上，这忽视了一个重要的现实问题：由于隐私考虑或通信限制，数据往往分布在多个地点，无法集中处理。

另一方面，分布式优化算法旨在解决数据存储和计算分散所带来的挑战。在无线传感器网络、多智能体系统和边缘计算等应用中，数据自然地分布在众多分布式节点上。由于隐私问题、通信开销或监管限制，将此类数据集中起来进行处理往往不切实际或效率低下。为解决这些问题，分布式算法允许各个节点执行本地计算，并仅与邻近节点交换有限信息，从而协同解决全局优化问题。这一领域已得到广泛研究，现有大量文献介绍了各种有效的分布式优化方法。奥尔法蒂-萨贝尔等人提出的早期平均共识协议为分布式优化奠定了通信基础，后续研究又在时变网络上分析了分布式次梯度方法并确定了其收敛性质，还有研究将随机梯度引入其中。与我们工作尤为相关的是某项研究，它首次提出了用于分布式凸优化的零梯度求和框架，使得智能体能够以指数速率持续收敛。理解零梯度求和原理的一个直观方式是通过物理类比：可以将每个局部梯度视为智能体局部目标产生的虚拟力，而网络交互则可看作连接相邻智能体的弹簧系统。零梯度求和机制则推动整个系统朝着这些力相互平衡的状态发展，即所有局部梯度之和为零。从这个意义上说，零梯度求和可被视为一种力量平衡机制，它能协调各智能体的局部目标，使其共同朝向同一个全局最优解前进。这种去中心化架构能有效避免单点故障，缓解通信瓶颈，提高系统可扩展性，同时相比集中式处理还能降低原始数据的暴露风险。不过，传统的分布式优化算法主要是为静态的已知数据集设计的，其优化过程通常需要在固定数据集上进行多轮迭代，因此不太适合直接处理持续涌入的动态数据流。

因此，在线学习和分布式优化分别从不同层面应对了大数据带来的挑战。所以，推进分布式在线学习的理论与方法发展——即将在线学习的实时自适应机制与分布式优化的去中心化协作框架相结合——便成为一项自然而重要的研究方向。这一领域吸引了众多关注，催生了多种方法的出现。齐亚诺斯等人提出的分布式在线梯度下降作为基础框架，为该领域的后续方法发展奠定了基础。为了提升性能，后续研究又提出了诸如在线分布式双平均算法、在线分布式镜像下降算法、在线分布式Frank-Wolfe算法、在线分布式原始-对偶次梯度算法等多种方法。不过，这些方法大多基于梯度或次梯度更新，并结合了节点间的信息交换。

在本工作中，我们提出了一种在线序列零梯度求和算法。与现有的分布式在线方法不同，该方法利用径向基函数神经网络正则化最小二乘形式所衍生的递归模型结构，通过引入辅助变量和伍德伯里公式，让每个节点通过序列矩阵递归而非简单的梯度步骤来整合新到达的数据。这使得本地学习阶段呈现出基于模型的递归形式，与大多数现有分布式在线算法中使用的梯度驱动更新有所不同。在网络层面上，这些本地序列更新又会与有向图上的零梯度求和算法相结合，从而使每个新到达的数据批次先经过递归式本地调整，再通过分布式协调进行处理。因此，所提方法更适合作为一种批量式分布式序列学习框架，而非传统的一阶分布式在线优化算法。本工作的主要贡献如下：

1. 为有向网络设计了一种基于零梯度求和策略的分布式在线序列学习算法。与标准的一阶分布式在线方法不同，该方法利用RBFNN的正则化最小二乘结构，通过基于伍德伯里公式的递归矩阵计算来实现本地模型更新。

2. 通过将递归式本地调整与基于零梯度求和的网络协调相结合，构建了一种批量式分布式序列学习机制。这样一来，新到达的数据可以在每个节点上逐步整合，无需从头开始重新训练，同时相邻节点也能在有向图上协同优化各自的模型参数。

3. 在RBFNN的正则化最小二乘形式以及权重平衡的强连通有向图假设下，证明了所有节点参数都会以指数速度收敛到相应的批量全局最优解。针对在线回归和时间序列预测任务的真实数据集实验进一步验证了所提方法的有效性。

符号说明：表示自然数集；表示实数集；表示实向量集；表示维矩阵集；表示维单位矩阵。表示矩阵的转置；表示两个向量的内积，表示向量的标准欧几里得范数；表示克罗内克积；分别表示函数 的梯度矩阵和海森矩阵。

章节节选

图论：我们考虑由有向图表示的网络，该图包含个节点，其中是有限的非空节点集，是节点有序对构成的边集，是有向图的加权邻接矩阵。邻接矩阵的定义为：当时，，否则。如果一个图中的每个顶点都能从其他所有顶点到达，则称该图为强连通图。拉普拉斯矩阵定义为：当且时为，否则为。如果是一个权重平衡的图，那么对于有。如果是一个强连通图，那么有。

径向基函数神经网络：在上一小节中，我们已经提出了问题描述。

问题描述：在分布式网络中，每个智能体都拥有一个独立的RBFNN模型用于本地在线学习。现在考虑一个包含个智能体的有向图。每个智能体在时间步会依次接收到本地数据，其中是输入数据，是输入标签。具体的数据分配方式如图1所示。我们的目标是学习一个全局模型参数，其中是隐藏层节点的数量，使得所有智能体的累积损失最小化。具体而言，在时间步，有

收敛性分析：在给出算法1收敛性的主要结果之前，我们首先列出一些假设和引理。

假设2：存在一个常数，使得对于每一个数据批次，与零梯度求和动力学相关的初始李雅普诺夫值满足，其中为。

假设3：存在一个常数，使得对于每一个数据批次和每一个，有

引理1[34]：假设该图是强连通且权重平衡的，那么存在一个正常数，使得，其中为该图的拉普拉斯矩阵。我们将其记为。

引理2[19]：在引理1的条件下，考虑一个

实验部分：在本节中，我们通过使用真实数据集对各种在线回归和时间序列预测任务进行实验，来验证算法1的有效性。我们证明了它的核心优势：在多种在线学习任务中都能保持稳定性能，这与[35]的研究结果类似。在本文中，我们还将算法1的性能与集中式在线学习算法进行了比较，同时 also对比了分布式在线梯度下降算法和分布式在线

结论与未来工作：在本文中，我们提出了一种基于零梯度求和策略的面向有向网络的分布式在线学习算法。通过将基于伍德伯里公式的本地递归更新与基于零梯度求和的分布式协调相结合，该算法实现了批量式在线学习，同时避免了原始数据的集中处理。在假设1以及本地成本函数具有强凸性的条件下，我们证明了该算法能够以指数速度收敛到相应的批量全局最优解。

CRediT作者贡献说明：谢进：写作——审稿与编辑，写作——初稿撰写，研究工作，资金获取。严薇薇：写作——初稿撰写，研究工作。高伟峰：指导监督，资源提供，资金获取。李鸿：指导监督，资源提供。王凌：指导监督，资源提供。

利益冲突声明：作者声明不存在任何可能影响本文研究的已知财务利益或个人关系。

致谢：本研究部分得到了国家自然科学基金项目62276202的支持，部分得到了中央高校基本科研业务费项目QTZX25074的支持，部分得到了浙江省自然科学基金联合资助项目LHZY24A010005的支持，部分得到了中国博士后科学基金会项目2024MD754039和2023T160501的支持，还部分得到了空间微波科技国家重点实验室的支持。谢进于2013年在中国保定华北电力大学获得数学学士学位，2020年在中国西安西安电子科技大学获得数学博士学位。他目前是西安电子科技大学数学与统计学院的副教授，研究兴趣包括机器学习、神经网络、半监督学习以及分布式学习。