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

3rd Conference on Causal Learning and Reasoning

作者： Dalvi, Abhishek Ashtekar, Neil Honavar, Vasant Penn State Univ University Pk PA 16802 USA

Matching is one of the simplest approaches for estimating causal effects from observational data. Matching techniques compare the observed outcomes across pairs of individuals with similar covariate values but different treatment statuses in order to estimate causal effects. However, traditional matching techniques are unreliable given high-dimensional covariates due to the infamous curse of dimensionality. To overcome this challenge, we propose a simple, fast, yet highly effective approach to matching using Random Hyperplane Tessellations (RHPT). First, we prove that the RHPT representation is an approximate balancing score - thus maintaining the strong ignorability assumption - and provide empirical evidence for this claim. Second, we report results of extensive experiments showing that matching using RHPT outperforms traditional matching techniques and is competitive with state-of-the-art deep learning methods for causal effect estimation. In addition, RHPT avoids the need for computationally expensive training of deep neural networks.

关键词： Matching randomized algorithms High-Dimensional data

来源：评论

学校读者我要写书评

暂无评论

Efficient Predicate Evaluation Using randomized Degeneracy Detection

引用

International Journal of Computational Geometry and Applications 2022年第1-2期32卷 39-54页

作者： Milenkovic, Victor Sacks, Elisha Department of Computer Science University of Miami Coral Gables 33124-4245 FL United States Computer Science Department Purdue University West Lafayette 47907-2066 IN United States

Computational geometry algorithms branch on the signs of predicates. Prior predicate evaluation techniques are slow on degenerate (zero sign) predicates, especially on predicates on algebraic numbers. Degeneracy is common for predicates whose arguments have common antecedents. We present three randomized algorithms for degeneracy detection. The first algorithm uses modular arithmetic to detect degenerate predicates on rational numbers. The second algorithm uses quotient rings to reduce detecting degenerate predicates on algebraic numbers to multiple rational predicates, which can be evaluated deterministically or using the first algorithm. This algorithm is impractical because it is exponential in the number of algebraic numbers, yet it is still much faster than prior work that uses root separation bounds. The third algorithm uses a perturbation to eliminate degenerate algebraic predicates that are not identical to zero and a second perturbation to detect those that are. The first and third algorithms are incorporated into an exact geometric computation library. By sampling values generated by the algorithms, the library estimates the degeneracy detection failure probability over the lifetime of every calling program. We call this approach statistical degeneracy detection (SDD). Extensive testing shows that predicate evaluation is reliable and fast. © 2022 World Scientific Publishing Company.

关键词： degenerate predicates Exact geometric computation perturbation methods randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight Analyses of Ordered and Unordered Linear Probing 65

Tight Analyses of Ordered and Unordered Linear Probing

引用

65th Symposium on Foundations of Computer Science

作者： Braverman, Mark Kuszmaul, William Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9798331516758;9798331516741

Linear-probing hash tables have been classically believed to support insertions in time Theta(x(2)), where 1-1/x is the load factor of the hash table. Recent work by Bender, Kuszmaul, and Kuszmaul (FOCS'21), however, has added a new twist to this story: in some versions of linear probing, if the maximum load factor is at most 1 - 1/x, then the amortized expected time per insertion will never exceed x polylog x (even in workloads that operate continuously at a load factor of 1-1/x). Determining the exact asymptotic value for the amortized insertion time remains open. In this paper, we settle the amortized complexity with matching upper and lower bounds of Theta(x log(1.5) x). Along the way, we also obtain tight bounds for the so-called path surplus problem, a problem in combinatorial geometry that has been shown to be closely related to linear probing. We also show how to extend Bender et al.'s bounds to say something not just about ordered linear probing (the version they study) but also about classical linear probing, in the form that is most widely implemented in practice.

关键词： data structures hash tables linear probing randomized algorithms robin hood hashing

来源：评论

学校读者我要写书评

暂无评论

Learning Minimum Linear Arrangement of Cliques and Lines 44

Learning Minimum Linear Arrangement of Cliques and Lines

引用

44th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Dallot, Julien Pacut, Maciej Bienkowski, Marcin Melnyk, Darya Schmid, Stefan Tech Univ Berlin Berlin Germany Univ Wroclaw Wroclaw Poland

ISBN: (纸本)9798350386066;9798350386059

In the well-known Minimum Linear Arrangement problem (MinLA), the goal is to arrange the nodes of an undirected graph into a permutation so that the total stretch of the edges is minimized. This paper studies an online variant of MinLA where the graph is not given at the beginning, but rather revealed piece-by-piece. The algorithm starts in a fixed initial permutation, and after a piece of the graph is revealed, the algorithm must update its current permutation to be a MinLA of the subgraph revealed so far. The objective is to minimize the total number of swaps of adjacent nodes as the algorithm updates the permutation. The main result of this paper is an online randomized algorithm that solves the online MinLA problem for the restricted cases where the graph is either a collection of cliques or a collection of lines. We show that the algorithm is 8 ln n-competitive, where n is the number of nodes of the graph. We complement this result by constructing a lower bound of Omega(ln n) for competitiveness of any online algorithm, concluding that our randomized algorithm is asymptotically optimal.

关键词： minimum linear arrangement online computation randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Temporal Motif Densest Subnetwork Discovery 24

Scalable Temporal Motif Densest Subnetwork Discovery

引用

30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

作者： Sarpe, Ilie Vandin, Fabio Gionis, Aristides KTH Royal Inst Technol Stockholm Sweden Univ Padua Padua Italy

ISBN: (纸本)9798400704901

Finding dense subnetworks, with density based on edges or more complex structures, such as subgraphs or k-cliques, is a fundamental algorithmic problem with many applications. While the problem has been studied extensively in static networks, much remains to be explored for temporal networks. In this work we introduce the novel problem of identifying the temporal motif densest subnetwork, i.e., the densest subnetwork with respect to temporal motifs, which are high-order patterns characterizing temporal networks. Identifying temporal motifs is an extremely challenging task, and thus, efficient methods are required. To address this challenge, we design two novel randomized approximation algorithms with rigorous probabilistic guarantees that provide high-quality solutions. We perform extensive experiments showing that our methods outperform baselines. Furthermore, our algorithms scale on networks with up to billions of temporal edges, while baselines cannot handle such large networks. We use our techniques to analyze a financial network and show that our formulation reveals important network structures, such as bursty temporal events and communities of users with similar interests.

关键词： temporal motifs temporal networks randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Singletons for simpletons revisiting windowed backoff with Chernoff bounds

引用

THEORETICAL COMPUTER SCIENCE 2022年 909卷 39-53页

作者： Zhou, Qian M. Calvert, Alice Young, Maxwell Mississippi State Univ Dept Math & Stat Mississippi State MS 39762 USA Program Mississippi State Univ & Mississippi Sch Mississippi State MS USA Mississippi State Univ Dept Comp Sci & Engn Mississippi State MS 39762 USA

Backoff algorithms are used in many distributed systems where multiple devices contend for a shared resource. For the classic balls-into-bins problem, the number of singletons- those bins with a single ball-is important to the analysis of several backoff algorithms;however, existing analyses employ advanced probabilistic tools. Here, we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing some well-known backoff algorithms. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Algorithmic simplicity Exponential backoff randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized Constraints Consensus for Distributed Robust Mixed-Integer Programming

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2021年第1期8卷 295-306页

作者： Chamanbaz, Mohammadreza Notarstefano, Giuseppe Sasso, Francesco Bouffanais, Roland Singapore Univ Technol & Design Engn Prod Dev EPD Singapore 487372 Singapore Univ Bologna Dept Elect Elect & Informat Engn G Marconi I-40126 Bologna Italy Univ Salento Dept Engn I-73100 Lecce Italy

In this article, we consider a network of processors aiming at cooperatively solving mixed-integer convex programs subject to uncertainty. Each node only knows a common cost function and its local uncertain constraint set. We propose a randomized, distributed algorithm working under asynchronous, unreliable, and directed communication. The algorithm is based on a local computation and communication paradigm. At each communication round, nodes perform two updates: 1) A verification in which they check-in a randomized fashion-the robust feasibility of a candidate optimal point, and 2) an optimization step in which they exchange their candidate basis (the minimal set of constraints defining a solution) with neighbors and locally solve an optimization problem. As a main result, we show that processors can stop the algorithm after a finite number of communication rounds (either because verification has been successful for a sufficient number of rounds or because a given threshold has been reached) so that candidate optimal solutions are consensual. The common solution has proven to be-with high confidence-feasible and, hence, optimal for the entire set of uncertainty except a subset having an arbitrarily small probability measure. We show the effectiveness of the proposed distributed algorithm using two examples: a random, uncertain mixed-integer linear program and a distributed localization in wireless sensor networks. The distributed algorithm is implemented on a multicore platform in which the nodes communicate asynchronously.

关键词： Distributed optimization mixed-integer programming randomized algorithms robust optimization

来源：评论

学校读者我要写书评

暂无评论

randomized Iterative Methods for Matrix Approximation 1

引用

7th International Conference on Machine Learning, Optimization, and Data Science (LOD) / 1st Symposium on Artificial Intelligence and Neuroscience (ACAIN)

作者： Azzam, Joy Ong, Benjamin W. Struthers, Allan A. Michigan Technol Univ Dept Math Sci Houghton MI 49931 USA

ISBN: (数字)9783030954703

ISBN: (纸本)9783030954703;9783030954697

Standard tools to update approximations to a matrix A (for example, Quasi-Newton Hessian approximations in optimization) incorporate computationally expensive one-sided samples AV. This article develops randomized algorithms to efficiently approximate A by iteratively incorporating cheaper two-sided samples U-inverted perpendicular AV. Theoretical convergence rates are proved and realized in numerical experiments. A heuristic accelerated variant is developed and shown to be competitive with existing methods based on one-sided samples.

关键词： Matrix approximation randomized algorithms Two-sided samples Quasi-Newton

来源：评论

学校读者我要写书评

暂无评论

Naively Sorting Evolving Data is Optimal and Robust 65

Naively Sorting Evolving Data is Optimal and Robust

引用

65th Symposium on Foundations of Computer Science

作者： Giakkoupis, George Kiwi, Marcos Los, Dimitrios Univ Rennes IRISA CNRS Inria Rennes France Univ Chile Santiago Chile

ISBN: (纸本)9798331516758;9798331516741

We study comparison sorting in the evolving data model, introduced by Anagnostopoulos, Kumar, Mahdian and Upfal (2011), where the true total order changes while the sorting algorithm is processing the input. More precisely, each comparison operation of the algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the rank of a random item by a "small" random value. The goal is to maintain an ordering that remains close to the true order over time. Previous works have analyzed adaptations of classic sorting algorithms, assuming that an evolution step changes the rank of an item by just one, and that a fixed constant number b of evolution steps take place between two comparisons. In fact, the only previous result achieving optimal linear total deviation, by Besa Vial, Devanny, Eppstein, Goodrich and Johnson (2018a), applies just for b = 1. We analyze a very simple sorting algorithm suggested by Mahdian (2014), which samples a random pair of adjacent items in each step and swaps them if they are out of order. We show that the algorithm achieves and maintains, with high probability, optimal total deviation, O(n), and optimal maximum deviation, O(log n), under very general model settings. Namely, the perturbation introduced by each evolution step is sampled from a general distribution of bounded moment generating function, and we just require that the average number of evolution steps between two sorting steps be bounded by an (arbitrary) constant, where the average is over a linear number of steps. The key ingredients of our proof are a novel potential function argument that inserts "gaps" in the list of items, and a general analysis framework which separates the analysis of sorting from that of the evolution steps, and is applicable to a variety of settings for which previous approaches do not apply. Our results settle conjectures and open problems in the three aforementioned works, and provide theoretical support that simple quadratic al

关键词： randomized algorithms sorting evolving data model evolving ranking exponential potential functions

来源：评论

学校读者我要写书评

暂无评论

Online Matching with High Probability 17th

Online Matching with High Probability

引用

17th International Symposium on Algorithmic Game Theory (SAGT)

作者： Mihail, Milena Trobst, Thorben Univ Calif Irvine Dept Comp Sci Irvine CA 92717 USA

ISBN: (纸本)9783031710322;9783031710339

We study the classical, randomized RANKING algorithm, which is known to be (1 - 1/epsilon)-competitive in expectation for the Online Bipartite Matching Problem. We give a tail inequality bound (Theorem 1), namely that RANKING is (1 - 1/epsilon - alpha)-competitive with probability at least 1 - e(-2 alpha 2n) where n is the size of the maximum matching in the instance. Building on this, we show similar concentration results for several generalizations of the Online Bipartite Matching Problem, including the Fully Online Matching Problem and the Online Vertex-Weighted Bipartite Matching Problem.

关键词： Online algorithms Concentration of Measure Online Matching randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：