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

Fair Secretaries with Unfair Predictions

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Balkanski, Eric Ma, Will Maggiori, Andreas Columbia University United States

algorithms with predictions is a recent framework for decision-making under uncertainty that leverages the power of machine-learned predictions without making any assumption about their quality. The goal in this framework is for algorithms to achieve an improved performance when the predictions are accurate while maintaining acceptable guarantees when the predictions are erroneous. A serious concern with algorithms that use predictions is that these predictions can be biased and, as a result, cause the algorithm to make decisions that are deemed unfair. We show that this concern manifests itself in the classical secretary problem in the learning-augmented setting—the state-of-the-art algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least max{Ω(1), 1 − O(Ε)} times the optimal value, where Ε is the prediction error. We show how to preserve this promise while also guaranteeing to accept the best candidate with probability Ω(1). Our algorithm and analysis are based on a new "pegging" idea that diverges from existing works and simplifies/unifies some of their results. Finally, we extend to the k-secretary problem and complement our theoretical analysis with experiments. © 2024, CC BY.

关键词： consensus algorithm

Log-Time K-Means for 1D Data: Novel Approaches with Proof and Implementation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hyun, Jake Computer Science and Engineering College of Engineering Seoul National University Korea Republic of

Clustering is a key task in machine learning, with k-means being widely used for its simplicity and effectiveness. While 1D clustering is common, existing methods often fail to exploit the structure of 1D data, leading to inefficiencies. This thesis introduces optimized algorithms for k-means++ initialization and Lloyd’s algorithm, leveraging sorted data, prefix sums, and binary search for improved computational performance. The main contributions are: (1) an optimized k-cluster algorithm achieving O(l · k2 · log n) complexity for greedy k-means++ initialization and O(i·k·log n) for Lloyd’s algorithm, where l is the number of greedy k-means++ local trials, and i is the number of Lloyd’s algorithm iterations, and (2) a binary search-based two-cluster algorithm, achieving O(log n) runtime with deterministic convergence to a Lloyd’s algorithm local minimum. Benchmarks demonstrate over a 4500x speedup compared to scikit-learn for large datasets while maintaining clustering quality measured by within-cluster sum of squares (WCSS). Additionally, the algorithms achieve a 300x speedup in an LLM quantization task, highlighting their utility in emerging applications. This thesis bridges theory and practice for 1D k-means clustering, delivering efficient and sound algorithms implemented in a JIT-optimized open-source Python library. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Second Order Bounds for Contextual Bandits with Function Approximation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Pacchiano, Aldo Boston University Broad Institute of MIT and Harvard United States

Many works have developed no-regret algorithms for contextual bandits with function approximation, where the mean rewards over context-action pairs belong to a function class F. Although there are many approaches to this problem, algorithms based on the principle of optimism, such as optimistic least squares have gained in importance. The regret of optimistic least squares scales as Or ´adeluderpF q logpF qT ¯ where deluderpF q is a statistical measure of the complexity of the function class F known as eluder dimension. Unfortunately, even if the variance of the measurement noise of the rewards at time_ t equals σt2 and these are close to zero, the optimistic least squares algorithm’s regret scales with ?T . In this work we are the first to develop algorithms that satisfy regret bounds for contextual bandits with function approximation of the form (formula presented) when the variances are unknown and satisfy σt2 "σ for all t and (fomula presented)when the variances change at every time-step. These bounds generalize existing techniques for deriving second order bounds in contextual linear problems. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

学校读者我要写书评

暂无评论

Directional descent

arXiv 2024年

作者： Young, Andrew J.

We identity the optimal non-infinitesimal direction of descent for a convex function. An algorithm is developed that can theoretically minimize a subset of (non-convex) Lipschitz functions. © 2024, CC BY.

关键词： consensus algorithm

A Secure Framework of Internet of Production for Data Exchange

学校读者我要写书评

暂无评论

A Secure Framework of Internet of Production for Data Exchan...

Advances in Computation, Communication and Information Technology (ICAICCIT), International Conference on

作者： Mohuya Chakraborty Subhalaxmi Chakraborty Sudip Kumar Palit Cybersecurity Centre of Excellence Institute of Engineering and Management (IEM) University of Engineering and Management Kolkata CST & CSIT Institute of Engineering and Management (IEM) University of Engineering and Management Kolkata

ISBN: (数字)9798331541217

ISBN: (纸本)9798331541224

The Internet of Production (IoP) is changing the manufacturing industry by helping companies work more efficiently, increase profits, and speed up product delivery. However, ensuring secure communication among different stakeholders in various supply chains is a major challenge that affects data sharing and collaboration. This study presents a strong framework that uses blockchain technology to improve secure communication among these stakeholders. The motivation for this research comes from the growing need for better security measures in the IoP, especially as the amount of data being exchanged increases. At the heart of this framework is a new algorithm designed to enhance both security and efficiency in data exchanges. Testing with the Automated Validation of Internet Security Protocols and Applications tool shows that the algorithm is safe from replay and man-in-themiddle attacks. Additionally, an analysis using the Burrows-Abadi-Needham method confirms that it provides mutual authentication among stakeholders. Performance analysis indicates that the algorithm achieves faster execution times ($\sim 18$ milliseconds) compared to existing methods, while its communication time is transitional ($\sim 5152$ bits), marking a significant improvement in the field. This work significantly contributes to the field by providing a secure and efficient solution for cross-domain communication in the IoP.

关键词： Resistance Supply chains Authentication Production consensus algorithm Blockchains Performance analysis Stakeholders Security Testing

Computing the Proximal Operator of the 1,q-norm for Group Sparsity

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Lin, Rongrong Chen, Shihai Feng, Han Liu, Yulan School of Mathematics and Statistics Guangdong University of Technology Guangzhou510520 China Department of Mathematics City University of Hong Kong Tat Chee Avenue Kowloon Tong Hong Kong

关键词： consensus algorithm

Robust Fair Clustering with Group Membership Uncertainty Sets

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Duppala, Sharmila Luque, Juan Dickerson, John Esmaeili, Seyed A. University of Maryland College Park United States Arthur University of Chicago United States

We study the canonical fair clustering problem where each cluster is constrained to have close to population-level representation of each group. Despite significant attention, the salient issue of having incomplete knowledge about the group membership of each point has been superficially addressed. In this paper, we consider a setting where the assigned group memberships are noisy. We introduce a simple noise model that requires a small number of parameters to be given by the decision maker. We then present an algorithm for fair clustering with provable robustness guarantees. Our framework enables the decision maker to trade off between the robustness and the clustering quality. Unlike previous work, our algorithms are backed by worst-case theoretical guarantees. Finally, we empirically verify the performance of our algorithm on real world datasets and show its superior performance over existing baselines. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

An Approach for Addressing Internally-Disconnected Communities in Louvain algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sahu, Subhajit IIIT Hyderabad Telangana Hyderabad India

Community detection is the problem of identifying densely connected clusters within a network. While the Louvain algorithm is commonly used for this task, it can produce internally-disconnected communities. To address this, the Leiden algorithm was introduced. This technical report introduces GSP-Louvain, a parallel algorithm based on Louvain, which mitigates this issue. Running on a system with two 16-core Intel Xeon Gold 6226R processors, GSP-Louvain outperforms Leiden, NetworKit Leiden, and cuGraph Leiden by 391×, 6.9×, and 2.6× respectively, processing 410M edges per second on a 3.8B edge graph. Furthermore, GSP-Louvain improves performance at a rate of 1.5× for every doubling of threads. © 2024, CC BY-NC-SA.

关键词： consensus algorithm

PatternBoost: Constructions in Mathematics with a Little Help from AI

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Charton, François Ellenberg, Jordan S. Wagner, Adam Zsolt Williamson, Geordie FAIR Meta – CERMICS Ecole des Ponts France Department of Mathematics University of Wisconsin–Madison United States Mathematical Sciences Department Worcester Polytechnic Institute United States Sydney Mathematical Research Institute University of Sydney Australia

We introduce PatternBoost, a flexible method for finding interesting constructions in mathematics. Our algorithm alternates between two phases. In the first "local" phase, a classical search algorithm is used to produce many desirable constructions. In the second "global" phase, a transformer neural network is trained on the best such constructions. Samples from the trained transformer are then used as seeds for the first phase, and the process is repeated. We give a detailed introduction to this technique, and discuss the results of its application to several problems in extremal combinatorics. The performance of PatternBoost varies across different problems, but there are many situations where its performance is quite impressive. Using our technique, we find the best known solutions to several long-standing problems, including the construction of a counterexample to a conjecture that had remained open for 30 *** Codes 05C35, 05D99, 68T20, 68V99 Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm