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

41st International Conference on machine learning, ICML 2024

作者： Shekhar, Shubhanshu Ramdas, Aaditya Department of Statistics and Data Science Carnegie Mellon University United States Machine Learning Department Carnegie Mellon University United States

We consider the problem of sequential change detection under minimal assumptions on the distribution generating the stream of observations. Formally, our goal is to design a scheme for detecting any changes in a parameter or functional θ of the data stream distribution that has small detection delay, but guarantees control on the frequency of false alarms in the absence of changes. We describe a simple reduction from sequential change detection to sequential estimation using confidence sequences (CSs): begin a new level-(1 − α) CS at each time step, and proclaim a change as soon as the intersection of all active CSs becomes empty. We prove that the average run length of our scheme is at least 1/α, resulting in a change detection scheme with minimal structural assumptions (thus allowing for possibly dependent observations, and nonparametric distribution classes), but strong guarantees. We also describe an interesting parallel with Lorden's reduction from change detection to sequential testing and connections to the recent "e-detector" framework. Copyright 2024 by the author(s)

关键词：

来源：评论

学校读者我要写书评

暂无评论

Foundations of Testing for Finite-Sample Causal Discovery 41

Foundations of Testing for Finite-Sample Causal Discovery

引用

41st International Conference on machine learning, ICML 2024

作者： Yan, Tom Xu, Ziyu Lipton, Zachary Machine Learning Department Carnegie Mellon University Pittsburgh United States Department of Statistics and Data Science Carnegie Mellon University Pittsburgh United States

Discovery of causal relationships is a fundamental goal of science and vital for sound decision making. As such, there has been considerable interest in causal discovery methods with provable guarantees. Existing works have thus far largely focused on discovery under hard intervention and infinite-samples, in which intervening on a node readily reveals the orientation of every edge incident to the node. This setup however overlooks the stochasticity inherent in real-world, finite-sample settings. Our work takes a step towards studying finite-sample causal discovery, wherein multiple interventions on a node are now needed for edge orientation. In this work, we study the canonical setup in theoretical causal discovery literature, where one assumes causal sufficiency and access to the graph skeleton. Our key observation is that discovery may be viewed as structured, multiple testing, and we develop a novel testing framework to this end. Crucially, our framework allows for anytime valid testing as multiple tests are needed to conclude an edge orientation. It also allows for flexible combination of structured test-statistics (enabling one to use Meek rules to propagate edge orientation) as well as robust testing. Through empirical simulations, we confirm the usefulness of our framework. In closing, using this testing framework, we show how one may efficiently verify graph structure by drawing a connection to multi-constraint bandits and designing a novel algorithm to this end. Copyright 2024 by the author(s)

关键词： Stochastic systems

来源：评论

学校读者我要写书评

暂无评论

Functional linear non-Gaussian acyclic model for causal discovery

引用

Behaviormetrika 2024年第2期51卷 567-588页

作者： Yang, Tian-Le Lee, Kuang-Yao Zhang, Kun Suzuki, Joe Graduate School of Engineering Science Osaka University Osaka Japan Department of Statistics Operations and Data Science Temple University Philadelphia United States Machine Learning Department Carnegie Mellon University Pittsburgh United States Machine Learning Department MBZUAI Abu Dhabi United Arab Emirates

In causal discovery, non-Gaussianity has been used to characterize the complete configuration of a linear non-Gaussian acyclic model (LiNGAM), encompassing both the causal ordering of variables and their respective connection strengths. However, LiNGAM can only deal with the finite-dimensional case. To expand this concept, we extend the notion of variables to encompass vectors and even functions, leading to the functional linear non-Gaussian acyclic model (Func-LiNGAM). Our motivation stems from the desire to identify causal relationships in brain-effective connectivity tasks involving, for example, fMRI and EEG datasets. We demonstrate why the original LiNGAM fails to handle these inherently infinite-dimensional datasets and explain the availability of functional data analysis from both empirical and theoretical perspectives. We establish theoretical guarantees of the identifiability of the causal relationship among non-Gaussian random vectors and even random functions in infinite-dimensional Hilbert spaces. To address the issue of sparsity in discrete time points within intrinsic infinite-dimensional functional data, we propose optimizing the coordinates of the vectors using functional principal component analysis. Experimental results on synthetic data verify the ability of the proposed framework to identify causal relationships among multivariate functions using the observed samples. For real data, we focus on analyzing the brain connectivity patterns derived from fMRI data. © The Behaviormetric Society 2024.

关键词： Causal discovery Darmois–Skitovich theorem Functional data Gaussian process LiNGAM Non-Gaussian

来源：评论

学校读者我要写书评

暂无评论

Optimal bounds for p sensitivity sampling via 2 augmentation 41

Optimal bounds for p sensitivity sampling via 2 augmentation

引用

41st International Conference on machine learning, ICML 2024

作者： Munteanu, Alexander Omlor, Simon Dortmund Data Science Center Faculties of Statistics and Computer Science TU Dortmund University Dortmund Germany Faculty of Statistics TU Dortmund University Dortmund Germany Lamarr-Institute for Machine Learning and Artificial Intelligence Dortmund Germany

data subsampling is one of the most natural methods to approximate a massively large data set by a small representative proxy. In particular, sensitivity sampling received a lot of attention, which samples points proportional to an individual importance measure called sensitivity. This framework reduces in very general settings the size of data to roughly the VC dimension d times the total sensitivity S while providing strong (1 ± Ε) guarantees on the quality of approximation. The recent work of Woodruff & Yasuda (2023c) improved substantially over the general Õ(Ε−2Sd) bound for the important problem of p subspace embeddings to Õ(Ε−2S2/p) for p ∈ [1, 2]. Their result was subsumed by an earlier Õ(Ε−2Sd1−p/2) bound which was implicitly given in the work of Chen & Derezinski (2021). We show that their result is tight when sampling according to plain p sensitivities. We observe that by augmenting the p sensitivities by 2 sensitivities, we obtain better bounds improving over the aforementioned results to optimal linear Õ(Ε−2(S+d)) = Õ(Ε−2d) sampling complexity for all p ∈ [1, 2]. In particular, this resolves an open question of Woodruff & Yasuda (2023c) in the affirmative for p ∈ [1, 2] and brings sensitivity subsampling into the regime that was previously only known to be possible using Lewis weights (Cohen & Peng, 2015). As an application of our main result, we also obtain an Õ(Ε−2µd) sensitivity sampling bound for logistic regression, where µ is a natural complexity measure for this problem. This improves over the previous Õ(Ε−2µ2d) bound of Mai et al. (2021) which was based on Lewis weights subsampling. Copyright 2024 by the author(s)

关键词： Importance sampling

来源：评论

学校读者我要写书评

暂无评论

Turnstile p leverage score sampling with applications 41

Turnstile p leverage score sampling with applications

引用

41st International Conference on machine learning, ICML 2024

The turnstile data stream model offers the most flexible framework where data can be manipulated dynamically, i.e., rows, columns, and even single entries of an input matrix can be added, deleted, or updated multiple times in a data stream. We develop a novel algorithm for sampling rows ai of a matrix A ∈ Rn×d, proportional to their p norm, when A is presented in a turnstile data stream. Our algorithm not only returns the set of sampled row indexes, it also returns slightly perturbed rows ãi ≈ ai, and approximates their sampling probabilities up to Ε relative error. When combined with preconditioning techniques, our algorithm extends to p leverage score sampling over turnstile data streams. With these properties in place, it allows us to simulate subsampling constructions of coresets for important regression problems to operate over turnstile data streams with very little overhead compared to their respective off-line subsampling algorithms. For logistic regression, our framework yields the first algorithm that achieves a (1 + Ε) approximation and works in a turnstile data stream using polynomial sketch/subsample size, improving over O(1) approximations, or exp(1/Ε) sketch size of previous work. We compare experimentally to plain oblivious sketching and plain leverage score sampling algorithms for p and logistic regression. Copyright 2024 by the author(s)

关键词： data streams

来源：评论

学校读者我要写书评

暂无评论

An Efficient Doubly-Robust Test for the Kernel Treatment Effect 37

An Efficient Doubly-Robust Test for the Kernel Treatment Eff...

引用

37th Conference on Neural Information Processing Systems, NeurIPS 2023

作者： Martinez-Taboada, Diego Ramdas, Aaditya Kennedy, Edward H. Department of Statistics and Data Science Carnegie Mellon University PittsburghPA15213 United States Department of Statistics and Data Science Machine Learning Department Carnegie Mellon University PittsburghPA15213 United States

ISBN: (纸本)9781713899921

The average treatment effect, which is the difference in expectation of the counterfactuals, is probably the most popular target effect in causal inference with binary treatments. However, treatments may have effects beyond the mean, for instance decreasing or increasing the variance. We propose a new kernel-based test for distributional effects of the treatment. It is, to the best of our knowledge, the first kernel-based, doubly-robust test with provably valid type-I error. Furthermore, our proposed algorithm is computationally efficient, avoiding the use of permutations. © 2023 Neural information processing systems foundation. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Convergence Analysis of Probability Flow ODE for Score-Based Generative Models

引用

IEEE Transactions on Information Theory 2025年第6期71卷 4581-4601页

作者： Huang, Daniel Zhengyu Huang, Jiaoyang Lin, Zhengjiang Peking University Beijing International Center for Mathematical Research Center for Machine Learning Research Beijing100871 China University of Pennsylvania Department of Statistics and Data Science PhiladelphiaPA19104 United States Massachusetts Institute of Technology Department of Mathematics CambridgeMA02139 United States

Score-based generative models have emerged as a powerful approach for sampling high-dimensional probability distributions. Despite their effectiveness, their theoretical underpinnings remain relatively underdeveloped. In this work, we study the convergence properties of deterministic samplers based on probability flow ODEs from both theoretical and numerical perspectives. Assuming access to L2 -accurate estimates of the score function, we prove the total variation between the target and the generated data distributions can be bounded above by Q(d3/4 δ1/2) in the continuous time level, where d denotes the data dimension and δ represents the L2 -score matching error. For practical implementations using a p-th order Runge-Kutta integrator with step size h, we establish error bounds of Q(d3/4 δ1/2 + d·(dhp) athe discrete level. Finally, we present numerical studies on problems up to 128 dimensions to verify our theory. © 1963-2012 IEEE.

关键词： Continuous time systems

来源：评论

学校读者我要写书评

暂无评论

Game-Theoretic statistics and Safe Anytime-Valid Inference

引用

Statistical science 2023年第4期38卷 576-597页

作者： Ramdas, Aaditya Grünwald, Peter Vovk, Vladimir Shafer, Glenn Statistics and Data Science Machine Learning Carnegie Mellon University Pittsburgh 15213 PA United States Machine Learning Group Centrum Wiskunde Informatica Amsterdam Netherlands Computer Science Royal Holloway University of London United Kingdom Rutgers University Piscataway 08854-8019 NJ United States

Safe anytime-valid inference (SAVI) provides measures of statistical evidence and certainty—e-processes for testing and confidence sequences for estimation—that remain valid at all stopping times, accommodating continuous monitoring and analysis of accumulating data and optional stopping or continuation for any reason. These measures crucially rely on test martingales, which are nonnegative martingales starting at one. Since a test martingale is the wealth process of a player in a betting game, SAVI centrally employs game-theoretic intuition, language and *** summarize the SAVI goals and philosophy, and report recent advances in testing composite hypotheses and estimating functionals in nonparametric settings. © (2023) All Rights Reserved.

关键词： confidence sequence e-process nonparametric composite hypothesis testing optional stopping reverse information projection Test martingales universal inference Ville’s inequality

来源：评论

学校读者我要写书评

暂无评论

Reducing sequential change detection to sequential estimation 24

Reducing sequential change detection to sequential estimatio...

引用

Proceedings of the 41st International Conference on machine learning

作者： Shubhanshu Shekhar Aaditya Ramdas Department of Statistics and Data Science Carnegie Mellon University Department of Statistics and Data Science and Machine Learning Department Carnegie Mellon University

We consider the problem of sequential change detection under minimal assumptions on the distribution generating the stream of observations. Formally, our goal is to design a scheme for detecting any changes in a parameter or functional θ of the data stream distribution that has small detection delay, but guarantees control on the frequency of false alarms in the absence of changes. We describe a simple reduction from sequential change detection to sequential estimation using confidence sequences (CSs): begin a new level- (1 - α) CS at each time step, and proclaim a change as soon as the intersection of all active CSs becomes empty. We prove that the average run length of our scheme is at least 1/α, resulting in a change detection scheme with minimal structural assumptions (thus allowing for possibly dependent observations, and nonparametric distribution classes), but strong guarantees. We also describe an interesting parallel with Lorden's reduction from change detection to sequential testing and connections to the recent "e-detector" framework

关键词：

来源：评论

学校读者我要写书评

暂无评论

More powerful multiple testing under dependence via randomization

arXiv

引用

arXiv 2023年

作者： Xu, Ziyu Ramdas, Aaditya Department of Statistics and Data Science Carnegie Mellon University United States Departments of Statistics and Data Science and Machine Learning Carnegie Mellon University United States

We show that two procedures for false discovery rate (FDR) control — the Benjamini-Yekutieli procedure for dependent p-values, and the e-Benjamini-Hochberg procedure for dependent e-values — can both be made more powerful by a simple randomization involving one independent uniform random variable. As a corollary, the Hommel test under arbitrary dependence is also improved. Importantly, our randomized improvements are never worse than the originals and are typically strictly more powerful, with marked improvements in simulations. The same technique also improves essentially every other multiple testing procedure based on e-values. Copyright © 2023, The Authors. All rights reserved.

关键词： Random processes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：