In this note we consider sampling from (non-homogeneous) strongly Rayleigh probability measures. As an important corollary, we obtain a fast mixing Markov Chain sampler for Determinantal Point Processes.
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,657 papers · 148 categories
Trend · papers per month
48 results for “fast sampling”
Markov chain Monte Carlo (MCMC) algorithms are simple and extremely powerful techniques to sample from almost arbitrary distributions. The flaw in practice is that it can take a large and/or unknown amount of time to converge to the stationary distribution. This paper gives sufficient conditions to guarantee that univa…
We present a fast variational Bayesian algorithm for performing non-negative matrix factorisation and tri-factorisation. We show that our approach achieves faster convergence per iteration and timestep (wall-clock) than Gibbs sampling and non-probabilistic approaches, and do not require additional samples to estimate t…
A new method speeds up sampling in diffusion models.
problem Slow sample generation in diffusion models.
method Proposed Splitting Integrators for fast stochastic sampling.
result Achieved FID score of 2.36 in 100 NFE, significantly faster than baselines.
We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose constraints. We consider the task of rapidly sampling from such constrained measures, and develop fast M…
SA-Solver improves stochastic sampling from DPMs.
problem Efficient sampling from Diffusion Probabilistic Models (DPMs) is time-consuming.
method Proposes SA-Solver, an improved stochastic Adams method for solving diffusion SDE.
result SA-Solver achieves improved or comparable performance compared to SOTA methods for few-step sampling.
YOASOVI improves stochastic VI for large models with fast, self-correcting sampling.
problem Efficiently performing stochastic Variational Inference on large Bayesian models.
method YOASOVI uses acceptance sampling to draw only one sample per iteration, improving convergence speed and accuracy.
result YOASOVI converges faster and more accurately than regular Monte Carlo and Quasi-Monte Carlo methods.
Fast algorithm samples confined polygons efficiently.
problem Sampling confined random equilateral closed polygons efficiently.
method Uses symplectic geometry to sample moment polytope, leading to a linear-time algorithm.
result Explicit formulas for expected distances and total curvature of vertices to the origin.
Inference in general Ising models is difficult, due to high treewidth making tree-based algorithms intractable. Moreover, when interactions are strong, Gibbs sampling may take exponential time to converge to the stationary distribution. We present an algorithm to project Ising model parameters onto a parameter set that…
A fast Gibbs sampler for Bayesian HMMs with missing data.
problem Complexity and slow mixing in EM and Gibbs samplers for HMMs with missing observations.
method Proposes a collapsed Gibbs sampler that integrates missing observations and latent states, achieving high accuracy, large ESS, and reduced computational complexity.
result The proposed sampler is faster and more efficient than existing methods, especially with many missing entries.
Favour speeds up variance estimation in BNNs, making them practical for performance-critical tasks.
problem Slow inference in Bayesian Neural Networks (BNNs) hinders their adoption.
method A fast algorithm for updating a diagonal-plus-low-rank matrix approximation under various operations.
result Favour is as fast as 2-3 inference samples but matches the performance of 10-100 samples.
Study shows convergence rate for empirical minimizer of unbounded functions with fast growth.
problem Convergence rate of empirical minimizer for unbounded functions with fast growth.
method Analyzes -distance convergence rate of the empiric minimizer for coercive functions sampled with noise.
result Convergence rate is bounded above by , where is the dimension and for every .
New algorithms for fast online decision making using neural networks and martingale posteriors.
problem Online sequential decision making under uncertainty.
method Martingale posterior neural networks for fast online learning and decision making.
result Achieves competitive performance-speed trade-offs in non-stationary contextual bandits and Bayesian optimization.
Autoregressive models (ARMs) currently hold state-of-the-art performance in likelihood-based modeling of image and audio data. Generally, neural network based ARMs are designed to allow fast inference, but sampling from these models is impractically slow. In this paper, we introduce the predictive sampling algorithm: a…
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.
The paper studies how quickly samples from Langevin dynamics become independent.
problem Understanding the dependence between samples along Langevin dynamics and related algorithms.
method Measures dependence via -mutual information and proves strong data processing inequalities.
result The -mutual information between samples decreases exponentially to zero.
Support Vector Data Description (SVDD) is a popular outlier detection technique which constructs a flexible description of the input data. SVDD computation time is high for large training datasets which limits its use in big-data process-monitoring applications. We propose a new iterative sampling-based method for SVDD…
Improved CEM for fast real-time planning in high-dimensional control tasks.
problem Sampling inefficiency of CEM in real-time planning.
method Novel additions to CEM including temporally-correlated actions and memory.
result 2.7-22x less samples and 1.2-10x performance increase.
Consistency Modelscs.LG
Consistency models generate high-quality samples fast and without iterative sampling.
problem Slow generation in diffusion models.
method Direct mapping of noise to data, supporting fast one-step generation and multistep sampling.
result Consistency models achieve state-of-the-art FID scores and outperform diffusion models in one-step generation.
Develops a fast, accurate method for comparing networks.
problem Comparing networks with repeated observations and varying sizes/sparsity.
method A novel two-sample hypothesis testing method with theoretical guarantees.
result Outperforms existing tools in speed and accuracy, power-optimal.
The paper analyzes reinforcement learning methods for estimating weights and quality functions with fast convergence rates.
problem Estimating weights and quality functions in reinforcement learning with function approximation.
method The paper uses minimax methods for estimating marginal importance weights and q-functions.
result The minimax approach enables fast rates of convergence for weights and quality functions, achieving first-order efficiency.
Fast and Robust Likelihood-Guided Diffusion Posterior Sampling with Amortized Variational Inferencestat.ML
Improved diffusion sampling for inverse problems with faster and more robust inference.
problem High computational cost and lack of robustness in diffusion posterior sampling.
method Amortized variational inference with explicit likelihood guidance.
result Improved trade-off between inference speed and robustness to unseen degradations.
Gradient-based meta-learning has proven to be highly effective at learning model initializations, representations, and update rules that allow fast adaptation from a few samples. The core idea behind these approaches is to use fast adaptation and generalization -- two second-order metrics -- as training signals on a me…
Improved diffusion model generation speed with speculative sampling.
problem Generating samples from computationally expensive diffusion models.
method Extending speculative sampling to diffusion models, using fast draft models for candidate token generation.
result Significant speedup in generation, halving the number of function evaluations.
Efficient algorithm finds fast Transformer models.
problem Slow inference time of Transformer models.
method Decompose Transformer architecture into components, use sampling-based one-shot search.
result Achieved 10% to 30% speedup on pre-trained BERT and 70% on top of a previous state-of-the-art model.
Efficiently handles contextual bandits with diffusion models.
problem Challenges in online decision-making with contextual bandits.
method Leverage pre-trained diffusion models as priors to capture action dependencies.
result Developed an algorithm for efficient posterior approximation.
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.
A fast method estimates Gaussian mixture components without iterative fitting.
problem Estimating the number of components in high-dimensional Gaussian mixtures.
method Center data, compute singular values, and count above a threshold.
result The estimator consistently recovers the true number of components under mild separation condition.
We develop a fast, tractable technique called Net-Trim for simplifying a trained neural network. The method is a convex post-processing module, which prunes (sparsifies) a trained network layer by layer, while preserving the internal responses. We present a comprehensive analysis of Net-Trim from both the algorithmic a…
Markov jump processes and continuous time Bayesian networks are important classes of continuous time dynamical systems. In this paper, we tackle the problem of inferring unobserved paths in these models by introducing a fast auxiliary variable Gibbs sampler. Our approach is based on the idea of uniformization, and sets…
A fast MCMC sampler for sparse Bayesian inference.
problem Sparse Bayesian inference problems with high computational cost.
method Asynchronous Gibbs sampler extended with data sub-sampling.
result The Markov chain admits an invariant distribution that recovers the main signal with high probability.
The Mondrian Kernelstat.ML
We introduce the Mondrian kernel, a fast random feature approximation to the Laplace kernel. It is suitable for both batch and online learning, and admits a fast kernel-width-selection procedure as the random features can be re-used efficiently for all kernel widths. The features are constructed by sampling trees via a…
Improved stochastic approximation method reduces residual error.
problem Reducing residual error in stochastic approximation algorithms.
method Fixed-schedule one-quarter barrier and bias-corrected acceleration.
result Achieves residual reduction with primitive samples.
Stochastic gradient method converges as fast as deterministic for overparametrized models.
problem Convergence rate of stochastic gradient methods in overparametrized models.
method Proposes a regularity condition enabling fast convergence of SGD.
result Stochastic gradient method achieves the same convergence rate as deterministic gradient method.
DPM-Solver speeds up DPM sampling to 10-20 function evaluations.
problem Slow sampling from Diffusion Probabilistic Models (DPMs).
method Exact formulation of diffusion ODE solutions, using change-of-variable and exponentially weighted integral.
result Generates high-quality samples in 10-20 function evaluations.
A fast method approximates likelihood scores for noisy linear inverse problems.
problem Solving noisy linear inverse problems efficiently.
method Proposes a simple closed-form approximation to the likelihood score for diffusion and flow-based models.
result Significantly faster than baseline methods while maintaining competitive or better reconstruction performances.
Gradient-based temporal difference (GTD) algorithms are widely used in off-policy learning scenarios. Among them, the two time-scale TD with gradient correction (TDC) algorithm has been shown to have superior performance. In contrast to previous studies that characterized the non-asymptotic convergence rate of TDC only…
New bounds for multi-task learning with varying task sizes.
problem Generalization in multi-task learning with tasks of different sizes.
method PAC-Bayesian bounds for unbalanced settings.
result Stronger generalization bounds for multi-task learning with varying task sizes.
Ensemble method for fast portfolio valuation and risk management.
problem Dynamic portfolio valuation and risk management from cash flow data.
method Regression trees for dynamic value process learning.
result Fast and accurate estimator with closed-form solution.
This thesis explores fast algorithms for large matrices and data augmentation to improve model efficiency.
problem Efficient handling of large models and data in scientific computing and machine learning.
method Randomized low-rank decomposition algorithms and data augmentation techniques.
result Improved sample efficiency and generalization of machine learning models.
FOOD detects out-of-distribution samples quickly without needing OOD data.
problem Detecting out-of-distribution samples efficiently in neural networks.
method Extended DNN classifier with Gaussian layer and log likelihood ratio test.
result FOOD achieves state-of-the-art performance and is fast and applicable.
One-step diffusion samplers reduce sampling time and computational costs.
problem Efficient sampling from complex distributions.
method One-step diffusion, self-distillation, deterministic flow.
result Achieves competitive sample quality with fewer evaluations.
Parallel sampling for smooth distributions with fast convergence.
problem Efficiently sampling from distributions with smooth densities.
method Parallelization of Langevin algorithms under log-Sobolev inequalities.
result Samples close to target distribution with low KL divergence or TV distance.
Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discoverystat.ME
Constraint-based causal discovery (CCD) algorithms require fast and accurate conditional independence (CI) testing. The Kernel Conditional Independence Test (KCIT) is currently one of the most popular CI tests in the non-parametric setting, but many investigators cannot use KCIT with large datasets because the test sca…
Enhash detects concept drift in data streams quickly and efficiently.
problem Detecting abrupt, gradual, virtual, or recurring events in data streams.
method Uses projection hash to insert incoming samples and detects concept drift.
result Enhash has competitive performance and moderate resource requirements compared to existing ensemble learners.
Efficient momentum-based methods for reinforcement learning with improved sample complexity.
problem Efficient reinforcement learning algorithms for non-concave performance functions.
method Adaptive momentum-based policy gradient methods using variance reduction and importance sampling techniques.
result Both IS-MBPG and HA-MBPG reach the best known sample complexity of for finding an -stationary point.
Paper proposes a distributed sampling method for Bayesian inference.
problem Privacy and communication constraints in spatially distributed datasets.
method Alternating Direction Method of Multipliers for distributed sampling.
result Algorithm converges to target distribution in Wasserstein distance.
Sample- and computationally-efficient distribution estimation is a fundamental tenet in statistics and machine learning. We present SURF, an algorithm for approximating distributions by piecewise polynomials. SURF is: simple, replacing prior complex optimization techniques by straight-forward {empirical probability} ap…