Paper provides exponential convergence guarantees for Iterative Markovian Fitting.
problem Addressing the Schrödinger Bridge problem in computational optimal transport and generative modeling.
method Develops non-asymptotic exponential convergence guarantees for Iterative Markovian Fitting.
result First non-asymptotic exponential convergence guarantees for IMF under mild structural assumptions.
Paper proves convergence of Markovian iteration for FBSDEs with fully coupled drift and Z process.
problem Proving convergence of Markovian iteration for FBSDEs with fully coupled drift and Z process.
method Differentiation-based approach to handle Z process, uniformly controlling Lipschitz continuity of decoupling fields.
result Proves convergence of Markovian iteration method for FBSDEs with fully coupled drift and Z process.
Paper derives convergence rates and confidence intervals for LSA with Markovian noise.
problem Analyzing convergence rates and constructing confidence intervals for LSA with Markovian noise.
method Derives non-asymptotic Berry-Esseen bounds and multiplier block bootstrap procedure.
result Provides O ( n − 1 / 4 ) \mathcal{O}(n^{-1/4}) O ( n − 1/4 ) convergence rates and guarantees consistent inference. Improved algorithm for optimal stopping problems reduces runtime.
problem Optimal stopping problems with infinite time horizon and random discounting.
method Flexible forward improvement iteration with a variable look-ahead distance.
result The new algorithm converges and can significantly reduce runtime.
We analyze SA with Markovian data and nonlinear updates, overcoming prior limitations.
problem Analyzing stochastic approximation with Markovian data and nonlinear updates.
method Fine-grained analysis of SA iterates and Markovian data, leveraging smoothness and recurrence properties.
result Established weak convergence and precise asymptotic bias of SA iterates.
New bounds for SA with arbitrary norm contractions and Markovian noise.
problem Finite-time analysis of two-time-scale stochastic approximation with arbitrary norm contractions and Markovian noise.
method Use of generalized Moreau envelope for arbitrary norm contractions and solutions of Poisson equation for Markovian noise.
result Mean square error decays at rates of O ( 1 / n 2 / 3 ) O(1/n^{2/3}) O ( 1/ n 2/3 ) and O ( 1 / n ) O(1/n) O ( 1/ n ) under different conditions. Study on bias of constant-step stochastic approximation with Markovian noise.
problem Understanding the bias in stochastic approximation algorithms with Markovian noise.
method Infinitesimal generator comparisons to analyze bias, Lyapunov equation for time-averaged bias, Richardson-Romberg extrapolation for bias reduction.
result Bias of the algorithm is of order O ( α ) O(α) O ( α ) and time-averaged bias is α V + O ( α 2 ) αV + O(α^2) α V + O ( α 2 ) , where V V V is a constant. Study on bias and extrapolation in LSA with Markovian data, showing bias reduction with Richardson-Romberg extrapolation.
problem Bias in LSA with constant stepsizes and Markovian data.
method Viewing LSA as a Markov chain, proving convergence and bias expansion, and applying Richardson-Romberg extrapolation.
result Bias is proportional to the stepsize up to higher order terms, and Richardson-Romberg extrapolation reduces the bias.
Paper analyzes LSA algorithm bias and error bounds with RR extrapolation.
problem Analyzing bias and high-order error bounds of LSA with Markovian noise.
method Polyak-Ruppert averaging, linearization, Richardson-Romberg extrapolation.
result RR extrapolation effectively cancels the leading bias term.
Study improves covariance estimation for SGD under Markovian data, matching best rates.
problem Improving covariance estimation for SGD in Markovian data settings.
method Online overlapping batch-means covariance estimator for SGD under Markovian sampling.
result Established convergence rates for covariance estimation under Markovian sampling.
Paper examines constant stepsize in LSA for Markovian data inference.
problem Improving statistical inference with constant stepsize in LSA for Markovian data.
method Established CLT, used averaged LSA iterates, applied Richardson-Romberg extrapolation.
result Constant stepsize leads to better CI coverage, especially with limited data.
Paper analyzes convergence of decentralized algorithms with noise and bias.
problem Finite time convergence analysis of decentralized stochastic approximation schemes.
method Separated iterates into consensual parts and consensus error; bounded consensus error in terms of stationarity.
result Decentralized SA scheme converges at O ( log T / T ) {\cal O}(\log T/ \sqrt{T} ) O ( log T / T ) rate. This work analyzes Q Q Q -learning with adaptive stepsizes for finite-time convergence.
problem Finite-time convergence analysis for average-reward Q Q Q -learning with adaptive stepsizes. method Adaptive stepsizes as local clocks, time-inhomogeneous Markovian reformulation, almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities.
result Convergence rates of i l d e O ( 1 / k ) ilde{\mathcal{O}}(1/k) i l d e O ( 1/ k ) for mean-square and pointwise mean-square convergence. Paper analyzes finite-time performance of SA in RL with Markovian noise.
problem Finite-time analysis of linear two-timescale stochastic approximation with Markovian noise.
method Finite-time analysis of linear two-timescale SA with Markovian noise, considering both transient and steady-state terms.
result No discrepancy in convergence rate between Markovian and martingale noise; transient term is o ( 1 / k c ) o(1/k^c) o ( 1/ k c ) and steady-state term is O ( 1 / k ) {\cal O}(1/k) O ( 1/ k ) . Paper analyzes CLT for TTSA with Markovian noise, broadening its applications.
problem Analyzing asymptotic behavior of TTSA under Markovian noise.
method Central Limit Theorem applied to TTSA with Markovian noise.
result Uncovered coupled dynamics of TTSA influenced by Markov chain.
Study on kinetic Langevin diffusions and their couplings, showing subtle TV bounds and new non-Markovian couplings.
problem Understanding and quantifying the TV distance between solutions of kinetic Langevin diffusions with different initial values.
method Established new non-Markovian couplings for kinetic Langevin diffusions, derived from optimal coalescence trajectories, and analyzed their TV bounds.
result No Markovian coupling can capture the asymptotic decay rate of the TV distance between solutions of kinetic Langevin diffusions with different initial values.
New method solves tree-structured Schrödinger Bridge problems.
problem Computing Schrödinger Bridge between tree-structured distributions.
method Iterative Markovian Fitting (IMF) procedure for tree-structured costs.
result Extends IMF to tree-structured Schrödinger Bridge problems.
Paper analyzes convergence of Adam-type RL algorithms under Markovian sampling.
problem Theoretical convergence analysis of Adam-type RL algorithms.
method Develops techniques for analyzing convergence under Markovian sampling.
result PG-AMSGrad and TD-AMSGrad converge to stationary points or global optima at specified rates.
A new measure predicts deep learning model performance.
problem Predicting the generalization error of deep learning models.
method 2sED measure based on effective dimension, layerwise iterative approximation.
result 2sED correlates well with training error and generalization error.
MER algorithm speeds up VI solving with Markovian data.
problem Solving stochastic variational inequalities with Markovian data.
method MER algorithm using multi-scale sampling from a Markovian buffer.
result Achieves faster convergence without knowing Markov chain mixing time.
This study improves convergence of two-timescale SA under Markovian noise in reinforcement learning.
problem Stability and convergence of two-timescale stochastic approximations under Markovian noise.
method Introduced a new control strategy for the fast timescale parameter.
result Established almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.
Unified framework for solving fixed-point equations in deterministic and stochastic settings.
problem Solving fixed-point equations for seminorm-contractive operators in both deterministic and stochastic contexts.
method Fixed-point theorem and stochastic approximation analysis.
result Unified finite-sample bounds for various reinforcement learning algorithms.
(Working Paper) Using a purely probabilistic argument, we prove the global well-posedness of multidimensional superquadratic backward stochastic differential equations (BSDEs) without Markovian assumption. The key technique is the interplay between the local well-posedness of fully coupled path-dependent forward backwa…
Estimates hybrid dynamical systems with polynomial expansions and Markovian switching.
problem Identifying hybrid dynamical systems with nonlinear autoregressive exogenous (NARX) components and Markovian switching.
method Probabilistic framework using Expectation Maximization for parameter estimation, including submodel coefficients, hidden state values, and transition probabilities. Disentangles mode classification and NARX regression tasks. Uses soft-labels and coordinate descent approach for parameter fitting.
result Demonstrated on a SMNARX problem with three nonlinear sub-models, achieving parsimonious models through l1-norm bridge estimation and hard-thresholding.
This paper improves sample complexity for AC and NAC algorithms under Markovian sampling.
problem Improving sample complexity for actor-critic and natural actor-critic algorithms.
method Characterizes convergence rate and sample complexity under Markovian sampling and mini-batch data.
result Improves sample complexity for AC and NAC algorithms by orders of magnitude.
Paper shows TD learning without projection converges robustly.
problem Investigate convergence of TD learning with linear approx.
method Simple unprojected TD(0) with novel self-bounding property.
result TD(0) converges with rate O ~ ( 1 / T ) \widetilde{\mathcal{O}}(1/\sqrt{T}) O ( 1/ T ) . SRMC framework reduces Monte Carlo variance by history-based sampling in high-dimensional spaces.
problem Efficient sampling in high-dimensional discrete or continuous state spaces.
method Score-Repellent Monte Carlo (SRMC) framework that summarizes history through running average of score evaluations.
result Improves estimator variance and mode coverage with constant memory usage.
In statistical learning theory, generalization error is used to quantify the degree to which a supervised machine learning algorithm may overfit to training data. Recent work [Xu and Raginsky (2017)] has established a bound on the generalization error of empirical risk minimization based on the mutual information $I(S;…
Non-Markovian point process shows power-law scaling, similar to nonlinear Markovian process.
problem Understanding the scaling behavior of non-Markovian point processes.
method Analyzed a confined fractional Brownian motion-driven point process and compared it to a nonlinear Markovian process.
result A nonlinear Markovian process can reproduce the power-law scaling behavior of a non-Markovian point process.
The paper analyzes convergence rates for stochastic approximation and reinforcement learning.
problem Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise.
method A novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the Moreau-envelope smoothing for contractive mappings.
result Almost sure convergence rates for specific learning rates are derived, with rates arbitrarily close to o ( n 1 − 2 η ) o(n^{1 - 2η}) o ( n 1 − 2 η ) and o ( n − 1 ) o(n^{-1}) o ( n − 1 ) . Cyclic and randomized stepsizes can lead to heavier tails in SGD, improving generalization.
problem Understanding when and why cyclic and randomized stepsizes outperform constant stepsize in SGD.
method Examined a general class of Markovian stepsizes, focusing on their tail-index behavior.
result Markovian stepsizes can achieve heavier tails, improving generalization over constant stepsize.
Study optimal and instance-dependent guarantees for solving linear equations with Markovian data.
problem Approximately solving linear fixed point equations with Markovian data.
method Non-asymptotic bounds and instance-dependent characterizations for stochastic approximation.
result Instance-optimality of the averaged SA estimator and matching upper and lower bounds.
Projects Markovian processes from Itô semimartingales with jumps.
problem Modeling Itô semimartingales with jumps using Markovian projections.
method Construct Markovian projections for Itô semimartingales with jumps using non-local FPKEs.
result Markovian projections match the marginal laws of the original process.
We propose a deep neural network-based algorithm to identify the Markovian Nash equilibrium of general large N N N -player stochastic differential games. Following the idea of fictitious play, we recast the N N N -player game into N N N decoupled decision problems (one for each player) and solve them iteratively. The individua…
This paper extends Markovian projections to semimartingales with jumps.
problem Extending Markovian projections to semimartingales with jumps.
method Using Markovian projections to match marginal laws of Itô semimartingales with jumps.
result Existence of Markovian projections for Itô semimartingales with jumps.
This paper solves the inversion problem for jump processes using Markovian projections.
problem Calibrating jump-diffusion models with both local and stochastic features.
method Inverting Markovian projections for pure jump processes.
result Constructs calibrated local stochastic intensity (LSI) models for credit risk applications.
Analyzes non-Markovian environments in stochastic approximation.
problem Understanding learning mechanisms in non-ergodic, non-Markovian settings.
method Analytic framework for transformer learning and continual learning.
result Proposes a new approach to transformer and continual learning.
Paper introduces PRMs to learn non-Markovian stochastic rewards for reinforcement learning.
problem Lack of structured representation for non-Markovian stochastic rewards in reinforcement learning.
method Introduces probabilistic reward machines (PRMs) and presents an algorithm to learn them from decision processes.
result Algorithm proves correct and convergent for learning PRMs from decision processes.
Stochastic differential equation approximation for linear TD(0) under Markovian noise
problem Temporal-difference learning with linear function approximation
method Stochastic differential equation approximation
result Explains the constant-stepsize error floor
This paper proposes DeepSynth, a method for effective training of deep Reinforcement Learning (RL) agents when the reward is sparse and non-Markovian, but at the same time progress towards the reward requires achieving an unknown sequence of high-level objectives. Our method employs a novel algorithm for synthesis of c…
Paper establishes convergence rates and concentration bounds for stochastic approximation and reinforcement learning with Markovian noise.
problem Analyzing convergence rates and concentration bounds for stochastic approximation and reinforcement learning with Markovian noise.
method Novel discretization of the mean ODE of stochastic approximation algorithms using intervals with diminishing length.
result First almost sure convergence rate and maximal concentration bound with exponential tails for contractive stochastic approximation algorithms with Markovian noise.
New RL algorithms correct bias in dynamic data analysis.
problem Dynamic data generation and analysis create endogeneity issues.
method Instrument variable (IV)-based reinforcement learning (RL) algorithms.
result Established theoretical properties of IV-RL algorithms.
Maximal concentration bounds for stochastic approximation with heavy-tailed noise.
problem Analyzing the convergence of stochastic approximation algorithms under heavy-tailed Markovian noise.
method Novel Lyapunov function and black-box truncation argument.
result Tail behavior of the error can be sub-Gaussian, sub-Weibull, or lighter than any Pareto but heavier than any Weibull.
Graph matching in noisy environments with Markovian errors.
problem Graph matching under time-dependent Markovian noise.
method Introduced edgelighter error model and analyzed graph matching thresholds.
result Graph matching thresholds and mixing times are of order Θ ( n 2 log n ) Θ(n^2\log n) Θ ( n 2 log n ) for Erdős-Rényi graphs, and O ( n α log n ) O(n^α\log n) O ( n α log n ) for Stochastic Block Model graphs. Unified analytical tool for non-Markovian jump processes.
problem Analyzing history-dependent jump processes with non-Markovian behavior.
method Developed a standard form of master equations using Laplace-space embedding and asymptotic solution.
result Unified analytical toolset for general non-Markovian processes, leading to the GLE approximation.
Constructs supermartingale couplings with full marginals constraints.
problem Optimal transport for supermartingale couplings with multiple marginals.
method Markovian iteration of one-period optimal supermartingale couplings.
result Explicit construction of supermartingale processes solving optimal transport problem.
New algorithm MTMC reduces MCMC evaluation costs.
problem High-dimensional sampling with intractable posterior evaluations.
method Iteratively updated approximation of posterior distribution for acceptance rate.
result Approximation converges to true posterior as iterations increase.
We develop a Markovian approximation for SVV models to compute hedging strategies.
problem Computing optimal hedging strategies for SVV models with non-Markovian noise.
method Develop a Markovian approximation of the Volterra noise kernel to compute hedging strategies.
result Error estimates for the approximation of volatility, prices, and optimal hedge.