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

BETTY: AN AUTOMATIC DIFFERENTIATION LIBRARY FOR MULTILEVEL OPTIMIZATION

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Choe, Sang Keun Neiswanger, Willie Xie, Pengtao Xing, Eric Carnegie Mellon University United States Stanford University United States UCSD United States MBZUAI United Arab Emirates

Gradient-based multilevel optimization (MLO) has gained attention as a framework for studying numerous problems, ranging from hyperparameter optimization and meta-learning to neural architecture search and reinforcement learning. However, gradients in MLO, which are obtained by composing best-response Jacobians via the chain rule, are notoriously difficult to implement and memory/compute intensive. We take an initial step towards closing this gap by introducing BETTY, a software library for large-scale MLO. At its core, we devise a novel dataflow graph for MLO, which allows us to (1) develop efficient automatic differentiation for MLO that reduces the computational complexity from O(d3) to O(d2), (2) incorporate systems support such as mixed-precision and data-parallel training for scalability, and (3) facilitate implementation of MLO programs of arbitrary complexity while allowing a modular interface for diverse algorithmic and systems design choices. We empirically demonstrate that BETTY can be used to implement an array of MLO programs, while also observing up to 11% increase in test accuracy, 14% decrease in GPU memory usage, and 20% decrease in training wall time over existing implementations on multiple benchmarks. We also showcase that BETTY enables scaling MLO to models with hundreds of millions of parameters. We open-source the code at https://***/leopard-ai/betty. Copyright © 2022, The Authors. All rights reserved.

关键词： parallel processing systems

Maker-Breaker is solved in polynomial time on hypergraphs of rank 3

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Galliot, Florian Gravier, Sylvain Sivignon, Isabelle Univ. Grenoble Alpes CNRS Institut Fourier Grenoble38000 France Univ. Grenoble Alpes CNRS Grenoble INP GIPSA-lab Grenoble38000 France Univ. Grenoble Alpes Maths à Modeler Grenoble38000 France

In the Maker-Breaker positional game, Maker and Breaker take turns picking vertices of a hypergraph H, and Maker wins if and only if he claims all the vertices of some edge of H. This paper provides a general framework to study Maker-Breaker games, centered on the notion of danger at a vertex x, which is a subhypergraph representing an urgent threat that Breaker must hit with his next pick if Maker picks x. We then apply this concept in hypergraphs of rank 3, providing a structural characterization of the winner with perfect play as well as optimal strategies for both players based on danger intersections. We construct a family F of dangers such that a hypergraph H of rank 3 is a Breaker win if and only if the F-dangers at x in H intersect for all x. By construction of F, this will mean that H is a Maker win if and only if Maker can guarantee the appearance, within the first three rounds of play, of a very specific elementary subhypergraph (on which Maker easily wins). This last result has a consequence on the algorithmic complexity of deciding which player has a winning strategy on a given hypergraph: this problem, which is known to be PSPACE-complete on 6-uniform hypergraphs [15], is in polynomial time on hypergraphs of rank 3. This validates a conjecture by Rahman and Watson [14]. Another corollary of our result is that, if Maker has a winning strategy on a hypergraph of rank 3, then he can ensure to claim an edge in a number of rounds that is logarithmic in the number of vertices. Copyright © 2022, The Authors. All rights reserved.

关键词： parallel processing systems

Compression ensembles quantify aesthetic complexity and the evolution of visual art

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Karjus, Andres Solà, Mar Canet Ohm, Tillmann Ahnert, Sebastian E. Schich, Maximilian ERA Cultural Data Analytics Tallinn University Estonia University of Cambridge United Kingdom The Alan Turing Institute United Kingdom

The quantification of visual aesthetics and complexity have a long history, the latter previously operationalized via the application of compression algorithms. Here we generalize and extend the compression approach beyond simple complexity measures to quantify algorithmic distance in historical and contemporary visual media. The proposed "ensemble" approach works by compressing a large number of transformed versions of a given input image, resulting in a vector of associated compression ratios. This approach is more efficient than other compression-based algorithmic distances, and is particularly suited for the quantitative analysis of visual artifacts, because human creative processes can be understood as algorithms in the broadest sense. Unlike comparable image embedding methods using machine learning, our approach is fully explainable through the transformations. We demonstrate that the method is cognitively plausible and fit for purpose by evaluating it against human complexity judgments, and on automated detection tasks of authorship and style. We show how the approach can be used to reveal and quantify trends in art historical data, both on the scale of centuries and in rapidly evolving contemporary NFT art markets. We further quantify temporal resemblance to disambiguate artists outside the documented mainstream from those who are deeply embedded in Zeitgeist. Finally, we note that compression ensembles constitute a quantitative representation of the concept of visual family resemblance, as distinct sets of dimensions correspond to shared visual characteristics otherwise hard to pin down. Our approach provides a new perspective for the study of visual art, algorithmic image analysis, and quantitative aesthetics more generally. Copyright © 2022, The Authors. All rights reserved.

关键词： parallel processing systems

Cryptanalysis of a System based on Twisted Dihedral Group Algebras

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Tinani, Simran

Several cryptographic protocols constructed based on less-known algorithmic problems, such as those in non-commutative groups, group rings, semigroups, etc., which claim quantum security, have been broken through classical reduction methods within their specific proposed platforms. A rigorous examination of the complexity of these algorithmic problems is therefore an important topic of research. In this paper, we present a cryptanalysis of a public key exchange system based on a decomposition-type problem in the so-called twisted group algebras of the dihedral group D2n over a finite field Fq. Our method of analysis relies on an algebraic reduction of the original problem to a set of equations over Fq involving circulant matrices, and a subsequent solution to these equations. Our attack runs in polynomial time and succeeds with probability at least 90 percent for the parameter values provided by the authors. We also show that the underlying algorithmic problem, while based on a non-commutative structure, may be formulated as a commutative semigroup action problem. © 2022, CC BY.

关键词： parallel processing systems

Measuring algorithmic interpretability: A human-learning-based framework and the corresponding cognitive complexity score

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Lalor, John P. Guo, Hong IT Analytics and Operations Department Mendoza College of Business University of Notre Dame Notre DameIN46556 United States

Algorithmic interpretability is necessary to build trust, ensure fairness, and track accountability. However, there is no existing formal measurement method for algorithmic interpretability. In this work, we build upon programming language theory and cognitive load theory to develop a framework for measuring algorithmic interpretability. The proposed measurement framework reflects the process of a human learning an algorithm. We show that the measurement framework and the resulting cognitive complexity score have the following desirable properties - universality, computability, uniqueness, and monotonicity. We illustrate the measurement framework through a toy example, describe the framework and its conceptual underpinnings, and demonstrate the benefits of the framework, in particular for managers considering tradeoffs when selecting algorithms. © 2022, CC BY.

关键词： parallel processing systems

DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Feng, Yelai Wang, Huaixi Zhu, Yining Liu, Xiandong Lu, Hongyi Liu, Qing College of Electronic Engineering National University of Defense Technology Hefei China College of Computer Science and Technology National University of Defense Technology Changsha China Ningbo Institute of Technolog Zhejiang University Ningbo China PerfXLab Technologies Co. Ltd Beijing China College of Electrical and Computer Engineering Technical University of Munich Munich Germany

The shortest paths problem is a fundamental challenge in graph theory, with a broad range of potential applications. The algorithms based on matrix multiplication exhibits excellent parallelism and scalability, but is constrained by high memory consumption and algorithmic complexity. Traditional shortest paths algorithms are limited by priority queues, such as BFS and Dijkstra algorithm, making the improvement of their parallelism a focal issue. We propose a matrix operation-optimized algorithm, which offers improved parallelism, reduced time complexity, and lower memory consumption. The novel algorithm requires O(Ewcc (i)) and O(Swcc · Ewcc) times for single-source and all-pairs shortest paths problems, respectively, where Swcc and Ewcc denote the number of nodes and edges included in the largest weakly connected component in graph. To evaluate the effectiveness of the novel algorithm, we tested it using graphs from SuiteSparse Matrix Collection and Gunrock benchmark dataset. Our algorithm outperformed the BFS implementations from Gunrock and GAP (the previous state-of-the-art solution), achieving an average speedup of 3.769× and 9.410×, respectively. © 2022, CC BY-NC-ND.

关键词： parallel processing systems

Essentially entropic lattice Boltzmann model: Theory and simulations

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Atif, Mohammad Kolluru, Praveen Kumar Ansumali, Santosh Jawaharlal Nehru Centre for Advanced Scientific Research Jakkur Bangalore560064 India SankhyaSutra Labs Limited Bangalore India

We present a detailed description of the essentially entropic lattice Boltzmann model. The entropic lattice Boltzmann model guarantees unconditional numerical stability by iteratively solving the nonlinear entropy evolution equation. In this paper we explain the construction of closed-form analytic solutions to this equation. We demonstrate that near equilibrium this exact solution reduces to the standard lattice Boltzmann model. We consider a few test cases to show that the exact solution does not exhibit any significant deviation from the iterative solution. We also extend the analytical solution for the ES-BGK model to remove the limitation on the Prandtl number for heat transfer problems. The simplicity of the exact solution removes the computational overhead and algorithmic complexity associated with the entropic lattice Boltzmann models. © 2022, CC BY.

关键词： parallel processing systems

Analytical Confidence Intervals for the Number of Different Objects in Data Streams

学校读者我要写书评

暂无评论

BIG DATA RESEARCH 2021年 25卷

作者： Aletti, Giacomo Univ Milan ADAMSS Ctr Milan Italy

This paper develops a new mathematical-statistical approach to analyze a class of Flajolet-Martin algorithms (FMa), and provides analytical confidence intervals for the number F-0 of distinct elements in a stream, based on Chernoff bounds. The class of FMa has reached a significant popularity in bigdata stream learning, and the attention of the literature has mainly been based on algorithmic aspects, basically complexity optimality, while the statistical analysis of these class of algorithms has been often faced heuristically. The analysis provided here shows deep connections with mathematical special functions and with extreme value theory. The latter connection may help in explaining heuristic considerations, while the first opens many numerical issues, faced at the end of the present paper. Finally, the algorithms are tested on an anonymized real data stream and MonteCarlo simulations are provided to support our analytical choice in this context. (C) 2021 Elsevier Inc. All rights reserved.

关键词： parallel processing systems

TOIChain™: A Proposal for High Performance Tamper Resistant Transactions Without Scaling Limits 20th

学校读者我要写书评

暂无评论

TOIChain™: A Proposal for High Performance Tamper Resistant...

20th International Conference on Foundations of Computer Science, FCS 2024, and 20th International Conference on Frontiers in Education, FECS 2024, held as part of the World Congress in Computer Science, Computer Engineering and Applied Computing, CSCE 2024

作者： Shi, Justin Y. SMC Labs 630 Freedom Business Drive King of PrussiaPA19406 United States SERC 315 College of Science and Technology Temple University PhiladelphiaPA19122 United States

ISBN: (纸本)9783031859298

This paper proposes a blockchain-based high performance transaction processing system called TOIChain. A new programming paradigm and architecture using Active Content Addressable Networking protocol and Statistic Multiplexed Computing runtime is introduced to overcome the typical service infrastructure scalability challenges. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： parallel processing systems