检索结果-内蒙古大学图书馆

Beyond Spectral Gap: The Role of the Topology in Decentralized Learning

JOURNAL OF MACHINE LEARNING RESEARCH 2023年 24卷

作者： Vogels, Thijs Hendrikx, Hadrien Jaggi, Martin Ecole Polytech Fed Lausanne Machine Learning & Optimizat Lab Lausanne Switzerland

In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them to use larger learning rates and optimize faster. In the decentralized setting, in which workers communicate over a sparse graph, current theory fails to capture important aspects of real-world behavior. First, the 'spectral gap' of the communication graph is not predictive of its empirical performance in (deep) learning. Second, current theory does not explain that collaboration enables larger learning rates than training alone. In fact, it prescribes smaller learning rates, which further decrease as graphs become larger, failing to explain convergence dynamics in infinite graphs. This paper aims to paint an accurate picture of sparsely-connected distributed optimization. We quantify how the graph topology influences convergence in a quadratic toy problem and provide theoretical results for general smooth and (strongly) convex objectives. Our theory matches empirical observations in deep learning, and accurately describes the relative merits of different graph topologies. This paper is an extension of the conference paper by Vogels et al. (2022). Code: ***/epfml/topology-in-decentralized-learning.

关键词： decentralized learning convex optimization stochastic gradient descent gossip algorithms spectral gap

来源：评论

学校读者我要写书评

暂无评论

Distributed primal-dual stochastic subgradient algorithms for multi-agent optimization under inequality constraints

引用

INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL 2013年第16期23卷 1846-1868页

作者： Yuan, Deming Xu, Shengyuan Zhang, Baoyong Rong, Lina Nanjing Univ Sci & Technol Sch Automat Nanjing 210094 Jiangsu Peoples R China

We consider the multi-agent optimization problem where multiple agents try to cooperatively optimize the sum of their local convex objective functions, subject to global inequality constraints and a convex constraint set over a network. Through characterizing the primal and dual optimal solutions as the saddle points of the associated Lagrangian function, which can be evaluated with stochastic errors, we propose the distributed primal-dual stochastic subgradient algorithms for two cases: (i) the time model is synchronous and (ii) the time model is asynchronous. In the first case, we obtain bounds on the convergence properties of the algorithm for a diminishing step size. In the second case, for a constant step size, we establish some error bounds on the algorithm's performance. In particular, we prove that the error bounds scale as n root n in the number of n agents. Copyright (c) 2012 John Wiley & Sons, Ltd.

关键词： multi-agent systems convex optimization subgradient methods distributed average consensus gossip algorithms

来源：评论

学校读者我要写书评

暂无评论

Beyond spectral gap: the role of the topology in decentralized learning

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2023年第1期24卷 17074-17104页

作者： Thijs Vogels Hadrien Hendrikx Martin Jaggi Machine Learning and Optimization Laboratory EPFL Lausanne Switzerland

关键词： decentralized learning convex optimization stochastic gradient descent gossip algorithms spectral gap

来源：评论

学校读者我要写书评

暂无评论

Randomized gossiping with Unreliable Communication: Dependent or Independent Node Updates

Randomized Gossiping with Unreliable Communication: Dependen...

引用

IEEE Annual Conference on Decision and Control

作者： Guodong Shi Mikael Johansson Karl Henrik Johansson ACCESS Linnaeus Centre School of Electrical Engineering Royal Institute of Technology

ISBN: (纸本)9781467320658

This paper studies an asynchronous randomized gossip algorithm under unreliable communication. At each instance, two nodes are selected to meet with a given probability. When nodes meet, two unreliable communication links are established with communication in each direction succeeding with a time-varying probability. It is shown that two particularly interesting cases arise when these communication processes are either perfectly dependent or independent. Necessary and sufficient conditions on the success probability sequence are proposed to ensure almost sure consensus or ∈-consensus. Weak connectivity is required when the communication is perfectly dependent, while double connectivity is required when the communication is independent. Moreover, it is proven that with odd number of nodes, average preserving turns from almost forever (with probability one for all initial conditions) for perfectly dependent communication, to almost never (with probability zero for almost all initial conditions) for the independent case. This average preserving property does not hold true for general number of nodes. These results indicate the fundamental role the node interactions have in randomized gossip algorithms.

关键词： gossip algorithms Unreliable communication Consensus Convergence analysis Communication Research Odd number INITIAL CONDITIONS Ganglia Telecommunication links dependent variables gossip Dependent RANDOMISING

来源：评论

学校读者我要写书评

暂无评论

Adaptive event dissemination for peer-to-peer multiplayer online games 11

Adaptive event dissemination for peer-to-peer multiplayer on...

引用

Proceedings of the 4th International ICST Conference on Simulation Tools and Techniques

作者： Gabriele D'Angelo Stefano Ferretti Moreno Marzolla Università di Bologna Bologna Italy

ISBN: (纸本)9781936968008

In this paper we show that gossip algorithms may be effectively used to disseminate game events in Peer-to-Peer (P2P) Multiplayer Online Games (MOGs). Game events are disseminated through an overlay network. The proposed scheme exploits the typical behavior of players to tune the data dissemination. In fact, it is well known that users playing a MOG typically generate game events at a rate that can be approximated using some (game dependent) probability distribution. Hence, as soon as a given node experiences a reception rate, for messages coming from a given peer, which is lower than expected, it can send a stimulus to the neighbor that usually forwards these messages, asking it to increase its dissemination probability. Three variants of this approach will be studied. According to the first one, upon reception of a stimulus from a neighbor, a peer increases its dissemination probability towards that node irrespectively from the sender. In the second protocol a peer increases only the dissemination probability for a given sender towards all its neighbors. Finally, the third protocol takes into consideration both the sender and the neighbor in order to decide how to increase the dissemination probability. We performed extensive simulations to assess the efficacy of the proposed scheme, and based on the simulation results we compare the different dissemination protocols. The results confirm that adaptive gossip schemes are indeed effective and deserve further investigation.

关键词： multiplayer online games peer-to-peer gossip algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards Scaling Byzantine Consensus Using Random Network Topology And Multi-Signatures

Towards Scaling Byzantine Consensus Using Random Network Top...

引用

Blockchain, Robotics and AI for Networking Security Conference (BRAINS)

作者： Parth Anand Shukla Saeed Samet School of Computer Science University of Windsor Windsor Canada

ISBN: (数字)9781728170916

ISBN: (纸本)9781728170923

With the growing interest in the adaptation of blockchain technology into current technology stacks, the tech industry has engendered strong research motivation towards the scalability aspect of consortium blockchains to make its efficiency and performance at par with the existing industry standards. There has been a surge in developing efficient consensus algorithms leading to faster finality. But many of them do not scale well with an increase in nodes or have special requirements that overcompensate the underlying requirement for high scale adaptability of a simplistic and efficient consensus mechanism for consortium industry-ready blockchain deployments. This paper presents a study that approaches to scale byzantine consensus using random network topology and multi-signatures. Based on the experiments and evaluations it can be clearly stated that given study scales better with increasing network sizes with a reduction in throughput of the at minimal levels.

关键词： blockchain byzantine fault-tolerance cryptography gossip algorithms state machine replication cryptography Random Network Network topology Scale formation topology

来源：评论

学校读者我要写书评

暂无评论

Fast and privacy preserving distributed low-rank regression

Fast and privacy preserving distributed low-rank regression

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Hoi-To Wai Anna Scaglione Jean Lafond Eric Moulines School of ECEE Arizona State Univ. USA Institut Mines-Telecom Telecom ParisTech CNRS LTCI France CMAP Ecole Polytechnique Palaiseau France

ISBN: (纸本)9781509041183

This paper proposes a fast and privacy preserving distributed algorithm for handling low-rank regression problems with nuclear norm constraint. Traditional projected gradient algorithms have high computation costs due to their projection steps when they are used to solve these problems. Our gossip-based algorithm, called the fast DeFW algorithm, overcomes this issue since it is projection-free. In particular, the algorithm incorporates a carefully designed decentralized power method step to reduce the complexity by distributed computation over network. Meanwhile, privacy is preserved as the agents do not exchange the private data, but only a random projection of them. We show that the fast DeFW algorithm converges for both convex and non-convex losses. As an application example, we consider the low-rank matrix completion problem and provide numerical results to support our findings.

关键词： distributed optimization Frank-Wolfe algorithm gossip algorithms low-rank regression power method Fasting Privacy private data Regression (Psychology) Distribute algorithms

来源：评论

学校读者我要写书评

暂无评论

DATA INJECTION ATTACK ON DECENTRALIZED OPTIMIZATION

DATA INJECTION ATTACK ON DECENTRALIZED OPTIMIZATION

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Sissi Xiaoxiao Wu Hoi-To Wai Anna Scaglione Angelia Nedi? Amir Leshem Shenzhen University College of Information Engineering Shenzhen China School of ECEE Arizona State Univ. Tempe AZ USA Faculty of Engg. Bar-Ilan Univ. Israel

ISBN: (纸本)9781538646595

This paper studies the security aspect of gossip-based decentralized optimization algorithms for multi agent systems against data injection attacks. Our contributions are two-fold. First, we show that the popular distributed projected gradient method (by Nedi? et al.) can be attacked by coordinated insider attacks, in which the attackers are able to steer the final state to a point of their choosing. Second, we propose a metric that can be computed locally by the trustworthy agents processing their own iterates and those of their neighboring agents. This metric can be used by the trustworthy agents to detect and localize the attackers. We conclude the paper by supporting our findings with numerical experiments.

关键词： Decentralized optimization gossip algorithms data injection attack

来源：评论

学校读者我要写书评

暂无评论

Convergence Results in Distributed Kalman Filtering

Convergence Results in Distributed Kalman Filtering

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Soummya Kar Shuguang Cui H. Vincent Poor Jose M. F. Moura Department of EE Princeton University Princeton NJ 08544 Department of ECE Texas A&M University College Station TX 77843 Department of ECE Carnegie Mellon University Pittsburgh PA 15213

ISBN: (纸本)9781457705380

The paper studies the convergence properties of the estimation error processes in distributed Kalman filtering for potentially unstable linear dynamical systems. In particular, it is shown that, in a weakly connected communication network, there exist (randomized) gossip based information dissemination schemes leading to a stochastically bounded estimation error at each sensor for any non-zero rate gamma of intersensor communication (the rate gamma is defined to be the average number of inter-sensor communications per signal evolution epoch). A gossip-based information exchange protocol, the M-GIKF, is presented, in which sensors exchange estimates and aggregate observations at a rate gamma > 0, leading to desired convergence properties. Under the assumption of global (centralized) detectability of the signal/observation model (necessary for a centralized estimator having access to all sensor observations at all times to yield bounded estimation error), it is shown that the distributed M-GIKF leads to a stochastically bounded estimation error at each sensor. The conditional estimation error covariance sequence at each sensor is shown to evolve as a random Riccati equation (RRE) with Markov modulated switching. The RRE is analyzed through a random dynamical system (RDS) formulation, and the asymptotic estimation error at each sensor is characterized in terms of an associated invariant measure (mu)~(gamma) of the RDS.

关键词： Distributed Kalman filtering gossip algorithms Ran-dom Dynamical Systems Invariant Measure Sensors Estimation error Kalman filtering radio data systems Respiratory Distress Syndrome TST gene Converge networks(communications) Bounded Distribute DYNAMICAL SYSTEMS

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：