Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer

• URL: http://arxiv.org/abs/2601.01502v1
• Date: Sun, 04 Jan 2026 12:05:48 GMT
• Title: Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer
• Authors: Milind Nakul, Tianjiao Li, Ashwin Pananjady,
• Abstract summary: We introduce the Multiscale Experience Replay (MER) algorithm for solving a class of variational inequalities (VIs)<n>Rather than uniformly sampling from the buffer, MER utilizes a multi-scale sampling scheme to emulate the behavior of VI algorithms designed for independent and identically distributed samples.
• Score: 10.836971562948042
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the Multiscale Experience Replay (MER) algorithm for solving a class of stochastic variational inequalities (VIs) in settings where samples are generated from a Markov chain and we have access to a memory buffer to store them. Rather than uniformly sampling from the buffer, MER utilizes a multi-scale sampling scheme to emulate the behavior of VI algorithms designed for independent and identically distributed samples, overcoming bias in the de facto serial scheme and thereby accelerating convergence. Notably, unlike standard sample-skipping variants of serial algorithms, MER is robust in that it achieves this acceleration in iteration complexity whenever possible, and without requiring knowledge of the mixing time of the Markov chain. We also discuss applications of MER, particularly in policy evaluation with temporal difference learning and in training generalized linear models with dependent data.

Related papers

• Self-Rewarding Sequential Monte Carlo for Masked Diffusion Language Models [58.946955321428845]
  This work presents self-rewarding sequential Monte Carlo (SMC)<n>Our algorithm stems from the observation that most existing MDLMs rely on a confidence-based sampling strategy.<n>We introduce the trajectory-level confidence as a self-rewarding signal for assigning particle importance weights.
  arXiv  Detail & Related papers  (2026-02-02T09:21:45Z)
• An Elementary Approach to Scheduling in Generative Diffusion Models [55.171367482496755]
  An elementary approach to characterizing the impact of noise scheduling and time discretization in generative diffusion models is developed.<n> Experiments across different datasets and pretrained models demonstrate that the time discretization strategy selected by our approach consistently outperforms baseline and search-based strategies.
  arXiv  Detail & Related papers  (2026-01-20T05:06:26Z)
• InvarDiff: Cross-Scale Invariance Caching for Accelerated Diffusion Models [2.6735992385049663]
  InvarDiff is a training-free acceleration method that exploits the relative temporal invariance across timestep-scale and layer-scale.<n> Experiments show that InvarDiff achieves $2$-$3times$ end-to-end speed-ups with minimal impact on standard quality metrics.
  arXiv  Detail & Related papers  (2025-11-29T02:34:23Z)
• LSCD: Lomb-Scargle Conditioned Diffusion for Time series Imputation [55.800319453296886]
  Time series with missing or irregularly sampled data are a persistent challenge in machine learning.<n>We introduce a different Lombiable--Scargle layer that enables a reliable computation of the power spectrum of irregularly sampled data.
  arXiv  Detail & Related papers  (2025-06-20T14:48:42Z)
• Stochastic-Constrained Stochastic Optimization with Markovian Data [2.1756081703276]
  We study the setting where data samples are drawn from a Markov chain and thus are not independent and identically distributed. We propose two variants of drift-plus-penalty; one is for the case when the mixing time of the underlying Markov chain is known. Our algorithms apply to a more general setting of constrained online convex optimization where the sequence of constraint functions follows a Markov chain.
  arXiv  Detail & Related papers  (2023-12-07T14:09:27Z)
• Compatible Transformer for Irregularly Sampled Multivariate Time Series [75.79309862085303]
  We propose a transformer-based encoder to achieve comprehensive temporal-interaction feature learning for each individual sample. We conduct extensive experiments on 3 real-world datasets and validate that the proposed CoFormer significantly and consistently outperforms existing methods.
  arXiv  Detail & Related papers  (2023-10-17T06:29:09Z)
• Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models [61.10851158749843]
  Key insights can be obtained by discovering lead-lag relationships inherent in the data. We develop a clustering-driven methodology for robust detection of lead-lag relationships in lagged multi-factor models.
  arXiv  Detail & Related papers  (2023-05-11T10:30:35Z)
• Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity [8.732260277121547]
  We develop sample complexity bounds for the estimator and establish conditions for minimaxity. We show that achieving a particular statistical risk bound involves a subtle and interesting trade-off between the strength of the mixing properties and the number of samples.
  arXiv  Detail & Related papers  (2022-11-14T03:39:59Z)
• A fast asynchronous MCMC sampler for sparse Bayesian inference [10.535140830570256]
  We propose a very fast approximate Markov Chain Monte Carlo (MCMC) sampling framework that is applicable to a large class of sparse Bayesian inference problems. We show that in high-dimensional linear regression problems, the Markov chain generated by the proposed algorithm admits an invariant distribution that recovers correctly the main signal.
  arXiv  Detail & Related papers  (2021-08-14T02:20:49Z)
• Bayesian Inference in High-Dimensional Time-Serieswith the Orthogonal Stochastic Linear Mixing Model [2.7909426811685893]
  Many modern time-series datasets contain large numbers of output response variables sampled for prolonged periods of time. In this paper, we propose a new Markov chain Monte Carlo framework for the analysis of diverse, large-scale time-series datasets.
  arXiv  Detail & Related papers  (2021-06-25T01:12:54Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Targeted stochastic gradient Markov chain Monte Carlo for hidden Markov models with rare latent states [48.705095800341944]
  Markov chain Monte Carlo (MCMC) algorithms for hidden Markov models often rely on the forward-backward sampler. This makes them computationally slow as the length of the time series increases, motivating the development of sub-sampling-based approaches. We propose a targeted sub-sampling approach that over-samples observations corresponding to rare latent states when calculating the gradient of parameters associated with them.
  arXiv  Detail & Related papers  (2018-10-31T17:44:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.