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

Statistical guarantees for local spectral clustering on random neighborhood graphs

Journal of machine learning Research 2021年第1期22卷 1-71页

作者： Green, Alden Balakrishnan, Sivaraman Tibshirani, Ryan J. 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

We study the Personalized PageRank (PPR) algorithm, a local spectral method for clustering, which extracts clusters using locally-biased random walks around a given seed node. In contrast to previous work, we adopt a classical statistical learning setup, where we obtain samples from an unknown nonparametric distribution, and aim to identify sufficiently salient clusters. We introduce a trio of population-level functionals—the normalized cut, conductance, and local spread, analogous to graph-based functionals of the same name—and prove that PPR, run on a neighborhood graph, recovers clusters with small population normalized cut and large conductance and local spread. We apply our general theory to establish that PPR identifies connected regions of high density (density clusters) that satisfy a set of natural geometric conditions. We also show a converse result, that PPR can fail to recover geometrically poorly-conditioned density clusters, even asymptotically. Finally, we provide empirical support for our theory. ©2021 Alden Green, Sivaraman Balakrishnan, and Ryan J. Tibshirani.

关键词： Unsupervised learning

来源：评论

学校读者我要写书评

暂无评论

Combining Evidence Across Filtrations

arXiv

引用

arXiv 2024年

作者： Choe, Yo Joong Ramdas, Aaditya Data Science Institute University of Chicago United States Department of Statistics and Data Science Machine Learning Department Carnegie Mellon University United States

In sequential anytime-valid inference, any admissible procedure must be based on e-processes: generalizations of test martingales that quantify the accumulated evidence against a composite null hypothesis at any stopping time. This paper proposes a method for combining e-processes constructed in different filtrations but for the same null. Although e-processes in the same filtration can be combined effortlessly (by averaging), e-processes in different filtrations cannot because their validity in a coarser filtration does not translate to a finer filtration. This issue arises in sequential tests of randomness and independence, as well as in the evaluation of sequential forecasters. We establish that a class of functions called adjusters can lift arbitrary e-processes across filtrations. The result yields a generally applicable "adjust-then-combine" procedure, which we demonstrate on the problem of testing randomness in real-world financial data. Furthermore, we prove a characterization theorem for adjusters that formalizes a sense in which using adjusters is necessary. There are two major implications. First, if we have a powerful e-process in a coarsened filtration, then we readily have a powerful e-process in the original filtration. Second, when we coarsen the filtration to construct an e-process, there is a logarithmic cost to recovering validity in the original filtration.1 © 2024, CC BY.

关键词： Wiener filtering

来源：评论

学校读者我要写书评

暂无评论

A permutation-free kernel independence test

The Journal of Machine Learning Research

引用

The Journal of machine learning Research 2023年第1期24卷 17707-17774页

作者： Shubhanshu Shekhar Ilmun Kim Aaditya Ramdas Department of Statistics and Data Science Carnegie Mellon University Pittsburgh PA Department of Statistics and Data Science Department of Applied Statistics Yonsei University Seodaemun-gu Seoul Republic of Korea Department of Statistics and Data Science Machine Learning Department Carnegie Mellon University Pittsburgh PA

In nonparametric independence testing, we observe i.i.d. data {(Xi, Yi)}ni=1, where X ∈ Χ, Y ∈ Y lie in any general spaces, and we wish to test the null that X is independent of Y. Modern test statistics such as the kernel Hilbert-Schmidt Independence Criterion (HSIC) and Distance Covariance (dCov) have intractable null distributions due to the degeneracy of the underlying U-statistics. Hence, in practice, one often resorts to using permutation testing, which provides a nonasymptotic guarantee at the expense of recalculating the quadratic-time statistics (say) a few hundred times. In this paper, we provide a simple but nontrivial modification of HSIC and dCov (called xHSIC and xdCov, pronounced "cross" HSIC/dCov) so that they have a limiting Gaussian distribution under the null, and thus do not require permutations. We show that our new tests, like the originals, are consistent against fixed alternatives, and minimax rate optimal against smooth local alternatives. Numerical simulations demonstrate that compared to the permutation tests, our variants have the same power within a constant factor, giving practitioners a new option for large problems or data-analysis pipelines where computation, not sample size, could be the bottleneck.

关键词： independence testing kernel-methods permutation-free tests Hilbert-Schmidt independence critrion (HSIC) distance covariance

来源：评论

学校读者我要写书评

暂无评论

Bagging in overparameterized learning: risk characterization and risk monotonization

The Journal of Machine Learning Research

引用

The Journal of machine learning Research 2023年第1期24卷 15081-15193页

作者： Pratik Patil Jin-Hong Du Arun Kumar Kuchibhotla Department of Statistics University of California Berkeley Berkeley CA Department of Statistics and Data Science & Machine Learning Department Carnegie Mellon University Pittsburgh PA Department of Statistics and Data Science Carnegie Mellon University Pittsburgh PA

Bagging is a commonly used ensemble technique in statistics and machine learning to improve the performance of prediction procedures. In this paper, we study the prediction risk of variants of bagged predictors under the proportional asymptotics regime, in which the ratio of the number of features to the number of observations converges to a constant. Specifically, we propose a general strategy to analyze the prediction risk under squared error loss of bagged predictors using classical results on simple random sampling. Specializing the strategy, we derive the exact asymptotic risk of the bagged ridge and ridgeless predictors with an arbitrary number of bags under a well-specified linear model with arbitrary feature covariance matrices and signal vectors. Furthermore, we prescribe a generic cross-validation procedure to select the optimal subsample size for bagging and discuss its utility to eliminate the non-monotonic behavior of the limiting risk in the sample size (i.e., double or multiple descents). In demonstrating the proposed procedure for bagged ridge and ridgeless predictors, we thoroughly investigate the oracle properties of the optimal subsample size and provide an in-depth comparison between different bagging variants.

关键词： subagging divide-and-conquer proportional asymptotics ridge regression

来源：评论

学校读者我要写书评

暂无评论

On the Origins of Linear Representations in Large Language Models 41

On the Origins of Linear Representations in Large Language M...

引用

41st International Conference on machine learning, ICML 2024

作者： Jiang, Yibo Rajendran, Goutham Ravikumar, Pradeep Aragam, Bryon Veitch, Victor Department of Computer Science University of Chicago United States Machine Learning Department Carnegie Mellon University United States Booth School of Business University of Chicago United States Department of Statistics University of Chicago United States Data Science Institute University of Chicago United States

Recent works have argued that high-level semantic concepts are encoded "linearly" in the representation space of large language models. In this work, we study the origins of such linear representations. To that end, we introduce a simple latent variable model to abstract and formalize the concept dynamics of the next token prediction. We use this formalism to show that the next token prediction objective (softmax with cross-entropy) and the implicit bias of gradient descent together promote the linear representation of concepts. Experiments show that linear representations emerge when learning from data matching the latent variable model, confirming that this simple structure already suffices to yield linear representations. We additionally confirm some predictions of the theory using the LLaMA-2 large language model, giving evidence that the simplified model yields generalizable insights. Copyright 2024 by the author(s)

关键词：

来源：评论

学校读者我要写书评

暂无评论

Optimal ridge regularization for out-of-distribution prediction 24

Optimal ridge regularization for out-of-distribution predict...

引用

Proceedings of the 41st International Conference on machine learning

作者： Pratik Patil Jin-Hong Du Ryan J. Tibshirani Department of Statistics University of California Berkeley CA Department of Statistics and Data Science and Machine Learning Department Carnegie Mellon University Pittsburgh PA

We study the behavior of optimal ridge regularization and optimal ridge risk for out-of-distribution prediction, where the test distribution deviates arbitrarily from the train distribution. We establish general conditions that determine the sign of the optimal regularization level under covariate and regression shifts. These conditions capture the alignment between the covariance and signal structures in the train and test data and reveal stark differences compared to the in-distribution setting. For example, a negative regularization level can be optimal under covariate shift or regression shift, even when the training features are isotropic or the design is underparameterized. Furthermore, we prove that the optimally tuned risk is monotonic in the data aspect ratio, even in the out-of-distribution setting and when optimizing over negative regularization levels. In general, our results do not make any modeling assumptions for the train or the test distributions, except for moment bounds, and allow for arbitrary shifts and the widest possible range of (negative) regularization levels.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Foundations of testing for finite-sample causal discovery 24

Foundations of testing for finite-sample causal discovery

引用

Proceedings of the 41st International Conference on machine learning

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

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.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Anytime-valid FDR control with the stopped e-BH procedure

arXiv

引用

arXiv 2025年

作者： Wang, Hongjian Dandapanthula, Sanjit Ramdas, Aaditya Department of Statistics and Data Science Carnegie Mellon University United States Machine Learning Department Carnegie Mellon University United States

The recent e-Benjamini-Hochberg (e-BH) procedure for multiple hypothesis testing is known to control the false discovery rate (FDR) under arbitrary dependence between the input e-values. This paper points out an important subtlety when applying the e-BH procedure with e-processes, which are sequential generalizations of e-values (where the data are observed sequentially). Since adaptively stopped e-processes are e-values, the e-BH procedure can be repeatedly applied at every time step, and one can continuously monitor the e-processes and the rejection sets obtained. One would hope that the "stopped e-BH procedure" (se-BH) has an FDR guarantee for the rejection set obtained at any stopping time. However, while this is true if the data in different streams are independent, it is not true in full generality, because each stopped e-process is an e-value only for stopping times in its own local filtration, but the se-BH procedure employs a stopping time with respect to a global filtration. This can cause information to leak across time, allowing one stream to know its future by knowing past data of another stream. This paper formulates a simple causal condition under which local e-processes are also global e-processes and thus the se-BH procedure does indeed control the FDR. The condition excludes unobserved confounding from the past and is met under most reasonable scenarios including genomics. Copyright © 2025, The Authors. All rights reserved.

关键词： Filtration

来源：评论

学校读者我要写书评

暂无评论

Active multiple testing with proxy p-values and e-values

arXiv

引用

arXiv 2025年

作者： Xu, Ziyu Wang, Catherine Wasserman, Larry Roeder, Kathryn Ramdas, Aaditya Department of Statistics and Data Science United States Machine Learning Department Germany Computational Biology Department Carnegie Mellon University United States

Researchers often lack the resources to test every hypothesis of interest directly or compute test statistics comprehensively, but often possess auxiliary data from which we can compute an estimate of the experimental outcome. We introduce a novel approach for selecting which hypotheses to query a statistic (i.e., run an experiment, perform expensive computation, etc.) in a hypothesis testing setup by leveraging estimates (e.g., from experts, machine learning models, previous experiments, etc.) to compute proxy statistics. Our framework allows a scientist to propose a a proxy statistic, and then query the true statistic with some probability based on the value of the proxy. We make no assumptions about how the proxy is derived and it can be arbitrarily dependent with the true statistic. If the true statistic is not queried, the proxy is used in its place. We characterize "active" methods that produce valid p-values and e-values in this setting and utilize this framework in the multiple testing setting to create procedures with false discovery rate (FDR) control. Through simulations and real data analysis of causal effects in scCRISPR screen experiments, we empirically demonstrate that our proxy framework has both high power and low resource usage when our proxies are accurate estimates of the respective true statistics. Copyright © 2025, The Authors. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

An efficient doubly-robust test for the kernel treatment effect 23

An efficient doubly-robust test for the kernel treatment eff...

引用

Proceedings of the 37th International Conference on Neural Information Processing Systems

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

The average treatment effect, which is the difference in expectation of the counter-factuals, 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.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：