We study the stochastic multi-armed bandit problem in the case when the arm samples are dependent over time and generated from so-called weak $\cC$-mixing processes. We establish a $\cC-$Mix Improved UCB agorithm and provide both problem-dependent and independent regret analysis in two different scenarios. In the first…
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 “Slow Mixing”
The Gibbs sampler is a particularly popular Markov chain used for learning and inference problems in Graphical Models (GMs). These tasks are computationally intractable in general, and the Gibbs sampler often suffers from slow mixing. In this paper, we study the Swendsen-Wang dynamics which is a more sophisticated Mark…
In this paper we address the following question: Can we approximately sample from a Bayesian posterior distribution if we are only allowed to touch a small mini-batch of data-items for every sample we generate?. An algorithm based on the Langevin equation with stochastic gradients (SGLD) was previously proposed to solv…
Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributionsstat.CO
New bounds for SMC show its advantage over MCMC in multimodal distributions.
problem Estimating expectations under multimodal distributions with slow global mixing.
method Proves finite sample complexities for SMC with local mixing times, addressing bias through sequential resampling.
result SMC provides fully polynomial time approximation for multimodal problems.
Systematic assessment of the quality of fit of the stochastic block model for empirical networksphysics.soc-ph
The stochastic block model accurately describes most empirical networks but struggles with large diameter and slow-mixing networks.
problem Assessing the quality of fit of the stochastic block model for empirical networks.
method Posterior predictive model checking using network descriptors.
result The stochastic block model can accurately describe most empirical networks but struggles with large diameter and slow-mixing networks.
The paper tackles long-context linear system identification with improved sample complexity bounds.
problem Identifying dynamical systems with long dependencies over fixed context windows.
method Established sample complexity bounds for systems with linear dependencies over a context window of length p.
result The learning process is not hindered by slow mixing properties in extended context windows.
Lower bound on BART's mixing time increases with data points.
problem Slow mixing time in BART's MCMC chains.
method Simplified BART with a single tree and reduced MCMC moves.
result Mixing time grows exponentially with data points.
Scalable Krylov Subspace Methods for Generalized Mixed-Effects Models with Crossed Random Effectsstat.ME
New Krylov subspace methods speed up mixed-effects models with crossed random effects.
problem Slow computations for high-dimensional crossed random effects in mixed-effects models.
method Krylov subspace-based methods for generalized mixed-effects models with cross effects.
result Speedups by factors of up to 10,000 in computations for mixed-effects models.
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.
Improved lower bound for parallel tempering's mixing time.
problem Slow convergence and mixing in multimodal target distributions.
method Presented a new lower bound for the spectral gap of parallel tempering.
result Improved the best existing bound on spectral gap with polynomial dependence on parameters.
Efficiently samples multimodal distributions using data-based initialization.
problem Sampling multimodal distributions with limited samples.
method Data-based initialization for Markov chains with spectral gap.
result Efficiently generates samples close to stationary distribution.
A new framework for sparse regression models with slow variations.
problem Parameter estimation for sparse regression models with slow variations.
method Formulated as a mixed-integer optimization problem, then reformulated as a binary convex optimization problem with a novel relaxation technique.
result Efficiently solves the problem to provable optimality using a cutting plane-type algorithm.
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.
Reflective Hamiltonian Monte Carlo struggles with high-dimensional sampling.
problem Slow mixing in reflective Hamiltonian Monte Carlo with inexact reflections.
method Quantifying instantaneous non-uniformity with Sinkhorn divergence; analyzing particle motion in spheres and cubes; constructing low-dimensional toy models.
result Particles spontaneously unmix, leading to resonances in particle density.
We introduce Deep Reasoning Networks (DRNets), an end-to-end framework that combines deep learning with reasoning for solving complex tasks, typically in an unsupervised or weakly-supervised setting. DRNets exploit problem structure and prior knowledge by tightly combining logic and constraint reasoning with stochastic…
Bayesian nonparametric (BNP) models provide elegant methods for discovering underlying latent features within a data set, but inference in such models can be slow. We exploit the fact that completely random measures, which commonly used models like the Dirichlet process and the beta-Bernoulli process can be expressed a…
Paper proposes new density estimators for high-dimensional data.
problem Prohibitive computational cost and slow convergence rate in high-dimensional density estimation.
method Adaptive hyperbolic cross density estimators in mixed smooth Sobolev spaces.
result Proposed estimators do not suffer curse of dimensionality under Integral Probability Metrics.
A hybrid algorithm combines optimization and enumeration for symbolic regression.
problem Finding any function from a set of operators without prior specification.
method Mixed-integer nonlinear optimization with explicit enumeration and constraints.
result The hybrid algorithm is competitive with state-of-the-art methods.
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.
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.
Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the netwo…
Develops variational inference for Neyman-Scott processes for faster sampling.
problem Slow mixing time in MCMC for posterior sampling in Neyman-Scott processes.
method Variational inference algorithm for Neyman-Scott processes, minimizing KL divergence.
result Achieves better prediction performance than MCMC with limited computational time.
2D-PT improves sampling in constrained optimization problems.
problem Sampling Boltzmann distributions with soft constraints.
method Two-dimensional extension of parallel tempering.
result 2D-PT achieves near-ideal mixing in constrained problems.
Adaptive stopping in MCMC using classifier-based dynamics
problem Sampling from complex, unnormalized probability densities
method Training state-dependent neural classifiers
result Significant reduction in average trajectory lengths
On Cyclical MCMC Samplingstat.CO
Cyclical MCMC tackles high-dimensional multimodal distributions, showing convergence under certain conditions.
problem High-dimensional multimodal posterior distributions in deep learning.
method Cyclical MCMC framework that tracks tempered versions of the target distribution over time.
result Cyclical MCMC converges to the target distribution under fast mixing kernels but fails in slow mixing cases.
Despite their exceptional flexibility and popularity, the Monte Carlo methods often suffer from slow mixing times for challenging statistical physics problems. We present a general strategy to overcome this difficulty by adopting ideas and techniques from the machine learning community. We fit the unnormalized probabil…
Unbiased gradient estimation for Markov chains
problem Estimating gradients of stationary means in Markov chains
method Propose new unbiased estimators
result Improves efficiency for slow mixing Markov chains
Indian Buffet Process based models are an elegant way for discovering underlying features within a data set, but inference in such models can be slow. Inferring underlying features using Markov chain Monte Carlo either relies on an uncollapsed representation, which leads to poor mixing, or on a collapsed representation…
This work interprets SFA through variational inference, relaxing linearity constraints.
problem Recover non-linear SFA from variational inference.
method Probabilistic interpretation of SFA through variational inference, relaxing linearity constraints.
result Reinterprets SFA as a variational framework, allowing slowness as a regularizer to reconstruction loss.
Decision trees are flexible models that are well suited for many statistical regression problems. In a Bayesian framework for regression trees, Markov Chain Monte Carlo (MCMC) search algorithms are required to generate samples of tree models according to their posterior probabilities. The critical component of such an …
We introduce Mix&Match (M&M) - a training framework designed to facilitate rapid and effective learning in RL agents, especially those that would be too slow or too challenging to train otherwise. The key innovation is a procedure that allows us to automatically form a curriculum over agents. Through such a curriculum …
Optimal crypto asset routing with CFMMs, including fixed costs.
problem Optimizing order execution on a network of CFMMs with fixed costs.
method Convex optimization for no fixed costs, mixed-integer convex for fixed costs, heuristics for approximate solutions.
result Approximate solutions to optimal routing and arbitrage certification problems.
Spectral deconfounding improves machine learning models by reducing hidden confounding effects.
problem Machine learning models can be misled by hidden confounders, leading to unreliable predictions.
method Develops a nonlinear spectral deconfounding framework for gradient boosting that modifies boosting dynamics to slow down in confounding-aligned directions.
result Spectrally deconfounded boosting improves estimation of the target function under hidden confounding and is more scalable.
During this last decades, several attempts to construct slow invariant manifold of the Lorenz-Krishnamurthy five-mode model of slow-fast interactions in the atmosphere have been made by various authors. Unfortunately, as in the case of many two-time scales singularly perturbed dynamical systems the various asymptotic p…
Travel time tomography with adaptive dictionariesphysics.geo-ph
We develop a 2D travel time tomography method which regularizes the inversion by modeling groups of slowness pixels from discrete slowness maps, called patches, as sparse linear combinations of atoms from a dictionary. We propose to use dictionary learning during the inversion to adapt dictionaries to specific slowness…
Method learns dynamics of slow variables from stochastic data.
problem Modeling unknown multiscale stochastic systems with limited data.
method Data-driven approach to learn effective dynamics from bursts of observation data.
result Generative model accurately captures effective dynamics of slow variables.
We propose Power Slow Feature Analysis, a gradient-based method to extract temporally slow features from a high-dimensional input stream that varies on a faster time-scale, as a variant of Slow Feature Analysis (SFA) that allows end-to-end training of arbitrary differentiable architectures and thereby significantly ext…
Split-Merge MCMC (Monte Carlo Markov Chain) is one of the essential and popular variants of MCMC for problems when an MCMC state consists of an unknown number of components. It is well known that state-of-the-art methods for split-merge MCMC do not scale well. Strategies for rapid mixing requires smart and informative …
The paper simplifies multi-agent RL dynamics in finite-state Markov games using homogenization.
problem Approximating complex multi-agent reinforcement learning dynamics in finite-state Markov games.
method Rescaling learning process by reducing learning rate and increasing update frequency, proving convergence to an ODE.
result The rescaled process converges to an ODE that approximates the agent's learning dynamics.
Time-lagged autoencoders (TAEs) have been proposed as a deep learning regression-based approach to the discovery of slow modes in dynamical systems. However, a rigorous analysis of nonlinear TAEs remains lacking. In this work, we discuss the capabilities and limitations of TAEs through both theoretical and numerical an…
Some model reduction techniques for multiple time-scale dynamical systems make use of the identification of low dimensional slow invariant attracting manifolds (SIAM) in order to reduce the dimensionality of the phase space by restriction to the slow flow. The focus of this work is on a proposition and discussion of a …
We provide a rigorous numerical computation method to validate periodic, homoclinic and heteroclinic orbits as the continuation of singular limit orbits for the fast-slow system with one-dimensional slow variable . Our validation procedure is based on topological tools called isolatin…
A new AI optimization method uses energy-conserving dynamics inspired by Born-Infeld theory.
problem Optimization challenges in non-convex loss functions and machine learning tasks.
method Discretization of Born-Infeld dynamics for energy-conserving Hamiltonian optimization.
result The method avoids high local minima and outperforms traditional methods in shallow valleys.
In Deep Learning, a well-known approach for training a Deep Neural Network starts by training a generative Deep Belief Network model, typically using Contrastive Divergence (CD), then fine-tuning the weights using backpropagation or other discriminative techniques. However, the generative training can be time-consuming…
Derives a biologically plausible neural network for Slow Feature Analysis.
problem Learning latent features from time series data.
method Starting from an SFA objective, derives Bio-SFA with a biologically plausible neural network implementation.
result Validates Bio-SFA on naturalistic stimuli, reproducing interesting properties of brain cells.
As an important Markov Chain Monte Carlo (MCMC) method, stochastic gradient Langevin dynamics (SGLD) algorithm has achieved great success in Bayesian learning and posterior sampling. However, SGLD typically suffers from slow convergence rate due to its large variance caused by the stochastic gradient. In order to allev…
Paper introduces slow kill for efficient large-scale variable screening.
problem Challenges in variable selection and parameter estimation for big data.
method Nonconvex constrained optimization, adaptive \(\ell_2\)-shrinkage, and increasing learning rates.
result Slow kill outperforms state-of-the-art algorithms in various situations.
The problem of sequential probability forecasting is considered in the most general setting: a model set C is given, and it is required to predict as well as possible if any of the measures (environments) in C is chosen to generate the data. No assumptions whatsoever are made on the model class C, in particular, no ind…