Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

• URL: http://arxiv.org/abs/2604.00179v1
• Date: Tue, 31 Mar 2026 19:30:36 GMT
• Title: Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation
• Abstract summary: We study the finite-time convergence of projected linear two-time-scale approximation with constant step sizes and Polyak-Ruppert averaging.<n>We establish an explicit mean-square error bound, decomposing it into two interpretable components, an approximation error determined by the constrained subspace and a statistical error decaying at a sublinear rate.
• Score: 9.227034835080307
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the finite-time convergence of projected linear two-time-scale stochastic approximation with constant step sizes and Polyak--Ruppert averaging. We establish an explicit mean-square error bound, decomposing it into two interpretable components, an approximation error determined by the constrained subspace and a statistical error decaying at a sublinear rate, with constants expressed through restricted stability margins and a coupling invertibility condition. These constants cleanly separate the effect of subspace choice (approximation errors) from the effect of the averaging horizon (statistical errors). We illustrate our theoretical results through a number of numerical experiments on both synthetic and reinforcement learning problems.

Related papers

• Residual-Based Time Discretization on Nonlinear Approximation Manifolds: Analysis and Gaussian Applications [0.0]
  We study time-discrete parametric approximations of evolution equations in Hilbert spaces based on residual minimization.<n>Two natural residual formulations are considered: discretization followed by parametrization of the evolution equation, and discretization of the Dirac--Frenkel variational principle governing the parameter dynamics.
  arXiv  Detail & Related papers  (2026-07-16T14:57:44Z)
• A Quantitative Approximation Framework for Flow Distillation in Diffusion Models [9.704954388992892]
  Local approximation errors can be strongly amplified in low-noise multimodal regimes.<n>We show that deep residual compositions efficiently approximate the long-horizon transport.<n>Experiments support the prediction and reduce end-to-end relative MSE by up to 51.9% with 8 segments compared with uniform grids.
  arXiv  Detail & Related papers  (2026-06-02T16:00:43Z)
• Statistical Inference on Gradient Flows [46.05870703588429]
  We develop a theory for time-uniform statistical inference on gradient flows arising from empirical risk minimization.<n>We introduce an algorithm-aware covariance estimator that evolves jointly with the gradient flow and avoids matrix inversion, resampling, or sample splitting.<n>Our results connect optimization dynamics with statistical inference and provide practical tools for uncertainty quantification in gradient-based methods.
  arXiv  Detail & Related papers  (2026-05-31T14:22:37Z)
• Extracting quantum field theory dynamics from an approximate ground state [0.0]
  We develop a linear-programming method to extract information from static ground-state correlators in quantum field theory.<n>We test the method on the $1+1$-dimensional $4$ model, using a variational approximation to the vacuum.<n>The resulting mass gaps agree with renormalized Hamiltonian truncation and Borel-resummed perturbation theory.
  arXiv  Detail & Related papers  (2025-12-22T17:25:24Z)
• Dimension-free error estimate for diffusion model and optimal scheduling [22.20348860913421]
  Diffusion generative models have emerged as powerful tools for producing synthetic data from an empirically observed distribution.<n>Previous analyses have quantified the error between the generated and the true data distributions in terms of Wasserstein distance or Kullback-Leibler divergence.<n>In this work, we derive an explicit, dimension-free bound on the discrepancy between the generated and the true data distributions.
  arXiv  Detail & Related papers  (2025-12-01T15:58:20Z)
• Generative Modeling with Continuous Flows: Sample Complexity of Flow Matching [60.37045080890305]
  We provide the first analysis of the sample complexity for flow-matching based generative models.<n>We decompose the velocity field estimation error into neural-network approximation error, statistical error due to the finite sample size, and optimization error due to the finite number of optimization steps for estimating the velocity field.
  arXiv  Detail & Related papers  (2025-12-01T05:14:25Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence [6.160559095588513]
  We show that the Lyapunov function exhibits convergence rates in both cases.<n>If the state noise parameters fully approach their limiting value, the Lyapunov function achieves an exponential convergence rate.
  arXiv  Detail & Related papers  (2025-09-14T02:06:15Z)
• Finite-Time Analysis of Discrete-Time Stochastic Interpolants [32.27430900126022]
  We present the first discrete-time analysis of the interpolant framework, where we derive a finite-time upper bound on its distribution estimation error.<n>Our result provides a novel way to design efficient schedules for convergence acceleration.
  arXiv  Detail & Related papers  (2025-02-13T10:07:35Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [55.80276145563105]
  We investigate the statistical properties of Temporal Difference learning with Polyak-Ruppert averaging.<n>We make three theoretical contributions that improve upon the current state-of-the-art results.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.<n>Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
  arXiv  Detail & Related papers  (2023-12-22T18:01:11Z)
• Learning Discretized Neural Networks under Ricci Flow [48.47315844022283]
  We study Discretized Neural Networks (DNNs) composed of low-precision weights and activations.<n>DNNs suffer from either infinite or zero gradients due to the non-differentiable discrete function during training.
  arXiv  Detail & Related papers  (2023-02-07T10:51:53Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)

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.