在快速增长的世界中，分散学习算法的设计很重要，在这个世界中，数据分布在有限的本地计算资源和通信的参与者上。在这个方向上，我们提出了一种在线算法最小化从网络上分布的单个数据/模型汇总的非凸损失函数。我们提供算法的理论性能保证，并在现实生活中展示其实用性。

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

最大化单调性函数是机器学习，经济学和统计数据中的一项基本任务。在本文中，我们提出了单调连续DR-submodular最大化问题的两种通信效率分散的在线算法，这两者都减少了函数梯度评估的数量，并从$ t^{3/2}中降低了每轮的通信复杂性$至$ 1 $。第一个，单发的分散式元弗兰克 - 沃尔夫（Mono-dmfw），达到了$（1-1/e）$ - 遗憾的是$ o（t^{4/5}）$。据我们所知，这是单调连续DR-submodular Maximization的第一个单发和无投射分散的在线算法。接下来，受到非界化的增强功能\ citep {zhang2022boosting}的启发，我们提出了分散的在线增强梯度上升（dobga）算法，该算法获得了$（1-1/e）$ - 遗憾的是$（\ sqrt {\ sqrt { t}）$。据我们所知，这是获得$（1-1/e）$的最佳$ o（\ sqrt {t}）$的第一个结果步。最后，各种实验结果证实了所提出的方法的有效性。

我们考虑使用一组并行代理和参数服务器分发在线MIN-MAX资源分配。我们的目标是最大限度地减少一组时变的凸起和降低成本函数的点最大值，而无需先验信息。我们提出了一种新的在线算法，称为分布式在线资源重新分配（DORA），其中非贸易人员学会通过陷入拖放者释放资源和共享资源。与大多数现有的在线优化策略不同，Dora的一个值得注意的特征是它不需要梯度计算或投影操作。这允许它基本上减少大规模和分布式网络中的计算开销。我们表明，所提出的算法的动态遗憾是由$ o lex的上限（t ^ {\ frac {3} {4}}（1 + p_t）^ {\ frac {1} {4} \右） $，$ t $是轮次的总数，$ p_t $是瞬时最小化器的路径长度。我们进一步考虑在分布式在线机器学习中的带宽分配问题的应用程序。我们的数值研究证明了所提出的解决方案及其性能优势在减少壁钟时间的基于梯度和/或投影的资源分配算法中的功效。

在分布式深度学习的背景下，陈旧的权重或梯度的问题可能导致算法性能差。这个问题通常通过延迟耐受算法来解决，并在目标函数和步进尺寸上有一些温和的假设。在本文中，我们提出了一种不同的方法来开发一种新算法，称为$ \ textbf {p} $ redicting $ \ textbf {c} $ lipping $ \ textbf {a} $ synchronous $ \ textbf {s} textbf {g} $ radient $ \ textbf {d} $ escent（aka，pc-asgd）。具体而言，PC -ASGD有两个步骤 - $ \ textIt {预测步骤} $利用泰勒扩展利用梯度预测来减少过时的权重的稳固性，而$ \ textit {clivipping step} $选择性地降低了过时的权重，以减轻过时的权重他们的负面影响。引入权衡参数以平衡这两个步骤之间的影响。从理论上讲，考虑到平滑的物镜函数弱键和非凸的延迟延迟的延迟，我们介绍了收敛速率。还提出了一种实用的PC-ASGD变体，即采用条件来帮助确定权衡参数。对于经验验证，我们在两个基准数据集上使用两个深神经网络体系结构演示了该算法的性能。

分散和联合学习的关键挑战之一是设计算法，这些算法有效地处理跨代理商的高度异构数据分布。在本文中，我们在数据异质性下重新审视分散的随机梯度下降算法（D-SGD）的分析。我们在D-SGD的收敛速率上展示了新数量的关键作用，称为\ emph {邻居异质性}。通过结合通信拓扑结构和异质性，我们的分析阐明了这两个分散学习中这两个概念之间的相互作用较低。然后，我们认为邻里的异质性提供了一种自然标准，可以学习数据依赖性拓扑结构，以减少（甚至可以消除）数据异质性对D-SGD收敛时间的有害影响。对于与标签偏度分类的重要情况，我们制定了学习这样一个良好拓扑的问题，例如我们使用Frank-Wolfe算法解决的可拖动优化问题。如一组模拟和现实世界实验所示，我们的方法提供了一种设计稀疏拓扑的方法，可以在数据异质性下平衡D-SGD的收敛速度和D-SGD的触电沟通成本。

在线优化是一个完善的优化范式，旨在鉴于对以前的决策任务的正确答案，旨在做出一系列正确的决策。二重编程涉及一个分层优化问题，其中所谓的外部问题的可行区域受内部问题的解决方案集映射的限制。本文将这两个想法汇总在一起，并研究了在线双层优化设置，其中一系列随时间变化的二聚体问题又一个接一个地揭示了一个。我们将已知的单层在线算法的已知遗憾界限扩展到双重设置。具体而言，我们引入了新的杂种遗憾概念，开发了一种在线交替的时间平均梯度方法，该方法能够利用光滑度，并根据内部和外部极型序列的长度提供遗憾的界限。

我们通过两种类型 - 主/工人（因此集中）架构（因此集中）架构和网格化（因此分散）网络，研究（强）凸起（强）凸起（强）凸起的鞍点问题（SPPS）的解决方案方法。由于统计数据相似度或其他，假设每个节点处的本地功能是相似的。我们为求解SPP的相当一般算法奠定了较低的复杂性界限。我们表明，在$ \ omega \ big（\ delta \ cdot \ delta / \ mu \ cdot \ log（1 / varepsilon）\ big）$ rounds over over over exoptimally $ \ epsilon> 0 $ over over master / workers网络通信，其中$ \ delta> 0 $测量本地功能的相似性，$ \ mu $是它们的强凸起常数，$ \ delta $是网络的直径。较低的通信复杂性绑定在网状网络上读取$ \ omega \ big（1 / {\ sqrt {\ rho}} \ cdot {\ delta} / {\ mu} \ cdot \ log（1 / varepsilon）\ big）$ ，$ \ rho $是用于邻近节点之间通信的八卦矩阵的（归一化）EIGENGAP。然后，我们提出算法与较低限制的网络（最多为日志因子）匹配。我们评估所提出的算法对强大的逻辑回归问题的有效性。

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

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

Federated learning is a distributed framework according to which a model is trained over a set of devices, while keeping data localized. This framework faces several systemsoriented challenges which include (i) communication bottleneck since a large number of devices upload their local updates to a parameter server, and (ii) scalability as the federated network consists of millions of devices. Due to these systems challenges as well as issues related to statistical heterogeneity of data and privacy concerns, designing a provably efficient federated learning method is of significant importance yet it remains challenging. In this paper, we present FedPAQ, a communication-efficient Federated Learning method with Periodic Averaging and Quantization. FedPAQ relies on three key features: (1) periodic averaging where models are updated locally at devices and only periodically averaged at the server; (2) partial device participation where only a fraction of devices participate in each round of the training; and (3) quantized messagepassing where the edge nodes quantize their updates before uploading to the parameter server. These features address the communications and scalability challenges in federated learning. We also show that FedPAQ achieves near-optimal theoretical guarantees for strongly convex and non-convex loss functions and empirically demonstrate the communication-computation tradeoff provided by our method.

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.

Most distributed machine learning systems nowadays, including TensorFlow and CNTK, are built in a centralized fashion. One bottleneck of centralized algorithms lies on high communication cost on the central node. Motivated by this, we ask, can decentralized algorithms be faster than its centralized counterpart?Although decentralized PSGD (D-PSGD) algorithms have been studied by the control community, existing analysis and theory do not show any advantage over centralized PSGD (C-PSGD) algorithms, simply assuming the application scenario where only the decentralized network is available. In this paper, we study a D-PSGD algorithm and provide the first theoretical analysis that indicates a regime in which decentralized algorithms might outperform centralized algorithms for distributed stochastic gradient descent. This is because D-PSGD has comparable total computational complexities to C-PSGD but requires much less communication cost on the busiest node. We further conduct an empirical study to validate our theoretical analysis across multiple frameworks (CNTK and Torch), different network configurations, and computation platforms up to 112 GPUs. On network configurations with low bandwidth or high latency, D-PSGD can be up to one order of magnitude faster than its well-optimized centralized counterparts.

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.

我们研究了具有大规模分布数据的机器学习模型问题的随机分散优化。我们扩展了以降低方差（VR）的广泛使用的额外和挖掘方法，并提出了两种方法：VR-Extra和VR挖掘。提出的VR-Extra需要$ o（（（\ kappa_s+n）\ log \ frac {1} {\ epsilon}）$随机梯度评估和$ o（（（\ kappa_b+kappa_c） } {\ epsilon}）$通信回合以达到Precision $ \ Epsilon $，这是非加速梯度型方法中最好的复杂性，其中$ \ kappa_s $和$ \ kappa_b $是随机条件和批次条件号和批次条件号和批次条件号和批次条件强烈凸和平滑问题的数字分别为$ \ kappa_c $是通信网络的条件编号，而$ n $是每个分布式节点上的样本大小。所提出的VR挖掘的通信成本更高，为$ O（（\ kappa_b+\ kappa_c^2）\ log \ frac {1} {\ epsilon}）$。我们的随机梯度计算复杂性与单机电VR方法（例如SAG，SAGA和SVRG）相同，我们的通信复杂性分别与额外的挖掘和挖掘相同。为了进一步加快收敛速度​​，我们还提出了加速的VR-Extra和VR挖掘，并使用最佳$ O（（（（\ sqrt {n \ kappa_s}+n）+log \ frac {1} {\ epsilon} {\ epsilon}）$随机梯度计算复杂度和$ O（\ sqrt {\ kappa_b \ kappa_c} \ log \ frac {1} {\ epsilon}）$ communication Complactity。我们的随机梯度计算复杂性也与单基加速的VR方法（例如Katyusha）相同，我们的通信复杂性与加速的全批次分散方法（例如MSDA）相同。

我们考虑一个多代理网络，其中每个节点具有随机（本地）成本函数，这取决于该节点的决策变量和随机变量，并且进一步的相邻节点的判定变量是成对受约束的。网络具有总体目标函数，其在节点处的本地成本函数的预期值ack，以及网络的总体目标是将该聚合目标函数的最小化解决方案最小化为所有成对约束。这将在节点级别使用分散的信息和本地计算来实现，其中仅具有相邻节点允许的压缩信息的交换。该文件开发算法，并在节点上获得两个不同型号的本地信息可用性模型的性能界限：（i）样本反馈，其中每个节点可以直接访问局部随机变量的样本，以评估其本地成本，（ii）babrit反馈，其中无随机变量的样本不可用，但只有每个节点可用的两个随机点处的本地成本函数的值可用。对于两种模型，具有邻居之间的压缩通信，我们开发了分散的骑马点算法，从没有通信压缩的那些没有不同（符号意义）的表现;具体而言，我们表明，与全局最小值和违反约束的偏差是由$ \ mathcal {o}的大约限制（t ^ { - \ frac {1} {2}}）$和$ \ mathcal {o} （t ^ { - \ frac {1} {4}}）分别为$ t $是迭代次数。本文中提供的数值例子证实了这些界限并证明了所提出的方法的通信效率。

为了通过分布式在线学习中的本地光计算处理复杂的约束，最近的一项研究提出了一种称为分布式在线条件梯度（D-OCG）的无投影算法（D-OCG），并获得了$ O（T^{3/4}）$遗憾的是凸出损失，其中$ t $是总回合的数量。但是，它需要$ t $通信回合，并且不能利用强大的损失凸度。在本文中，我们提出了一个改进的D-OCG的变体，即D-BOCG，可以达到相同的$ O（t^{3/4}）$遗憾，只有$ o（\ sqrt {t}）$凸损失的通信回合，以及$ o（t^{2/3}（\ log t）^{1/3}）$的更好遗憾，少于$ o（t^{1/3}（\ log log） t）^{2/3}）$通信回合，以实现强烈凸出的损失。关键思想是采用延迟的更新机制，以降低通信复杂性，并重新定义D-OCG中的替代损失功能以利用强凸度。此外，我们提供了下限，以证明D-BOCG所需的$ O（\ sqrt {t}）$通信回合是最佳的（以$ t $为单位）实现$ O（T^{3/4} ）$遗憾带有凸损失，以及$ o（t^{1/3}（\ log t）^{2/3}）$ d-bocg所需的通信回合近距离）实现$ o（t^{2/3}（\ log t）^{1/3}）$遗憾的是，强烈凸出的损失归属于多凝集因子。最后，为了处理更具挑战性的强盗设置，其中只有损失值可用，我们将经典的单点梯度估计器纳入D-BOCG，并获得类似的理论保证。

个性化联合学习（PFL）最近看到了巨大的进步，允许设计新颖的机器学习应用来保护培训数据的隐私。该领域的现有理论结果主要关注分布式优化以实现最小化问题。本文是第一个研究马鞍点问题的PFL（涵盖更广泛的优化问题），允许更丰富的应用程序，需要更多地解决最小化问题。在这项工作中，我们考虑最近提出的PFL设置与混合目标函数，一种方法将全球模型与当地分布式学习者相结合的方法。与最先前的工作不同，这仅考虑集中设置，我们在更一般和分散的设置中工作，允许我们设计和分析将设备连接到网络的更实用和联合的方法。我们提出了新的算法来解决这个问题，并在随机和确定性案例中提供平滑（强）凸起（强）凹凸点问题的理论分析。双线性问题的数值实验和对抗噪声的神经网络展示了所提出的方法的有效性。

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

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.