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…
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,932 papers · 148 categories
Trend · papers per month
48 results for “fast mixing”
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…
Paper proposes a new approach for agents to explore environments efficiently.
problem Learning policies that explore uniformly and mix quickly in environments without external rewards.
method Introduces a surrogate objective to maximize entropy and develops a model-based reinforcement learning algorithm, IDEAL.
result Demonstrates improved exploration and mixing in hard-exploration tasks.
TD(0) with Polyak-Ruppert averaging achieves robust and fast convergence rates
problem TD(0) learning under Markovian sampling
method Polyak-Ruppert averaging with a single stepsize
result Simultaneous high-probability convergence guarantees for TD(0) iterates and PR average
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.
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…
The paper analyzes convergence rates of Langevin dynamics and Proximal Sampler using -divergence.
problem Analyzing convergence rates of Langevin dynamics and Proximal Sampler.
method Extending mixing time analyses to -divergence, using strong data processing inequalities.
result Convergence of -divergence to 0 exponentially fast along Unadjusted Langevin Algorithm and Proximal Sampler.
New RL method MAC improves performance in sparse reward settings.
problem Slow mixing in large state spaces or sparse rewards.
method Multi-level Monte Carlo Actor-Critic (MAC) algorithm.
result Achieves convergence rate comparable to state-of-the-art AC algorithms.
The present research work proposes a new fast fixed-point averaging algorithm on the compact Stiefel manifold based on a mixed retraction/lifting pair. Numerical comparisons between fixed-point algorithms based on the proposed non-associated retraction/lifting map pair and two associated retraction/lifting pairs confir…
Inference is typically intractable in high-treewidth undirected graphical models, making maximum likelihood learning a challenge. One way to overcome this is to restrict parameters to a tractable set, most typically the set of tree-structured parameters. This paper explores an alternative notion of a tractable set, nam…
Bayesian test assesses dependence between mixed data types.
problem Assessing dependence between text, image, and sound data.
method Bayesian kernelised correlation test using Dirichlet process model.
result Demonstrated effectiveness compared to other methods.
We improve Gaussian copula models for imputing mixed data types with precise approximations.
problem Imputing missing values with mixed data types in surveys and medical applications.
method We use randomized quasi-Monte Carlo procedures for direct and arbitrarily precise approximations of model estimation and imputation.
result Our method yields lower errors for model parameters and imputed values compared to existing methods.
We investigate the systematic mechanism for designing fast mixing Markov chain Monte Carlo algorithms to sample from discrete point processes under the Dobrushin uniqueness condition for Gibbs measures. Discrete point processes are defined as probability distributions over all subsets $S\in 2^…
Mix-IRLS solves imbalanced mixed linear regression problems efficiently.
problem Imbalanced mixed linear regression problems.
method Sequential robust regression approach.
result Mix-IRLS outperforms other methods on imbalanced mixtures and real-world datasets.
In this paper, we give a new sharp generalization bound of lp-MKL which is a generalized framework of multiple kernel learning (MKL) and imposes lp-mixed-norm regularization instead of l1-mixed-norm regularization. We utilize localization techniques to obtain the sharp learning rate. The bound is characterized by the d…
metabeta uses neural networks to speed up Bayesian mixed-effects regression.
problem Bayesian mixed-effects regression is computationally expensive.
method metabeta is a neural network model that pre-trains to estimate posterior distributions.
result metabeta achieves comparable performance to MCMC at a fraction of the time.
Joint sparsity offers powerful structural cues for feature selection, especially for variables that are expected to demonstrate a "grouped" behavior. Such behavior is commonly modeled via group-lasso, multitask lasso, and related methods where feature selection is effected via mixed-norms. Several mixed-norm based spar…
Improved VI method for deep mixed models in finance.
problem Inaccurate and slow variational inference in high dimensions.
method Natural gradient hybrid VI method targeting joint posterior.
result Natural gradient method is faster and more accurate than existing methods.
New clustering algorithm for mixed data improves applicability and efficiency.
problem Clustering large, mixed data with improved accuracy and efficiency.
method Developed a new clustering algorithm using peak-finding technique, reducing computational complexity.
result Algorithm detects outliers, clusters of lower density, and determines correct number of clusters.
Observations consisting of measurements on relationships for pairs of objects arise in many settings, such as protein interaction and gene regulatory networks, collections of author-recipient email, and social networks. Analyzing such data with probabilisic models can be delicate because the simple exchangeability assu…
Study on bandits with fading memory, improving regret bounds.
problem Stochastic multi-armed bandit problem with dependent samples.
method Developed a $\cC-$Mix Improved UCB algorithm and analyzed regret bounds in two scenarios.
result Regret bounds similar to independent case in slow mixing scenario, with an additive term.
Improved Metropolized HMC mixing time with multi-step gradients.
problem Improving the efficiency of sampling from complex probability distributions.
method Analyzing Metropolized HMC with multi-step integrators and applying sharpening techniques.
result Non-asymptotic upper bound on mixing time for Metropolized HMC with explicit step-size and leapfrog steps.
UncertaintyPlayground simplifies uncertainty estimation in Python.
problem Uncertainty estimation in supervised learning tasks.
method Sparse and Variational Gaussian Process Regressions for normally distributed outcomes, Mixed Density Networks for mixed distributions.
result Fast and simplified uncertainty estimation through Python library.
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.
The study examines mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression.
problem Investigating convergence properties of data-augmentation samplers for Bayesian probit regression.
method Using recent results on Gibbs samplers for log-concave targets, the study provides non-asymptotic bounds on mixing times.
result Explicit non-asymptotic bounds on mixing times depend on design matrix and prior precision, holding uniformly over responses.
Method completes mixed matrix from complex surveys with heterogeneous missingness.
problem Recovering a mixed dataframe matrix from complex survey sampling with different missingness patterns.
method Two-stage procedure: logistic regression for missingness modeling, and weighted log-likelihood maximization with low-rank constraint.
result The proposed method achieves sublinear convergence and shows superior performance compared to existing methods.
uHMC achieves fast mixing in high dimensions with gradient evaluations.
problem Quantifying mixing time of uHMC in high dimensions.
method Construction of successful couplings for uHMC.
result uHMC mixes in total variation with logarithmic dependence on dimension.
Study fast learning rates for square loss in dependent data with hypercontractivity condition.
problem Learning from dependent data with fast rates matching independent data.
method Martingale difference noise, trajectory hypercontractivity condition, least-squares estimator.
result Excess risk bound matches iid rate after burn-in time, independent of mixing-time.
A scalable Bayesian inference method for mixed-effects models in systems biology.
problem Scalable Bayesian inference for complex hierarchical mixed-effects models in systems biology.
method Constructing amortized approximations of likelihood and posterior distributions, refined for each individual dataset.
result Our method is both fast and competitive in statistical accuracy compared to exact pseudomarginal Bayesian inference.
In this paper, we study the nonnegative matrix factorization problem under the separability assumption (that is, there exists a cone spanned by a small subset of the columns of the input nonnegative data matrix containing all columns), which is equivalent to the hyperspectral unmixing problem under the linear mixing mo…
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.
Novel ML approach solves complex warehouse routing problem.
problem Efficiently routing pickers in mixed-shelves warehouses.
method Hierarchical and parallel multi-agent reinforcement learning.
result State-of-the-art performance in solution quality and inference speed.
Outlier detection amounts to finding data points that differ significantly from the norm. Classic outlier detection methods are largely designed for single data type such as continuous or discrete. However, real world data is increasingly heterogeneous, where a data point can have both discrete and continuous attribute…
We propose and analyze two new MCMC sampling algorithms, the Vaidya walk and the John walk, for generating samples from the uniform distribution over a polytope. Both random walks are sampling algorithms derived from interior point methods. The former is based on volumetric-logarithmic barrier introduced by Vaidya wher…
A new portfolio optimization model minimizes maximum drawdown, offering faster and more robust solutions.
problem Optimizing portfolios during financial distress, especially during crises.
method Linearization of Markowitz model based on maximum drawdown, with a Mixed-Integer Linear Programming variation.
result 200 times faster solving time with a more profitable and robust solution.
Analysis of reactive-diffusion simulations requires a large number of independent model runs. For each high-fidelity simulation, inputs are varied and the predicted mixing behavior is represented by changes in species concentration. It is then required to discern how the model inputs impact the mixing process. This tas…
Machine learning models accurately predict the state and dynamics of reactive mixing.
problem Accurate prediction of reactive mixing for Earth and environmental science applications.
method Built a high-fidelity numerical model to simulate reactive mixing scenarios. Used 20 different machine learning emulators to classify mixing state and predict three QoIs.
result Ensemble methods and MLP models accurately predict the state of reactive mixing and QoIs, significantly faster than high-fidelity simulations.
Langevin Dynamics speeds up mixing time with manifold hypothesis and multi-scale approach.
problem Langevin Dynamics struggles in high dimensions and nonconvex landscapes.
method Utilizes manifold hypothesis to reduce mixing time and employs multi-scale approach to improve image generation quality.
result Mixing time depends on intrinsic dimension rather than ambient dimension, significantly reducing computational complexity.
We develop an HMC algorithm to easily marginalize random effects in LMMs.
problem Bayesian inference in LMMs is challenging, especially marginalizing random effects.
method Developed an HMC algorithm to marginalize random effects in LMMs efficiently.
result Marginalization is always beneficial when applicable and improves various models, especially cognitive science models.
dcFCI discovers causal relationships robustly under latent confounding and mixed data.
problem Causal discovery under latent confounding and unfaithfulness.
method dcFCI integrates a new score to assess PAG compatibility, guided by FCI search.
result Significantly outperforms state-of-the-art methods in small and heterogeneous datasets.
Efficiently calibrates Bergomi models to VIX derivatives using vector quantization.
problem Calibrating Bergomi models to VIX derivatives for accurate pricing.
method Applied vector quantization in mixed Bergomi models for fast and efficient option pricing.
result Calibration of Bergomi models to VIX derivatives is feasible and accurate over daily data.
Given data over the joint distribution of two random variables and , we consider the problem of inferring the most likely causal direction between and . In particular, we consider the general case where both and may be univariate or multivariate, and of the same or mixed data types. We take an inf…
Hybrid method improves sampling from multimodal distributions.
problem Sampling from multimodal posterior distributions efficiently.
method Jump-Diffusion Langevin Dynamics hybrid with Metropolis.
result Calibrated hybrid method outperforms pure methods.
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…
We prove new fast learning rates for the one-vs-all multiclass plug-in classifiers trained either from exponentially strongly mixing data or from data generated by a converging drifting distribution. These are two typical scenarios where training data are not iid. The learning rates are obtained under a multiclass vers…
Given a linear regression setting, Iterative Least Trimmed Squares (ILTS) involves alternating between (a) selecting the subset of samples with lowest current loss, and (b) re-fitting the linear model only on that subset. Both steps are very fast and simple. In this paper we analyze ILTS in the setting of mixed linear …
Efficient Monte Carlo and greedy heuristic for the inference of stochastic block modelsphysics.data-an
We present an efficient algorithm for the inference of stochastic block models in large networks. The algorithm can be used as an optimized Markov chain Monte Carlo (MCMC) method, with a fast mixing time and a much reduced susceptibility to getting trapped in metastable states, or as a greedy agglomerative heuristic, w…
Linear mixed models (LMMs) are used extensively to model dependecies of observations in linear regression and are used extensively in many application areas. Parameter estimation for LMMs can be computationally prohibitive on big data. State-of-the-art learning algorithms require computational complexity which depends …