In this paper, we study random subsampling of Gaussian process regression, one of the simplest approximation baselines, from a theoretical perspective. Although subsampling discards a large part of training data, we show provable guarantees on the accuracy of the predictive mean/variance and its generalization ability.…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Randomized Subsampling”
New insights into how randomization affects greedy model selection.
problem Understanding the impact of feature subsampling on greedy model selection.
method Investigated greedy forward selection with feature subsampling, proving effects on bias and variance.
result Ensembling with feature subsampling reduces both bias and variance, unlike convex base learners.
Enhances random forest performance with exogenous randomness.
problem Improving random forest performance through exogenous randomness.
method Developed non-asymptotic MSE expansions for individual trees and forests, identified two types of randomness, and conducted simulations.
result Exogenous randomness, particularly feature subsampling, reduces both bias and variance of random forests.
We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms. Specifically, we provide a tight upper bound on the Rényi Differential Privacy (RDP) (Mironov, 2017) parameters for algorithms that: (1) subsamp…
Differential privacy comes equipped with multiple analytical tools for the design of private data analyses. One important tool is the so-called "privacy amplification by subsampling" principle, which ensures that a differentially private mechanism run on a random subsample of a population provides higher privacy guaran…
Early stopping is a well known approach to reduce the time complexity for performing training and model selection of large scale learning machines. On the other hand, memory/space (rather than time) complexity is the main constraint in many applications, and randomized subsampling techniques have been proposed to tackl…
A new neural subsampling method reduces data volume for deep models.
problem Efficiently process huge volumes of high-dimensional data like images.
method Two-stage end-to-end neural subsampling model that optimizes for arbitrary downstream tasks.
result Outperforms baselines under low subsampling rates on various tasks.
New sampling scheme improves privacy in DP-SGD without sacrificing utility.
problem Suboptimal privacy amplification due to participation variance in Poisson subsampling.
method Balanced Iteration Subsampling (BIS) with structured randomness.
result BIS achieves stronger privacy amplification than Poisson subsampling and is optimal at both extremes of noise spectrum.
Unified theory and debiasing framework for random oblique projections in high dimensions.
problem Systematic statistical bias in random oblique projections induced by sampling.
method Unified non-asymptotic theory and debiasing framework.
result Sharp bias--variance characterizations and improved approximation accuracy.
SubTSBR to tackle high noise and outliers for data-driven discovery of differential equationsstat.ML
Data-driven discovery of differential equations has been an emerging research topic. We propose a novel algorithm subsampling-based threshold sparse Bayesian regression (SubTSBR) to tackle high noise and outliers. The subsampling technique is used for improving the accuracy of the Bayesian learning algorithm. It has tw…
Paper bridges statistical inference for DP-SGD, a privacy-preserving machine learning method.
problem Asymptotic statistical inference for Differentially Private Stochastic Gradient Descent (DP-SGD).
method Established asymptotic properties of SGD under randomized subsampling, extended to DP-SGD, proposed methods for constructing valid confidence intervals.
result Valid confidence intervals for DP-SGD output achieve nominal coverage rates while maintaining privacy.
A significant hurdle for analyzing large sample data is the lack of effective statistical computing and inference methods. An emerging powerful approach for analyzing large sample data is subsampling, by which one takes a random subsample from the original full sample and uses it as a surrogate for subsequent computati…
A new model-free subsampling method using uniform designs is proposed.
problem Model-based subsampling methods are often dependent on model assumptions.
method Developed a criterion (GEFD) and a model-free subsampling method based on uniform designs.
result The proposed method outperforms random sampling and is robust under diverse model specifications.
Statistical machine learning models should be evaluated and validated before putting to work. Conventional k-fold Monte Carlo Cross-Validation (MCCV) procedure uses a pseudo-random sequence to partition instances into k subsets, which usually causes subsampling bias, inflates generalization errors and jeopardizes the r…
Unified framework for subsampling mechanisms with tighter privacy guarantees.
problem Improving privacy in machine learning models through subsampling.
method Conditional optimal transport for deriving mechanism-specific subsampling guarantees.
result Tighter privacy bounds for subsampled mechanisms compared to traditional methods.
Ensemble methods improve model performance by averaging over subsampled predictors.
problem Understanding the effect of feature subsampling in ensemble methods.
method Fit linear predictors using ordinary least squares on random submatrices of the data matrix.
result The asymptotic risk of an ensemble is equal to the ridge regression risk, optimal for linear predictors.
Unified methodology for statistical inference in least squares and PCA via randomized sketching.
problem Statistical inference in least squares and PCA problems.
method Randomized sketching and projections, asymptotic normality of quadratic forms.
result Unified statistical inference methods for various sketching distributions.
Improved SRHT for linear SVM classification with higher accuracy.
problem Inefficient random projection methods for high-dimensional data.
method Importance sampling and deterministic top- sampling for effective low-dimensional embedding.
result Higher classification accuracy on real-life datasets.
Asymptotic Distributions and Rates of Convergence for Random Forests via Generalized U-statisticsstat.ML
Random forests remain among the most popular off-the-shelf supervised learning algorithms. Despite their well-documented empirical success, however, until recently, few theoretical results were available to describe their performance and behavior. In this work we push beyond recent work on consistency and asymptotic no…
We introduce extensions of stability selection, a method to stabilise variable selection methods introduced by Meinshausen and Bühlmann (J R Stat Soc 72:417-473, 2010). We propose to apply a base selection method repeatedly to random observation subsamples and covariate subsets under scrutiny, and to select covariates …
Develops an empirical likelihood framework for random forests and ensembles.
problem Quantifying the statistical uncertainty of random forests and ensembles.
method Empirical likelihood framework exploiting the incomplete -statistic structure of ensemble predictions.
result Modified empirical likelihood statistic achieves accurate coverage and practical reliability.
Random forests have proven to be reliable predictive algorithms in many application areas. Not much is known, however, about the statistical properties of random forests. Several authors have established conditions under which their predictions are consistent, but these results do not provide practical estimates of ran…
This paper explains CART random forests using stochastic control theory.
problem Understanding the inner workings of CART random forests.
method Developed a stochastic-control perspective on CART random forests, interpreting feature subsampling as a random feasible action set and the split rule as a policy.
result Established that the CART policy is locally stabilizing but globally suboptimal for the forest objective.
We study Nyström type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling leve…
Improved DNN estimator with scalable subsampling for efficient inference.
problem Efficient inference for deep neural networks (DNNs).
method Non-random subsampling technique (scalable subsampling) applied to DNNs.
result Subagged DNN estimator offers computational efficiency and accurate point estimation/prediction intervals.
The infinitesimal jackknife (IJ) has recently been applied to the random forest to estimate its prediction variance. These theorems were verified under a traditional random forest framework which uses classification and regression trees (CART) and bootstrap resampling. However, random forests using conditional inferenc…
We propose Subsampling MCMC, a Markov Chain Monte Carlo (MCMC) framework where the likelihood function for observations is estimated from a random subset of observations. We introduce a highly efficient unbiased estimator of the log-likelihood based on control variates, such that the computing cost is much smal…
Develops a faster model selection method using influence functions.
problem Time-consuming and computationally inefficient model selection.
method Model-specific data subsampling guided by influence functions.
result Empirically shows improved selection of high-quality models.
FastForest boosts Random Forest speed by 24%.
problem Efficiency in processing speed for Random Forest.
method Subsample Aggregating, Logarithmic Split-Point Sampling, Dynamic Restricted Subspacing.
result Average 24% increase in processing speed with accuracy maintained.
Combining differential privacy and federated learning improves data security.
problem Ensuring privacy in distributed machine learning.
method Integrating differential privacy with federated learning protocols.
result Achieved comparable prediction accuracy to non-distributed learning while maintaining strict privacy.
Enhanced privacy, utility, and efficiency through MUST subsampling.
problem Balancing privacy, utility, and computational efficiency in data analysis.
method MUltistage Sampling Technique (MUST) for privacy amplification in differential privacy.
result MUST offers stronger privacy guarantees () than one-stage subsampling methods while maintaining similar utility and computational efficiency.
We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small \emph{subset} of the or…
The paper explores effective data selection methods for weakly supervised learning.
problem Efficiently selecting a subset of unlabeled data for weakly supervised learning.
method Using a surrogate model to predict labels and selecting a subset of samples for training.
result Data selection can significantly improve model performance over training on the full dataset.
New method reduces inference variance for faster optimization.
problem High variance in black-box variational inference.
method Joint control variate addressing both data subsampling and Monte Carlo noise.
result Significantly reduced gradient variance, leading to faster optimization.
Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that…
A new method detects outliers using ensembles of Dirichlet process mixtures.
problem Challenges in unsupervised outlier detection using Dirichlet process mixtures.
method Ensembles of Dirichlet process Gaussian mixtures with random subspace and subsampling.
result Empirically outperforms existing approaches in unsupervised outlier detection.
A well-known problem in data science and machine learning is {\em linear regression}, which is recently extended to dynamic graphs. Existing exact algorithms for updating the solution of dynamic graph regression require at least a linear time (in terms of : the size of the graph). However, this time complexity might…
Jackknife variance estimation validated for generalized U-statistics.
problem Uncertainty quantification for subsampling-based estimators.
method Jackknife variance estimation for generalized U-statistics with row-wise weak law.
result Jackknife and delete- variance estimators are ratio-consistent for generalized U-statistics.
The paper analyzes bagging in overparameterized learning, deriving risk properties and optimal subsample sizes.
problem Characterizing the risk of bagged predictors in overparameterized settings.
method General strategy using classical results on simple random sampling, specialized for ridge and ridgeless predictors.
result Derives exact asymptotic risk of bagged ridge and ridgeless predictors under various conditions.
A new method selects a representative subsample for efficient kernel density estimation.
problem Selecting a representative subsample without model assumptions.
method Optimal transport techniques for model-free subsampling with an efficient algorithm.
result The selected subsample can be used for efficient density estimation with derived convergence rates and optimal bandwidth.
Tempering by Subsamplingstat.ML
In this paper we demonstrate that tempering Markov chain Monte Carlo samplers for Bayesian models by recursively subsampling observations without replacement can improve the performance of baseline samplers in terms of effective sample size per computation. We present two tempering by subsampling algorithms, subsampled…
This paper investigates the approximation power of three types of random neural networks: (a) infinite width networks, with weights following an arbitrary distribution; (b) finite width networks obtained by subsampling the preceding infinite width networks; (c) finite width networks obtained by starting with standard G…
This paper optimizes subsampling for large datasets using Poisson distribution.
problem Efficiently subsample large datasets for quasi-likelihood estimation.
method Derives optimal Poisson subsampling probabilities and develops a distributed subsampling framework.
result Consistent and asymptotically normal estimators are obtained.
State-of-the-art methods for Convolutional Sparse Coding usually employ Fourier-domain solvers in order to speed up the convolution operators. However, this approach is not without shortcomings. For example, Fourier-domain representations implicitly assume circular boundary conditions and make it hard to fully exploit …
Bayesian coresets improved with random sampling and quasi-Newton optimization.
problem Efficiently approximate Bayesian posterior distributions for computationally expensive inference.
method Randomly select a subset of data points, then optimize weights using quasi-Newton method.
result First algorithm with high-probability KL divergence bound on coreset quality.
Safe, Scalable, and Accurate Bayes Posterior Sampling for Large-Data Generalized Linear Mixed Modelsstat.ME
New method for Bayesian inference on large datasets.
problem Scalable sampling for Bayesian generalized linear mixed models on large datasets.
method Mirror Langevin dynamics with data subsampling, post-processing for variance estimation.
result Asymptotic, order-wise correct estimation of posterior variance.
Large sample size brings the computation bottleneck for modern data analysis. Subsampling is one of efficient strategies to handle this problem. In previous studies, researchers make more fo- cus on subsampling with replacement (SSR) than on subsampling without replacement (SSWR). In this paper we investigate a kind of…
New method improves inference for hierarchical models.
problem Challenges in inference for large hierarchical models.
method Locally enhanced variational bounds with subsampling.
result Better posterior approximations than baselines.