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

Prophet Inequality from Samples: Is the More the Merrier?

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ezra, Tomer Harvard University Cambridge United States

We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distribution and has only access to a set of samples from the distributions. Rubinstein et al. [2020] showed that the optimal competitive-ratio of ½ can surprisingly be obtained by observing a set of n samples, one from each of the distributions. In this paper, we prove that this competitive-ratio of ½becomes unattainable when the decision-maker is provided with a set of more samples. We then examine the natural class of ordinal static threshold algorithms, where the algorithm selects the i-th highest ranked sample, sets this sample as a static threshold, and then chooses the first value that exceeds this threshold. We show that the best possible algorithm within this class achieves a competitive-ratio of 0.433. Along the way, we utilize the tools developed in the paper and provide an alternative proof of the main result of Rubinstein et al. [2020]. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

MINI-BATCH KERNEL k-MEANS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jourdan, Ben Schwartzman, Gregory University of Edinburgh United Kingdom Japan

We present the first mini-batch kernel k-means algorithm, offering an order of magnitude improvement in running time compared to the full batch algorithm. A single iteration of our algorithm takes O͠(kb2) time, significantly faster than the O(n2) time required by the full batch kernel k-means, where n is the dataset size and b is the batch size. Extensive experiments demonstrate that our algorithm consistently achieves a 10-100x speedup with minimal loss in quality, addressing the slow runtime that has limited kernel k-means adoption in practice. We further complement these results with a theoretical analysis under an early stopping condition, proving that with a batch size of Ω͠ (max ｛γ4, γ2｝ · ϵ−2), the algorithm terminates in O(γ2/ϵ) iterations with high probability, where γ bounds the norm of points in feature space and ϵ is a termination threshold. Our analysis holds for any reasonable center initialization, and when using k-means++ initialization, the algorithm achieves an approximation ratio of O(log k) in expectation. For normalized kernels, such as Gaussian or Laplacian it holds that γ = 1. Taking ϵ = O(1) and b = Θ(log n), the algorithm terminates in O(1) iterations, with each iteration running in O͠(k) time. © 2024, CC BY.

关键词： consensus algorithm

OOD-CHAMELEON: IS algorithm SELECTION FOR OOD GENERALIZATION LEARNABLE?

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Jiang, Liangze Teney, Damien EPFL Idiap Research Institute Switzerland Idiap Research Institute Switzerland

Out-of-distribution (OOD) generalization is challenging because distribution shifts come in many forms. A multitude of learning algorithms exist and each can improve performance in specific OOD situations. We posit that much of the challenge of OOD generalization lies in choosing the right algorithm for the right dataset. However, such algorithm selection is often elusive under complex real-world shifts. In this work, we formalize the task of algorithm selection for OOD generalization and investigate whether it could be approached by learning. We propose a solution, dubbed OOD-CHAMELEON that treats the task as a supervised classification over candidate algorithms. We construct a dataset of datasets to learn from, which represents diverse types, magnitudes and combinations of shifts (covariate shift, label shift, spurious correlations). We train the model to predict the relative performance of algorithms given a dataset’s characteristics. This enables a priori selection of the best learning strategy, i.e. without training various models as needed with traditional model selection. Our experiments show that the adaptive selection outperforms any individual algorithm and simple selection heuristics, on unseen datasets of controllable and realistic image data. Inspecting the model shows that it learns non-trivial data/algorithms interactions, and reveals the conditions for any one algorithm to surpass another. This opens new avenues for (1) enhancing OOD generalization with existing algorithms instead of designing new ones, and (2) gaining insights into the applicability of existing algorithms with respect to datasets’ properties. © 2024, CC BY.

关键词： consensus algorithm

Dependable IoT Using Blockchain-Based Technology

学校读者我要写书评

暂无评论

Dependable IoT Using Blockchain-Based Technology

Latin-American Symposium on Dependable Computing, LADC

作者： Avelino F. Zorzo Henry C. Nunes Roben C. Lunardi Regio A. Michelin Salil S. Kanhere Pontifical Catholic University of Rio Grande do Sul (PUCRS) Porto Alegre Brazil Federal Institute of Rio Grande do Sul (IFRS) Porto Alegre Brazil University of New South Wales (UNSW) Sydney Australia

ISBN: (纸本)9781538684900;9781538684894

In the last few years, novel approaches for using blockchain to solve Internet of Things (IoT) security and dependability issues have been proposed. Currently, different solutions were applied to Smart Homes, Smart Cities, Smart Grids, Supply Chains, Industry, and Vehicular Networks scenarios. Despite of that, the main advantages on the adoption of different architectures, models and algorithms proposed in the state of art of blockchain in IoT scenarios are not yet clear. This paper presents some discussion about the usage of blockchain technology in IoT environments and proposes a layer model of blockchains for IoT. In addition, we present an overview of the latest research regarding network architectures, consensus algorithms, data management, and applications. Finally, this paper presents open issues and future trends about blockchain in IoT.

关键词： Blockchain consensus algorithm Computer architecture Bitcoin Proposals Smart contracts

Constructive Verifiability of algorithms and P Versus Np

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Hole, Arne University of Oslo P.O Box 1099 Blindern Oslo0317 Norway

A class of decision problems related to inconsistency proofs for formal theories is used to argue that under a constructive interpretation of algorithm verifiability, an assumption referred to as the MW thesis is valid. If one includes the MW thesis as an axiom in complexity theory, one may explicitly construct decision problems in NP which are not algorithmically solvable. In particular, the MW thesis implies that P is not equal to NP. © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Conjugacy in finite classical groups

学校读者我要写书评

暂无评论

arXiv 2024年

作者： De Franceschi, Giovanni Liebeck, Martin W. O’Brien, E.A. Department of Mathematics University of Auckland Auckland New Zealand Imperial College LondonSW7 2AZ United Kingdom

Let G be a classical group defined over a finite field. We consider the following fundamental problems concerning conjugacy in G: • List a representative for each conjugacy class of G. • Given x ∈ G, describe the centralizer of x in G, by giving its group structure and a generating set. • Given x, y ∈ G, establish whether x and y are conjugate in G and, if so, then find explicit z ∈ G such that z−1xz = y. We present comprehensive theoretical solutions to all three problems, and use our solutions to formulate practical algorithms. In parallel to our theoretical work, we have developed in Magma complete implementations of our algorithms. They form a critical component of various general algorithms in computational group theory - for example, computing character tables and solving conjugacy problems in arbitrary finite *** Codes 20C33, 20E45 © 2024, CC BY-NC-ND.

关键词： consensus algorithm

ON EVENTUALLY GREEDY BEST UNDERAPPROXIMATIONS BY EGYPTIAN FRACTIONS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kovač, Vjekoslav Department of Mathematics Faculty of Science University of Zagreb Bijenička cesta 30 Zagreb10000 Croatia

Erdős and Graham found it conceivable that the best n-term Egyptian underapproximation of almost every positive number for sufficiently large n gets constructed in a greedy manner, i.e., from the best (n−1)-term Egyptian underapproximation. We show that the opposite is true: the set of real numbers with this property has Lebesgue measure zero. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Decentralized Online Riemannian Optimization with Dynamic Environments

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Hengchao Sun, Qiang University of Toronto Canada MBZUAI United Arab Emirates

This paper develops the first decentralized online Riemannian optimization algorithm on Hadamard manifolds. Our algorithm, the decentralized projected Riemannian gradient descent, iteratively performs local updates using projected Riemannian gradient descent and a consensus step via weighted Fréchet mean. Theoretically, we establish linear variance reduction for the consensus step. Building on this, we prove a dynamic regret bound of order O(pT(1 + PT)/p(1 - σ2(W))), where T is the time horizon, PT represents the path variation measuring nonstationarity, and σ2(W) measures the network connectivity. The weighted Fréchet mean in our algorithm incurs a minimization problem, which can be computationally expensive. To further alleviate this cost, we propose a simplified consensus step with a closed-form, replacing the weighted Fréchet mean. We then establish linear variance reduction for this alternative and prove that the decentralized algorithm, even with this simple consensus step, achieves the same dynamic regret bound. Finally, we validate our approach with experiments on nonstationary decentralized Fréchet mean computation over hyperbolic spaces and the space of symmetric positive definite matrices, demonstrating the effectiveness of our methods. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

A Comparative Analysis of Distributed Linear Solvers under Data Heterogeneity

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Velasevic, Boris Parasnis, Rohit Brinton, Christopher G. Azizan, Navid MIT United States Purdue United States

We consider the fundamental problem of solving a large-scale system of linear equations in a distributed/federated manner. The taskmaster solves the system with the help of a set of machines, each possessing a subset of the equations. While there exist several approaches for solving this problem, missing is a rigorous comparison between the convergence rates of two different classes of algorithms, namely, the projection-based methods and the optimization-based ones. In this paper, we provide a comprehensive analysis and comparison of these two classes of algorithms, with a particular focus on the most efficient method from each class, i.e., the recently proposed Accelerated Projection-Based consensus (APC) [1] and the Distributed Heavy-Ball Method (D-HBM). To this end, we first introduce a novel, geometric notion of data heterogeneity called angular heterogeneity and discuss its generality. Using this notion, we characterize and compare the optimal convergence rates of several well-known algorithms and capture the effects of the number of machines, the number of equations, and both cross-machine and local data heterogeneity on these rates. Our analysis not only establishes the superiority of APC for realistic scenarios where there is a large data heterogeneity, but also provides several insights into the effect of angular heterogeneity on the efficiencies of the studied methods. Additionally, we leverage existing results in numerical linear algebra to obtain distributed algorithms for the efficient computation of the proposed angular heterogeneity metrics. Lastly, as a by-product of our investigation, we obtain a tight bound on the condition number of an arbitrary square matrix in terms of the Euclidean norms of its rows and the angles between them. Our theoretical findings are validated through numerical analyses, confirming the superior performance of APC in typical real-world settings and providing a deeper understanding of the effects of angular heterogeneity on

关键词： consensus algorithm