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

A Two-timescale Primal-dual algorithm for Decentralized Optimization with Compression

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Liu, Haoming Yau, Chung-Yiu Wai, Hoi-To Dept. of Systems Engineering & Engineering Management The Chinese University of Hong Kong Hong Kong

This paper proposes a two-timescale compressed primal-dual (TiCoPD) algorithm for decentralized optimization with improved communication efficiency over prior works on primal-dual decentralized optimization. The algorithm is built upon the primal-dual optimization framework and utilizes a majorization-minimization procedure. The latter naturally suggests the agents to share a compressed difference term during the iteration. Furthermore, the TiCoPD algorithm incorporates a fast timescale mirror sequence for agent consensus on nonlinearly compressed terms, together with a slow timescale primal-dual recursion for optimizing the objective function. We show that the TiCoPD algorithm converges with a constant step size. It also finds an O(1/T) stationary solution after T iterations. Numerical experiments on decentralized training of a neural network validate the efficacy of TiCoPD algorithm. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

A relaxed proximal point algorithm with double-inertial effects for nonconvex equilibrium problems

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Tran, Van Nam Faculty of Applied Sciences Ho Chi Minh City University of Technology and Education Ho Chi Minh City Viet Nam

In this paper, we present a relaxation proximal point method with double inertial effects to approximate a solution of a non-convex equilibrium problem. We give global convergence results of the iterative sequence generated by our algorithm. Some known results are recovered as special cases of our results. Numerical test is given to support the theoretical findings. © 2025, CC BY.

关键词： consensus algorithm

AES-based Privacy Protection strategy of virtual power plant under blockchain

学校读者我要写书评

暂无评论

AES-based Privacy Protection strategy of virtual power plant...

IEEE Information Technology and Mechatronics Engineering Conference (ITOEC)

作者： Zhong Gan Yilong Chen Xianjiong Yao Chen Feng Ming Zhang State Grid Shanghai Electric Power Company China NARI Information & Communication Technology Co. Ltd Nanjing China

ISBN: (数字)9798331529482

ISBN: (纸本)9798331529499

As the energy structure shifts from fossil fuels to renewable energy, the energy industry is evolving towards decentralization and intelligence, with virtual power plants gradually gaining attention as a novel form of energy organization. However, virtual power plants still face significant challenges in data privacy protection when participating in electricity market transactions. To address the issue of privacy leakage, this paper proposes a privacy protection strategy for virtual power plants based on a blockchain integrated with the AES algorithm. Firstly, the AES algorithm is used to encrypt the transaction data information to ensure that the internal data of the virtual power plant is encrypted and protected during the calculation process. Second, the RBFT consensus algorithm is combined with blockchain technology for data storage and identity verification. Finally, through MATLAB simulations, the effectiveness of this algorithm in protecting privacy during transactions is demonstrated.

关键词： Privacy Data privacy Scalability consensus algorithm Virtual power plants Electricity supply industry Blockchains Encryption Protection Faces

Improved Sublinear algorithms for Classical and Quantum Graph Coloring

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ferber, Asaf Hardiman, Liam Chen, Xiaonan

We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree ∆. The first is a simple algorithm that extends the idea of Morris and Song to color graphs with maximum degree ∆ using ∆ + 1 colors. Combined with the greedy algorithm, it achieves an expected runtime of O(n3/2√log n) in the query model, improving on Assadi, Chen, and Khanna’s algorithm by a √log n factor in expectation. When we allow quantum queries to the graph, we can accelerate the first algorithm using Grover’s famous algorithm, resulting in a runtime of Õ(n4/3) quantum queries. Finally, we introduce a quantum algorithm for (1 + ∊)∆-coloring, achieving O(∊−1n5/4 log3/2 n) quantum queries, offering a polynomial improvement over the previous best bound by Morris and Song. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Distributed Training for Multi-Layer Neural Networks by consensus

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2020年第5期31卷 1771-1778页

作者： Liu, Bo Ding, Zhengtao Lv, Chen Univ Manchester Sch Elect & Elect Engn Manchester M13 9PL Lancs England Nanyang Technol Univ Sch Mech & Aerosp Engn Singapore 639798 Singapore

Over the past decade, there has been a growing interest in large-scale and privacy-concerned machine learning, especially in the situation where the data cannot be shared due to privacy protection or cannot be centralized due to computational limitations. Parallel computation has been proposed to circumvent these limitations, usually based on the master-slave and decentralized topologies, and the comparison study shows that a decentralized graph could avoid the possible communication jam on the central agent but incur extra communication cost. In this brief, a consensus algorithm is designed to allow all agents over the decentralized graph to converge to each other, and the distributed neural networks with enough consensus steps could have nearly the same performance as the centralized training model. Through the analysis of convergence, it is proved that all agents over an undirected graph could converge to the same optimal model even with only a single consensus step, and this can significantly reduce the communication cost. Simulation studies demonstrate that the proposed distributed training algorithm for multi-layer neural networks without data exchange could exhibit comparable or even better performance than the centralized training model.

关键词： Training Neural networks consensus algorithm Distributed databases Topology Convergence Network topology Backpropagation consensus distributed training graph theory Lyapunov

CSMCSM: Client-Server Model for Comprehensive Security in MANETs

学校读者我要写书评

暂无评论

INTERNATIONAL JOURNAL OF INFORMATION SECURITY AND PRIVACY 2021年第1期15卷 44-64页

作者： Salama, Hatem Mahmoud Abd El Mageed, Mohamed Zaki Salama, Gouda Ismail Mohamed Badran, Khaled Mahmoud Mil Tech Coll Cairo Egypt Al Azhar Univ Cairo Egypt

Many MANET research works are based on the popular informal definition that MANET is a wireless ad-hoc network that has neither infrastructure nor backbone and every network node is autonomous and moves depending on its mobility. Unfortunately, this definition pays no attention to the network servers that are essential in core-based, mission-critical, and military MANETs. In core-based MANETs, external intrusion detection systems (IDS) cannot detect internal Byzantine attacks;in addition, internal Byzantine fault tolerant (BFT) systems are unqualified to detect typical external wireless attack. Therefore, there is a real need to combine both internal and external mobile ad-hoc network (MANET) ID systems. Here, CSMCSM is presented as a two-level client server model for comprehensive security in MANETs that integrates internal and external attack detectors in one device. The internal component is based on a BFT consensus algorithm while the external component employs decision tree to classify the MANET attacks.

关键词： Byzantine Attack Byzantine Fault Tolerant Client Server Comprehensive Security consensus algorithm Decision Tree Classifier MANET Attacks Raft algorithm

ON FINE FLUCTUATIONS OF THE COMPLEXITY OF THE QUICKSELECT algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ischebeck, Jasper Neininger, Ralph Goethe University Frankfurt Institute of Mathematics Frankfurt A.M. 60629 Germany

The Quickselect algorithm (also called FIND) is a fundamental algorithm for selecting ranks or quantiles within a set of data. Grübel and Rösler showed that the number of key comparisons required by Quickselect considered as a process of the quantiles α ∈ [0,1] converges within a natural probabilistic model after normalization in distribution within the càdlàg space D[0,1] endowed with the Skorokhod metric. We show that the residual process in the latter convergence after normalization converges in distribution towards a mixture of Gaussian processes in D[0,1]. A similar result holds for the related algorithm QuickVal. Our method is applicable to other cost measures such as the number of swaps (key exchanges) required by Quickselect, or cost measures being based on key comparisons taking additionally into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions. For all the arising mixtures of Gaussian limit processes, we also discuss the Hölder continuity of their *** Codes 60F17, 68Q25, 68P10, 60C05 © 2024, CC BY.

关键词： consensus algorithm

Greediness is not always a vice: Efficient Discovery algorithms for Assignment Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Duvignau, Romaric Gillet, Noël Klasing, Ralf Chalmers University of Technology University of Gothenburg Sweden Univ. Orléans INSA Centre Val de Loire LIFO UR 4022 OrléansFR-45067 France CNRS LaBRI Université de Bordeaux Talence France

Finding a maximum-weight matching is a classical and well-studied problem in computer science, solvable in cubic time in general graphs. We consider the specialization called assignment problem where the input is a bipartite graph, and introduce in this work the "discovery" variant considering edge weights that are not provided as input but must be queried, requiring additional and costly computations. We develop here discovery algorithms aiming to minimize the number of queried weights while providing guarantees on the computed solution. We first show in this work the inherent challenges of designing discovery algorithms for general assignment problems. We then provide and analyze several efficient greedy algorithms that can make use of natural assumptions about the order in which the nodes are processed by the algorithms. Our motivations for exploring this problem stem from finding practical solutions to a variation of maximum-weight matching in bipartite hypergraphs, a problem recently emerging in the formation of peer-to-peer energy sharing communities. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Precise Asymptotics and Refined Regret of Variance-Aware UCB

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fan, Yingying Han, Yuxuan Lv, Jinchi Xu, Xiaocong Zhou, Zhengyuan Data Sciences and Operations Department University of Southern California Los AngelesCA90089 United States Stern School of Business New York University New YorkNY10003 United States

In this paper, we study the behavior of the Upper Confidence Bound-Variance (UCB-V) algorithm for the Multi-Armed Bandit (MAB) problems, a variant of the canonical Upper Confidence Bound (UCB) algorithm that incorporates variance estimates into its decision-making process. More precisely, we provide an asymptotic characterization of the arm-pulling rates for UCB-V, extending recent results for the canonical UCB in Kalvit and Zeevi (2021) and Khamaru and Zhang (2024). In an interesting contrast to the canonical UCB, our analysis reveals that the behavior of UCB-V can exhibit instability, meaning that the arm-pulling rates may not always be asymptotically deterministic. Besides the asymptotic characterization, we also provide non-asymptotic bounds for the arm-pulling rates in the high probability regime, offering insights into the regret analysis. As an application of this high probability result, we establish that UCB-V can achieve a more refined regret bound, previously unknown even for more complicate and advanced variance-aware online decision-making algorithms. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm