Extrapolated cross-validation for randomized ensembles
- URL: http://arxiv.org/abs/2302.13511v3
- Date: Fri, 15 Dec 2023 21:13:09 GMT
- Title: Extrapolated cross-validation for randomized ensembles
- Authors: Jin-Hong Du, Pratik Patil, Kathryn Roeder, Arun Kumar Kuchibhotla
- Abstract summary: This paper introduces a cross-validation method, ECV, for tuning the ensemble and subsample sizes in randomized ensembles.
We show that ECV yields $delta$-optimal ensembles for squared prediction risk.
In comparison to sample-split cross-validation and $K$-fold cross-validation, ECV achieves higher accuracy avoiding sample splitting.
- Score: 2.3609229325947885
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Ensemble methods such as bagging and random forests are ubiquitous in various
fields, from finance to genomics. Despite their prevalence, the question of the
efficient tuning of ensemble parameters has received relatively little
attention. This paper introduces a cross-validation method, ECV (Extrapolated
Cross-Validation), for tuning the ensemble and subsample sizes in randomized
ensembles. Our method builds on two primary ingredients: initial estimators for
small ensemble sizes using out-of-bag errors and a novel risk extrapolation
technique that leverages the structure of prediction risk decomposition. By
establishing uniform consistency of our risk extrapolation technique over
ensemble and subsample sizes, we show that ECV yields $\delta$-optimal (with
respect to the oracle-tuned risk) ensembles for squared prediction risk. Our
theory accommodates general ensemble predictors, only requires mild moment
assumptions, and allows for high-dimensional regimes where the feature
dimension grows with the sample size. As a practical case study, we employ ECV
to predict surface protein abundances from gene expressions in single-cell
multiomics using random forests. In comparison to sample-split cross-validation
and $K$-fold cross-validation, ECV achieves higher accuracy avoiding sample
splitting. At the same time, its computational cost is considerably lower owing
to the use of the risk extrapolation technique. Additional numerical results
validate the finite-sample accuracy of ECV for several common ensemble
predictors under a computational constraint on the maximum ensemble size.
Related papers
- Optimal Multi-Distribution Learning [88.3008613028333]
Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.
We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
arXiv Detail & Related papers (2023-12-08T16:06:29Z) - Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning [5.293069542318491]
We employ random matrix theory to establish consistency of generalized cross validation (GCV) for estimating prediction risks of sketched ridge regression ensembles.
For squared prediction risk, we provide a decomposition into an unsketched equivalent implicit ridge bias and a sketching-based variance, and prove that the risk can be globally tuning by only sketch size in infinite ensembles.
We also propose an "ensemble trick" whereby the risk for unsketched ridge regression can be efficiently estimated via GCV using small sketched ridge ensembles.
arXiv Detail & Related papers (2023-10-06T16:27:43Z) - Corrected generalized cross-validation for finite ensembles of penalized estimators [5.165142221427927]
Generalized cross-validation (GCV) is a widely-used method for estimating the squared out-of-sample prediction risk.
We show that GCV is inconsistent for any finite ensemble of size greater than one.
arXiv Detail & Related papers (2023-10-02T17:38:54Z) - Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validation [4.87717454493713]
We study subsampling-based ridge ensembles in the proportionals regime.
We prove that the risk of the optimal full ridgeless ensemble (fitted on all possible subsamples) matches that of the optimal ridge predictor.
arXiv Detail & Related papers (2023-04-25T17:43:27Z) - Bagging in overparameterized learning: Risk characterization and risk
monotonization [2.6534407766508177]
We study the prediction risk of variants of bagged predictors under the proportionals regime.
Specifically, we propose a general strategy to analyze the prediction risk under squared error loss of bagged predictors.
arXiv Detail & Related papers (2022-10-20T17:45:58Z) - Mitigating multiple descents: A model-agnostic framework for risk
monotonization [84.6382406922369]
We develop a general framework for risk monotonization based on cross-validation.
We propose two data-driven methodologies, namely zero- and one-step, that are akin to bagging and boosting.
arXiv Detail & Related papers (2022-05-25T17:41:40Z) - Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
We propose a novel class of deep predictors for classifying metric data on graphs within PAC-Bayes risk certification paradigm.
Building on the recent PAC-Bayes literature and data-dependent priors, this approach enables learning posterior distributions on the hypothesis space.
arXiv Detail & Related papers (2022-01-26T19:59:14Z) - AdaPT-GMM: Powerful and robust covariate-assisted multiple testing [0.7614628596146599]
We propose a new empirical Bayes method for co-assisted multiple testing with false discovery rate (FDR) control.
Our method refines the adaptive p-value thresholding (AdaPT) procedure by generalizing its masking scheme.
We show in extensive simulations and real data examples that our new method, which we call AdaPT-GMM, consistently delivers high power.
arXiv Detail & Related papers (2021-06-30T05:06:18Z) - A One-step Approach to Covariate Shift Adaptation [82.01909503235385]
A default assumption in many machine learning scenarios is that the training and test samples are drawn from the same probability distribution.
We propose a novel one-step approach that jointly learns the predictive model and the associated weights in one optimization.
arXiv Detail & Related papers (2020-07-08T11:35:47Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
In [1], an ensemble of randomly projected linear discriminants is used to classify datasets.
We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator.
We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
arXiv Detail & Related papers (2020-04-17T12:47:04Z) - Survival Cluster Analysis [93.50540270973927]
There is an unmet need in survival analysis for identifying subpopulations with distinct risk profiles.
An approach that addresses this need is likely to improve characterization of individual outcomes.
arXiv Detail & Related papers (2020-02-29T22:41:21Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.