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

Online Matrix Completion: A Collaborative Approach with Hott Items

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Baby, Dheeraj Pal, Soumyabrata UC Santa Barbara United States Adobe Research United States

We investigate the low rank matrix completion problem in an online setting with M users, N items, T rounds, and an unknown rank-r reward matrix R ∈ RM×N. This problem has been well-studied in the literature [23, 12, 39, 45] and has several applications in practice. In each round, we recommend S carefully chosen distinct items to every user and observe noisy rewards. In the regime where M, N T, we propose two distinct computationally efficient algorithms for recommending items to users and analyze them under the benign hott items assumption 1) First, for S = 1, under additional incoherence/smoothness assumptions on R, we propose the phased algorithm PhasedClusterElim. Our algorithm obtains a near-optimal per-user regret of Oe(NM-1(∆-1 + ∆-hott2)) where ∆hott, ∆ are problem-dependent gap parameters with ∆hott ∆ almost always. 2) Second, we consider a simplified setting with S = r where we make significantly milder assumptions on R. Here, we introduce another phased algorithm, DeterminantElim, to derive a regret guarantee of Oe(NM-1/r∆-det1)) where ∆det is another problem-dependent gap. Both algorithms crucially use collaboration among users to jointly eliminate sub-optimal items for groups of users successively in phases, but with distinctive and novel approaches. © 2024, CC BY.

关键词： consensus algorithm

algorithmS FOR DETERMINATION OF T-MODULE STRUCTURES ON SOME EXTENSION GROUPS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gloch, Filip Kędzierski, Dawid E. Krasoń, Piotr Institute of Mathematics Department of Exact and Natural Sciences University of Szczecin ul. Wielkopolska 15 Szczecin70-451 Poland

In [11] the second and third author extended the methods of [17] and determined the t−module structure on Ext1(Φ, Ψ) where Φ and Ψ were Anderson t−modules over A = Fq[t] of some specific types. This approach involved the concept of biderivation and certain reduction algorithm. In this paper we generalize the results of [17] and [11] and present complete algorithm for computation of t−module structure on Ext1(Φ, Ψ) for t−modules Φ and Ψ such that degτ Φ > degτ Ψ. The last condition is not sufficient for our algorithm to be executable. We show that it can be applied when the matrix at the biggest power of τ in Φt is invertible. We also introduce a notion of τ -composition series which we find suitable for the additive category of t−modules and show that under certain assumptions on the composition series of Φ and Ψ our algorithm is also executable. © 2024, CC BY.

关键词： consensus algorithm

Reinforcement Learning-based Trajectory Planning for Cooperative Source Seeking

学校读者我要写书评

暂无评论

Reinforcement Learning-based Trajectory Planning for Coopera...

Industrial Automation, Robotics and Control Engineering (IARCE), International Conference on

作者： Weiran Wu Zhuo Li Jian Sun Gang Wang School of Automation Beijing Institute of Technology Beijing China Beijing Institute of Technology Chongqing Innovation Center Chongqing China

ISBN: (数字)9798350380323

ISBN: (纸本)9798350380330

This paper investigates the cooperative source seeking problem via a networked multi-vehicle system, and proposes a reinforcement learning (RL)-based trajectory planning scheme for the system. In contrast to most existing works, the source position of this work is determined by multiple types of signal fields, and each vehicle in the network is responsible to take measurements of a type of signal field. In another word, a single vehicle cannot localize the source position and must cooperate with its neighbors. To cooperatively localize and simultaneously reach the source position, the vehicle is equipped with a trajectory planning scheme that combines consensus algorithm for cooperative source seeking and an RL-based algorithm for maximizing the value of its corresponding signal field. Thus, each trajectory planner only requires measurements of a field and relative positions between neighboring vehicles, which is especially appealing to global position system (GPS)-denied environments. Simulations are provided to validate the efficacy of the proposed trajectory planning scheme. The RL-based trajectory planner actively leads the vehicle to positions with higher field measurements, without the need for gradient or absolute position information. And we demonstrate the successful deployment of the model learned in single vehicle settings to the cooperative source seeking task.

关键词： Location awareness Control engineering Automation Trajectory planning Service robots consensus algorithm Reinforcement learning Position measurement Trajectory Planning

Decentralized Neural Networks for Robust and Scalable Eigenvalue Computation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Katende, Ronald

This paper introduces a novel method for eigenvalue computation using a distributed cooperative neural network framework. Unlike traditional techniques that face scalability challenges in large systems, our decentralized algorithm enables multiple autonomous agents to collaboratively estimate the smallest eigenvalue of large matrices. Each agent employs a localized neural network, refining its estimates through communication with neighboring agents. Our empirical results confirm the algorithm's convergence towards the true eigenvalue, with estimates clustered closely around the true value. Even in the presence of communication delays or network disruptions, the method demonstrates strong robustness and scalability. Theoretical analysis further validates the accuracy and stability of the proposed approach, while empirical tests highlight its efficiency and precision, surpassing traditional centralized algorithms in large-scale eigenvalue computations. © 2024, CC BY.

关键词： consensus algorithm

A Probably Approximately Correct Analysis of Group Testing algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bharadwaja, Sameera H. Murthy, Chandra R. Dept. of ECE Indian Institute of Science Bangalore India

We consider the problem of identifying the defectives from a population of items via a non-adaptive group testing framework with a random pooling-matrix design. We analyze the sufficient number of tests needed for approximate set identification, i.e., for identifying almost all the defective and non-defective items with high confidence. To this end, we view the group testing problem as a function learning problem and develop our analysis using the probably approximately correct (PAC) framework. Using this formulation, we derive sufficiency bounds on the number of tests for three popular binary group testing algorithms: column matching, combinatorial basis pursuit, and definite defectives. We compare the derived bounds with the existing ones in the literature for exact recovery theoretically and using simulations. Finally, we contrast the three group testing algorithms under consideration in terms of the sufficient testing rate surface and the sufficient number of tests contours across the range of the approximation and confidence levels. © 2024, CC BY.

关键词： consensus algorithm

Convergence in total variation for the kinetic Langevin algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lehec, Joseph Université de Poitiers CNRS LMA Poitiers France

We prove non asymptotic total variation estimates for the kinetic Langevin algorithm in high dimension when the target measure satisfies a Poincaré inequality and has gradient Lipschitz potential. The main point is that the estimate improves significantly upon the corresponding bound for the non kinetic version of the algorithm, due to Dalalyan. In particular the dimension dependence drops from O(n) to O(√n).MSC Codes 35H10, 65C05, 68W20 © 2024, CC BY.

关键词： consensus algorithm

Fission: Autonomous, Scalable Sharding for IoT Blockchain

学校读者我要写书评

暂无评论

Fission: Autonomous, Scalable Sharding for IoT Blockchain

IEEE Annual International Computer Software and Applications Conference (COMPSAC)

作者： Chaoran Luo Yueyang Hu Su Zhang Ying Zhang Yi Liu Xingchun Diao Gang Huang Key Lab of High Confidence Software Technologies Peking University Beijing China School of Software and Microelectronics Peking University Beijing China National Engineering Research Center of Software Engineering Peking University Beijing China Advanced Institute of Big Data Beijing China

ISBN: (数字)9781665488105

ISBN: (纸本)9781665488112

IoT blockchain suffers heavy performance issues because of the massive transactions generated by various IoT nodes. By dividing nodes into different shards, sharding can produce blocks in parallel and hence improve the throughput of the blockchain system. Unlike the traditional blockchain system, IoT blockchain mainly consists of smart devices and the transactions are usually generated from the real world, such as the sensor data, photos taken by cameras, and so on. In IoT blockchain, closer nodes usually share a lower network latency and the transactions they generate are more related. Therefore, location-based sharding is an effective approach to improve the performance of IoT blockchain. Traditionally, IoT nodes are di-vided into different shards based on geographical locations or the connected edge server. However, the key challenge of sharding in IoT blockchain is how to guarantee the equality of shards division as to the unpredictable distribution and the dynamic behavior of IoT nodes. On one hand, shards can not be pre-divided because we can not predict the number or the distribution of the IoT nodes. On the other hand, nodes continuously joining or quitting shards will also break the equality of the shards division. In this paper, we propose Fission, a sharding mechanism designed for IoT blockchain. Fission divide shards based on the Voronoi diagram without any preknowledge about the nodes distribution, and support dynamic, autonomous sharding adjustment based on distributed Delaunay Triangulation. In addition, Fission uses a new diffusion-based consensus algorithm to achieve the linear scalability of throughput. The experimental results show that Fission can construct and adjust shards at a very low cost and can execute in a decentralized manner. The throughput can reach 1900tps in 500 nodes with only 5M bps bandwidth, and can scale linearly as the nodes increase.

关键词： Scalability Software algorithms consensus algorithm Throughput Cameras Software Blockchains

Extending Stable and Popular Matching algorithms from Bipartite to Arbitrary Instances

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Csáji, Gergely HUN-REN KRTK KTI Hungary

We consider stable and popular matching problems in arbitrary graphs, which are referred to as stable roommates instances. We extend the 3/2-approximation algorithm for the maximum size weakly stable matching problem to the roommates case, which solves a more than 20 year old open question of Irving and Manlove about the approximability of maximum size weakly stable matchings in roommates instances with ties [28] and has nice applications for the problem of matching residents to hospitals in the presence of couples. We also extend the algorithm that finds a maximum size popular matching in bipartite graphs in the case of strict preferences and the algorithm to find a popular matching among maximum weight matchings. While previous attempts to extend the idea of promoting the agents or duplicating the edges from bipartite instances to arbitrary ones failed, these results show that with the help of a simple observation, we can indeed bridge the gap and extend these algorithms. © 2024, CC BY.

关键词： consensus algorithm

Distributed Economical Dispatch for Renewable Power System with Time-varying Topology and Fluctuating Power Generations

学校读者我要写书评

暂无评论

Distributed Economical Dispatch for Renewable Power System w...

2017 International Electrical and Energy Conference (CIEEC 2017)

作者： XIA Shiwei ZHANG Qian ZOU Weiwei LI Gengyin State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources North China Electric Power University

In order to solve the limitations in centralized economical dispatch(ED),a distributed algorithm is properly designed by selecting generator incremental costs as the consensus variables in this paper to solve the ED problem in a center-free *** proposed distributed algorithm is more effective than the conventional central one in the situation that the topologies are *** addition,the convergence rate,as an important performance indicator of distributed algorithm,is also investigated for different communication topologies in this *** wind power generation with relatively large fluctuations,the proposed algorithm has been tested on a 10-generator system with fluctuating wind power generations,and the simulations have demonstrated the effectiveness of the distributed ED algorithm for power system ED with time-varying power generations and topologies.

关键词： Distributed economic dispatch incremental cost consensus algorithm convergence rate fluctuating power generations