In this paper, we study the Nystr{ö}m type subsampling for large scale kernel methods to reduce the computational complexities of big data. We discuss the multi-penalty regularization scheme based on Nystr{ö}m type subsampling which is motivated from well-studied manifold regularization schemes. We develop a theoretica…
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “Nyström subsampling”
Paper develops a new kernel approximation framework.
problem High time and space complexity of kernel methods for large datasets.
method Perturbation-based kernel approximation framework using classical perturbation theory.
result Framework generalizes and improves upon existing methods.
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 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.
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…
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…
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 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.
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.
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…
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.
This paper proves subsampled Newton methods work for high-dimensional data.
problem The high cost of forming Hessian matrices in Newton methods for high-dimensional data.
method Subsampled Newton methods approximate Hessians using subsampling techniques, requiring only samples.
result Only samples are needed, where is much smaller than for high-dimensional data.
The paper analyzes how subsampling Gaussian process regression works.
problem The accuracy and generalization of Gaussian process regression with subsampling.
method The authors use graphon theory to embed kernel matrices and analyze the approximation and generalization errors.
result Subsampling achieves a better trade-off between accuracy and runtime compared to other methods.
In this paper we model the problem of learning preferences of a population as an active learning problem. We propose an algorithm can adaptively choose pairs of items to show to users coming from a heterogeneous population, and use the obtained reward to decide which pair of items to show next. We provide computational…
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.
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.
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.
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 …
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…
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.
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,…
A new method subsamples data without weights to improve model performance.
problem Training complex models on large datasets is computationally expensive.
method Unweighted Influence Data Subsampling (UIDS) method.
result The subset-model outperforms the full-set-model in diverse tasks.
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.
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.
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…
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.
Subsampling reduces computational cost in supervised learning in reproducing kernel Hilbert spaces.
problem Reducing computational cost in supervised learning
method Subsampling minimizes empirical risk in reproducing kernel Hilbert spaces
result Optimal subsampling scheme revealed
SubTSBR to tackle high noise and outliers for data-driven discovery of differential equationsstat.ML
SubTSBR tackles noisy data for differential equation discovery.
problem Discovering differential equations from noisy or outlier-laden data.
method Subsampling-based threshold sparse Bayesian regression (SubTSBR) with subsampling size and number of subsamples.
result SubTSBR outperforms TSBR in accuracy for differential equation discovery.
Efficient methods for training deep neural networks using subsampled Gauss-Newton and natural gradient.
problem Training deep neural networks with large datasets and variables.
method Subsampled Gauss-Newton and natural gradient methods with subsampled gradient estimates.
result Methods converge to a stationary point and are efficient to implement.
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…
Study ridge ensembles in proportional feature-to-sample size regime, proving risk equivalence and GCV consistency.
problem Characterizing and optimizing ridge ensembles in proportional feature-to-sample size regimes.
method Proportional asymptotics analysis, GCV for tuning, proving risk equivalence.
result Risk of optimal full ridgeless ensemble matches optimal ridge predictor's risk.
We consider the problem of metric learning for multi-view data and present a novel method for learning within-view as well as between-view metrics in vector-valued kernel spaces, as a way to capture multi-modal structure of the data. We formulate two convex optimization problems to jointly learn the metric and the clas…
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.
For classification problems with significant class imbalance, subsampling can reduce computational costs at the price of inflated variance in estimating model parameters. We propose a method for subsampling efficiently for logistic regression by adjusting the class balance locally in feature space via an accept-reject …
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…
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.
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…
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.
Subbagging estimation for big data reduces memory usage while maintaining statistical consistency.
problem Memory constraints in analyzing massive datasets.
method Randomly subsample the data, aggregate estimators from subsamples, and use incomplete U-statistics theory.
result Subbagging estimator achieves -consistency and asymptotic normality under certain conditions.
Theory and method for reducing prediction variance in noisy feature-subsampled ridge ensembles.
problem Reduction of prediction variance in noisy data with feature bagging.
method Developed analytical learning curves for noisy ridge ensembles, introduced heterogeneous feature ensembling.
result Subsampling shifts the double-descent peak, leading to improved performance over a single linear predictor.
Robust data fusion via subsampling improves model performance for rare data types.
problem Challenges in integrating large, contaminated external data with limited target data.
method Subsampling strategies to reduce biases and minimize variances, combined with error bounds analysis.
result Proposed methods enhance transfer learning performance, especially for rare data types.
New cross-validation method reduces bias and improves prediction error.
problem Subsampling bias in k-fold cross-validation.
method Best-discrepancy systematic sampling.
result Reduces subsampling bias and improves prediction error.
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.
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.