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

本文着重于随机鞍点问题的分布式优化。本文的第一部分专门针对平滑（强）（强）（强）凹形鞍点问题以及实现这些结合的近乎最佳算法的平滑（强）凸出的凹点鞍点问题的平滑（强）凸出的（强）凸出的凸出鞍点问题。接下来，我们提出了一种新的联合算法，用于分布式鞍点问题 - 额外的步骤本地SGD。对新方法的理论分析是针对强烈凸出的凹形和非convex-non-concave问题进行的。在本文的实验部分中，我们在实践中显示了方法的有效性。特别是，我们以分布方式训练甘恩。

我们通过两种类型 - 主/工人（因此集中）架构（因此集中）架构和网格化（因此分散）网络，研究（强）凸起（强）凸起（强）凸起的鞍点问题（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。然后，我们提出算法与较低限制的网络（最多为日志因子）匹配。我们评估所提出的算法对强大的逻辑回归问题的有效性。

近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加，我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始，显示一般非凸面问题无法在合理的时间内有效地解决。然后，我们提供了一个问题列表，可以通过利用问题的结构来有效地找到全球最小化器，因为可能的问题。处理非凸性的另一种方法是放宽目标，从找到全局最小，以找到静止点或局部最小值。对于该设置，我们首先为确定性一阶方法的收敛速率提出了已知结果，然后是最佳随机和随机梯度方案的一般理论分析，以及随机第一阶方法的概述。之后，我们讨论了非常一般的非凸面问题，例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能，这仍然允许获得一阶的理论融合保证方法。然后，我们考虑更高阶和零序/衍生物的方法及其收敛速率，以获得非凸优化问题。

联合学习（FL）是机器学习的一个子领域，在该子机学习中，多个客户试图在通信约束下通过网络进行协作学习模型。我们考虑在二阶功能相似性条件和强凸度下联合优化的有限和联合优化，并提出了两种新算法：SVRP和催化的SVRP。这种二阶相似性条件最近越来越流行，并且在包括分布式统计学习和差异性经验风险最小化在内的许多应用中得到满足。第一种算法SVRP结合了近似随机点评估，客户采样和降低方差。我们表明，当功能相似性足够高时，SVRP是沟通有效的，并且在许多现有算法上取得了卓越的性能。我们的第二个算法，催化的SVRP，是SVRP的催化剂加速变体，在二阶相似性和强凸度下，现有的联合优化算法可实现更好的性能，并均匀地改善了现有的算法。在分析这些算法的过程中，我们提供了可能具有独立关注的随机近端方法（SPPM）的新分析。我们对SPPM的分析很简单，允许进行近似近端评估，不需要任何平滑度假设，并且在通信复杂性上比普通分布式随机梯度下降显示出明显的好处。

联邦学习（FL）是一种越来越受欢迎的机器学习范式，其中多个节点在隐私，通信和多个异质性约束下尝试协同学习。联邦学习中的持续存在问题是，不清楚优化目标应该：监督学习的标准平均风险最小化在处理联合学习的几个主要限制方面是不充分的，例如沟通适应性和个性化控制。我们在联合学习的框架中识别几个关键的Desiderata，并介绍了一个新的框架，Flix，考虑到联合学习所带来的独特挑战。 Flix具有标准的有限和形式，使从业者能够利用分布式优化的现有（潜在非本地）方法的巨大财富。通过不需要任何通信的智能初始化，Flix不需要使用本地步骤，但仍然可以通过本地方法执行不一致的正则化。我们提供了几种用于在通信约束下有效解决FLIX制剂的算法。最后，我们通过广泛的实验证实了我们的理论结果。

受到Mishchenko等人（2022）的最新突破的启发，他们首次表明局部梯度步骤可以导致可证明的通信加速，我们提出了一种替代算法，该算法获得了与他们的方法相同的通信加速度（Proxsskip）。但是，我们的方法非常不同：它基于Chambolle和Pock（2011）的著名方法，并具有多种不平凡的修改：i）我们允许通过适当的强烈凸出功能的代理操作员进行不精确的计算。基于梯度的方法（例如，GD，Fast GD或FSFOM），ii）我们对双重更新步骤进行仔细的修改，以保留线性收敛。我们的一般结果为强凸孔座鞍点问题提供了新的最先进率，其双线性耦合为特征，其特征是双重功能缺乏平滑度。当应用于联邦学习时，我们获得了Proxskip的理论上更好的替代方案：我们的方法需要更少的本地步骤（$ O（\ kappa^{1/3}）$或$ o（\ kappa^{1/4}）$，与Proxskip的$ O（\ kappa^{1/2}）$相比，并执行确定性的本地步骤。像Proxskip一样，我们的方法可以应用于连接网络的优化，我们在这里也获得了理论改进。

我们研究了具有大规模分布数据的机器学习模型问题的随机分散优化。我们扩展了以降低方差（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）相同。

我们提出了随机方差降低算法，以求解凸 - 凸座鞍点问题，单调变异不平等和单调夹杂物。我们的框架适用于Euclidean和Bregman设置中的外部，前向前后和前反向回复的方法。所有提出的方法都在与确定性的对应物相同的环境中收敛，并且它们要么匹配或改善了解决结构化的最低最大问题的最著名复杂性。我们的结果加强了变异不平等和最小化之间的差异之间的对应关系。我们还通过对矩阵游戏的数值评估来说明方法的改进。

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.

This study investigates clustered federated learning (FL), one of the formulations of FL with non-i.i.d. data, where the devices are partitioned into clusters and each cluster optimally fits its data with a localized model. We propose a novel clustered FL framework, which applies a nonconvex penalty to pairwise differences of parameters. This framework can automatically identify clusters without a priori knowledge of the number of clusters and the set of devices in each cluster. To implement the proposed framework, we develop a novel clustered FL method called FPFC. Advancing from the standard ADMM, our method is implemented in parallel, updates only a subset of devices at each communication round, and allows each participating device to perform a variable amount of work. This greatly reduces the communication cost while simultaneously preserving privacy, making it practical for FL. We also propose a new warmup strategy for hyperparameter tuning under FL settings and consider the asynchronous variant of FPFC (asyncFPFC). Theoretically, we provide convergence guarantees of FPFC for general nonconvex losses and establish the statistical convergence rate under a linear model with squared loss. Our extensive experiments demonstrate the advantages of FPFC over existing methods.

作为一个普遍的分布式学习范式，联邦学习（FL）训练了大量通信的大量设备的全球模型。本文研究了FL设置中的一类复合优化和统计恢复问题，其损失函数由数据依赖的平滑损耗和非平滑正常器组成。示例包括使用套索的稀疏线性回归，使用核标准正则化等等的低级矩阵恢复等。在现有文献中，联合复合优化算法仅从优化的角度设计，而无需任何统计保证。此外，他们不考虑在统计恢复问题中常用（受限）强凸度。从优化和统计角度来看，我们都会推进此问题的前沿。从优化的前期，我们提出了一种名为\ textit {快速联合双平均}的新算法，用于强烈凸出和平滑损失，并在复合设置中建立最新的迭代和通信复杂性。特别是，我们证明它具有快速的速度，线性加速和减少的沟通回合。从统计前期开始，对于受限制的强烈凸出和平滑损失，我们设计了另一种算法，即\ textIt {多阶段联合双重平均}，并证明了与线性加速绑定到最佳统计精度的高概率复杂性。合成数据和真实数据的实验表明，我们的方法的性能优于其他基线。据我们所知，这是为FL中复合问题提供快速优化算法和统计恢复保证的第一项工作。

在分散的学习中，节点网络协作以最小化通常是其本地目标的有限总和的整体目标函数，并结合了非平滑的正则化术语，以获得更好的泛化能力。分散的随机近端梯度（DSPG）方法通常用于培训这种类型的学习模型，而随机梯度的方差延迟了收敛速率。在本文中，我们提出了一种新颖的算法，即DPSVRG，通过利用方差减少技术来加速分散的训练。基本思想是在每个节点中引入估计器，该节点周期性地跟踪本地完整梯度，以校正每次迭代的随机梯度。通过将分散的算法转换为具有差异减少的集中内隙近端梯度算法，并控制错误序列的界限，我们证明了DPSVRG以o（1 / t）$的速率收敛于一般凸起目标加上非平滑术语以$ t $作为迭代的数量，而dspg以$ o（\ frac {1} {\ sqrt {t}}）$汇聚。我们对不同应用，网络拓扑和学习模型的实验表明，DPSVRG会收敛于DSPG的速度要快得多，DPSVRG的损耗功能与训练时期顺利降低。

本文是对解决平滑（强）单调随机变化不平等的方法的调查。首先，我们给出了随机方法最终发展的确定性基础。然后，我们回顾了通用随机配方的方法，并查看有限的总和设置。本文的最后部分致力于各种算法的各种（不一定是随机）的变化不平等现象。

从经验上证明，在跨客户聚集之前应用多个本地更新的实践是克服联合学习（FL）中的通信瓶颈的成功方法。在这项工作中，我们提出了一种通用食谱，即FedShuffle，可以更好地利用FL中的本地更新，尤其是在异质性方面。与许多先前的作品不同，FedShuffle在每个设备的更新数量上没有任何统一性。我们的FedShuffle食谱包括四种简单的功能成分：1）数据的本地改组，2）调整本地学习率，3）更新加权，4）减少动量方差（Cutkosky and Orabona，2019年）。我们对FedShuffle进行了全面的理论分析，并表明从理论和经验上讲，我们的方法都不遭受FL方法中存在的目标功能不匹配的障碍，这些方法假设在异质FL设置中，例如FedAvg（McMahan等人，McMahan等， 2017）。此外，通过将上面的成分结合起来，FedShuffle在Fednova上改善（Wang等，2020），以前提议解决此不匹配。我们还表明，在Hessian相似性假设下，通过降低动量方差的FedShuffle可以改善非本地方法。最后，通过对合成和现实世界数据集的实验，我们说明了FedShuffle中使用的四种成分中的每种如何有助于改善FL中局部更新的使用。

最近有利息线性编程（LP）的一阶方法。在本文中，我们提出了一种使用差异减少的随机算法，并重新启动，用于解决LP等尖锐的原始 - 双重问题。我们表明，所提出的随机方法表现出具有高概率的尖锐实例的线性收敛速率，这提高了现有的确定性和随机算法的复杂性。此外，我们提出了一个有效的基于坐标的随机甲骨文，用于无限制的双线性问题，它具有$ \ Mathcal O（1）$彼得迭代成本并改善总牌数量达到一定的准确性。

在本文中，我们提出\ texttt {fgpr}：一个联合高斯进程（$ \ mathcal {gp} $）回归框架，它使用了用于本地客户端计算的模型聚合和随机梯度血缘的平均策略。值得注意的是，由此产生的全局模型在个性化中excels作为\ texttt {fgpr}共同学习所有客户端之前的全局$ \ mathcal {gp} $。然后通过利用该本地数据来获得预测后的后退，并在从特定客户端编码个性化功能的本地数据获得。从理论上讲，我们显示\ texttt {fgpr}会聚到完整对数似然函数的关键点，但符合统计误差。通过广泛的案例研究，我们展示了\ TextTT {FGPR}在广泛的应用中擅长，并且是隐私保留多保真数据建模的有希望的方法。

The increasing size of data generated by smartphones and IoT devices motivated the development of Federated Learning (FL), a framework for on-device collaborative training of machine learning models. First efforts in FL focused on learning a single global model with good average performance across clients, but the global model may be arbitrarily bad for a given client, due to the inherent heterogeneity of local data distributions. Federated multi-task learning (MTL) approaches can learn personalized models by formulating an opportune penalized optimization problem. The penalization term can capture complex relations among personalized models, but eschews clear statistical assumptions about local data distributions. In this work, we propose to study federated MTL under the flexible assumption that each local data distribution is a mixture of unknown underlying distributions. This assumption encompasses most of the existing personalized FL approaches and leads to federated EM-like algorithms for both client-server and fully decentralized settings. Moreover, it provides a principled way to serve personalized models to clients not seen at training time. The algorithms' convergence is analyzed through a novel federated surrogate optimization framework, which can be of general interest. Experimental results on FL benchmarks show that our approach provides models with higher accuracy and fairness than state-of-the-art methods.

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

我们提出了一种在异质环境中联合学习的沟通有效方法。在存在$ k $不同的数据分布的情况下，系统异质性反映了，每个用户仅从$ k $分布中的一个中采样数据。所提出的方法只需要在用户和服务器之间进行一次通信，从而大大降低了通信成本。此外，提出的方法通过在样本量方面实现最佳的于点错误（MSE）率，即在异质环境中提供强大的学习保证相同的数据分布，前提是，每个用户的数据点数量高于我们从系统参数方面明确表征的阈值。值得注意的是，这是可以实现的，而无需任何了解基础分布，甚至不需要任何分布数量$ k $。数值实验说明了我们的发现并强调了所提出的方法的性能。