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

3-Majority and 2-Choices with Many Opinions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Shimizu, Nobutaka Shiraga, Takeharu Institute of Science Tokyo Japan Chuo University Japan

We present the first nearly-optimal bounds on the consensus time for the well-known synchronous consensus dynamics, specifically 3-Majority and 2-Choices, for an arbitrary number of opinions. In synchronous consensus dynamics, we consider an n-vertex complete graph with self-loops, where each vertex holds an opinion from {1, . . ., k}. At each discrete-time round, all vertices update their opinions simultaneously according to a given protocol. The goal is to reach a consensus, where all vertices support the same opinion. In 3-Majority, each vertex chooses three random neighbors with replacement and updates its opinion to match the majority, with ties broken randomly. In 2-Choices, each vertex chooses two random neighbors with replacement. If the selected vertices hold the same opinion, the vertex adopts that opinion. Otherwise, it retains its current opinion for that round. Improving upon a line of work [Becchetti et al., SPAA’14], [Becchetti et al., SODA’16], [Berenbrink et al., PODC’17], [Ghaffari and Lengler, PODC’18], we prove that, for every 2 ≤ k ≤ n, 3-Majority (resp. 2-Choices) reaches consensus within Θ(min e {k, √n}) (resp. Θ(e k)) rounds with high probability. Prior to this work, the best known upper bound on the consensus time of 3-Majority was Oe(k) if k n1/3 and Oe(n2/3) otherwise, and for 2-Choices, the consensus time was known to be Oe(k) for k √n. © 2025, CC BY.

关键词： consensus algorithm

How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lowy, Andrew Ullman, Jonathan Wright, Stephen J. Wisconsin Institute for Discovery University of Wisconsin-Madison United States Khoury College of Computer Sciences Northeastern University United States Department of Computer Sciences University of Wisconsin–Madison United States

We provide a simple and flexible framework for designing differentially private algorithms to find approximate stationary points of non-convex loss functions. Our framework is based on using a private approximate risk minimizer to "warm start" another private algorithm for finding stationary points. We use this framework to obtain improved, and sometimes optimal, rates for several classes of non-convex loss functions. First, we obtain improved rates for finding stationary points of smooth non-convex empirical loss functions. Second, we specialize to quasar-convex functions, which generalize star-convex functions and arise in learning dynamical systems and training some neural nets. We achieve the optimal rate for this class. Third, we give an optimal algorithm for finding stationary points of functions satisfying the Kurdyka-Lojasiewicz (KL) condition. For example, over-parameterized neural networks often satisfy this condition. Fourth, we provide new state-of-the-art rates for stationary points of non-convex population loss functions. Fifth, we obtain improved rates for non-convex generalized linear models. A modification of our algorithm achieves nearly the same rates for second-order stationary points of functions with Lipschitz Hessian, improving over the previous state-of-the-art for each of the above problems. © 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

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

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

A Communication-Efficient Semi-Decentralized Approach for Federated Learning with Stragglers

学校读者我要写书评

暂无评论

A Communication-Efficient Semi-Decentralized Approach for Fe...

IEEE (first ITW conference of the year) Information Theory Workshop (ITW)

作者： Chengxi Li Ming Xiao Mikael Skoglund School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm Sweden

ISBN: (数字)9798350348934

ISBN: (纸本)9798350348941

We study the problem of federated learning (FL) in the presence of stragglers, the devices that are intermittently connected to the central server. Although under the newly developed semi-decentralized federated learning (SFL) framework, gradient coding (GC) can be applied to evade the stragglers by letting them relay their locally computed gradients to the central server via non-stragglers, the communication burden of GC in SFL is very heavy. To overcome this drawback, motivated by the communication-optimal exact consensus algorithm (CECA) proposed in the literature, we propose a new communicationefficient semi-decentralized method (COFFEE) in SFL. In each round of COFFEE, the devices take a certain number of steps towards consensus in a decentralized manner with high communication efficiency, and each of them acquires the average of its own gradient and the gradients of its previous neighbors. After that, the non-straggler devices send the obtained average results to the server, which aggregates the received vectors to yield the global model update. The learning performance of the proposed method is analyzed through convergence analysis. Finally, we run simulations to show the superiority of COFFEE over the baseline method, i.e., GC in SFL.

关键词： Performance evaluation Federated learning Conferences Information processing consensus algorithm Vectors Encoding Servers Relays Convergence

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