Distributionally Robust Optimization (DRO), which aims to find an optimal decision that minimizes the worst case cost over the ambiguity set of probability distribution, has been widely applied in diverse applications, e.g., network behavior analysis, risk management, etc. However, existing DRO techniques face three key challenges: 1) how to deal with the asynchronous updating in a distributed environment; 2) how to leverage the prior distribution effectively; 3) how to properly adjust the degree of robustness according to different scenarios. To this end, we propose an asynchronous distributed algorithm, named Asynchronous Single-looP alternatIve gRadient projEction (ASPIRE) algorithm with the itErative Active SEt method (EASE) to tackle the distributed distributionally robust optimization (DDRO) problem. Furthermore, a new uncertainty set, i.e., constrained D-norm uncertainty set, is developed to effectively leverage the prior distribution and flexibly control the degree of robustness. Finally, our theoretical analysis elucidates that the proposed algorithm is guaranteed to converge and the iteration complexity is also analyzed. Extensive empirical studies on real-world datasets demonstrate that the proposed method can not only achieve fast convergence, and remain robust against data heterogeneity as well as malicious attacks, but also tradeoff robustness with performance.

Bilevel optimization plays an essential role in many machine learning tasks, ranging from hyperparameter optimization to meta-learning. Existing studies on bilevel optimization, however, focus on either centralized or synchronous distributed setting. The centralized bilevel optimization approaches require collecting massive amount of data to a single server, which inevitably incur significant communication expenses and may give rise to data privacy risks. Synchronous distributed bilevel optimization algorithms, on the other hand, often face the straggler problem and will immediately stop working if a few workers fail to respond. As a remedy, we propose Asynchronous Distributed Bilevel Optimization (ADBO) algorithm. The proposed ADBO can tackle bilevel optimization problems with both nonconvex upper-level and lower-level objective functions, and its convergence is theoretically guaranteed. Furthermore, it is revealed through theoretic analysis that the iteration complexity of ADBO to obtain the $\epsilon$-stationary point is upper bounded by $\mathcal{O}(\frac{1}{{{\epsilon ^2}}})$. Thorough empirical studies on public datasets have been conducted to elucidate the effectiveness and efficiency of the proposed ADBO.

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.

由于其在数据隐私保护，有效的沟通和并行数据处理方面的好处，联邦学习（FL）近年来引起了人们的兴趣。同样，采用适当的算法设计，可以实现fl中收敛效应的理想线性加速。但是，FL上的大多数现有作品仅限于I.I.D.的系统。数据和集中参数服务器以及与异质数据集分散的FL上的结果仍然有限。此外，在完全分散的FL下，与数据异质性在完全分散的FL下，可以实现收敛的线性加速仍然是一个悬而未决的问题。在本文中，我们通过提出一种称为Net-Fleet的新算法，以解决具有数据异质性的完全分散的FL系统，以解决这些挑战。我们算法的关键思想是通过合并递归梯度校正技术来处理异质数据集，以增强FL（最初旨在用于通信效率）的本地更新方案。我们表明，在适当的参数设置下，所提出的净型算法实现了收敛的线性加速。我们进一步进行了广泛的数值实验，以评估所提出的净化算法的性能并验证我们的理论发现。

This paper studies the communication complexity of risk averse optimization over a network. The problem generalizes the well-studied risk-neutral finite-sum distributed optimization problem and its importance stems from the need to handle risk in an uncertain environment. For algorithms in the literature, there exists a gap in communication complexities for solving risk-averse and risk-neutral problems. We propose two distributed algorithms, namely the distributed risk averse optimization (DRAO) method and the distributed risk averse optimization with sliding (DRAO-S) method, to close the gap. Specifically, the DRAO method achieves the optimal communication complexity by assuming a certain saddle point subproblem can be easily solved in the server node. The DRAO-S method removes the strong assumption by introducing a novel saddle point sliding subroutine which only requires the projection over the ambiguity set $P$. We observe that the number of $P$-projections performed by DRAO-S is optimal. Moreover, we develop matching lower complexity bounds to show that communication complexities of both DRAO and DRAO-S are not improvable. Numerical experiments are conducted to demonstrate the encouraging empirical performance of the DRAO-S method.

To lower the communication complexity of federated min-max learning, a natural approach is to utilize the idea of infrequent communications (through multiple local updates) same as in conventional federated learning. However, due to the more complicated inter-outer problem structure in federated min-max learning, theoretical understandings of communication complexity for federated min-max learning with infrequent communications remain very limited in the literature. This is particularly true for settings with non-i.i.d. datasets and partial client participation. To address this challenge, in this paper, we propose a new algorithmic framework called stochastic sampling averaging gradient descent ascent (SAGDA), which i) assembles stochastic gradient estimators from randomly sampled clients as control variates and ii) leverages two learning rates on both server and client sides. We show that SAGDA achieves a linear speedup in terms of both the number of clients and local update steps, which yields an $\mathcal{O}(\epsilon^{-2})$ communication complexity that is orders of magnitude lower than the state of the art. Interestingly, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact a control-variate-free special version of SAGDA, we immediately arrive at an $\mathcal{O}(\epsilon^{-2})$ communication complexity result for FSGDA. Therefore, through the lens of SAGDA, we also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.

最近，由于这些问题与一些新兴应用的相关性，最近有许多研究工作用于开发有效算法，以解决理论收敛的保证。在本文中，我们提出了一种统一的单环交替梯度投影（AGP）算法，用于求解平滑的非convex-（强烈）凹面和（强烈）凸出 - 非concave minimax问题。 AGP采用简单的梯度投影步骤来更新每次迭代时的原始变量和双变量。我们表明，它可以在$ \ MATHCAL {O} \ left（\ Varepsilon ^{ - 2} \ right）$（rep. $ \ Mathcal {O} \ left）中找到目标函数的$ \ VAREPSILON $ -STAIMATARY点。 （\ varepsilon ^{ - 4} \ right）$）$迭代，在nonconvex-strongly凹面（resp。nonconvex-concave）设置下。此外，获得目标函数的$ \ VAREPSILON $ -STAIMATARY的梯度复杂性由$ \ Mathcal {o} \ left（\ varepsilon ^{ - 2} \ right）界限O} \ left（\ varepsilon ^{ - 4} \ right）$在强烈的convex-nonconcave（resp。，convex-nonconcave）设置下。据我们所知，这是第一次开发出一种简单而统一的单环算法来解决非convex-（强烈）凹面和（强烈）凸出 - 非concave minimax问题。此外，在文献中从未获得过解决后者（强烈）凸线 - 非孔孔的最小问题的复杂性结果。数值结果表明所提出的AGP算法的效率。此外，我们通过提出块交替近端梯度（BAPG）算法来扩展AGP算法，以求解更通用的多块非块非conmooth nonmooth nonmooth noncovex-（强）凹面和（强烈）convex-nonconcave minimax问题。我们可以在这四个不同的设置下类似地建立所提出算法的梯度复杂性。

在许多机器学习应用程序中出现了非convex-concave min-max问题，包括最大程度地减少一组非凸函数的最大程度，并对神经网络的强大对抗训练。解决此问题的一种流行方法是梯度下降（GDA）算法，不幸的是，在非凸性的情况下可以表现出振荡。在本文中，我们引入了一种“平滑”方案，该方案可以与GDA结合以稳定振荡并确保收敛到固定溶液。我们证明，稳定的GDA算法可以实现$ O（1/\ epsilon^2）$迭代复杂性，以最大程度地减少有限的非convex函数收集的最大值。此外，平滑的GDA算法达到了$ O（1/\ epsilon^4）$ toseration复杂性，用于一般的nonconvex-concave问题。提出了这种稳定的GDA算法的扩展到多块情况。据我们所知，这是第一个实现$ o（1/\ epsilon^2）$的算法，用于一类NonConvex-Concave问题。我们说明了稳定的GDA算法在健壮训练中的实际效率。

当今部署在边缘网络上的联合学习（FL）系统由大量在数据和/或计算能力中具有高度异质性的工人组成，这些工人要求在时间，努力，数据异质性等方面参加灵活的工作者参与为了满足灵活的工人参与的需求，我们考虑了一种新的FL范式，称为“无政府状态联邦学习”（AFL）（AFL）。与常规FL模型形成鲜明对比的是，AFL中的每个工人都可以自由选择i）何时参加FL，ii）根据当前情况（例如，电池，通信，电池级别，通信渠道，隐私问题）。但是，AFL中这种混乱的工人行为在算法设计中引发了许多新的开放问题。特别是，尚不清楚是否可以开发收敛的AFL训练算法，如果是的，则在什么条件下以及可实现的收敛速度的速度下。为此，我们提出了两种无政府状态的联合平均（AFA）算法，分别命名为AFA-CD和AFA-CS的跨设备和跨核心设置的双向学习率。令人惊讶的是，我们表明，在轻度的无政府状态假设下，这两种AFL算法都达到了最著名的收敛速率，作为常规FL的最新算法。此外，它们保留了新的AFL范式中的工人数量和本地步骤，保留了高度可取的{\ em线性加速效应}。我们通过对现实世界数据集进行广泛的实验来验证提出的算法。

用于解决具有量化消息传递的实际边缘计算系统中的一般机器学习（ML）问题的联邦学习（FL）算法的最佳设计仍然是一个打开问题。本文考虑了服务器和工人在发送消息之前具有不同的计算和通信能力以及使用量化的优势计算系统。为了探讨这种优势计算系统中的FL的全部潜力，我们首先介绍一般的FL算法，即GenQSGD，由全局和局部迭代，迷你批量大小和步骤尺寸序列参数化。然后，我们分析其对任意步长序列的融合，并指定三个常用的步大规则下的收敛结果，即常数，指数和递减的步长规则。接下来，我们优化算法参数，以最小化时间约束和收敛误差约束下的能量成本，重点是FL的整体实施过程。具体地，对于在每个考虑的步长规则下的任何给定的步骤尺寸序列，我们优化全局和本地迭代和迷你批量大小的数量，以最佳地实现具有预设步长序列的应用程序的FL。我们还优化了步骤序列以及这些算法参数，以探索FL的全部潜力。由此产生的优化问题是具有非可分性约束函数的非凸面问题。我们提出了使用通用内近似（GIA）的迭代算法来获得KKT点和用于解决互补几何编程（CGP）的技巧。最后，我们用现有的FL算法用优化的算法参数进行了数值展示了GenQSGD的显着收益，并揭示了最佳地设计了一般FL算法的重要性。

Federated learning (FL) has emerged as an instance of distributed machine learning paradigm that avoids the transmission of data generated on the users' side. Although data are not transmitted, edge devices have to deal with limited communication bandwidths, data heterogeneity, and straggler effects due to the limited computational resources of users' devices. A prominent approach to overcome such difficulties is FedADMM, which is based on the classical two-operator consensus alternating direction method of multipliers (ADMM). The common assumption of FL algorithms, including FedADMM, is that they learn a global model using data only on the users' side and not on the edge server. However, in edge learning, the server is expected to be near the base station and have direct access to rich datasets. In this paper, we argue that leveraging the rich data on the edge server is much more beneficial than utilizing only user datasets. Specifically, we show that the mere application of FL with an additional virtual user node representing the data on the edge server is inefficient. We propose FedTOP-ADMM, which generalizes FedADMM and is based on a three-operator ADMM-type technique that exploits a smooth cost function on the edge server to learn a global model parallel to the edge devices. Our numerical experiments indicate that FedTOP-ADMM has substantial gain up to 33\% in communication efficiency to reach a desired test accuracy with respect to FedADMM, including a virtual user on the edge server.

在许多机器学习应用中，在许多移动或物联网设备上生成大规模和隐私敏感数据，在集中位置收集数据可能是禁止的。因此，在保持数据本地化的同时估计移动或物联网设备上的参数越来越吸引人。这种学习设置被称为交叉设备联合学习。在本文中，我们提出了第一理论上保证的跨装置联合学习设置中的一般Minimax问题的算法。我们的算法仅在每轮训练中只需要一小部分设备，这克服了设备的低可用性引入​​的困难。通过在与服务器通信之前对客户端执行多个本地更新步骤，并利用全局梯度估计来进一步减少通信开销，并利用全局梯度估计来校正由数据异质性引入的本地更新方向上的偏置。通过基于新型潜在功能的开发分析，我们为我们的算法建立了理论融合保障。 AUC最大化，强大的对抗网络培训和GAN培训任务的实验结果展示了我们算法的效率。

大规模凸孔concave minimax问题在许多应用中出现，包括游戏理论，强大的培训和生成对抗网络的培训。尽管它们的适用性广泛，但使用现有的随机最小值方法在大量数据的情况下，有效，有效地解决此类问题是具有挑战性的。我们研究了一类随机最小值方法，并开发了一种沟通效率的分布式随机外算法Localadaseg，其自适应学习速率适合在参数 - 服务器模型中求解凸Conconcove minimax问题。 Localadaseg具有三个主要功能：（i）定期沟通策略，可降低工人与服务器之间的通信成本； （ii）在本地计算并允许无调实现的自适应学习率； （iii）从理论上讲，在随机梯度的估计中，相对于主要差异项的几乎线性加速在平滑和非平滑凸凸环设置中都证明了。 Localadaseg用于解决随机双线游戏，并训练生成的对抗网络。我们将localadaseg与几个用于最小问题的现有优化者进行了比较，并通过在均质和异质环境中的几个实验来证明其功效。

SGD在分布式和多GPU系统上的实现创建了新的漏洞，可以通过一个或多个对抗代理来识别和滥用这些漏洞。最近，已经显示出众所周知的拜占庭式弹性梯度聚集方案确实容易受到可以定制攻击的知情攻击者的影响（Fang等，2020; Xie等，2020b）。我们介绍了Mixtailor，这是一种基于聚合策略的随机化计划，使攻击者无法充分了解。确定性方案可以直接将其集成到混合式尾勒中，而无需引入任何其他超参数。随机化降低了强大的对手来量身定制其攻击的能力，而随之而来的随机聚合方案在性能方面仍然具有竞争力。对于IID和非IID设置，我们建立了几乎确定的融合保证，这些保证既比文献中可用的融合更强大，更一般。我们在各种数据集，攻击和设置中进行的实证研究验证了我们的假设，并表明当知名的拜占庭耐受性计划失败时，Mixtailor会成功辩护。

标准联合优化方法成功地适用于单层结构的随机问题。然而，许多当代的ML问题 - 包括对抗性鲁棒性，超参数调整和参与者 - 批判性 - 属于嵌套的双层编程，这些编程包含微型型和组成优化。在这项工作中，我们提出了\ fedblo：一种联合交替的随机梯度方法来解决一般的嵌套问题。我们在存在异质数据的情况下为\ fedblo建立了可证明的收敛速率，并引入了二聚体，最小值和组成优化的变化。\ fedblo引入了多种创新，包括联邦高级计算和降低方差，以解决内部级别的异质性。我们通过有关超参数\＆超代理学习和最小值优化的实验来补充我们的理论，以证明我们方法在实践中的好处。代码可在https://github.com/ucr-optml/fednest上找到。

我们提出了一种使用加权节点的联合学习方法，可以在其中修改权重以在单独的验证集上优化模型的性能。该问题被称为双重优化，其中内部问题是加权节点的联合学习问题，外部问题着重于基于从内部问题返回的模型的验证性能优化权重。沟通效率的联合优化算法旨在解决此双重优化问题。在遇到错误的假设下，我们分析了输出模型的概括性能，并识别我们的方法在理论上优于训练模型，而仅在本地训练和使用静态且均匀分布的权重进行联合学习。

亚当是训练深神经网络的最具影响力的自适应随机算法之一，即使在简单的凸面设置中，它也被指出是不同的。许多尝试，例如降低自适应学习率，采用较大的批量大小，结合了时间去相关技术，寻求类似的替代物，\ textit {etc。}，以促进Adam-type算法融合。与现有方法相反，我们引入了另一种易于检查的替代条件，这仅取决于基础学习率的参数和历史二阶时刻的组合，以确保通用ADAM的全球融合以解决大型融合。缩放非凸随机优化。这种观察结果以及这种足够的条件，对亚当的差异产生了更深刻的解释。另一方面，在实践中，无需任何理论保证，广泛使用了迷你ADAM和分布式ADAM。我们进一步分析了分布式系统中的批次大小或节点的数量如何影响亚当的收敛性，从理论上讲，这表明迷你批次和分布式亚当可以通过使用较大的迷你批量或较大的大小来线性地加速节点的数量。最后，我们应用了通用的Adam和Mini Batch Adam，具有足够条件来求解反例并在各种真实世界数据集上训练多个神经网络。实验结果完全符合我们的理论分析。

Emerging technologies and applications including Internet of Things (IoT), social networking, and crowd-sourcing generate large amounts of data at the network edge. Machine learning models are often built from the collected data, to enable the detection, classification, and prediction of future events. Due to bandwidth, storage, and privacy concerns, it is often impractical to send all the data to a centralized location. In this paper, we consider the problem of learning model parameters from data distributed across multiple edge nodes, without sending raw data to a centralized place. Our focus is on a generic class of machine learning models that are trained using gradientdescent based approaches. We analyze the convergence bound of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best trade-off between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment. The experimentation results show that our proposed approach performs near to the optimum with various machine learning models and different data distributions.

分布式机器学习实现可扩展性和计算卸载，但需要大量的通信。因此，分布式学习设置中的沟通效率是一个重要的考虑因素，尤其是当通信是无线且采用电池驱动设备时。在本文中，我们开发了一种基于审查的重球（CHB）方法，用于在服务器工作者体系结构中分布式学习。除非其本地梯度与先前传播的梯度完全不同，否则每个工人的自我审查员。 HB学习问题的显着实际优势是众所周知的，但是尚未解决降低通信的问题。 CHB充分利用HB平滑来消除报告的微小变化，并证明达到了与经典HB方法相当的线性收敛速率，以平滑和强烈凸出目标函数。 CHB的收敛保证在理论上是合理的，对于凸和非凸案。此外，我们证明，在某些情况下，至少可以消除所有通信的一半，而不会对收敛率产生任何影响。广泛的数值结果验证了CHB在合成和真实数据集（凸，非凸和非不同情况）上的通信效率。鉴于目标准确性，与现有算法相比，CHB可以显着减少通信数量，从而实现相同的精度而不减慢优化过程。

联合学习（FL）是一种保护隐私的范式，其中多个参与者共同解决机器学习问题而无需共享原始数据。与传统的分布式学习不同，FL的独特特征是统计异质性，即，跨参与者的数据分布彼此不同。同时，神经网络解释的最新进展已广泛使用神经切线核（NTK）进行收敛分析。在本文中，我们提出了一个新颖的FL范式，该范式由NTK框架赋予了能力。该范式通过传输比常规FL范式更具表现力的更新数据来解决统计异质性的挑战。具体而言，通过样本的雅各布矩阵，而不是模型的权重/梯度，由参与者上传。然后，服务器构建了经验内核矩阵，以更新全局模型，而无需明确执行梯度下降。我们进一步开发了一种具有提高沟通效率和增强隐私性的变体。数值结果表明，与联邦平均相比，所提出的范式可以达到相同的精度，同时将通信弹的数量减少数量级。