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

A Provably Communication-Efficient Asynchronous distributed Inference Method for Convex and Nonconvex Problems

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年 68卷 3325-3340页

作者： Ren, Jineng Haupt, Jarvis Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA

This paper proposes and analyzes a communication-efficient distributed optimization framework for general nonconvex nonsmooth signal processing and machine learning problems under an asynchronous protocol. At each iteration, worker machines compute gradients of a known empirical loss function using their own local data, and a master machine solves a related minimization problem to update the current estimate. We prove that for nonconvex nonsmooth problems, the proposed algorithm converges to a stationary point with a sublinear rate over the number of communication rounds, coinciding with the best theoretical rate that can be achieved for this class of problems. Linear convergence to a global minimum is established without any statistical assumptions on the local data for problems characterized by composite loss functions whose smooth part is strongly convex. Extensive numerical experiments verify that the performance of the proposed approach indeed improves - sometimes significantly - over other state-of-the-art algorithms in terms of total communication efficiency.

关键词： Signal processing algorithms Convergence Optimization distributed algorithms Machine learning Principal component analysis Network topology Communication-efficiency asynchronous distributed algorithm convergence nonconvex strongly convex

来源：评论

学校读者我要写书评

暂无评论

distributed Mixed-Integer Linear Programming via Cut Generation and Constraint Exchange

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第4期65卷 1456-1467页

作者： Testa, Andrea Rucco, Alessandro Notarstefano, Giuseppe Univ Salento Dept Engn I-73100 Lecce Italy Univ Bologna Dept Elect Elect & Informat Engn I-40136 Bologna Italy

Many problems of interest for cyber-physical network systems can be formulated as mixed-integer linear programs in which the constraints are distributed among the agents. In this paper, we propose a distributed algorithmic framework to solve this class of optimization problems in a peer-to-peer network with no coordinator and with limited computation and communication capabilities. At each communication round, agents locally solve a small linear program, generate suitable cutting planes, and communicate a fixed number of active constraints. Within the distributed framework, we first propose an algorithm that, under the assumption of integer-valued optimal cost, guarantees finite-time convergence to an optimal solution. Second, we propose an algorithm for general problems that provides a suboptimal solution up to a given tolerance in a finite number of communication rounds. Both algorithms work under asynchronous, directed, unreliable networks. Finally, through numerical computations, we analyze the algorithm scalability in terms of the network size. Moreover, for a multi-agent multi-task assignment problem, we show, consistently with the theory, its robustness to packet loss.

关键词： distributed algorithms Approximation algorithms Optimization Task analysis Mixed integer linear programming Peer-to-peer computing Convergence Cutting planes distributed optimization mixed-integer multi-agent multi-task assignment

来源：评论

学校读者我要写书评

暂无评论

Multi-MEC collaboration for VR video transmission: Architecture and cache algorithm design

引用

COMPUTER NETWORKS 2023年第1期234卷

作者： Chen, Luyao Tang, Yong Xia, Jingwen Chen, Siyang Zheng, Chengyu Lin, Hai Wang, Wenyong Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Sichuan Peoples R China China Telecom Corp Sichuan Branch Chengdu 610031 Sichuan Peoples R China Macau Univ Sci & Technol Taipa 999078 Macao Special A Peoples R China

Virtual Reality (VR) is becoming an important use case for 5G wireless networks, and Mobile Edge Computing (MEC) servers are being explored as a way to reduce VR video latency. To address the limited cache space of a single MEC server, this paper proposes dividing geographically close MEC servers into collaborative domains. A new VR video transmission architecture is designed after analyzing video compression *** proposed architecture splits the VR video into equal-sized tile files to simplify the cache problem and improve caching efficiency. However, the large number of different tile files presents a challenge. To address this, the paper proposes an optimized k-shortest paths (OKSP) algorithm with a time complexity of O((K & BULL;M+N)& BULL;M & BULL;log N), where K is the number of tiles that all M MEC servers can cache in the collaboration domain and N is the number of tile files. For extremely large-scale data cases, a greedy-based approximation algorithm is also proposed. The numerical results demonstrate the OKSP algorithm's excellent performance in solving large-scale data, outperforming other caching algorithms in experiments.

关键词： Virtual reality Mobile edge computing Multimedia communication distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient live exploration of a dynamic ring with mobile robots

引用

THEORETICAL COMPUTER SCIENCE 2023年 980卷

作者： Mandal, Subhrangsu Molla, Anisur Rahaman Moses, William K., Jr. Indian Inst Technol Indore Dept Comp Sci & Engn Indore India Indian Stat Inst Comp & Commun Sci Div Kolkata India Univ Durham Dept Comp Sci Durham England

The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One important requirement of exploration is the termination condition, i.e., the robots must know that exploration is completed. The problem of live exploration of a dynamic ring using mobile robots was recently introduced by Di Luna et al. [DC 2020]. More specifically, they studied the problem of live exploration in a dynamic ring and proposed multiple algorithms to solve this problem in the fully synchronous and semi-synchronous settings with various guarantees when 2 robots were involved. They also showed that, under certain assumptions, exploration of the ring using two robots was impossible. An important question left open was how the presence of 3 robots would affect the results. In this paper, we try to settle this question in a fully synchronous setting and also show how to extend our results to a semi-synchronous *** particular, we present algorithms for exploration with explicit termination using 3 robots in conjunction with either (i) unique IDs of the robots and edge crossing detection capability (i.e., two robots moving in opposite directions through an edge in the same round can detect each other), or (ii) access to randomness. The time complexity of our deterministic algorithm is asymptotically optimal. We also provide complementary impossibility results showing that there does not exist any explicit termination algorithm for 2 robots even when each robot has a unique ID, edge crossing detection capability, and access to randomness. The theoretical analysis and comprehensive simulations of our algorithm show the effectiveness and efficiency of the algorithm in dynamic rings. We also present an algorithm to achieve exploration with partial termination using 3 robots with unique IDs in the semi-synchronous setting, when r

关键词： Multi-agent systems Mobile robots Exploration Uniform deployment distributed algorithms Dynamic graph Ring graph

来源：评论

学校读者我要写书评

暂无评论

Near-Linear Time Leader Election in Multiagent Networks 25

Near-Linear Time Leader Election in Multiagent Networks

引用

Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems

作者： Ajay D. Kshemkalyani Manish Kumar Anisur Rahaman Molla Gokarna Sharma University of Illinois at Chicago Chicago IL USA Indian Institute of Technology Madras Chennai India Indian Statistical Institute Kolkata Kolkata India Kent State University Kent OH USA

ISBN: (纸本)9798400714269

Leader election is a fundamental and widely studied problem in distributed computing, traditionally explored in the message-passing model, where each node in a distributed network graph represents a static computational device that communicates with others by exchanging messages. This paper studies leader election in the agent-based network, in which the computational devices are modeled as relocatable or mobile agents that explore a graph and perform computations. Each node in the graph serves as a container or host for these mobile agents, and communication occurs between agents when they move to the same node. We consider the scenario where n agents are arbitrarily placed on the nodes of an anonymous, arbitrary n-node, m-edge graph G. The goal is for the agents to elect a leader such that one agent is designated as the leader, knowing it is the leader, while all other agents recognize they are not the leader. The objective is to minimize the time to elect the leader and memory usage per agent. Following the literature, we consider the synchronous setting where each agent performs its operations synchronously with others and hence the time complexity is measured in rounds. There exists a deterministic solution that elects a leader in O(m) rounds with O(nłog n) bits of memory at each agent in the agent-based network. In this paper, we present a deterministic algorithm that elects a leader in O(n łog2 n) rounds with each agent using only O(łog n) bits. This is a significant improvement, as the memory usage is optimal and the time complexity is almost linear in n (up to O(łog2 n) factor). Additionally, leveraging this leader election result, we provide improved time and/or memory bounds for four core distributed graph problems: minimum spanning tree, gathering, maximal independent set, and minimal dominating set.

关键词： distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Research on Pricing Method of Electric Vehicle Charging Pile Optimization Based on Particle Swarm Optimization Algorithm

Research on Pricing Method of Electric Vehicle Charging Pile...

引用

Electrical Automation and Artificial Intelligence (ICEAAI), International Conference on

作者： Yue Gan Lichun Tian Min Zheng Nan Ye State Grid Fujian Electric Power Co. LTD. Fuzhou Fujian China State Grid Fujian Electric Power Co. LTD. Marketing Service Center Fuzhou Fujian China

ISBN: (数字)9798331506797

ISBN: (纸本)9798331506803

In recent years, with the rapid expansion of electric vehicles, charging service market also rapid development, the construction of charging station operation will be dominated by the government gradually to various social capital in investment construction, different charging stations belonging to different charging station operators, in order to maximize their own interests, a competitive relationship between the charging stations. In order to solve the problem of multi-subject interest balance in the charging market scenario composed of multiple charging stations and multiple electric vehicle (EV) travelers, it is necessary to study the charging price pricing method of calculating the interest game of charging stations. Therefore, this paper proposes the EV charging pile pricing method optimized based on the particle swarm algorithm to solve the problem that the charging price pricing method cannot take into account the multi-party interests of charging stations and EV travelers.

关键词： Government Pricing Games Charging stations Electric vehicle charging Main-secondary Particle swarm optimization distributed algorithms Optimization Investment

来源：评论

学校读者我要写书评

暂无评论

Module Addition-Aware Dynamic Shape Recognition for Lattice-Based Modular Robots

Module Addition-Aware Dynamic Shape Recognition for Lattice-...

引用

IEEE Middle East and North Africa Communications Conference (MENACOMM)

作者： Jad Bassil Benoît Piranda Abdallah Makhoul Julien Bourgeois FEMTO-ST Institute CNRS Univ. Franche-Comté Montbéliard France

ISBN: (数字)9798331519957

ISBN: (纸本)9798331519964

Self-Reconfigurable Modular Robots typically consist of high number of modules with uniform docking interfaces, allowing them to transform into various shape. Recognizing the shape of such a system composed of hundreds of modules is a significant challenge. Given a new configuration, a modular robots system must be able to determine and update its shape dynamically and in a distributed manner. In a previous work, we developed an algorithm that identifies overlapping boxes to cover the entire robot configuration through message-passing, enabling robots to determine a representation of their current shape. However, this algorithm was static and did not react to changes in real time. In this paper, we introduce an updated shape recognition algorithm that dynamically and in real-time recognizes the addition of modules to update the shape description of the entire configuration using local information. The dynamic algorithm to update the shape description is tested in a simulated environment and compared to re-executing the shape recognition algorithm on the whole configuration. The results show the efficiency of our algorithm in updating the robot’s current shape in real time.

关键词： Shape Heuristic algorithms Transforms Africa Real-time systems distributed algorithms Robots

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Revisiting Lower Bounds for Two-Step Consensus 25

Brief Announcement: Revisiting Lower Bounds for Two-Step Con...

引用

Proceedings of the ACM Symposium on Principles of distributed Computing

作者： Fedor Ryabinin Alexey Gotsman Pierre Sutra IMDEA Software Institute Madrid Spain Universidad Politécnica de Madrid Madrid Spain Télécom SudParis Palaiseau France Inria Saclay Palaiseau France Institut Polytechnique de Paris Palaiseau France

ISBN: (纸本)9798400718854

A seminal result by Lamport shows that at least max{2e + f + 1, 2f + 1} processes are required to implement partially synchronous consensus that tolerates f process failures and can furthermore decide in two message delays under f failures. This lower bound is matched by the classical Fast Paxos protocol. However, more recent practical protocols, such as Egalitarian Paxos, provide two-step decisions with fewer processes, seemingly contradicting the lower bound. We show that this discrepancy arises because the classical bound requires two-step decisions under a wide range of scenarios, not all of which are relevant in practice. We propose a more pragmatic condition for which we establish tight bounds on the number of processes required. Interestingly, these bounds depend on whether consensus is implemented as an atomic object or a decision task. For consensus as an object, max{2e + f - 1, 2f + 1} processes are necessary and sufficient for two-step decisions, while for a task the tight bound is max{2e + f, 2f + 1}.

关键词： distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A Dual Approach for Optimal algorithms in distributed Optimization over Networks

A Dual Approach for Optimal Algorithms in Distributed Optimi...

引用

Information Theory and Applications Workshop, ITA

作者： César A. Uribe Soomin Lee Alexander Gasnikov Angelia Nedić Laboratory for Information and Decision Systems and the Institute for Data Systems and Society Massachusetts Institute of Technology Cambridge Massachusetts USA Yahoo! Research Sunnyvale California USA Moscow Institute of Physics and Technology and Institute for Information Transmission Moscow Oblast Russia School of Electrical Computer and Energy Engineering Arizona State University Tempe Arizona USA

ISBN: (数字)9781728141909

ISBN: (纸本)9781728188256

We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum Σ i=1 m f i (z) of functions over in a network. We provide complexity bounds for four different cases, namely: each function f is strongly convex and smooth, each function is either strongly convex or smooth, and when it is convex but neither strongly convex nor smooth. Our approach is based on the dual of an appropriately formulated primal problem, which includes a graph that models the communication restrictions. We propose distributed algorithms that achieve the same optimal rates as their centralized counterparts (up to constant and logarithmic factors), with an additional optimal cost related to the spectral properties of the network. Initially, we focus on functions for which we can explicitly minimize its Legendre-Fenchel conjugate, i.e., admissible or dual friendly functions. Then, we study distributed optimization algorithms for non-dual friendly functions, as well as a method to improve the dependency on the parameters of the functions involved. Numerical analysis of the proposed algorithms is also provided.

关键词： Smoothing methods Numerical analysis Convex functions Complexity theory distributed algorithms Optimization Convergence

来源：评论

学校读者我要写书评

暂无评论

distributed forward-backward (half) forward algorithms for generalized Nash equilibrium seeking

Distributed forward-backward (half) forward algorithms for g...

引用

European Control Conference (ECC)

作者： Barbara Franci Mathias Staudigl Sergio Grammatico Delft Center for System and Control TU Delft The Netherlands Department of Data Science and Knowledge Engineering Maastricht University The Netherlands

ISBN: (数字)9783907144022

ISBN: (纸本)9781728188133

We present two distributed algorithms for the computation of a generalized Nash equilibrium in monotone games. The first algorithm follows from a forward-backward-forward operator splitting, while the second, which requires the pseudo-gradient mapping of the game to be cocoercive, follows from the forward-backward-half-forward operator splitting. Finally, we compare them with the distributed, preconditioned, forward-backward algorithm via numerical experiments.

关键词： Games Nash equilibrium Cost function Couplings Symmetric matrices Europe distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：