Privacy protection and nonconvexity are two challenging problems in decentralized optimization and learning involving sensitive data. Despite some recent advances addressing each of the two problems separately, no results have been reported that have theoretical guarantees on both privacy protection and saddle/maximum avoidance in decentralized nonconvex optimization. We propose a new algorithm for decentralized nonconvex optimization that can enable both rigorous differential privacy and saddle/maximum avoiding performance. The new algorithm allows the incorporation of persistent additive noise to enable rigorous differential privacy for data samples, gradients, and intermediate optimization variables without losing provable convergence, and thus circumventing the dilemma of trading accuracy for privacy in differential privacy design. More interestingly, the algorithm is theoretically proven to be able to efficiently { guarantee accuracy by avoiding} convergence to local maxima and saddle points, which has not been reported before in the literature on decentralized nonconvex optimization. The algorithm is efficient in both communication (it only shares one variable in each iteration) and computation (it is encryption-free), and hence is promising for large-scale nonconvex optimization and learning involving high-dimensional optimization parameters. Numerical experiments for both a decentralized estimation problem and an Independent Component Analysis (ICA) problem confirm the effectiveness of the proposed approach.
translated by 谷歌翻译
通过使多个代理在缺乏中央协调员的情况下合作解决全球优化问题,分散的随机优化在像机器学习,控制和传感器网络这样的多种多样的领域中,人们的注意力越来越多。由于相关数据通常包含敏感信息,例如用户位置和个人身份,因此在实施分散的随机优化时,隐私保护已成为至关重要的需求。在本文中,我们提出了一种分散的随机优化算法,即使在存在与量化幅度成正比的积极量化误差的情况下,该算法也能够保证可证明的收敛精度。该结果同时适用于凸面和非凸目标函数,使我们能够利用积极的量化方案来混淆共享信息,因此可以在不失去可证明的优化精度的情况下进行隐私保护。实际上,通过使用将任何值量化为三个数值级别的任何值的{随机}三元量化方案,我们在分散的随机优化中实现了基于量化的严格差异隐私,以前尚未报告。结合提出的量化方案,提出的算法首次确保了分散的随机优化中的严格差异隐私,而不会失去可证明的收敛精度。分布式估计问题以及基准计算机学习数据集上分散学习的数值实验的仿真结果证实了所提出方法的有效性。
translated by 谷歌翻译
在本文中,我们处理了一个通用分布式约束的在线学习问题,并在随着时间变化的网络上进行了隐私,其中考虑了一类不可分配的目标功能。在此设置下,每个节点仅控制全球决策变量的一部分,所有节点的目标是在时间范围内协作最小化全球目标,同时保证传输信息的安全性。对于此类问题,我们首先设计了一种新颖的通用算法框架,称为DPSDA,使用Laplace机制和双重平均方法的随机变体进行了差异性私有分布式在线学习。然后,我们建议在此框架下提出两种算法,称为DPSDA-C和DPSDA-PS。理论结果表明,两种算法都达到了预期的遗憾上度上限$ \ MATHCAL {O}(\ sqrt {t})$当目标函数是凸的时,它符合通过切割边缘算法来实现的最佳效用。最后,数值实验在现实世界和随机生成的数据集上都验证了我们算法的有效性。
translated by 谷歌翻译
非平滑的有限和最小化是机器学习中的一个基本问题。本文开发了一种具有随机重新洗牌的分布式随机近端梯度算法,以解决随着时变多代理网络的有限和最小化。目标函数是可分辨率凸起功能的总和和非平滑的正则化。网络中的每个代理通过本地信息更新具有恒定步长大小的局部变量,并协作以寻求最佳解决方案。我们证明了所提出的算法产生的局部变量估计实现共识,并且与$ \ mathcal {o}(\ frac {1} {t} + \ frac {1} {\SQRT {T}})$收敛率。此外,本文通过选择足够的阶梯尺寸,可以任意地小的目标函数的稳态误差。最后,提供了一些比较仿真来验证所提出的算法的收敛性能。
translated by 谷歌翻译
培训期间的对抗性攻击能够强烈影响多功能增强学习算法的性能。因此,非常希望增加现有算法,使得消除对抗对协作网络的对抗性攻击的影响,或者至少有界限。在这项工作中,我们考虑一个完全分散的网络,每个代理商收到本地奖励并观察全球州和行动。我们提出了一种基于弹性共识的演员 - 批评算法,其中每个代理估计了团队平均奖励和价值函数,并将关联的参数向量传送到其立即邻居。我们表明,在拜占庭代理人的存在下,其估算和通信策略是完全任意的,合作社的估计值会融合到有概率一体的有界共识值,条件是在附近的最多有$ H $拜占庭代理商每个合作社和网络都是$(2h + 1)$ - 强大。此外,我们证明,合作社的政策在其团队平均目标函数的局部最大化器周围汇聚在其团队平均目标函数的概率上,这是对渐关节转移变得稳定的普发因子的政策。
translated by 谷歌翻译
机器学习已开始在许多应用中发挥核心作用。这些应用程序中的许多应用程序通常还涉及由于设计约束(例如多元系统)或计算/隐私原因(例如,在智能手机数据上学习),这些数据集分布在多个计算设备/机器上。这样的应用程序通常需要以分散的方式执行学习任务,其中没有直接连接到所有节点的中央服务器。在现实世界中的分散设置中,由于设备故障,网络攻击等,节点容易出现未发现的故障,这可能会崩溃非稳固的学习算法。本文的重点是在发生拜占庭失败的节点的存在下对分散学习的鲁棒化。拜占庭故障模型允许故障节点任意偏离其预期行为,从而确保设计最健壮的算法的设计。但是,与分布式学习相反,对分散学习中拜占庭式的弹性的研究仍处于起步阶段。特别是,现有的拜占庭式分散学习方法要么不能很好地扩展到大规模的机器学习模型,要么缺乏统计收敛性可确保有助于表征其概括错误。在本文中,引入了一个可扩展的,拜占庭式的分散的机器学习框架,称为拜占庭的分散梯度下降(桥梁)。本文中还提供了强烈凸出问题和一类非凸问题的算法和统计收敛保证。此外,使用大规模的分散学习实验来确定桥梁框架是可扩展的,并且为拜占庭式弹性凸和非convex学习提供了竞争结果。
translated by 谷歌翻译
在分散的学习中,节点网络协作以最小化通常是其本地目标的有限总和的整体目标函数,并结合了非平滑的正则化术语,以获得更好的泛化能力。分散的随机近端梯度(DSPG)方法通常用于培训这种类型的学习模型,而随机梯度的方差延迟了收敛速率。在本文中,我们提出了一种新颖的算法,即DPSVRG,通过利用方差减少技术来加速分散的训练。基本思想是在每个节点中引入估计器,该节点周期性地跟踪本地完整梯度,以校正每次迭代的随机梯度。通过将分散的算法转换为具有差异减少的集中内隙近端梯度算法,并控制错误序列的界限,我们证明了DPSVRG以o(1 / t)$的速率收敛于一般凸起目标加上非平滑术语以$ t $作为迭代的数量,而dspg以$ o(\ frac {1} {\ sqrt {t}})$汇聚。我们对不同应用,网络拓扑和学习模型的实验表明,DPSVRG会收敛于DSPG的速度要快得多,DPSVRG的损耗功能与训练时期顺利降低。
translated by 谷歌翻译
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.
translated by 谷歌翻译
这项工作审查了旨在在通信约束下运行的自适应分布式学习策略。我们考虑一个代理网络,必须从持续观察流数据来解决在线优化问题。代理商实施了分布式合作策略,其中允许每个代理商与其邻居执行本地信息交换。为了应对通信约束,必须不可避免地压缩交换信息。我们提出了一种扩散策略,昵称为ACTC(适应 - 压缩 - 然后组合),其依赖于以下步骤:i)每个代理执行具有恒定步长大小的单独随机梯度更新的适应步骤; ii)一种压缩步骤,它利用最近引入的随机压缩操作员;和III)每个代理组合从其邻居接收的压缩更新的组合步骤。这项工作的区别要素如下。首先,我们专注于自适应策略,其中常数(而不是递减)阶梯大小对于实时响应非间断变化至关重要。其次,我们考虑一般的指导图表和左随机组合政策,使我们能够增强拓扑和学习之间的相互作用。第三,与对所有个人代理的成本职能承担强大的凸起的相关作品相比,我们只需要在网络水平的强大凸起,即使单个代理具有强凸的成本,剩余的代理商也不满足凸起成本。第四,我们专注于扩散(而不是共识)战略。在压缩信息的苛刻设置下,建立ACTC迭代在所需的优化器周围波动,在相邻代理之间交换的比特方面取得了显着的节省。
translated by 谷歌翻译
分析若干缔约方拥有的数据,同时在效用和隐私之间实现良好的权衡是联邦学习和分析的关键挑战。在这项工作中,我们介绍了一种新颖的差异隐私(LDP)的放松,自然地出现在完全分散的算法中,即,当参与者通过沿着网络图的边缘传播没有中央协调员的边缘交换信息时。我们呼叫网络DP的这种放松捕获了用户只有系统的本地视图。为了展示网络DP的相关性,我们研究了一个分散的计算模型,其中令牌在网络图上执行散步,并由接收它的方顺序更新。对于诸如实际求和,直方图计算和具有梯度下降的优化等任务,我们提出了在环和完整拓扑上的简单算法。我们证明,网络DP下我们算法的隐私式实用权折衷显着提高了LDP下可实现的内容(有时甚至与可信赖的策展人模型的效用)的可实现,首次显示正式隐私收益可以从中获得完全分散。我们的实验说明了通过随机梯度下降的分散训练方法的改进效用。
translated by 谷歌翻译
在本文中,我们考虑了分散的优化问题,在这些问题中,代理具有个人成本函数,以最大程度地减少受到子空间约束的约束,这些子空间约束需要整个网络的最小化器才能位于低维子空间中。这种约束的公式包括共识或单任务优化作为特殊情况,并允许更一般的任务相关性模型,例如多任务平滑度和耦合优化。为了应对沟通限制,我们提出并研究一种自适应分散策略,在该策略中,代理人在与邻居进行交流之前,使用差异随机量化器来压缩其估计。分析表明,在量化噪声的某些一般条件下,对于足够小的步长$ \ mu $,该策略在均方误差和平均比特率方面都是稳定的:通过减少$ \ mu $,可以将估计错误保持较小(按$ \ mu $)保持较小,而不会无限地增加比特率为$ \ mu \ rightarrow 0 $。模拟说明了理论发现和提议方法的有效性,表明可以实现分散学习,但仅需少量。
translated by 谷歌翻译
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.
translated by 谷歌翻译
在本文中,我们考虑了在$ 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(最多常数因素)匹配。
translated by 谷歌翻译
我们考虑一个多代理网络,其中每个节点具有随机(本地)成本函数,这取决于该节点的决策变量和随机变量,并且进一步的相邻节点的判定变量是成对受约束的。网络具有总体目标函数,其在节点处的本地成本函数的预期值ack,以及网络的总体目标是将该聚合目标函数的最小化解决方案最小化为所有成对约束。这将在节点级别使用分散的信息和本地计算来实现,其中仅具有相邻节点允许的压缩信息的交换。该文件开发算法,并在节点上获得两个不同型号的本地信息可用性模型的性能界限:(i)样本反馈,其中每个节点可以直接访问局部随机变量的样本,以评估其本地成本,(ii)babrit反馈,其中无随机变量的样本不可用,但只有每个节点可用的两个随机点处的本地成本函数的值可用。对于两种模型,具有邻居之间的压缩通信,我们开发了分散的骑马点算法,从没有通信压缩的那些没有不同(符号意义)的表现;具体而言,我们表明,与全局最小值和违反约束的偏差是由$ \ mathcal {o}的大约限制(t ^ { - \ frac {1} {2}})$和$ \ mathcal {o} (t ^ { - \ frac {1} {4}})分别为$ t $是迭代次数。本文中提供的数值例子证实了这些界限并证明了所提出的方法的通信效率。
translated by 谷歌翻译
近年来,由于它们在对点对点网络上的分散性学习问题(例如,多机构元学习,多机构的多方强化增强学习学习)上,分散的双层优化问题在网络和机器学习社区中引起了越来越多的关注。 ,个性化的培训和拜占庭的弹性学习)。但是,对于具有有限的计算和通信功能的对等网络上的分散式双层优化,如何实现低样本和通信复杂性是迄今为止尚未探索的两个基本挑战。在本文中,我们首次尝试研究了分别与外部和内部子问题相对应的非凸和强结构结构的分散双重优化问题。本文中我们的主要贡献是两倍: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})$在达到与确定算法相同的通信复杂性时。据我们所知,这项工作是第一个实现低样本和通信复杂性,以解决网络上的分散双层优化问题。我们的数值实验也证实了我们的理论发现。
translated by 谷歌翻译
本文涉及一种计算代理网络,旨在以分布式方式解决在线优化问题,即通过本地计算和通信,没有任何中央协调员。我们提出了具有自适应动量估计(GTADAM)分布式算法的梯度跟踪,其将梯度跟踪机制与梯度的第一和二阶动量估计相结合。该算法在线设置中分析了具有Lipschitz连续梯度的强凸起成本函数的在线设置。我们为动态遗憾提供了一个与初始条件相关的术语的动态遗憾的上限,以及与客观函数的时间变化有关的另一个术语。此外,在静态设置中保证了线性收敛速率。在从图像分类中,在(移动)目标定位问题上和随机优化设置中的时变分类问题测试该算法。在来自多智能经验学习的这些数值实验中,GTADAM优于最先进的分布式优化方法。
translated by 谷歌翻译
分散和联合学习的关键挑战之一是设计算法,这些算法有效地处理跨代理商的高度异构数据分布。在本文中,我们在数据异质性下重新审视分散的随机梯度下降算法(D-SGD)的分析。我们在D-SGD的收敛速率上展示了新数量的关键作用,称为\ emph {邻居异质性}。通过结合通信拓扑结构和异质性,我们的分析阐明了这两个分散学习中这两个概念之间的相互作用较低。然后,我们认为邻里的异质性提供了一种自然标准,可以学习数据依赖性拓扑结构,以减少(甚至可以消除)数据异质性对D-SGD收敛时间的有害影响。对于与标签偏度分类的重要情况,我们制定了学习这样一个良好拓扑的问题,例如我们使用Frank-Wolfe算法解决的可拖动优化问题。如一组模拟和现实世界实验所示,我们的方法提供了一种设计稀疏拓扑的方法,可以在数据异质性下平衡D-SGD的收敛速度和D-SGD的触电沟通成本。
translated by 谷歌翻译
我们研究了随机近似的分散变体,这是一种数据驱动的方法,用于在嘈杂的测量中找到操作员的根。一个具有自己的操作员和数据观察的代理网络,合作地通过分散的通信图找到了聚合操作员的固定点。我们的主要贡献是在从马尔可夫过程中采样时在每个代理下观察到的数据时,对这种分散的随机近似方法提供有限的时间分析;这种缺乏独立性使迭代率偏向和(可能)无限。在相当标准的假设下,我们表明所提出方法的收敛速率与样本是独立的基本相同,仅由对数因子的差异而不同,该对数因素是说明了马尔可夫过程的混合时间。我们的分析中的关键思想是引入一种新型的Razumikhin-Lyapunov函数,该功能是由用于分析延迟普通微分方程的稳定性的一种动机。我们还讨论了拟议方法在多代理系统中许多有趣的学习问题上的应用。
translated by 谷歌翻译
分散的优化在机器学习方面越来越受欢迎,其可伸缩性和效率。直观地,它也应提供更好的隐私保证,因为节点只能观察到网络图中其邻居发送的消息。但是,正式化和量化这一收益是具有挑战性的:现有结果通常仅限于当地差异隐私(LDP)保证忽略权力下放的优势。在这项工作中,我们介绍了成对网络差异隐私,这是一种放松的LDP,该隐藏率捕获了一个事实,即从节点$ u $到节点$ v $的隐私泄漏可能取决于它们在图中的相对位置。然后,我们分析局部噪声注入与固定和随机通信图上的(简单或随机)八卦方案的组合。我们还得出了一种差异化的分散优化算法,该算法在局部梯度下降步骤和八卦平均之间进行交替。我们的结果表明,我们的算法放大隐私保证是图表中节点之间距离的函数,与受信任策展人的隐私性权衡取舍相匹配,直到明确取决于图形拓扑的因素。最后,我们通过有关合成和现实世界数据集的实验来说明我们的隐私收益。
translated by 谷歌翻译
在联邦学习方案中,多方共同从其各自的数据中学习模型,有两个相互矛盾的目标是选择适当的算法。一方面,必须在存在\ textit {semi-honest}合作伙伴的情况下尽可能保持私人和敏感的培训数据,而另一方面,必须在不同方之间交换一定数量的信息学习实用程序。这样的挑战要求采用隐私的联合学习解决方案,该解决方案最大程度地提高了学习模型的效用,并维护参与各方的私人数据的可证明的隐私保证。本文说明了一个一般框架,即a)从统一信息理论的角度来制定隐私损失和效用损失之间的权衡,而b)在包括随机化,包括随机性,包括随机的机制,包括随机性,,包括随机性,,包括随机性,,包括随机性,,包括随机性,,包括随机性,,包括随机性,,包括随机性,包括随机性,,使用稀疏性和同态加密。结果表明,一般而言\ textit {没有免费的午餐来进行隐私 - 私人权衡取舍},并且必须用一定程度的降级效用进行保存隐私。本文中说明的定量分析可以作为实用联合学习算法设计的指导。
translated by 谷歌翻译