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…
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,695 papers · 148 categories
Trend · papers per month
48 results for “subsampled algorithms”
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…
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…
For massive data, the family of subsampling algorithms is popular to downsize the data volume and reduce computational burden. Existing studies focus on approximating the ordinary least squares estimate in linear regression, where statistical leverage scores are often used to define subsampling probabilities. In this p…
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…
A genetic algorithm improves multivariate kernel density estimation.
problem Efficiently estimating multivariate kernel density functions.
method Genetic algorithm applied to subsamples of the original data.
result The genetic algorithm-based estimator performs better than traditional methods.
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…
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.
We present a matrix factorization algorithm that scales to input matrices that are large in both dimensions (i.e., that contains morethan 1TB of data). The algorithm streams the matrix columns while subsampling them, resulting in low complexity per iteration andreasonable memory footprint. In contrast to previous onlin…
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.
We describe an adaptation of the simulated annealing algorithm to nonparametric clustering and related probabilistic models. This new algorithm learns nonparametric latent structure over a growing and constantly churning subsample of training data, where the portion of data subsampled can be interpreted as the inverse …
The rapid development of computing power and efficient Markov Chain Monte Carlo (MCMC) simulation algorithms have revolutionized Bayesian statistics, making it a highly practical inference method in applied work. However, MCMC algorithms tend to be computationally demanding, and are particularly slow for large datasets…
Hamiltonian Monte Carlo (HMC) samples efficiently from high-dimensional posterior distributions with proposed parameter draws obtained by iterating on a discretized version of the Hamiltonian dynamics. The iterations make HMC computationally costly, especially in problems with large datasets, since it is necessary to c…
A new method reduces variance in SGMCMC by preferentially subsampling data.
problem High variance in stochastic gradient estimates impacts sampler performance.
method Use a non-uniform probability distribution to preferentially subsample data points and adaptively adjust subsample size.
result Maintains accuracy while substantially reducing average subsample size.
New research finds many coreset methods for logistic regression are not better than simple sampling.
problem Evaluation of coreset methods for reducing data size in logistic regression.
method Comparison of multiple coreset and optimal subsampling methods for logistic regression.
result Many coreset methods do not outperform simple uniform subsampling.
New insights into privacy guarantees for subsampled mechanisms under composition.
problem Tight privacy guarantees for the composition of subsampled differentially private mechanisms.
method Addressed confusion points in privacy accounting for subsampled mechanisms, providing examples and counterexamples.
result Privacy guarantees for subsampled mechanisms differ significantly between Poisson subsampling and sampling without replacement.
Speeding up Markov Chain Monte Carlo (MCMC) for datasets with many observations by data subsampling has recently received considerable attention. A pseudo-marginal MCMC method is proposed that estimates the likelihood by data subsampling using a block-Poisson estimator. The estimator is a product of Poisson estimators,…
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.
The study provides theoretical foundations for using smaller instances to predict algorithm performance on larger ones.
problem Scalability challenge in evaluating algorithms on large instances.
method Formalized size generalization, providing theoretical guarantees for predicting algorithm performance on large instances using smaller, representative instances.
result Characterized the subsample size sufficient to ensure performance on the subsample reflects performance on the full instance.
A deep learning subsampling technique improves modulation classification accuracy.
problem Improving modulation classification accuracy in wireless communication systems.
method Proposes a data-driven subsampling strategy using deep neural networks to simulate signal removal.
result Improves classification accuracy to higher levels than traditional methods.
A new algorithm PBNN improves scalability of Bayesian Neural Networks.
problem Scalability issues in Neural Network posterior sampling with large datasets.
method Penalty Bayesian Neural Networks (PBNN) using subsampled batch data.
result PBNN achieves good predictive performance with small mini-batch sizes.
We present a matrix-factorization algorithm that scales to input matrices with both huge number of rows and columns. Learned factors may be sparse or dense and/or non-negative, which makes our algorithm suitable for dictionary learning, sparse component analysis, and non-negative matrix factorization. Our algorithm str…
Greedy algorithms outperform UCB in many-armed bandit problems.
problem Optimizing multi-armed bandit problems with many arms.
method Subsampled UCB and greedy algorithms comparison.
result Greedy algorithms achieve optimal regret in many-armed bandit problems.
A new method combines variational inference and MCMC for efficient data subsampling.
problem Combining variational inference and MCMC for data subsampling.
method Introduces a surrogate likelihood to learn jointly with variational parameters.
result Permits an intuitive trade-off between inference fidelity and computational cost.
SGLDiff approximates Bayesian posterior distributions with subsampling error.
problem Approximating Bayesian posterior distributions in large-scale data settings.
method Stochastic Gradient Langevin Diffusion (SGLDiff) with subsampling.
result The Wasserstein distance between the posterior and SGLDiff's limiting distribution is bounded by a fractional power of the mean waiting time.
Improved kernel quadrature with convex weights using subsampling.
problem Constructing quadrature rules with small worst-case error.
method Combining spectral properties of the kernel with recombination results.
result Effective algorithms for constructing convex quadrature rules with i.i.d. samples.
A fast algorithm for -means clustering using subsampled SDP.
problem Efficiently solving large-scale -means clustering problems.
method Sketch-and-Lift (SL) approach for approximating SDP relaxed -means.
result SL method achieves similar exact recovery threshold as full SDP on full dataset.
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…
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.
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.
Feature selection from a large number of covariates (aka features) in a regression analysis remains a challenge in data science, especially in terms of its potential of scaling to ever-enlarging data and finding a group of scientifically meaningful features. For example, to develop new, responsive drug targets for ovar…
SNG-DBSCAN clusters data faster with subsampled similarity queries.
problem Efficiently clustering large datasets with DBSCAN's high complexity.
method Subsampled -neighborhood graph for similarity queries.
result Subsampling of the graph leads to 200x speedup and 250x RAM reduction.
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.
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.
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…
The Sampled Gaussian Mechanism's noise level decreases with larger subsampling rates, improving privacy-utility trade-offs.
problem Improving privacy-utility trade-offs in differentially private stochastic optimization.
method Proof of a conjecture about the Sampled Gaussian Mechanism's noise level and subsampling rate relationship.
result A rigorous proof of the conjecture, completing the proof of Theorem 6.2 in the original paper.
Group-equivariant subsampling layers improve CNNs' equivariance.
problem Non-translation equivariance in subsampling operations.
method Translation and group-equivariant subsampling/upsampling layers.
result Group-equivariant autoencoders learn equivariant representations.
Develops a method to optimize hyperparameters for subsampling methods.
problem Optimizing hyperparameters for subsampling methods to improve estimator efficiency.
method Careful theoretical analysis leading to an optimal choice of hyperparameters.
result Improves the statistical efficiency of subsampling estimators without extra CPU time.
New equivalences found between subsampling and ridge regularization methods.
problem Establishing precise structural and risk equivalences between subsampling and ridge regularization.
method Proved structural and risk equivalences between subsample ridge estimators and different ridge regularization levels and subsample aspect ratios.
result Optimally tuned ridge regression exhibits a monotonic prediction risk in the data aspect ratio.
The paper analyzes the risk of bagging regularized M-estimators under proportional asymptotics.
problem Characterizing the risk of ensemble estimators trained with subsamples and regularizers.
method Developed a consistent estimator for the risk of ensemble estimators under proportional asymptotics.
result Optimal subsample size tends to be in the overparameterized regime for the full-ensemble estimator.
Enhances financial optimization under model uncertainty using subsampling.
problem Model uncertainty in financial decision-making from limited data.
method Superimposes uncertainty measure on model space, uses subsampling for model distribution approximation, adapts SGD for efficiency.
result Uncertainty measures outperform traditional methods and achieve comparable performance to Bayesian methods.
In the setting of nonparametric regression, we propose and study a combination of stochastic gradient methods with Nyström subsampling, allowing multiple passes over the data and mini-batches. Generalization error bounds for the studied algorithm are provided. Particularly, optimal learning rates are derived considerin…
The paper improves privacy accounting for discrete-valued mechanisms and the subsampled Gaussian mechanism.
problem Improving the accuracy and efficiency of differential privacy accounting for discrete outputs.
method Uses fast Fourier transform (FFT) for rigorous error analysis and accounting of privacy loss.
result Provides strict lower and upper bounds for -values, demonstrating up to 75% reduction in noise variance.
A new Markov subsampling strategy based on Huber criterion improves data processing from noisy full data.
problem High noise level in data leads to poor performance of subsampling procedures.
method Design a Markov subsampling strategy based on Huber criterion to construct an informative subset from noisy full data.
result The estimator based on HMS is statistically consistent with a sub-Gaussian deviation bound.
Improved sampling accuracy in SG-MCMC methods via non-uniform gradient subsampling.
problem Computational inefficiency and sampling error in stochastic gradient MCMC methods.
method Proposes a non-uniform subsampling scheme to reduce sampling error in EWSG, a variant of SG-MCMC.
result EWSG reduces sampling error compared to uniform subsampling, improving accuracy without sacrificing convergence speed.
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.
Subsampled Newton methods approximate Hessian matrices through subsampling techniques, alleviating the cost of forming Hessian matrices but using sufficient curvature information. However, previous results require samples to approximate Hessians, where is the dimension of data points, making it less practica…
A two-stage GPR framework with automatic kernel search and subsampling improves prediction accuracy and efficiency.
problem Inaccurate predictions due to misspecified mean and kernel functions in Gaussian Process Regression.
method Two-stage GPR, automatic kernel search, subsampling for hyperparameter initialization.
result Competitive or better performance compared to full dataset training, robust on real-world datasets.