We explain theoretically a curious empirical phenomenon: "Approximating a matrix by deterministically selecting a subset of its columns with the corresponding largest leverage scores results in a good low-rank matrix surrogate". To obtain provable guarantees, previous work requires randomized sampling of the columns wi…
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 “empirical leverage scores”
This paper improves random feature sampling using empirical leverage scores.
problem Optimizing the number of features for kernel approximation and supervised learning.
method Uses empirical leverage scores to optimize feature sampling.
result Empirical sampling of random features using leverage scores outperforms vanilla Monte Carlo sampling.
Improves generative model coverage of underrepresented modes.
problem Generative models miss underrepresented modes in data.
method Leverage score sampling for complete mode coverage.
result Significantly improves mode coverage compared to standard methods.
Sketched SVD improves SVD runtime for large datasets.
problem Efficiently applying SVD to large datasets.
method Randomized sketching to approximate SVD.
result Sketched SVD provides accurate leverage score ordering.
Efficiently approximates statistical leverage scores for faster KRR.
problem Accurately estimating statistical leverage scores for fast KRR.
method Analytic formula for statistical leverage scores, leveraging kernel spectral density.
result Linear time approximation with theoretical guarantees, significantly faster than existing methods.
Active learning aims to obtain a classifier of high accuracy by using fewer label requests in comparison to passive learning by selecting effective queries. Many active learning methods have been developed in the past two decades, which sample queries based on informativeness or representativeness of unlabeled data poi…
SALSA efficiently approximates leverage scores for big data, improving ARMA model fitting.
problem Efficiently approximating leverage scores for large matrices.
method Sequential approximate leverage-score algorithm (SALSA) using randomized numerical linear algebra.
result SALSA approximates leverage scores within with high probability.
Estimates score function from data with optimal rate in high dimensions.
problem Estimating the score function of an unknown probability distribution from data.
method Empirical Bayes smoothing with a Gaussian kernel.
result Optimal rate of estimation for dimensions.
Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Accesscs.LG
Improved sample complexity for diffusion models without needing empirical risk minimizers.
problem Theoretical limitations in sample complexity for diffusion models.
method Structured decomposition of score estimation error, eliminating dependence on neural network parameters.
result Achieved sample complexity bound of O(ε^(-4)) without empirical risk minimizer access.
LSAR efficiently estimates AR models for big time series data.
problem Efficiently analyzing large-scale time series data with high accuracy.
method Developed a fast algorithm to estimate leverage scores and an efficient LSAR algorithm for fitting AR models.
result LSAR algorithm finds maximum likelihood estimates with high probability and improved worst-case running time.
The statistical leverage scores of a complex matrix record the degree of alignment between col and the coordinate axes in . These score are used in random sampling algorithms for solving certain numerical linear algebra problems. In this paper we present a max-plus algebr…
Paper develops efficient methods for leverage score sampling and kernel ridge regression.
problem Efficiently sampling leverage scores for large matrices.
method Novel algorithm for leverage score sampling and kernel ridge regression solver.
result Proposed algorithms are the most efficient and accurate for leverage score sampling and kernel ridge regression.
This paper improves matrix completion by leveraging element importance and non-uniform sampling.
problem The challenge of completing low-rank matrices from noisy, subsampled measurements.
method Employing leverage scores to characterize element importance and devising a biased sampling procedure.
result Theoretical and empirical evidence shows that a smaller number of entries (about ) can recover a low-rank matrix with noise.
Generalizes leverage score sampling for neural networks, accelerating kernel methods and deep learning.
problem Accelerating kernel methods and deep learning training.
method Generalizes leverage score sampling to neural networks and proves equivalence to neural tangent kernel ridge regression.
result Equivalence between regularized neural network and neural tangent kernel ridge regression under leverage score sampling initialization.
We give the first algorithm for kernel Nyström approximation that runs in *linear time in the number of training points* and is provably accurate for all kernel matrices, without dependence on regularity or incoherence conditions. The algorithm projects the kernel onto a set of landmark points sampled by their *rid…
New active learning methods use statistical leverage scores to select examples efficiently.
problem Efficiently selecting labeled examples for high model accuracy with limited labeled data.
method Proposes ALEVS and DBALEVS methods based on statistical leverage scores.
result DBALEVS selects diverse, representative examples efficiently.
ScoreAG generates unrestricted adversarial images maintaining semantic integrity.
problem Limited robustness evaluations due to -norm constraints.
method Score-Based Adversarial Generation (ScoreAG) using score-based generative models.
result ScoreAG improves robustness assessments across multiple benchmarks.
Statistical leverage scores emerged as a fundamental tool for matrix sketching and column sampling with applications to low rank approximation, regression, random feature learning and quadrature. Yet, the very nature of this quantity is barely understood. Borrowing ideas from the orthogonal polynomial literature, we in…
New algorithms estimate matrix leverage scores using rank revealing and randomization.
problem Estimating leverage scores for matrices of arbitrary rank.
method Combining rank revealing methods with randomized dimensionality reduction.
result Effective estimators for leverage scores, even in rank deficient cases.
A Unified Comparative Study with Generalized Conformity Scores for Multi-Output Conformal Regressionstat.ML
Unified study of nine multi-output conformal methods with generalized scores.
problem Challenges in extending conformal prediction to multi-output problems.
method Nine conformal methods with generalized multi-output conformity scores.
result Generalized scores ensure asymptotic conditional coverage and exact finite-sample marginal coverage.
Deep Generative Model using Unregularized Score for Anomaly Detection with Heterogeneous Complexitycs.LG
Accurate and automated detection of anomalous samples in a natural image dataset can be accomplished with a probabilistic model for end-to-end modeling of images. Such images have heterogeneous complexity, however, and a probabilistic model overlooks simply shaped objects with small anomalies. This is because the proba…
Faster Training of Diffusion Models and Improved Density Estimation via Parallel Score Matchingcs.LG
Parallel score matching accelerates DPM training and improves density estimation.
problem Extended training periods and limited modeling flexibility in DPMs.
method Partitioning the learning task into independent time sub-intervals and modeling the score at each time point separately.
result Significant acceleration of training process and improved density estimation performance.
A new method improves efficiency of conformal prediction for ensemble models.
problem Efficiently estimating uncertainty for ensemble models without distributional assumptions.
method Proposes a multivariate score function to merge prediction regions of individual models, reducing conservatism.
result Demonstrates more efficient prediction regions compared to existing methods.
Binary testing for softmax models requires many samples, similar to leverage score models.
problem Binary hypothesis testing for softmax models and leverage score models.
method Analyzing sample complexity and drawing analogies between models.
result Sample complexity is asymptotically \(O(ε^{-2})\), where \(ε\) is the distance between model parameters.
Recently theoretical guarantees have been obtained for matrix completion in the non-uniform sampling regime. In particular, if the sampling distribution aligns with the underlying matrix's leverage scores, then with high probability nuclear norm minimization will exactly recover the low rank matrix. In this article, we…
One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on…
New method assesses individual training points' privacy risk without retraining.
problem Privacy vulnerability of individual training points in membership inference attacks.
method Derives a closed-form decomposition of individual black-box MIA vulnerability, extending to deep networks.
result Proposes a surrogate score operating on last-layer representations that requires only a single trained model.
Introduces VSMD to improve generative diffusion processes without high costs.
problem High training costs and scalability issues in generative diffusion processes.
method Introduces variational Schrödinger momentum diffusion (VSMD) with adaptively transport-optimized variational scores and critical-damping transform.
result Efficiently generates anisotropic shapes while maintaining transport efficacy, outperforming alternatives.
Extends importance sampling to nonlinear models using adjoint operators.
problem Lack of tools for identifying important data points in nonlinear models.
method Introduces adjoint operator for nonlinear maps, generalizes norm and leverage scores.
result Generalized scores provide approximation guarantees for nonlinear mappings.
NE-GMM uses ES and GMM to improve uncertainty quantification.
problem Challenges in estimating mean and variance of complex distributions.
method Integrates Gaussian Mixture Model with Energy Score.
result NE-GMM outperforms in predictive accuracy and uncertainty quantification.
We use the score function for causal discovery, tackling challenges with hidden variables.
problem Causal discovery from observational data with hidden variables.
method Fine-tuning identifiability results, establishing conditions for inferring causal relations from the score, proposing a flexible algorithm.
result Empirical validation of the proposed algorithm for causal discovery on linear, nonlinear, and latent variable models.
Generative models solve medical imaging inverse problems without needing paired data.
problem Reconstructing medical images from partial measurements.
method Score-based generative models trained on medical images, then sampling to reconstruct images consistent with measurements and physical model.
result Comparable or better performance in CT and MRI tasks, with improved generalization to unknown measurement processes.
Proximal Diffusion Models improve generative model efficiency.
problem Improving generative model efficiency and accuracy.
method Developed Proximal Diffusion Models using proximal maps instead of scores.
result Proximal Diffusion Models achieve faster convergence and higher accuracy.
A new robust PCA method uses Innovation Search and Leverage Scores.
problem Outlier detection and robust PCA in data clustering.
method Innovation Search and Leverage Scores.
result The method provides theoretical guarantees and outperforms existing algorithms.
We derive optimal statistical and computational complexity bounds for exp-concave stochastic minimization in terms of the effective dimension. For common eigendecay patterns of the population covariance matrix, this quantity is significantly smaller than the ambient dimension. Our results reveal interesting connections…
A new sampling method estimates scores without training or nested MCMC.
problem Efficient sampling from complex, unnormalised distributions.
method Multiscale averaging in SDEs for score estimation.
result Empirical results show competitive accuracy and efficiency.
Experiment shows author rankings can improve peer review scores.
problem Improving accuracy in machine learning conference peer review.
method Used Isotonic Mechanism to calibrate review scores using author rankings.
result Calibrated scores outperform raw scores in estimating ground truth review scores.
We consider the problem of exact recovery of any matrix of rank from a small number of observed entries via the standard nuclear norm minimization framework. Such low-rank matrices have degrees of freedom . We show that any arbitrary low-rank matrices can be recovered exa…
We consider estimating the parametric components of semi-parametric multiple index models in a high-dimensional and non-Gaussian setting. Such models form a rich class of non-linear models with applications to signal processing, machine learning and statistics. Our estimators leverage the score function based first and…
This work improves SGMs' convergence guarantees for semiconvex distributions with discontinuous gradients.
problem Establishing convergence guarantees for SGMs under weak regularity conditions.
method Developed non-asymptotic Wasserstein-2 convergence analysis for SGMs targeting semiconvex distributions with discontinuous gradients.
result Achieved optimal dependence of on data dimension and convergence rate of order one.
Proposes MSS to identify causal structure from heterogeneous environments.
problem Distribution shifts between environments violate i.i.d. data assumption.
method Sparse mechanism shift hypothesis, score-based approach.
result Identifies entire causal structure with high probability.
DrBO uses Bayesian optimization to learn DAGs more efficiently.
problem Inaccurate and inefficient DAG learning from observational data.
method Bayesian optimization to find high-scoring DAGs efficiently.
result DrBO finds higher-scoring DAGs more efficiently than existing methods.
Stein discrepancy improves UDA performance in low-data scenarios.
problem Improving model performance on unlabeled target domains with limited data.
method Proposes a novel UDA framework using Stein discrepancy, an asymmetric measure that depends on the target distribution through its score function.
result Consistently outperforms prior UDA approaches under limited target data across multiple benchmarks.
This paper explores adversarial robustness of flow-based generative models.
problem Robustness of flow-based generative models to adversarial attacks.
method Theoretical and empirical analysis of adversarial robustness for simple and complex flow-based models.
result Flow-based generative models are highly sensitive to adversarial attacks, but robustness can be significantly improved using hybrid adversarial training.
A new method for training diffusion models using likelihood matching.
problem Training efficient and accurate diffusion models.
method Likelihood Matching approach, quasi-likelihood approximation, score and Hessian estimation.
result Consistent matching of first two transitional moments between diffusion steps.
Paper accelerates diffusion models, improving sampling speed.
problem Low sampling speed in score-based diffusion models.
method Design of novel training-free algorithms for deterministic and stochastic samplers.
result Accelerated samplers converge faster with improved rates.
Optimal score function estimation via empirical risk minimization
problem Estimating the score function of a probability measure on the flat torus from a sample
method Constraining the hypothesis space to a Sobolev ball
result Minimax estimation rates are achieved
Random Fourier features is a widely used, simple, and effective technique for scaling up kernel methods. The existing theoretical analysis of the approach, however, remains focused on specific learning tasks and typically gives pessimistic bounds which are at odds with the empirical results. We tackle these problems an…