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.
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,742 papers · 148 categories
Trend · papers per month
48 results for “exact 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.
Determinantal point processes (DPPs) are an important concept in random matrix theory and combinatorics. They have also recently attracted interest in the study of numerical methods for machine learning, as they offer an elegant "missing link" between independent Monte Carlo sampling and deterministic evaluation on reg…
Unsupervised learning of probabilistic models is a central yet challenging problem in machine learning. Specifically, designing models with tractable learning, sampling, inference and evaluation is crucial in solving this task. We extend the space of such models using real-valued non-volume preserving (real NVP) transf…
Exact distribution of split conformal prediction coverage found.
problem Determining the reliability of prediction sets in batch mode.
method Analysis of exchangeable data to find universal distribution of empirical coverage.
result Exact distribution of empirical coverage is universal and determined by nominal miscoverage level and calibration sample size.
This paper solves the multiple reference model problem in RLHF with exact solutions and sample complexity guarantees.
problem Limitations of single reference models in aligning LLMs with human feedback.
method Integrates multiple reference models into RLHF frameworks, addressing theoretical challenges with exact solutions and sample complexity guarantees.
result First exact solution to the multiple reference model problem in reverse KL-regularized RLHF.
Exact learning improves naive Bayes classifier performance for small samples.
problem Improving naive Bayes classifier performance with small sample sizes.
method Proposes an exact learning augmented naive Bayes classifier (ANB) that ensures a class variable with no parents.
result The proposed ANB method outperforms other methods in comparison experiments.
New method for exact matrix completion with reduced observation complexity.
problem Exact recovery of matrices with high coherence.
method Adaptive sampling method and relation to sparsest vector of column and row spaces.
result Exact recovery of -coherent column space matrices with much smaller observation complexity.
Exact inference method for Wasserstein distance with finite-sample coverage.
problem Asymptotic approximation methods for Wasserstein distance lack finite-sample validity.
method Selective Inference inspired approach for exact inference.
result Valid confidence interval for Wasserstein distance with finite-sample coverage.
The paper proposes a method to learn the structure of continuous-action games with non-parametric utilities using a limited number of samples.
problem Learning the exact structure of continuous-action games with non-parametric utility functions.
method An regularized method that encourages sparsity of the Fourier transform coefficients of the utility functions, accessed via a few Nash equilibria and their noisy utilities.
result The method recovers the exact structure of the utility functions and the game structure with provable theoretical guarantees.
Determinantal point processes (DPPs) enable the modeling of repulsion: they provide diverse sets of points. The repulsion is encoded in a kernel that can be seen as a matrix storing the similarity between points. The diversity comes from the fact that the inclusion probability of a subset is equal to the determinan…
Computing the permanent of a non-negative matrix is a core problem with practical applications ranging from target tracking to statistical thermodynamics. However, this problem is also #P-complete, which leaves little hope for finding an exact solution that can be computed efficiently. While the problem admits a fully …
TDS provides exact samples for conditional distributions in diffusion models.
problem Lack of exact sampling methods for diffusion models.
method Sequential Monte Carlo (SMC) algorithm with twisting technique.
result TDS offers more accurate approximations with fewer particles compared to heuristics.
Compact learning results across various loss functions.
problem Understanding sample complexity in transductive learning.
method Analyzing finite projections and sample complexities for different loss functions.
result Exact compactness of sample complexity holds broadly across realizable and agnostic learning.
This study approximates distances between Gaussian processes and covariance operators using RKHS.
problem Approximating distances between Gaussian processes and covariance operators from finite samples.
method Using reproducing kernel Hilbert space (RKHS) covariance and cross-covariance operators, the study shows how to consistently and efficiently estimate Sinkhorn divergence from finite samples.
result Convergence rates are dimension-independent and of the same order as Hilbert-Schmidt distance.
We obtain the first positive results for bounded sample compression in the agnostic regression setting with the loss, where . We construct a generic approximate sample compression scheme for real-valued function classes exhibiting exponential size in the fat-shattering dimension but independen…
Exact learning of tree-structured models with side info and noise.
problem Learning tree-structured graphical models with side information and noise.
method Probabilistic tools from strong large deviations theory.
result Exact asymptotics of structure learning from samples.
To improve the efficiency of Monte Carlo estimation, practitioners are turning to biased Markov chain Monte Carlo procedures that trade off asymptotic exactness for computational speed. The reasoning is sound: a reduction in variance due to more rapid sampling can outweigh the bias introduced. However, the inexactness …
Exact guidance for discrete data improves posterior sampling efficiency.
problem Inefficient guidance for discrete data in posterior sampling.
method Derive exact transition rate for desired distribution given learned discrete flow matching model.
result Significantly improved efficiency with single forward pass per sampling step.
Communication costs, resulting from synchronization requirements during learning, can greatly slow down many parallel machine learning algorithms. In this paper, we present a parallel Markov chain Monte Carlo (MCMC) algorithm in which subsets of data are processed independently, with very little communication. First, w…
We consider the inference of the structure of an undirected graphical model in an exact Bayesian framework. More specifically we aim at achieving the inference with close-form posteriors, avoiding any sampling step. This task would be intractable without any restriction on the considered graphs, so we limit our explora…
This paper improves parameter estimation in cardiac models using Gaussian process-based MH sampling.
problem Uncertainty in estimating patient-specific model parameters from sparse and noisy clinical data.
method Integrates surrogate modeling into Metropolis-Hastings sampling to improve computational efficiency and accuracy.
result Significant gain in computational efficiency without compromising accuracy, and insights into tissue heterogeneity.
Exact and high order discretization schemes for Wishart processes and their affine extensionsmath.PR
This work deals with the simulation of Wishart processes and affine diffusions on positive semidefinite matrices. To do so, we focus on the splitting of the infinitesimal generator, in order to use composition techniques as Ninomiya and Victoir or Alfonsi. Doing so, we have found a remarkable splitting for Wishart proc…
For optimization on large-scale data, exactly calculating its solution may be computationally difficulty because of the large size of the data. In this paper we consider subsampled optimization for fast approximating the exact solution. In this approach, one gets a surrogate dataset by sampling from the full data, and …
This paper develops the first method for the exact simulation of reflected Brownian motion (RBM) with non-stationary drift and infinitesimal variance. The running time of generating exact samples of non-stationary RBM at any time is uniformly bounded by where is the average drift of…
Exact expressions for double descent and implicit regularization in over-parameterized models.
problem Understanding the generalization error of over-parameterized models like deep neural networks.
method Surrogate random design to replace standard i.i.d. design, leading to exact expressions for mean squared error and implicit regularization.
result Exact non-asymptotic expressions for double descent and implicit regularization in over-parameterized models.
New exact tests detect changepoints in binary and count data, especially when normal approximations fail.
problem Detecting changepoints in multichannel binary and count data.
method Exact tests combining two-sample conditional tests with multiplicity correction.
result Exact tests are much more powerful than asymptotic tests in various settings.
Federated learning supports exact support recovery with minimal communication.
problem Learning the exact support of sparse linear regression in federated learning.
method One-shot communication algorithm for exact support recovery without optimization.
result Polynomial sample complexity and logarithmic number of clients required.
Unified method for MMD variance estimation improves accuracy and computational efficiency.
problem Variance estimation for MMD in nonparametric testing.
method Unified finite-sample characterization of MMD variance through U-statistic and Hoeffding decomposition; exact acceleration method for univariate case.
result Unified estimators improve accuracy and computational efficiency for MMD variance.
Proposes exact inference for continuous-time Gaussian process dynamics.
problem Inexact inference methods for continuous-time Gaussian process dynamics are impractical for irregularly-sampled data.
method Uses higher-order numerical integrators to discretize dynamics with arbitrary accuracy and proposes multistep and Taylor integrators for exact inference.
result Demonstrates accurate representation of continuous-time systems through exact GP inference.
We study the complexity of sampling from a distribution over all index subsets of the set with the probability of a subset proportional to the determinant of the submatrix of some p.s.d. matrix , where corresponds to the entries of ind…
Exact Bayesian inference for discrete models using probability generating functions.
problem Discrete statistical models with infinite support and continuous priors.
method Probabilistic programming language with automatic differentiation and probability generating functions.
result Genfer tool provides exact solutions for a wide range of inference problems.
In this paper we outline methodology to efficiently simulate (jump) diffusion bridge sample paths without discretisation error. We achieve this by considering the simulation of conditioned (jump) diffusion bridge sample paths in light of recent work developing a mathematical framework for simulating finite dimensional …
Taking advantage of the recent litterature on exact simulation algorithms (Beskos, Papaspiliopoulos and Roberts) and unbiased estimation of the expectation of certain fonctional integrals (Wagner, Beskos et al. and Fearnhead et al.), we apply an exact simulation based technique for pricing continuous arithmetic average…
New methods for tuning alpha in Gibbs posteriors improve speed and accuracy.
problem Inconsistency in Bayesian inference and lack of fast tuning methods for alpha.
method Proposed two data-driven methods: sample-splitting and bootstrapping. Formulated alpha-posteriors for three models.
result Sample-splitting outperforms SafeBayes in speed and accuracy, especially in complex models.
A new method approximates the exact posterior score for diffusion models.
problem Training-free guidance of diffusion models for image restoration and inverse problems.
method Presented a novel expression for the exact posterior score, leveraging it to compute step sizes on the fly.
result Demonstrated competitive performance with fewer time steps compared to state-of-the-art techniques.
Contrastive Divergence (CD) and Persistent Contrastive Divergence (PCD) are popular methods for training the weights of Restricted Boltzmann Machines. However, both methods use an approximate method for sampling from the model distribution. As a side effect, these approximations yield significantly different biases and…
Given a real matrix A with n columns, the problem is to approximate the Gram product AA^T by c << n weighted outer products of columns of A. Necessary and sufficient conditions for the exact computation of AA^T (in exact arithmetic) from c >= rank(A) columns depend on the right singular vector matrix of A. For a Monte-…
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…
A new method clusters intersecting lines using hypergraphs.
problem Clustering intersecting lines in subspace clustering.
method Constructing a geometric hypergraph and using spectral algorithm.
result Achieves information-theoretic bounds for line clustering.
We propose an exact slice sampler for Hierarchical Dirichlet process (HDP) and its associated mixture models (Teh et al., 2006). Although there are existing MCMC algorithms for sampling from the HDP, a slice sampler has been missing from the literature. Slice sampling is well-known for its desirable properties includin…
A new permutation method improves two-sample testing power.
problem Two-sample testing with improved power and validity.
method Structured block-restricted cross-swaps.
result Block-restricted permutations achieve higher power than full permutations.
Homogenized SGD explains SGD dynamics in high dimensions.
problem Understanding SGD dynamics in high-dimensional settings.
method Developed a homogenized SGD model to analyze high-dimensional SGD.
result Convergent high-dimensional SGD to homogenized SGD for quadratic statistics.
Cardinality potentials are a generally useful class of high order potential that affect probabilities based on how many of D binary variables are active. Maximum a posteriori (MAP) inference for cardinality potential models is well-understood, with efficient computations taking O(DlogD) time. Yet efficient marginalizat…
Exact computation of posterior distribution of mixture weights in hierarchical Bayesian modelsstat.ME
This paper computes exact posterior distributions of mixture weights in hierarchical Bayesian models.
problem Uncertainty in class membership or data-generating processes in heterogeneous data.
method Exact marginalization of mixture weights using dynamic programming and FFT for two components, and joint dynamic program for K >= 3 components.
result Exact posterior distributions of mixture weights are finite mixtures of Beta distributions, providing credible intervals and per-observation local false-discovery rates.
FLASH-MAX predicts electromagnetic fields from sparse data in seconds.
problem Predicting homogeneous electromagnetic fields from sparse pointwise observations.
method Exact-by-construction neural network architecture that satisfies Maxwell's equations symbolically.
result FLASH-MAX achieves sub-1% relative validation error from 1K sparse observations in seconds.
The computational cost of training with softmax cross entropy loss grows linearly with the number of classes. For the settings where a large number of classes are involved, a common method to speed up training is to sample a subset of classes and utilize an estimate of the loss gradient based on these classes, known as…
New method uses diffusion models for unsupervised combinatorial optimization.
problem Learning to sample from intractable discrete distributions without training data.
method Lifts the restriction of generative models needing exact sample likelihoods using a loss that bounds reverse KL divergence.
result Achieves new state-of-the-art results in data-free Combinatorial Optimization.