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

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ye, Chenlu Jin, Yujia Agarwal, Alekh Zhang, Tong University of Illinois Urbana-Champaign United States United States Google Research United States

Typical contextual bandit algorithms assume that the rewards at each round lie in some fixed range [0, R], and their regret scales polynomially with this reward range R. However, many practical scenarios naturally involve heavy-tailed rewards or rewards where the worst-case range can be substantially larger than the variance. In this paper, we develop an algorithmic approach building on Catoni’s estimator from robust statistics, and apply it to contextual bandits with general function approximation. When the variance of the reward at each round is known, we use a variance-weighted regression approach and establish a regret bound that depends only on the cumulative reward variance and logarithmically on the reward range R as well as the number of rounds T . For the unknown-variance case, we further propose a careful peeling-based algorithm and remove the need for cumbersome variance estimation. With additional dependence on the fourth moment, our algorithm also enjoys a variance-based bound with logarithmic reward-range dependence. Moreover, we demonstrate the optimality of the leading-order term in our regret bound through a matching lower bound. © 2025, CC BY.

关键词： consensus algorithm

Leveraging Formal Methods to Blockchain consensus Protocols: A Scoping Literature Review

学校读者我要写书评

暂无评论

Leveraging Formal Methods to Blockchain Consensus Protocols:...

iNnovative Informatics of Biskra (ISNIB), International Symposium on

作者： Wissam Bouzegag Leyla Belaiche Laid Kahloul Hammadi Bennoui Department of Computer Science LINFI Laboratory University of Biskra Algeria

Recently, the concept of blockchain has emerged and caused a stir in the digital world and this translates into a new perspective on the security, flexibility, and efficiency of systems. To solve various problems that exist in Byzantine environments the blockchain uses consensus algorithms to solve these problems. These consensus algorithms are essential to ensure long-term stability in a blockchain system, so consensus forms the basis of blockchain technology. Therefore, the appearance of a set of consensus protocols aims to improve the efficiency of blockchain systems and meet the individual needs of different application areas. On the other hand, to make blockchain platforms more secure and reliable for information sharing, and an optimal solution for value transfer, formal methods have been used to provide sufficient mathematical proofs to ensure user safety and security. In this paper, a scoping literature review on leveraging formal methods to consensus protocols is presented and discussed.

关键词： Bibliographies Information sharing consensus algorithm Robustness consensus protocol Safety Security

Distributed Graph Augmentation Protocols to Achieve Strong Connectivity in Multi-Agent Networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ramos, Guilherme Poças, Diogo Pequito, Sérgio Dept. of Computer Science and Engineering Instituto Superior Técnico University of Lisbon Portugal Instituto de Telecomunicações Lisbon1049-001 Portugal Dept. of Mathematics Instituto Superior Técnico University of Lisbon Portugal Instituto de Telecomunicações Lisbon1049-001 Portugal LARSyS Lisbon Portugal

In multi-agent systems, strong connectivity of the communication network is often crucial for establishing consensus protocols, which underpin numerous applications in decision-making and distributed optimization. However, this connectivity requirement may not be inherently satisfied in geographically distributed settings. Consequently, we need to find the minimum number of communication links to add to make the communication network strongly connected. To date, such problems have been solvable only through centralized methods. This paper introduces a fully distributed algorithm that efficiently identifies an optimal set of edge additions to achieve strong connectivity, using only local information. The majority of the communication between agents is local (according to the digraph structure), with only a few steps requiring communication among non-neighboring agents to establish the necessary additional communication links. A comprehensive empirical analysis of the algorithm’s performance on various random communication networks reveals its efficiency and scalability. © 2024, CC BY.

关键词： consensus algorithm

Small-Signal Modeling and Stability Analysis of Delay-Dependent Cyber-Physical Microgrid System Under Hybrid Secondary Control

学校读者我要写书评

暂无评论

Small-Signal Modeling and Stability Analysis of Delay-Depend...

Power Electronics and Power System Conference (PEPSC)

作者： Yanyang Ding Rongwu Zhu Department of Electrical Engineering Harbin Institute of Technology Shenzhen China

ISBN: (数字)9798350390193

ISBN: (纸本)9798350390209

This paper studies stability issues in islanded delay-dependent cyber-physical microgrid systems (CPMGSs) with the distributed hierarchical control framework. Firstly, a distributed consensus algorithm and decentralized point of common coupling voltage estimation-based hybrid secondary control is proposed for the distinctive capability of PCC voltage restoration, as well as power sharing and frequency restoration. Besides a novel linearized small-signal modeling method is developed for the frequency-domain stability analysis with low computational complexity, based on which the time-delayed state-space model (SSM) of the CPMGS is derived. Lastly, the time-domain simulations carried out in Matlab and systematical eigenvalue analysis in frequency-domain stability verify the effectiveness of the proposed control method and the accuracy of the SSM.

关键词： Analytical models Frequency-domain analysis Microgrids consensus algorithm Power system stability Stability analysis Eigenvalues and eigenfunctions Voltage control Time-domain analysis Frequency control

Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kim, Seok-Jin Oh, Min-Hwan Columbia University New YorkNY United States Seoul National Univeristy Seoul Korea Republic of

We study the performance guarantees of exploration-free greedy algorithms for the linear contextual bandit problem. We introduce a novel condition, named the Local Anti-Concentration (LAC) condition, which enables a greedy bandit algorithm to achieve provable efficiency. We show that the LAC condition is satisfied by a broad class of distributions, including Gaussian, exponential, uniform, Cauchy, and Student’s t distributions, along with other exponential family distributions and their truncated variants. This significantly expands the class of distributions under which greedy algorithms can perform efficiently. Under our proposed LAC condition, we prove that the cumulative expected regret of the greedy algorithm for the linear contextual bandit is bounded by O(poly log T). Our results establish the widest range of distributions known to date that allow a sublinear regret bound for greedy algorithms, further achieving a sharp poly-logarithmic regret. © 2024, CC BY-NC-ND.

关键词： consensus algorithm

A topology-based algorithm for the isomorphism check of 2-level Orthogonal Arrays

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Fontana, Roberto Guerra, Marco Department of Mathematical Sciences Politecnico di Torino Corso Duca degli Abruzzi 24 Torino10129 Italy Institut Fourier Université Grenoble-Alpes CNRS 100 Rue des Mathematiques Gières38610 France

We introduce a construction and an algorithm, both based on Topological Data Analysis (TDA), to tackle the problem of the isomorphism check of Orthogonal Arrays (OAs). Specifically, we associate to any binary OA a persistence diagram, one of the main tools in TDA, and explore how the Wasserstein distance between persistence diagrams can be used to inform whether two designs are *** Codes 62R40, 55N31 © 2024, CC BY.

关键词： consensus algorithm

An Efficient algorithm for Vertex Enumeration of Arrangement

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dong, Zelin Fan, Fenglei Xiong, Huan Zeng, Tieyong Department of Mathematics The Chinese University of Hong Kong Hong Kong IASM Harbin Institute of Technology China

This paper presents a state-of-the-art algorithm for the vertex enumeration problem of arrangements. We introduce a new pivot rule, called the Zero rule. The Zero rule possesses several desirable properties: i) It eliminates the objective function;ii) Its terminal dictionary is single;iii) We establish the if-and-only-if condition between the Zero pivot and its valid reverse pivot;iv) Applying the Zero pivot recursively definitely terminates in d steps, where d is the dimension of the input variables. Based on this rule and its properties, we leverage it to obtain a more efficient vertex enumeration algorithm. Theoretically, given an arrangement in d composed of n hyperplanes with v vertices, where vd of those vertices reach the terminal in exactly d steps when applying the Zero pivot, the algorithm’s complexity is O(n2d2(v − vd) − ndvd). For the class of simple arrangements, the complexity is Ο(nd4v), which significantly improves O(n2dv) of the Avis and Fukuda algorithm. Systematic and comprehensive experiments confirm that our algorithm is effective. © 2024, CC BY.

关键词： consensus algorithm

Pathfinding with Lazy Successor Generation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Okumura, Keisuke University of Cambridge United Kingdom Japan

We study a pathfinding problem where only locations (i.e., vertices) are given, and edges are implicitly defined by an oracle answering the connectivity of two locations. Despite its simple structure, this problem becomes non-trivial with a massive number of locations, due to posing a huge branching factor for search algorithms. Limiting the number of successors, such as with nearest neighbors, can reduce search efforts but compromises completeness. Instead, we propose a novel LaCAS∗ algorithm, which does not generate successors all at once but gradually generates successors as the search progresses. This scheme is implemented with k-nearest neighbors search on a k-d tree. LaCAS∗ is a complete and anytime algorithm that eventually converges to the optima. Extensive evaluations demonstrate the efficacy of LaCAS∗, e.g., solving complex pathfinding instances quickly, where conventional methods falter. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Discretely Beyond 1/e: Guided Combinatorial algorithms for Submodular Maximization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Yixin Nath, Ankur Peng, Chunli Kuhnle, Alan Department of Computer Science & Engineering Texas A&M University Colloge StationTX United States

For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than 1/e require continuous ideas, such as queries to the multilinear extension of a submodular function and its gradient, which are typically expensive to simulate with the original set function. For combinatorial algorithms, the best known approximation ratios for both size and matroid constraint are obtained by a simple randomized greedy algorithm of Buchbinder et al. [9]: 1/e ≈ 0.367 for size constraint and 0.281 for the matroid constraint in O(kn) queries, where k is the rank of the matroid. In this work, we develop the first combinatorial algorithms to break the 1/e barrier: we obtain approximation ratio of 0.385 in O(kn) queries to the submodular set function for size constraint, and 0.305 for a general matroid constraint. These are achieved by guiding the randomized greedy algorithm with a fast local search algorithm. Further, we develop deterministic versions of these algorithms, maintaining the same ratio and asymptotic time complexity. Finally, we develop a deterministic, nearly linear time algorithm with ratio 0.377. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm