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

On Maintaining Linear Convergence of distributed Learning and Optimization Under Limited Communication

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年 68卷 6101-6116页

作者： Magnusson, Sindri Shokri-Ghadikolaei, Hossein Li, Na Harvard Univ Dept Elect Engn Har Cambridge MA 02138 USA Stockholm Univ Dept Comp & Syst Sci S-16455 Stockholm Sweden KTH Royal Inst Technol S-10044 Stockholm Sweden Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Harvard John A Paulson Sch Engn & Appl Sci Cambridge MA 02138 USA

In distributed optimization and machine learning, multiple nodes coordinate to solve large problems. To do this, the nodes need to compress important algorithm information to bits so that it can be communicated over a digital channel. The communication time of these algorithms follows a complex interplay between a) the algorithm's convergence properties, b) the compression scheme, and c) the transmission rate offered by the digital channel. We explore these relationships for a general class of linearly convergent distributed algorithms. In particular, we illustrate how to design quantizers for these algorithms that compress the communicated information to a few bits while still preserving the linear convergence. Moreover, we characterize the communication time of these algorithms as a function of the available transmission rate. We illustrate our results on learning algorithms using different communication structures, such as decentralized algorithms where a single master coordinates information from many workers and fully distributed algorithms where only neighbours in a communication graph can communicate. We conclude that a co-design of machine learning and communication protocols are mandatory to flourish machine learning over networks.

关键词： Signal processing algorithms Convergence Optimization distributed algorithms Quantization (signal) Machine learning algorithms Program processors Optimization machine learning quantization communication

来源：评论

学校读者我要写书评

暂无评论

distributed Online VAR Control for Unbalanced Distribution Networks With Photovoltaic Generation

引用

IEEE TRANSACTIONS ON SMART GRID 2020年第6期11卷 4760-4772页

作者： Li, Jiayong Liu, Chengying Khodayar, Mohammad E. Wang, Ming-Hao Xu, Zhao Zhou, Bin Li, Canbing Hunan Univ Coll Elect & Informat Engn Changsha 410082 Peoples R China Southern Methodist Univ Dept Elect & Comp Engn Dallas TX 75275 USA Hong Kong Polytech Univ Dept Elect Engn Hong Kong Peoples R China Shanghai Jiao Tong Univ Dept Elect Engn Shanghai 200240 Peoples R China

The unbalanced nature of the distribution networks (DNs) and communication asynchrony pose considerable challenges to the distributed voltage regulation. In this paper, two distributed voltage control algorithms are proposed to overcome these challenges in multiphase unbalanced DNs. The proposed algorithms can be leveraged in online implementations to cope with the fast-varying system operating conditions. By adopting the linearized multiphase DistFlow model, the voltage control problem is formulated as a convex quadratic programming problem for which a synchronous distributed algorithm is developed based on the dual ascent method. To account for communication delays, an asynchronous distributed algorithm is proposed evolving from the synchronous one by incorporating an event-triggered communication protocol. Furthermore, closed-form solutions to the optimization subproblems are derived to enhance the computational efficiency, and communication complexity is reduced significantly to the extent that only neighborhood information exchange is required. Finally, the convergence of the proposed algorithms to the global optimality is established analytically. Numerical tests on the IEEE 123-bus network not only corroborate that our proposed algorithms are more efficient in eliminating voltage violations and minimizing network loss compared with two benchmarks but also validate their effectiveness for online implementations.

关键词： Voltage control Reactive power distributed algorithms Delays Distribution networks Optimization Mathematical model Distribution networks multiphase unbalance online voltage control synchronous and asynchronous distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Power-Aware Allocation of Graph Jobs in Geo-distributed Cloud Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2020年第4期31卷 749-765页

作者： Hosseinalipour, Seyyedali Nayak, Anuj Dai, Huaiyu North Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA

In the era of big-data, the jobs submitted to the clouds exhibit complicated structures represented by graphs, where the nodes denote the sub-tasks each of which can be accommodated at a slot in a server, while the edges indicate the communication constraints among the sub-tasks. We develop a framework for efficient allocation of graph jobs in geo-distributed cloud networks (GDCNs), explicitly considering the power consumption of the datacenters (DCs). We address the following two challenges arising in graph job allocation: i) the allocation problem belongs to NP-hard nonlinear integer programming;ii) the allocation requires solving the NP-complete sub-graph isomorphism problem, which is particularly cumbersome in large-scale GDCNs. We develop a suite of efficient solutions for GDCNs of various scales. For small-scale GDCNs, we propose an analytical approach based on convex programming. For medium-scale GDCNs, we develop a distributed allocation algorithm exploiting the processing power of DCs in parallel. Afterward, we provide a novel low-complexity (decentralized) sub-graph extraction method, based on which we introduce cloud crawlers aiming to extract allocations of good potentials for large-scale GDCNs. Given these suggested strategies, we further investigate strategy selection under both fixed and adaptive DC pricing schemes, and propose an online learning algorithm for each.

关键词： Resource management Cloud computing Power demand Servers Task analysis Twitter distributed algorithms Big-data graph jobs geo-distributed cloud networks datacenter power consumption job allocation integer programming convex optimization online learning

来源：评论

学校读者我要写书评

暂无评论

Privacy-Preserving distributed Maximum Consensus

引用

IEEE SIGNAL PROCESSING LETTERS 2020年 27卷 1839-1843页

作者： Venkategowda, Naveen K. D. Werner, Stefan Norwegian Univ Sci & Technol Dept Elect Syst N-7491 Trondheim Norway

We propose a privacy-preserving distributed maximum consensus algorithm where the local state of the agents and identity of the maximum state owner is kept private from adversaries. To that end, we reformulate the maximum consensus problem over a distributed network as a linear program. This optimization problem is solved in a distributed manner using the alternating direction method of multipliers (ADMM) and perturbing the primal update step with Gaussian noise. We define the privacy of an agent as the estimation error of its local state at the adversary and obtain theoretical bounds on the privacy loss for the proposed method. Further, we prove that the proposed algorithm converges to the maximum value at all agents. In addition to the analytical results, we illustrate the convergence speed and privacy-accuracy trade-off through numerical simulations.

关键词： Privacy Nickel Signal processing algorithms Optimization Linear programming Convex functions Gaussian noise ADMM consensus distributed algorithms privacy

来源：评论

学校读者我要写书评

暂无评论

Lyapunov Criterion for Stochastic Systems and Its Applications in distributed Computation

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第2期65卷 546-560页

作者： Qin, Yuzhen Cao, Ming Anderson, Brian B. O. Univ Groningen Fac Sci & Engn Inst Engn & Technol NL-9747 AG Groningen Netherlands Hangzhou Dianzi Univ Sch Automat Hangzhou 310018 Peoples R China Data61 CSIRO Canberra ACT 2601 Australia Australian Natl Univ Res Sch Elect Energy & Mat Engn Canberra ACT 2601 Australia

This paper presents new sufficient conditions for convergence and asymptotic or exponential stability of a stochastic discrete-time system, under which the constructed Lyapunov function always decreases in expectation along the system's solutions after a finite number of steps, but without necessarily strict decrease at every step, in contrast to the classical stochastic Lyapunov theory. As the first application of this new Lyapunov criterion, we look at the product of any random sequence of stochastic matrices, including those with zero diagonal entries, and obtain sufficient conditions to ensure the product almost surely converges to a matrix with identical rows;we also show that the rate of convergence can be exponential under additional conditions. As the second application, we study a distributed network algorithm for solving linear algebraic equations. We relax existing conditions on the network structures, while still guaranteeing the equations are solved asymptotically.

关键词： Agreement distributed algorithms products of stochastic matrices Stochastic Lyapunov functions

来源：评论

学校读者我要写书评

暂无评论

distributed Algorithm Design for Nonsmooth Resource Allocation Problems

引用

IEEE TRANSACTIONS ON CYBERNETICS 2020年第7期50卷 3208-3217页

作者： Deng, Zhenhua Nian, Xiaohong Hu, Chen Cent South Univ Sch Automat Changsha 410075 Peoples R China Rocket Force Univ Engn Res Lab 101 Xian 710025 Peoples R China

This paper investigates resource allocation problems, where the cost functions of agents are nonsmooth and the decisions of agents are constrained by heterogeneous local constraints and network resource constraints. We design a distributed subgradient-based algorithm to achieve the optimal resource allocation. Moreover, we analyze the convergence of the algorithm to the optimal solution. The algorithm can solve resource allocation problems with strongly convex cost functions and weight-balanced digraphs, as well as resource allocation problems with strictly convex cost functions and connected undirected graphs. With the algorithm, the decisions of all agents asymptotically converge to the optimal allocation. Simulation examples verify the effectiveness of the algorithm.

关键词： Resource management Cost function Convergence distributed algorithms Eigenvalues and eigenfunctions Cybernetics distributed optimization nonsmooth analysis resource allocation subgradient-based algorithms weight-balanced digraphs

来源：评论

学校读者我要写书评

暂无评论

distributed Pareto Optimization for Large-Scale Noisy Subset Selection

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2020年第4期24卷 694-707页

作者： Qian, Chao Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210023 Peoples R China Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230027 Peoples R China

Subset selection, aiming to select the best subset from a ground set with respect to some objective function, is a fundamental problem with applications in many areas, such as combinatorial optimization, machine learning, data mining, computer vision, information retrieval, etc. Along with the development of data collection and storage, the size of the ground set grows larger. Furthermore, in many subset selection applications, the objective function evaluation is subject to noise. We thus study the large-scale noisy subset selection problem in this paper. The recently proposed DPOSS algorithm based on multiobjective evolutionary optimization is a powerful distributed solver for large-scale subset selection. Its performance, however, has been only validated in the noise-free environment. In this paper, we first prove its approximation guarantee under two common noise models, i.e., multiplicative noise and additive noise, disclosing that the presence of noise degrades the performance of DPOSS largely. Next, we propose a new distributed multiobjective evolutionary algorithm called DPONSS for large-scale noisy subset selection. We prove that the approximation guarantee of DPONSS under noise is significantly better than that of DPOSS. We also conduct experiments on the application of sparse regression, where the objective evaluation is often estimated using a sample data, bringing noise. The results on various real-world data sets, whose size can reach millions, clearly show the excellent performance of DPONSS.

关键词： Linear programming Noise measurement Approximation algorithms Optimization Greedy algorithms Additive noise distributed algorithms distributed algorithms experimental studies large-scale multiobjective evolutionary algorithms (MOEAs) noise Pareto optimization subset selection theoretical analyses

来源：评论

学校读者我要写书评

暂无评论

Broadcast distributed voting algorithm in population protocols

引用

IET SIGNAL PROCESSING 2020年第10期14卷 846-853页

作者： Bandealinaeini, Hamidreza Salehkaleybar, Saber Sharif Univ Technol Dept Elect Engn Tehran Iran

The authors consider the problem of multi-choice majority voting in a network of n agents where each agent initially selects a choice from a set of K possible choices. The agents try to infer the choice in the majority merely by performing local interactions. Extending the popular 'Population Protocol' framework for pairwise interactions between agents, in this study, they propose a new model called 'Broadcasting Population Protocol'. In the proposed model, each agent broadcasts its messages in such a way that all its neighbours will receive the message simultaneously. They design two distributed algorithms for solving the multi-choice majority voting problem in this new model. They show that these algorithms return the correct output, i.e. the choice in the majority. They also analyse their performances in terms of time and message complexities. They establish via simulations that the proposed algorithms improve both time and message complexities significantly with respect to previous algorithms proposed in conventional population protocols, and they can be utilised in networks where messages can be transmitted to a subset of agents simultaneously, such as wireless networks.

关键词： communication complexity protocols distributed algorithms broadcast communication message passing multichoice majority voting problem pairwise interactions Broadcasting Population Protocol broadcast distributed voting algorithm population protocol framework wireless networks

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Decentralized Accelerated Stochastic Gradient Descent

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY

引用

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2021年第2期2卷 802-811页

作者： Lan, Guanghui Zhou, Yi Georgia Inst Technol Dept Ind & Syst Engn Atlanta GA 30332 USA IBM Almaden Res Ctr AI Secur & Privacy Solut San Jose CA 95120 USA

In this paper, we introduce an asynchronous decentralized accelerated stochastic gradient descent type of algorithm for decentralized stochastic optimization. Considering communication and synchronization costs are the major bottlenecks for decentralized optimization, we attempt to reduce these costs from an algorithmic design aspect, in particular, we are able to reduce the number of agents involved in one round of update via randomization. Our major contribution is to develop a class of accelerated randomized decentralized algorithms for solving general convex composite problems. We establish O(1/epsilon) (resp., O(1/root epsilon)) communication complexity and O(1/epsilon(2)) (resp., O(1/epsilon)) sampling complexity for solving general convex (resp., strongly convex) problems. It worths mentioning that our proposing algorithm only sublinear depends on the Lipschitz constant if there is a smooth component presented in the objective function. Moreover, we also conduct some preliminary numerical experiments to demonstrate the advantages of our proposing algorithms over the state-of-the-art synchronous decentralized algorithm.

关键词： distributed algorithms machine learning algorithms gradient methods decentralized control

来源：评论

学校读者我要写书评

暂无评论

A Novel distributed Algorithm for Phase Synchronization in Unmanned Aerial Vehicles

引用

IEEE COMMUNICATIONS LETTERS 2020年第10期24卷 2260-2264页

作者： Pourranjbar, Ali Baniasadi, Mohammadamin Abbasfar, Aliazam Kaddoum, Georges Ecole Technol Super LaCIME Lab Dept Elect Engn Montreal PQ H3C 0J9 Canada Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA Univ Tehran Fac Elect & Comp Engn Tehran 14305 Iran

In this letter, the problem of phase synchronization for a group of drones acting as relays to build a connection between a base station (BS) and a ground receiver (GR) is investigated. The received signal strength (RSS) of the GR significantly degrades due to phase-mismatch caused by mobility of the drones. To tackle this challenge, a distributed synchronization algorithm that utilizes a few feedbacks is proposed and its convergence is proved for a specified bound on the frequency deviation. To evaluate the performance of the proposed method, the received signal strength (RSS) of the GR is presented assuming different deviation frequencies and number of drones. Provided simulation results demonstrate that our proposed method is capable of synchronizing the drones' phases for all the considered deviation frequencies and number of drones. Moreover, the proposed method outperforms the existing cumulative positive one-bit feedback based approaches in terms of convergence speed and RSS, which renders the proposed algorithm viable for practical deployment.

关键词： Drones Synchronization Relays Convergence distributed algorithms Frequency synchronization Drones one-bit feedback phase synchronization distributed nodes synchronization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：