PRS improves rejection sampling by learning better proposals.
problem High rejection rate in traditional rejection sampling.
method PRS uses a kernel estimator to learn better sampling proposals.
result PRS guarantees a low number of accepted samples.
We provide a method for approximating Bayesian inference using rejection sampling. We not only make the process efficient, but also dramatically reduce the memory required relative to conventional methods by combining rejection sampling with particle filtering. We also provide an approximate form of rejection sampling …
Delayed rejection HMC improves sampling efficiency for multiscale distributions.
problem Hamiltonian Monte Carlo struggles with wide-ranging distributions, especially in high-curvature areas.
method Introduces a delayed rejection variant of HMC, using geometrically smaller step sizes for retries.
result Up to five-fold performance gains in effective sample size per gradient evaluation.
Algorithmic trading systems on DEXs reject most candidate tokens, but the counterfactual outcome of rejected candidates is rarely measured.
problem Measuring the counterfactual outcome of rejected tokens in algorithmic trading systems on decentralized exchanges.
method Post-Rejection Follow-up Sampling (PRFS) introduces a methodology for collecting and analyzing the data needed to evaluate filter precision against actual market outcomes of rejected candidates.
result PRFS produces the data needed to evaluate filter precision against actual market outcomes of rejected candidates, not against synthetic backtest reconstructions.
Rejection Sampling is a fundamental Monte-Carlo method. It is used to sample from distributions admitting a probability density function which can be evaluated exactly at any given point, albeit at a high computational cost. However, without proper tuning, this technique implies a high rejection rate. Several methods h…
New algorithms reduce rejection sampling complexity for shape-constrained distributions.
problem Generating exact samples from shape-constrained distributions efficiently.
method Sublinear query complexity algorithms for rejection sampling.
result Sublinear complexity algorithms for sampling from shape-constrained distributions.
RMT-Net tackles biased credit scoring data by learning from both default/non-default and rejection/approval tasks.
problem Missing-not-at-random selection bias in financial credit scoring data.
method Reject-aware Multi-Task Network (RMT-Net) that leverages the correlation between default/non-default and rejection/approval tasks.
result RMT-Net improves credit scoring models by learning from both default/non-default and rejection/approval tasks.
Proposes a method combining CNFs and rejection-resampling for sampling from unnormalized densities.
problem Sampling from unnormalized probability densities, especially multimodal ones.
method Combines continuous normalizing flows with rejection-resampling steps based on importance weights.
result The method improves sampling accuracy and performance compared to state-of-the-art methods.
Naive approaches to amortized inference in probabilistic programs with unbounded loops can produce estimators with infinite variance. This is particularly true of importance sampling inference in programs that explicitly include rejection sampling as part of the user-programmed generative procedure. In this paper we de…
Credit scoring models support loan approval decisions in the financial services industry. Lenders train these models on data from previously granted credit applications, where the borrowers' repayment behavior has been observed. This approach creates sample bias. The scoring model (i.e., classifier) is trained on accep…
Improved inference for models with continuous latent variables.
problem Inference accuracy with traditional variational methods is limited.
method Reparameterized Variational Rejection Sampling (RVRS) using a proposal distribution with a reparameterized gradient estimator.
result RVRS offers a better trade-off between computational cost and inference fidelity.
Paper reinterprets ARP algorithm and improves its analysis and speed.
problem Column subset selection in data analysis.
method Volume sampling and active learning connections, new analysis, rejection sampling.
result Faster implementations and new analysis for ARP algorithm.
Generative classifiers have been shown promising to detect illegal inputs including adversarial examples and out-of-distribution samples. Supervised Deep Infomax~(SDIM) is a scalable end-to-end framework to learn generative classifiers. In this paper, we propose a modification of SDIM termed SDIM-\emph{logit}. Instead …
Variational inference using the reparameterization trick has enabled large-scale approximate Bayesian inference in complex probabilistic models, leveraging stochastic optimization to sidestep intractable expectations. The reparameterization trick is applicable when we can simulate a random variable by applying a differ…
Accelerated RPCholesky speeds up kernel matrix approximations.
problem Efficiently approximating large kernel matrices.
method Accelerated randomly pivoted Cholesky (RPCholesky) with block matrix computations and rejection sampling.
result Approximates kernel matrices up to 40 times faster.
Hour-Aware Adaptive Risk Management for Autonomous Memecoin Trading
problem Autonomous memecoin trading system performance
method Hour-of-day effects, filter precision, fragility
result 40.5% win rate, mean per-trade return of +0.62%, cumulative +117.7%
A method for making predictions with a reject option using conformal prediction.
problem Uncertainty in machine learning predictions, especially when models are unsure.
method Formalizing ML with reject option, using conformal prediction for distribution-free error guarantees.
result Theoretical guarantees on error rate for prediction sets with distribution-free validity.
TabNAS improves neural architecture search for tabular datasets by rejecting suboptimal architectures.
problem Finding optimal neural architectures for tabular datasets with resource constraints.
method Develops a reinforcement learning controller motivated by rejection sampling to handle resource constraints.
result TabNAS finds better models that obey resource constraints compared to previous methods.
We propose a rejection sampling scheme using the discriminator of a GAN to approximately correct errors in the GAN generator distribution. We show that under quite strict assumptions, this will allow us to recover the data distribution exactly. We then examine where those strict assumptions break down and design a prac…
This paper addresses challenges in flexibly modeling multimodal data that lie on constrained spaces. Such data are commonly found in spatial applications, such as climatology and criminology, where measurements are restricted to a geographical area. Other settings include domains where unsuitable recordings are discard…
Learning latent variable models with stochastic variational inference is challenging when the approximate posterior is far from the true posterior, due to high variance in the gradient estimates. We propose a novel rejection sampling step that discards samples from the variational posterior which are assigned low likel…
Method uses normalizing flows to efficiently sample from complex target densities.
problem Sampling from complex target densities with zero values in regions of transformation.
method Normalizing flows to address exploding reverse Kullback-Leibler divergence.
result Demonstrated efficient sampling from multi-mode complex density function.
Optimizes sampling from target distributions with applications to online learning.
problem Optimizing the total variation distance between target and sampled distributions.
method Analyzes the sample complexity of approximate rejection sampling and its applications.
result The optimal total variation distance is given by $ ildeΘ( rac{D}{f'(n)})$.
The paper tackles sampling bias in credit scoring models and proposes methods to improve their training and evaluation.
problem Sampling bias in credit scoring models leads to an incomplete representation of the borrower population.
method Bias-aware self-learning framework and Bayesian evaluation method to correct for bias.
result Bayesian evaluation outperforms standard accuracy measures in predicting future performance.
New sampling algorithm for non-smooth potentials.
problem Sampling from non-smooth potentials.
method Proximal algorithm based on rejection sampling.
result Achieves better complexity than existing methods.
This work tackles scalable sampling for nonsymmetric DPPs.
problem Scalability issue in existing DPP sampling algorithms for nonsymmetric DPPs.
method Developed a linear-time algorithm for kernels with low-rank structure and a sublinear-time rejection sampling algorithm.
result Bounded rejection rate for kernels with structural constraints.
Improved adaptive algorithms for identifying the best arm in MABs with fixed budget.
problem Identifying the best arm in stochastic Multi-Armed Bandits with a fixed sampling budget.
method Established a connection between Large Deviation Principles and adaptive algorithms, improving error probability bounds and devising new algorithms.
result The \sred algorithm outperforms existing algorithms in identifying the best arm.
We present a method for performing Hamiltonian Monte Carlo that largely eliminates sample rejection for typical hyperparameters. In situations that would normally lead to rejection, instead a longer trajectory is computed until a new state is reached that can be accepted. This is achieved using Markov chain transitions…
The paper audits trading filters, finding a high save-to-miss ratio.
problem Improving the efficiency and accuracy of trading filters in decentralized exchanges.
method A precision audit of filter rules against real trading data, classifying rejection events.
result Conservative save-to-miss ratio of 3.7 : 1, with wider interpretation of 14.8 : 1.
Algorithm samples from Bingham distribution efficiently.
problem Sampling from the Bingham distribution on a sphere.
method Rejection sampling with polynomial approximation.
result Exact samples from Bingham distribution in polynomial time.
A minimalist approach improves LLM reasoning by filtering incorrect responses.
problem Improving large language model (LLM) reasoning on complex tasks.
method Revisit GRPO from a reinforce-like algorithm perspective, proposing Reinforce-Rej.
result RAFT, a simple rejection sampling baseline, outperforms GRPO and PPO.
New algorithm improves mixing in Bayesian mixture models.
problem Slow mixing in Bayesian mixture models.
method A new Monte Carlo algorithm for sampling from the marginal posterior of a general integrable mixture.
result The new algorithm achieves excellent mixing times, outperforming standard Gibbs sampling in some cases.
PDHAMS improves sampling for discrete distributions with quadratic potential functions.
problem Sampling discrete distributions efficiently and accurately.
method Integrates a second-order approximation of the potential function and uses Gaussian integral trick.
result PDHAMS yields superior performance compared to other methods.
No GANs can learn disconnected manifolds precisely.
problem Learning disconnected manifolds is challenging due to unimodal latent distributions.
method Formalized a no free lunch theorem and derived a rejection sampling method.
result Upper bound on the precision of the targeted disconnected manifold distribution.
Markov chain (MC) algorithms are ubiquitous in machine learning and statistics and many other disciplines. Typically, these algorithms can be formulated as acceptance rejection methods. In this work we present a novel estimator applicable to these methods, dubbed Markov chain importance sampling (MCIS), which efficient…
New algorithms sample convex bodies using Markov chains and restricted Gaussian oracles.
problem Sampling uniformly from convex bodies efficiently.
method Markov chain Monte Carlo with proximal sampler and restricted Gaussian oracle.
result Efficient implementation of RGO for uniform sampling on convex bodies.
Paper addresses RLHF alignment challenges with novel algorithms.
problem Challenges in RLHF alignment, especially in strategic exploration.
method Develops a reverse-KL regularized contextual bandit formulation and proposes efficient algorithms with theoretical guarantees.
result Proposed methods significantly outperform existing RLHF algorithms in real-world experiments.
This Chapter, "ABC Samplers", is to appear in the forthcoming Handbook of Approximate Bayesian Computation (2018). It details the main ideas and algorithms used to sample from the ABC approximation to the posterior distribution, including methods based on rejection/importance sampling, MCMC and sequential Monte Carlo.
Paper tackles regression with cost-based rejection, balancing prediction and rejection costs.
problem Regression with cost-based rejection, balancing prediction and rejection costs in a continuous target space.
method Formulated expected risk, derived Bayes optimal solution, proposed surrogate loss function.
result Bayes optimal solution can be recovered by the proposed surrogate loss function.
Cost-aware SBI reduces expensive simulations in complex models.
problem High computational cost in simulating complex models.
method Combination of rejection and self-normalised importance sampling.
result Significant reduction in overall cost of inference.
Framework to mitigate adversarial attacks by allowing classifiers to abstain.
problem Vulnerability of classifiers to adversarial examples.
method Adversarial training with a rejection option.
result ATRO framework improves classifier reliability against adversarial attacks.
In this work, we propose a method to reject out-of-distribution samples which can be adapted to any network architecture and requires no additional training data. Publicly available chest x-ray data (38,353 images) is used to train a standard ResNet-50 model to detect emphysema. Feature activations of intermediate laye…
Energy-based models (EBMs) are powerful probabilistic models, but suffer from intractable sampling and density evaluation due to the partition function. As a result, inference in EBMs relies on approximate sampling algorithms, leading to a mismatch between the model and inference. Motivated by this, we consider the sam…
We propose Learned Accept/Reject Sampling (LARS), a method for constructing richer priors using rejection sampling with a learned acceptance function. This work is motivated by recent analyses of the VAE objective, which pointed out that commonly used simple priors can lead to underfitting. As the distribution induced …
New MC simulation methods use classifiers to estimate pdf ratios without explicit pdfs.
problem Estimating ratios of probability density functions (pdfs) without explicit pdfs.
method Proposes classifier-based pdf-free versions of MC simulation algorithms.
result Enables pdf-free simulation algorithms using surrogate functions computed by classifiers.
The paper tackles uniform sampling from databases with duplicates.
problem Sampling uniformly from entities with duplicate records.
method Two-stage process: frequency estimation followed by rejection sampling.
result Efficient sampling algorithms under various data properties.
New method uses zeroth-order queries to approximate proximal sampling efficiently.
problem Approximating proximal sampling with zeroth-order information.
method Direct simulation of heat flow dynamics, treating intermediate distribution as Gaussian mixture.
result Inherits exponential convergence under isoperimetric conditions, avoids rejection sampling.
We prove exact BNN posterior convergence to GP limit and provide sampling methods.
problem Theoretical and empirical challenges in obtaining exact posterior distributions of wide BNNs.
method Theoretical proof and rejection sampling for generating exact samples.
result Exact BNN posterior converges to GP limit as width increases.