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

Best-Arm Identification in Unimodal Bandits

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Poiani, Riccardo Jourdan, Marc Kaufmann, Emilie Degenne, Rémy Bocconi University Milan Italy EPFL Lausanne Switzerland Univ. Lille Inria CNRS Centrale Lille UMR 9189-CRIStAL France

We study the fixed-confidence best-arm identification problem in unimodal bandits, in which the means of the arms increase with the index of the arm up to their maximum, then decrease. We derive two lower bounds on the stopping time of any algorithm. The instance-dependent lower bound suggests that due to the unimodal structure, only three arms contribute to the leading confidence-dependent cost. However, a worst-case lower bound shows that a linear dependence on the number of arms is unavoidable in the confidence-independent cost. We propose modifications of Track-and-Stop and a Top Two algorithm that leverage the unimodal structure. Both versions of Track-and-Stop are asymptotically optimal for one-parameter exponential families. The Top Two algorithm is asymptotically near-optimal for Gaussian distributions and we prove a non-asymptotic guarantee matching the worse-case lower bound. The algorithms can be implemented efficiently and we demonstrate their competitive empirical performance. © 2024, CC BY.

关键词： consensus algorithm

TESTING THE FAIRNESS-ACCURACY IMPROVABILITY OF algorithmS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Auerbach, Eric Liang, Annie Okumura, Kyohei Tabord-Meehan, Max Department of Economics Northwestern University United States Department of Economics University of Chicago United States

Many organizations use algorithms that have a disparate impact, i.e., the benefits or harms of the algorithm fall disproportionately on certain social groups. Addressing an algorithm’s disparate impact can be challenging, however, because it is often unclear whether it is possible to reduce this impact without sacrificing other objectives of the organization, such as accuracy or profit. Establishing the improvability of algorithms with respect to multiple criteria is of both conceptual and practical interest: in many settings, disparate impact that would otherwise be prohibited under US federal law is permissible if it is necessary to achieve a legitimate business interest. The question is how an analyst can formally substantiate, or refute, this "necessity" defense. In this paper, we provide an econometric framework for testing the hypothesis that it is possible to improve on the fairness of an algorithm without compromising on other pre-specified objectives. Our proposed test is simple to implement and can be applied under any exogenous constraint on the algorithm space. We establish the large-sample validity and consistency of our test, and microfound the test’s robustness to manipulation based on a game between a policymaker and the analyst. Finally, we apply our approach to evaluate a healthcare algorithm originally considered by Obermeyer et al. (2019), and quantify the extent to which the algorithm’s disparate impact can be reduced without compromising the accuracy of its predictions. © 2024, CC BY.

关键词： consensus algorithm

Perfect Matchings and Popularity in the Many-to-Many Setting

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kavitha, Telikepalli Makino, Kazuhisa Tata Institute of Fundamental Research Mumbai India Research Institute for Mathematical Sciences Kyoto University Kyoto Japan

We consider a matching problem in a bipartite graph G where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume G admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible for us and we are interested in those perfect matchings that are popular within the set of perfect matchings. It is known that such matchings (called popular perfect matchings) always exist and can be efficiently computed. What we seek here is not any popular perfect matching, but a min-cost one. We show a polynomial-time algorithm for finding such a matching;this is via a characterization of popular perfect matchings in G in terms of stable matchings in a colorful auxiliary instance. This is a generalization of such a characterization that was known in the one-to-one setting. © 2024, CC BY.

关键词： consensus algorithm

A FINITENESS CONDITION FOR COMPLEX CONTINUED FRACTION algorithmS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kalle, Charlene Sélley, Fanni M. Thuswaldner, Jörg M. Mathematisch Instituut Leiden University Niels Bohrweg 1 Leiden2333CA Netherlands Lehrstuhl für Mathematik und Statistik Montanuniversität Leoben Franz Josef Straße 18 LeobenA-8700 Austria

It is desirable that a given continued fraction algorithm is simple in the sense that the possible representations can be characterized in an easy way. In this context the so-called finite range condition plays a prominent role. We show that this condition holds for complex α-Hurwitz algorithms with parameters α ∈ Q2. This is equivalent to the existence of certain finite partitions related to these algorithms and lies at the root of explorations into their Diophantine properties. Our result provides a partial answer to a recent question formulated by Lukyanenko and *** Codes 11J70 © 2024, CC BY.

关键词： consensus algorithm

Chinese Remainder Theorem Approach to Montgomery-Type algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Xu, Guangwu Jia, Yiran Yang, Yanze SCST Shandong University China

This paper explores the ability of the Chinese Remainder Theorem formalism to model Montgomery-type algorithms. A derivation of CRT based on Qin’s Identity gives Montgomery reduction algorithm immediately. This establishes a unified framework to treat modular reduction algorithms of Montgomery-type. Several recent notable variants of Montgomery algorithm are analyzed, validation of these methods are performed within the framework. Problems in some erroneous design of reduction algorithms of Montgomery-type in the literature are detected and counter examples are easily generated by using the CRT formulation. © 2024, CC BY.

关键词： consensus algorithm

Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Nikolaev, Maksim S. Steklov Institute of Mathematics Academy of Sciences St. Petersburg Russia

In the Shortest Common Superstring problem, one needs to find the shortest superstring for a set of strings. This problem is APX-hard, and many approximation algorithms were proposed, with the current best approximation factor of 2.466. Whereas these algorithms are technically involved, for more than thirty years the Greedy Conjecture remains unsolved, that states that the Greedy algorithm "take two strings with the maximum overlap;merge them;repeat" is a 2-approximation. This conjecture is still open, and one way to approach it is to consider its stronger version, which may make the proof easier due to the stronger premise or provide insights from its refutation. In this paper, we propose two directions to strengthen the conjecture. First, we introduce the Locally Greedy algorithm (LGA), that selects a pair of strings not with the largest overlap but with the locally largest overlap, that is, the largest among all pairs of strings with the same first or second string. Second, we change the quality metric: instead of length, we evaluate the solution by the number of occurrences of an arbitrary symbol. Despite the double strengthening, we prove that LGA is a uniform 4-approximation, that is, it always constructs a superstring with no more than four times as many occurrences of an arbitrary symbol as any other superstring. At the same time, we discover the limitations of the greedy heuristic: we show that LGA is at least 3-approximation, and the Greedy algorithm is at least uniform 2.5-approximation. These result show that if the Greedy Conjecture is true, it is not because the Greedy algorithm is locally greedy or is uniformly 2-approximation. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

FastEnsemble: scalable ensemble clustering on large networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Tabatabaee, Yasamin Wedell, Eleanor Park, Minhyuk Warnow, Tandy Siebel School of Computing and Data Science University of Illinois Urbana-Champaign UrbanaIL United States

Many community detection algorithms are inherently stochastic, leading to variations in their output depending on input parameters and random seeds. This variability makes the results of a single run of these algorithms less reliable. Moreover, different clustering algorithms, optimization criteria (e.g., modularity, the Constant Potts model), and resolution values can result in substantially different partitions on the same network. consensus clustering methods, such as ECG and Fastconsensus, have been proposed to reduce the instability of non-deterministic algorithms and improve their accuracy by combining a set of partitions resulting from multiple runs of a clustering algorithm. In this work, we introduce FastEnsemble, a new consensus clustering method. Our results on a wide range of synthetic networks show that FastEnsemble produces more accurate clusterings than two other consensus clustering methods, ECG and Fastconsensus, for many model conditions. Furthermore, FastEnsemble is fast enough to be used on networks with more than 3 million nodes, and so improves on the speed and scalability of Fastconsensus. Finally, we showcase the utility of consensus clustering methods in mitigating the effect of resolution limit and clustering networks that are only partially covered by communities. © 2024, CC BY.

关键词： consensus algorithm

Greedy Sets and Greedy Numerical Semigroups

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Pérez-Rosés, Hebert Serradilla-Merinero, José Miguel Bras-Amorós, Maria Dept. of Computer Science and Mathematics Universitat Rovira i Virgili Avda. Paisos Catalans 26 Catalonia Tarragona43007 Spain

Motivated by the change-making problem, we extend the notion of greediness to sets of positive integers not containing the element 1, and from there to numerical semigroups. We provide an algorithm to determine if a given set (not necessarily containing the number 1) is greedy. We also give specific conditions for sets of cardinality three, and we prove that numerical semigroups generated by three consecutive integers are *** Codes 06F05, 11Y55, 68R05 Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Parallel Dynamic Maximal Matching

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ghaffari, Mohsen Trygub, Anton MIT United States

We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the maximal matching to these updates in poly(log n) depth and using poly(log n) amortized work per update. That is, the amortized work for processing a batch of k updates is k poly(log n), while all this work is done in poly(log n) depth, with high probability. This can be seen as a parallel counterpart of the sequential dynamic algorithms for constant-approximate and maximal matching [Onak and Rubinfeld STOC'10;Baswana, Gupta, and Sen FOCS'11;and Solomon FOCS'16]. Our algorithm readily generalizes to maximal matching in hypergraphs of rank r-where each hyperedge has at most r endpoints-with a poly(r) increase in work, while retaining the poly(log n) depth. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm