本文涉及一种计算代理网络，旨在以分布式方式解决在线优化问题，即通过本地计算和通信，没有任何中央协调员。我们提出了具有自适应动量估计（GTADAM）分布式算法的梯度跟踪，其将梯度跟踪机制与梯度的第一和二阶动量估计相结合。该算法在线设置中分析了具有Lipschitz连续梯度的强凸起成本函数的在线设置。我们为动态遗憾提供了一个与初始条件相关的术语的动态遗憾的上限，以及与客观函数的时间变化有关的另一个术语。此外，在静态设置中保证了线性收敛速率。在从图像分类中，在（移动）目标定位问题上和随机优化设置中的时变分类问题测试该算法。在来自多智能经验学习的这些数值实验中，GTADAM优于最先进的分布式优化方法。

非平滑的有限和最小化是机器学习中的一个基本问题。本文开发了一种具有随机重新洗牌的分布式随机近端梯度算法，以解决随着时变多代理网络的有限和最小化。目标函数是可分辨率凸起功能的总和和非平滑的正则化。网络中的每个代理通过本地信息更新具有恒定步长大小的局部变量，并协作以寻求最佳解决方案。我们证明了所提出的算法产生的局部变量估计实现共识，并且与$ \ mathcal {o}（\ frac {1} {t} + \ frac {1} {\SQRT {T}}）$收敛率。此外，本文通过选择足够的阶梯尺寸，可以任意地小的目标函数的稳态误差。最后，提供了一些比较仿真来验证所提出的算法的收敛性能。

我们考虑分散的优化问题，其中许多代理通过在基础通信图上交换来最大程度地减少其本地功能的平均值。具体而言，我们将自己置于异步模型中，其中只有一个随机部分在每次迭代时执行计算，而信息交换可以在所有节点之间进行，并以不对称的方式进行。对于此设置，我们提出了一种算法，该算法结合了整个网络上梯度跟踪和差异的差异。这使每个节点能够跟踪目标函数梯度的平均值。我们的理论分析表明，在预期混合矩阵的轻度连通性条件下，当局部目标函数强烈凸面时，算法会汇聚。特别是，我们的结果不需要混合矩阵是双随机的。在实验中，我们研究了一种广播机制，该机制将信息从计算节点传输到其邻居，并确认我们方法在合成和现实世界数据集上的线性收敛性。

这项工作审查了旨在在通信约束下运行的自适应分布式学习策略。我们考虑一个代理网络，必须从持续观察流数据来解决在线优化问题。代理商实施了分布式合作策略，其中允许每个代理商与其邻居执行本地信息交换。为了应对通信约束，必须不可避免地压缩交换信息。我们提出了一种扩散策略，昵称为ACTC（适应 - 压缩 - 然后组合），其依赖于以下步骤：i）每个代理执行具有恒定步长大小的单独随机梯度更新的适应步骤; ii）一种压缩步骤，它利用最近引入的随机压缩操作员;和III）每个代理组合从其邻居接收的压缩更新的组合步骤。这项工作的区别要素如下。首先，我们专注于自适应策略，其中常数（而不是递减）阶梯大小对于实时响应非间断变化至关重要。其次，我们考虑一般的指导图表和左随机组合政策，使我们能够增强拓扑和学习之间的相互作用。第三，与对所有个人代理的成本职能承担强大的凸起的相关作品相比，我们只需要在网络水平的强大凸起，即使单个代理具有强凸的成本，剩余的代理商也不满足凸起成本。第四，我们专注于扩散（而不是共识）战略。在压缩信息的苛刻设置下，建立ACTC迭代在所需的优化器周围波动，在相邻代理之间交换的比特方面取得了显着的节省。

在本文中，我们考虑了在$ N $代理的分布式优化问题，每个都具有本地成本函数，协作最小化连接网络上的本地成本函数的平均值。为了解决问题，我们提出了一种分布式随机重新洗脱（D-RR）算法，该算法结合了经典分布式梯度下降（DGD）方法和随机重新洗脱（RR）。我们表明D-RR继承了RR的优越性，以使光滑强凸和平的非凸起目标功能。特别是，对于平稳强凸的目标函数，D-RR在平方距离方面实现$ \ Mathcal {o}（1 / T ^ 2）$汇率（这里，$ t $计算迭代总数）在迭代和独特的最小化之间。当假设客观函数是平滑的非凸块并且具有Lipschitz连续组件函数时，我们将D-RR以$ \ Mathcal {O}的速率驱动到0美元的平方标准（1 / T ^ {2 / 3}）$。这些收敛结果与集中式RR（最多常数因素）匹配。

遗憾已被广泛用作评估分布式多代理系统在线优化算法的性能的首选指标。但是，与代理相关的数据/模型变化可以显着影响决策，并需要在代理之间达成共识。此外，大多数现有的作品都集中在开发（强烈或非严格地）凸出的方法上，对于一般非凸损失的分布式在线优化中的遗憾界限，几乎没有得到很少的结果。为了解决这两个问题，我们提出了一种新型的综合遗憾，并使用新的基于网络的基于遗憾的度量标准来评估分布式在线优化算法。我们具体地定义了复合遗憾的静态和动态形式。通过利用我们的综合遗憾的动态形式，我们开发了一种基于共识的在线归一化梯度（CONGD）的伪convex损失方法，事实证明，它显示了与最佳器路径变化的规律性术语有关的透明性行为。对于一般的非凸损失，我们首先阐明了基于最近进步的分布式在线非凸学习的遗憾，因此没有确定性算法可以实现sublinear的遗憾。然后，我们根据离线优化的Oracle开发了分布式的在线非凸优化（Dinoco），而无需进入梯度。迪诺科（Dinoco）被证明是统一的遗憾。据我们所知，这是对一般分布在线非convex学习的第一个遗憾。

在本文中，我们处理了一个通用分布式约束的在线学习问题，并在随着时间变化的网络上进行了隐私，其中考虑了一类不可分配的目标功能。在此设置下，每个节点仅控制全球决策变量的一部分，所有节点的目标是在时间范围内协作最小化全球目标，同时保证传输信息的安全性。对于此类问题，我们首先设计了一种新颖的通用算法框架，称为DPSDA，使用Laplace机制和双重平均方法的随机变体进行了差异性私有分布式在线学习。然后，我们建议在此框架下提出两种算法，称为DPSDA-C和DPSDA-PS。理论结果表明，两种算法都达到了预期的遗憾上度上限$ \ MATHCAL {O}（\ sqrt {t}）$当目标函数是凸的时，它符合通过切割边缘算法来实现的最佳效用。最后，数值实验在现实世界和随机生成的数据集上都验证了我们算法的有效性。

Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}(\epsilon^{-3/2})$ in sample and communication complexities for achieving an $\epsilon$-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.

在本文中，我们提出了GT-GDA，这是一种分布式优化方法来解决表单的鞍点问题：$ \ min _ {\ Mathbf {x}}} \ max _ {\ Mathbf {y Mathbf {y}}} \ {f（ 。 $，其中函数$ g（\ cdot）$，$ h（\ cdot）$，以及耦合矩阵$ \ overline {p} $的耦合矩阵{p} $是在强烈连接的节点网络上分发的。 GT-GDA是一种使用梯度跟踪来消除节点之间异质数据分布引起的差异的一阶方法。在最通用的形式中，GT-GDA包括与本地耦合矩阵的共识，以达到最佳（独特的）鞍点，但是，以增加通信为代价。为了避免这种情况，我们提出了一个更有效的变体GT-GDA-LITE，该变体不会引起额外的交流并在各种情况下分析其收敛性。我们表明，当$ g（\ cdot）$平滑且凸，$ h（\ cdot）$平稳且强烈凸时，GT-GDA线性收敛到唯一的鞍点解决方案，并且全局耦合矩阵$ \ overline {p } $具有完整的列等级。我们进一步表征了GT-GDA表现出与网络拓扑无关的收敛行为的制度。接下来，我们显示GT-GDA的线性收敛到围绕唯一鞍点的错误，当耦合成本$ {\ langle \ mathbf y，\ overline {p} \ mathbf x \ rangle} $是零时为零。所有节点，或当$ g（\ cdot）$和$ h（\ cdot）$是二次时。数值实验说明了GT-GDA和GT-GDA-LITE对多种应用的收敛属性和重要性。

在互联网上的多种代理环境中的新兴应用程序，如互联网，网络传感，自主系统和联合学习，呼叫分散算法，以便在计算和通信方面是资源有效的有限总和优化。在本文中，我们考虑了原型设置，其中代理正在协作地工作，以通过在预定的网络拓扑中与其邻居通信来最小化局部损失函数的总和。我们开发了一种新的算法，称为分散的随机递归梯度方法（DESTRess），用于非耦合有限和优化，它与集中式算法的最佳增量一阶Oracle（IFO）复杂性匹配，用于查找一阶静止点，同时保持通信效率。详细的理论和数值比较证实了迭代在广泛的参数制度上提高现有分散算法的资源效率。 Descress利用了多个关键算法设计思路，包括随机激活的随机递增渐变渐变更新，具有用于本地计算的迷你批次，梯度跟踪，梯度跟踪，用于额外混合（即，多个八卦轮），用于偏移通信，以及仔细选择超参数和新的分析框架可证明达到理想的计算 - 通信权衡。

This paper considers the distributed online convex optimization problem with time-varying constraints over a network of agents. This is a sequential decision making problem with two sequences of arbitrarily varying convex loss and constraint functions. At each round, each agent selects a decision from the decision set, and then only a portion of the loss function and a coordinate block of the constraint function at this round are privately revealed to this agent. The goal of the network is to minimize the network-wide loss accumulated over time. Two distributed online algorithms with full-information and bandit feedback are proposed. Both dynamic and static network regret bounds are analyzed for the proposed algorithms, and network cumulative constraint violation is used to measure constraint violation, which excludes the situation that strictly feasible constraints can compensate the effects of violated constraints. In particular, we show that the proposed algorithms achieve $\mathcal{O}(T^{\max\{\kappa,1-\kappa\}})$ static network regret and $\mathcal{O}(T^{1-\kappa/2})$ network cumulative constraint violation, where $T$ is the time horizon and $\kappa\in(0,1)$ is a user-defined trade-off parameter. Moreover, if the loss functions are strongly convex, then the static network regret bound can be reduced to $\mathcal{O}(T^{\kappa})$. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.

Several recently proposed stochastic optimization methods that have been successfully used in training deep networks such as RMSPROP, ADAM, ADADELTA, NADAM are based on using gradient updates scaled by square roots of exponential moving averages of squared past gradients. In many applications, e.g. learning with large output spaces, it has been empirically observed that these algorithms fail to converge to an optimal solution (or a critical point in nonconvex settings). We show that one cause for such failures is the exponential moving average used in the algorithms. We provide an explicit example of a simple convex optimization setting where ADAM does not converge to the optimal solution, and describe the precise problems with the previous analysis of ADAM algorithm. Our analysis suggests that the convergence issues can be fixed by endowing such algorithms with "long-term memory" of past gradients, and propose new variants of the ADAM algorithm which not only fix the convergence issues but often also lead to improved empirical performance.

近年来，由于它们在对点对点网络上的分散性学习问题（例如，多机构元学习，多机构的多方强化增强学习学习）上，分散的双层优化问题在网络和机器学习社区中引起了越来越多的关注。 ，个性化的培训和拜占庭的弹性学习）。但是，对于具有有限的计算和通信功能的对等网络上的分散式双层优化，如何实现低样本和通信复杂性是迄今为止尚未探索的两个基本挑战。在本文中，我们首次尝试研究了分别与外部和内部子问题相对应的非凸和强结构结构的分散双重优化问题。本文中我们的主要贡献是两倍：i）我们首先提出了一种称为Interact的确定性算法（Inter-gradient-descent-out-outer-tracked-gradeent），需要$ \ Mathcal {o}的样品复杂性（n \ epsilon） ^{ - 1}）$和$ \ mathcal {o}的通信复杂性（\ epsilon^{ - 1}）$解决双重优化问题，其中$ n $和$ \ epsilon> 0 $是样本的数量在每个代理和所需的平稳性差距上。 ii）为了放宽每次迭代中进行全面梯度评估的需求，我们提出了一个随机方差的互动版本（SVR Interact），该版本将样品复杂性提高到$ \ Mathcal {o}（\ sqrt {n} \ epsilon ^{ - 1}）$在达到与确定算法相同的通信复杂性时。据我们所知，这项工作是第一个实现低样本和通信复杂性，以解决网络上的分散双层优化问题。我们的数值实验也证实了我们的理论发现。

Bilevel programming has recently received attention in the literature, due to a wide range of applications, including reinforcement learning and hyper-parameter optimization. However, it is widely assumed that the underlying bilevel optimization problem is solved either by a single machine or in the case of multiple machines connected in a star-shaped network, i.e., federated learning setting. The latter approach suffers from a high communication cost on the central node (e.g., parameter server) and exhibits privacy vulnerabilities. Hence, it is of interest to develop methods that solve bilevel optimization problems in a communication-efficient decentralized manner. To that end, this paper introduces a penalty function based decentralized algorithm with theoretical guarantees for this class of optimization problems. Specifically, a distributed alternating gradient-type algorithm for solving consensus bilevel programming over a decentralized network is developed. A key feature of the proposed algorithm is to estimate the hyper-gradient of the penalty function via decentralized computation of matrix-vector products and few vector communications, which is then integrated within our alternating algorithm to give the finite-time convergence analysis under different convexity assumptions. Owing to the generality of this complexity analysis, our result yields convergence rates for a wide variety of consensus problems including minimax and compositional optimization. Empirical results on both synthetic and real datasets demonstrate that the proposed method works well in practice.

多智能体增强学习（Marl）最近引起了很多研究。然而，与其单一代理对应物不同，Marl的许多理论和算法方面尚未得到很好的理解。在本文中，我们使用演员 - 评论家（AC）算法研究了自主代理的协调行为的出现。具体而言，我们提出并分析了一类协调的演员 - 批评算法（CAC），其中单独的参数化政策有一个{\ IT共享}部分（其中在所有代理中共同优化）和{\ IT个性化}部分（这是只有当地优化）。这种类型的{\它部分个性化}策略允许代理通过利用同伴的过去的经验来学习协调并适应各个任务。我们设计的灵活性允许提出的Marl-CAC算法用于{\ IT完全分散}设置中使用，其中代理商只能与其邻居通信，以及偶尔代理的{\ IT联合}设置与服务器通信，同时优化其（部分个性化）本地模型。从理论上讲，在一些标准规律性假设下，所提出的Marl-CAC算法需要$ \ mathcal {o}（\ epsilon ^ { - \ frac {5} {2}}）$样本来实现$ \ epsilon $ - 固定式解决方案（定义为目标函数梯度的平方标准的解决方案小于$ \ epsilon $）。据我们所知，这项工作为具有部分个性化策略的分散式交流算法提供了第一个有限的样本保证。

Enhancing resilience in distributed networks in the face of malicious agents is an important problem for which many key theoretical results and applications require further development and characterization. This work focuses on the problem of distributed optimization in multi-agent cyberphysical systems, where a legitimate agent's dynamic is influenced both by the values it receives from potentially malicious neighboring agents, and by its own self-serving target function. We develop a new algorithmic and analytical framework to achieve resilience for the class of problems where stochastic values of trust between agents exist and can be exploited. In this case we show that convergence to the true global optimal point can be recovered, both in mean and almost surely, even in the presence of malicious agents. Furthermore, we provide expected convergence rate guarantees in the form of upper bounds on the expected squared distance to the optimal value. Finally, we present numerical results that validate the analytical convergence guarantees we present in this paper even when the malicious agents compose the majority of agents in the network.

我们研究了随机近似的分散变体，这是一种数据驱动的方法，用于在嘈杂的测量中找到操作员的根。一个具有自己的操作员和数据观察的代理网络，合作地通过分散的通信图找到了聚合操作员的固定点。我们的主要贡献是在从马尔可夫过程中采样时在每个代理下观察到的数据时，对这种分散的随机近似方法提供有限的时间分析；这种缺乏独立性使迭代率偏向和（可能）无限。在相当标准的假设下，我们表明所提出方法的收敛速率与样本是独立的基本相同，仅由对数因子的差异而不同，该对数因素是说明了马尔可夫过程的混合时间。我们的分析中的关键思想是引入一种新型的Razumikhin-Lyapunov函数，该功能是由用于分析延迟普通微分方程的稳定性的一种动机。我们还讨论了拟议方法在多代理系统中许多有趣的学习问题上的应用。

我们研究了多智能经纪增强学习的政策评估问题，其中一组代理商，共同观察到的国家和私人本地行动和奖励，协作，以通过连接的无向网络通过本地计算和通信学习给定策略的价值函数。各种大型多种代理系统中出现此问题，包括电网，智能交通系统，无线传感器网络和多代理机器人。当状态动作空间的尺寸大时，广泛使用具有线性函数近似的时间差异学习。在本文中，我们开发了一种新的分布式时间差异学习算法，量化其有限时间性能。我们的算法将分布式随机原始方法与基于同型的方法进行了自适应调整学习率的方法，以便通过从因果导轨轨迹中采用新鲜的在线样本来最小化平均投影的Bellman误差。我们明确考虑了采样的Markovian性质，并改善了从$ O（1 / \ sqrt {t}）$到〜$ o（1 / t）$的最佳已知的有限时间误差，其中$ t $迭代的总数。

本文研究了协同多智能体增强学习（MARL）的分布式政策梯度，在通信网络上的代理人旨在找到最佳政策，以最大限度地提高所有代理人的当地返回的平均值。由于政策梯度的非凹形性能函数，用于凸面问题的现有分布式随机优化方法不能直接用于Marl中的政策梯度。本文提出了一种具有方差减少和渐变跟踪的分布式策略梯度，以解决政策梯度的高差，并利用重要的重量来解决采样过程中的非静止问题。然后，我们在平均平均固定间隙上提供一个上限，这取决于迭代的数量，迷你批量大小，秒钟大小，问题参数和网络拓扑。我们进一步建立了样本和通信复杂性，以获得$ \ epsilon $-upprymate静止点。对MARL控制问题的数值实验进行了验证了所提出算法的有效性。

我们开发了一个通用框架，统一了几种基于梯度的随机优化方法，用于在集中式和分布式场景中，用于经验风险最小化问题。该框架取决于引入的增强图的引入，该图形由对样品进行建模和边缘建模设备设备间通信和设备内随机梯度计算。通过正确设计增强图的拓扑结构，我们能够作为特殊情况恢复为著名的本地-SGD和DSGD算法，并提供了统一的方差还原（VR）和梯度跟踪（GT）方法（例如Saga） ，本地-SVRG和GT-SAGA。我们还提供了统一的收敛分析，以依靠适当的结构化lyapunov函数，以实现平滑和（强烈的）凸目标，并且获得的速率可以恢复许多现有算法的最著名结果。速率结果进一步表明，VR和GT方法可以有效地消除设备内部和跨设备内的数据异质性，从而使算法与最佳解决方案的确切收敛性。数值实验证实了本文中的发现。