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

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第12期66卷 7835-7855页

作者： Acharya, Jayadev Canonne, Clement L. Tyagi, Himanshu Cornell Univ Dept Elect & Comp Engn Ithaca NY 14853 USA IBM Res Almaden CA 95120 USA Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India Indian Inst Sci Robert Bosch Ctr Cyberphys Syst Bengaluru 560012 India

Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels W, which can be instantiated to capture, among others, both the communication- and privacy-constrained settings. The referee uses the players' messages to solve an inference problem on the unknown distribution that generated the samples. We derive lower bounds for the sample complexity of learning and testing discrete distributions in this information-constrained setting. Underlying our bounds is a characterization of the contraction in chi-square distance between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both public- and private-coin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.

关键词： distributed algorithms inference algorithms statistical analysis minimax techniques parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Smoothed Analysis of Leader Election in distributed Networks 1

引用

22nd International Symposium on Stabilization, Safety, and Security of distributed Systems

作者： Molla, Anisur Rahaman Shur, Disha Indian Stat Inst Comp & Commun Sci Div Kolkata India Indian Stat Inst RC Bose Ctr Cryptol & Secur Kolkata India

ISBN: (数字)9783030643485

ISBN: (纸本)9783030643478;9783030643485

We study smoothed analysis of the leader election (LE) problem in distributed networks. Smoothed analysis is a hybrid between worst-case analysis and average-case analysis. It takes a worst-case instance for the algorithm and perturbs the input by adding some random noise and analyzes the algorithm on this perturbed input. We consider smoothed analysis, in which the topology of the input graph G is randomly perturbed by adding random edges to G. The complexity of the algorithm is parameterized by a smoothing parameter 0 <= epsilon(n) <= 1 which controls the amount of random edges to be added to the input graph G per round, where epsilon is a small function of n, e.g., n(-4) (n is the number of nodes in the graph G). Informally, epsilon is the probability that a random edge can be added to a node per round. We analyze the time and message complexity of leader election in the above smoothing model. We present the following three results in synchronous CONGEST distributed model: (i) A simple randomized algorithm that elects a leader with high probability (With high probability (or w.h.p. in short) means with probability >= 1 - 1/n.) in O((log n)/epsilon) rounds and uses O(root n log(2.5) n) messages. Note that both the time and the message bounds are optimal (up to a polylog n factor). (ii) A time-improved randomized algorithm that elects a leader with high probability in O(log n/root epsilon) rounds, but uses O(m + n log n) messages, where m is the number of edges in the input graph G. (iii) A deterministic algorithm (except the randomized smoothing part) which solves leader election in O(log(2) n/root epsilon) rounds and incurs O(m+n root epsilon log(2) n) messages. Our work extends the study of smoothed analysis of distributed problems one step further, an open direction raised by [7].

关键词： distributed algorithms Smoothed analysis Random model Leader election

来源：评论

学校读者我要写书评

暂无评论

An Efficient Routing Method for Range Queries in Skip Graph

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2020年第3期E103D卷 516-525页

作者： Banno, Ryohei Shudo, Kazuyuki Tokyo Inst Technol Tokyo 1528550 Japan

Skip Graph is a promising distributed data structure for large scale systems and known for its capability of range queries. Although several methods of routing range queries in Skip Graph have been proposed, they have inefficiencies such as a long path length or a large number of messages. In this paper, we propose a novel routing method for range queries named Split-Forward Broadcasting (SFB). SFB introduces a divide-and-conquer approach, enabling nodes to make full use of their routing tables to forward a range query. It brings about a shorter average path length than existing methods, as well as a smaller number of messages by avoiding duplicate transmission. We clarify the characteristics and effectiveness of SFB through both analytical and experimental comparisons. The results show that SFB can reduce the average path length roughly 30% or more compared with a state-of-the-art method.

关键词： Skip Graph overlay networks peer-to-peer networks routing algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A Sustainable Incentive Scheme for Federated Learning

引用

IEEE INTELLIGENT SYSTEMS 2020年第4期35卷 58-69页

作者： Yu, Han Liu, Zelei Liu, Yang Chen, Tianjian Cong, Mingshu Weng, Xi Niyato, Dusit Yang, Qiang Nanyang Technol Univ NTU Sch Comp Sci & Engn SCSE Singapore Singapore Nanyang Technol Univ Sch Comp Sci & Engn Sch Comp Sci & Engn SCSE Singapore Singapore WeBank AI Dept Shenzhen Peoples R China Univ Hong Kong FinTech & Blockchain Lab Dept Comp Sci Hong Kong Peoples R China Peking Univ Guanghua Sch Management Beijing Peoples R China Nanyang Technol Univ Singapore Singapore WeBank AI Shenzhen Peoples R China Hong Kong Univ Sci & Technol Hong Kong Peoples R China

In federated learning (FL), a federation distributedly trains a collective machine learning model by leveraging privacy preserving technologies. However, FL participants need to incur some cost for contributing to the FL models. The training and commercialization of the models will take time. Thus, there will be delays before the federation could pay back the participants. This temporary mismatch between contributions and rewards has not been accounted for by existing payoff-sharing schemes. To address this limitation, we propose the FL incentivizer (FLI). It dynamically divides a given budget in a context-aware manner among data owners in a federation by jointly maximizing the collective utility while minimizing the inequality among the data owners, in terms of the payoff received and the waiting time for receiving payoffs. Comparisons with five state-of-the-art payoff-sharing schemes show that FLI attracts high-quality data owners and achieves the highest expected revenue for a federation.

关键词： Games Data models Computational modeling Intelligent systems Training data Machine learning Collaborative work distributed algorithms Learning systems

来源：评论

学校读者我要写书评

暂无评论

The static parallel distribution algorithms for hybrid density-functional calculations in HONPAS package

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2020年第2期34卷 159-168页

作者： Qin, Xinming Shang, Honghui Xu, Lei Hu, Wei Yang, Jinlong Li, Shigang Zhang, Yunquan Univ Sci & Technol China Dept Chem Phys Hefei Natl Lab Phys Sci Microscale Hefei Anhui Peoples R China Univ Sci & Technol China Synerget Innovat Ctr Quantum Informat & Quantum P Hefei Anhui Peoples R China Chinese Acad Sci Inst Comp Technol State Key Lab Comp Architecture Beijing Peoples R China

Hybrid density-functional calculation is one of the most commonly adopted electronic structure theories in computational chemistry and materials science because of its balance between accuracy and computational cost. Recently, we have developed a novel scheme called NAO2GTO to achieve linear scaling (Order-N) calculations for hybrid density-functionals. In our scheme, the most time-consuming step is the calculation of the electron repulsion integrals (ERIs) part, so creating an even distribution of these ERIs in parallel implementation is an issue of particular importance. Here, we present two static scalable distributed algorithms for the ERIs computation. Firstly, the ERIs are distributed over ERIs shell pairs. Secondly, the ERIs are distributed over ERIs shell quartets. In both algorithms, the calculation of ERIs is independent of each other, so the communication time is minimized. We show our speedup results to demonstrate the performance of these static parallel distributed algorithms in the Hefei Order-N packages for ab initio simulations.

关键词： distributed algorithms hybrid density-functional calculations HONPAS package electron repulsion integrals parallel implementation

来源：评论

学校读者我要写书评

暂无评论

PALE: Time Bounded Practical Agile Leader Election

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2020年第2期31卷 470-485页

作者： Sidik, Bronislav Puzis, Rami Zilberman, Polina Elovici, Yuval Ben Gurion Univ Negev Dept Software & Informat Syst Engn Telekom Innovat Labs POB 653 IL-8410501 Beer Sheva Israel

Many tasks executed in dynamic distributed systems, such as sensor networks or enterprise environments with bring-your-own-device policy, require central coordination by a leader node. In the past it has been proven that distributed leader election in dynamic environments with constant changes and asynchronous communication is not possible. Thus, state-of-the-art leader election algorithms are not applicable in asynchronous environments with constant network changes. Some algorithms converge only after the network stabilizes (an unrealistic requirement in many dynamic environments). Other algorithms reach consensus in the presence of network changes but require a global clock or some level of communication synchrony. Determining the weakest assumptions, under which bounded leader election is possible, remains an unresolved problem. In this study we present a leader election algorithm that operates in the presence of changes and under weak (realistic) assumptions regarding message delays and regarding the clock drifts of the distributed nodes. The proposed algorithm is self-sufficient, easy to implement and can be extended to support multiple regions, self-stabilization, and mobile ad-hoc networks. We prove the algorithms correctness and provide a complexity analysis of the time, space, and number of messages required to elect a leader.

关键词： Heuristic algorithms Voting Delays Clocks Task analysis Stability criteria Leader election dynamic partial synchrony timed distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-Agent Motion Planning for Dense and Dynamic Environments via Deep Reinforcement Learning

引用

IEEE ROBOTICS AND AUTOMATION LETTERS 2020年第2期5卷 3221-3226页

作者： Semnani, Samaneh Hosseini Liu, Hugh Everett, Michael de Ruiter, Anton How, Jonathan P. Ryerson Univ Aerosp Engn Dept Toronto ON M5B 2K3 Canada Isfahan Univ Technol Dept Elect & Comp Engn Esfahan *** Iran Univ Toronto Fac Appl Sci & Engn Toronto ON M5S 1A1 Canada MIT Aerosp Controls Lab 77 Massachusetts Ave Cambridge MA 02139 USA

This letter introduces a hybrid algorithm of deep reinforcement learning (RL) and Force-based motion planning (FMP) to solve distributed motion planning problem in dense and dynamic environments. Individually, RL and FMP algorithms each have their own limitations. FMP is not able to produce time-optimal paths and existing RL solutions are not able to produce collision-free paths in dense environments. Therefore, we first tried improving the performance of recent RL approaches by introducing a new reward function that not only eliminates the requirement of a pre supervised learning (SL) step but also decreases the chance of collision in crowded environments. That improved things, but there were still a lot of failure cases. So, we developed a hybrid approach to leverage the simpler FMP approach in stuck, simple and high-risk cases, and continue using RL for normal cases in which FMP can't produce optimal path. Also, we extend GA3C-CADRL algorithm to 3D environment. Simulation results show that the proposed algorithm outperforms both deep RL and FMP algorithms and produces up to 50$\%$ more successful scenarios than deep RL and up to 75$\%$ less extra time to reach goal than FMP.

关键词： Motion planning distributed algorithms collision avoidance deep learning reinforcement learning trajectory optimization hybrid control

来源：评论

学校读者我要写书评

暂无评论

GHS algorithm on a graph with random weights

引用

THEORETICAL COMPUTER SCIENCE 2020年 828卷 19-31页

作者： Rybarczyk, Katarzyna Adam Mickiewicz Univ Fac Math & Comp Sci PL-60769 Poznan Poland

GHS algorithm is the classical distributed algorithm constructing a minimum spanning tree in a graph with weights assigned to its edges. We are interested in the average performance of GHS algorithm, i.e. time complexity of GHS algorithm on a random input. As a random input we choose a complete graph with randomly assigned weights. In the analysis we study some properties of the classical random graph process and a minimum degree graph process related to it. (C) 2020 Published by Elsevier B.V.

关键词： distributed algorithms Minimum spanning tree Random graph

来源：评论

学校读者我要写书评

暂无评论

Energy provision minimisation in large-scale wireless powered communication networks with throughput demand

引用

IET COMMUNICATIONS 2020年第3期14卷 458-465页

作者： Ge, Haijiang Yu, Zhanwei Chi, Kaikai Mao, Keji Shao, Qike Chen, Lijian Zhejiang Univ Technol Sch Comp Sci & Technol Hangzhou 310023 Zhejiang Peoples R China Hangzhou Vocat & Tech Coll Inst Informat Engn Hangzhou 310018 Zhejiang Peoples R China

So far, the research of wireless powered communication networks (WPCNs) mainly considers the scenarios with a single radio-frequency (RF) energy transmitter (ET) and a single sink. However, in practice, there are many applications where multiple ETs and sinks need to be deployed. This study focuses on large-scale WPCNs having multiple RF ETs and sinks. Specifically, the authors aim to minimise the total energy provision by optimising ETs' transmit powers with the node-throughput demand and sum-throughput demand, respectively. For the node-throughput demand case, they firstly formulate it to be a convex optimisation problem, then transform it to be a linear programming (LP) problem, and finally present a distributed algorithm to obtain the optimal solution. For the sum-throughput demand case, they firstly formulate it to be a non-linear optimisation problem, then prove its convexity and finally propose an efficient dual subgradient algorithm to obtain the optimal solution. Simulation results demonstrate that compared to the sum-throughput demand, imposing the node-throughput demand can effectively alleviate the throughput unfairness at the cost of increased energy provision;the proposed optimal algorithms can substantially decrease the total energy provision of ETs;the energy provision reduction percentage achieved by their schemes increases as the number of ETs increases.

关键词： inductive power transmission linear programming optimisation cooperative communication convex programming distributed algorithms resource allocation efficient dual subgradient algorithm optimal transmit power throughput unfairness problem increased energy provision total energy provision energy provision reduction percentage ETs increases energy provision minimisation wireless powered communication networks single radio-frequency energy transmitter single sink multiple ETs available power provision data collection schemes multiple RF ETs transmit power allocation large-scale WPCNs node-throughput demand case convex optimisation problem linear programming problem sum-throughput demand case nonlinear optimisation problem

来源：评论

学校读者我要写书评

暂无评论

High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年 68卷 2128-2142页

作者： Du, Yuqing Yang, Sheng Huang, Kaibin Univ Hong Kong Dept Elect & Elect Engn Hong Kong Peoples R China Univ Paris Saclay Cent Supelec Lab Signals & Syst Gif Sur Yvette 91190 France

Edge machine learning involves the deployment of learning algorithms at the wireless network edge so as to leverage massive mobile data for enabling intelligent applications. The mainstream edge learning approach, federated learning, has been developed based on distributed gradient descent. Based on the approach, stochastic gradients are computed at edge devices and then transmitted to an edge server for updating a global AI model. Since each stochastic gradient is typically high-dimensional, communication overhead becomes a bottleneck for edge learning. To address this issue, we propose a novel framework of hierarchical gradient quantization and study its effect on the learning performance. First, the framework features a practical hierarchical architecture for decomposing the stochastic gradient into its norm and normalized block gradients, and efficiently quantizes them using a uniform quantizer and a low-dimensional Grassmannian codebook, respectively. Subsequently, the quantized normalized block gradients are scaled and cascaded to yield the quantized normalized stochastic gradient using a socalled hinge vector, which is compressed using another low-dimensional Grassmannian quantizer designed under the criterion of minimum distortion. The other feature of the framework is a bit-allocation scheme for reducing the distortion, which divides the total quantization bits to determine the resolutions of low-dimensional quantizers. The framework is proved to guarantee model convergency by analyzing the convergence rate as a function of quantization bits. Furthermore, by simulation, our design is shown to substantially reduce the communication overhead compared with the state-of-the-art signSGD scheme, while achieving similar learning accuracies.

关键词： Vector quantization gradient methods learning (artificial intelligence) distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：