Temporal Robustness in Discrete Time Linear Dynamical Systems

• URL: http://arxiv.org/abs/2505.02347v2
• Date: Wed, 21 May 2025 20:54:47 GMT
• Title: Temporal Robustness in Discrete Time Linear Dynamical Systems
• Authors: Nilava Metya, Arunesh Sinha,
• Abstract summary: In some problems, there is uncertainty about the time horizon for which the system runs.<n>This creates uncertainty about the cost (or reward) incurred based on the state distribution when the system stops.<n>We show an equivalence between a discrete time Markov Chain on a probability simplex and a global stable (GAS) discrete time linear dynamical system.
• Score: 13.291758569446348
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Discrete time linear dynamical systems, including Markov chains, have found many applications. However, in some problems, there is uncertainty about the time horizon for which the system runs. This creates uncertainty about the cost (or reward) incurred based on the state distribution when the system stops. Given past data samples of how long a system ran, we propose to theoretically analyze a distributional robust cost estimation task in a Wasserstein ambiguity set, instead of learning a probability distribution from a few samples. Towards this, we show an equivalence between a discrete time Markov Chain on a probability simplex and a global asymptotic stable (GAS) discrete time linear dynamical system, allowing us to base our study on a GAS system only. Then, we provide various polynomial time algorithms and hardness results for different cases in our theoretical study, including a fundamental result about Wasserstein distance based polytope.

Related papers

• Flow-Based Non-stationary Temporal Regime Causal Structure Learning [49.77103348208835]
  We introduce FANTOM, a unified framework for causal discovery.<n>It handles non stationary processes along with non Gaussian and heteroscedastic noises.<n>It simultaneously infers the number of regimes and their corresponding indices and learns each regime's Directed Acyclic Graph.
  arXiv  Detail & Related papers  (2025-06-20T15:12:43Z)
• Learning Controlled Stochastic Differential Equations [61.82896036131116]
  This work proposes a novel method for estimating both drift and diffusion coefficients of continuous, multidimensional, nonlinear controlled differential equations with non-uniform diffusion. We provide strong theoretical guarantees, including finite-sample bounds for (L2), (Linfty), and risk metrics, with learning rates adaptive to coefficients' regularity. Our method is available as an open-source Python library.
  arXiv  Detail & Related papers  (2024-11-04T11:09:58Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework.<n>We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points.<n>Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Exact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Sparse Disturbances or Semi-Oblivious Attacks [16.705631360131886]
  We study the problem of learning a nonlinear dynamical system by parameterizing its dynamics using basis functions.<n>We show that finite-time exact recovery is achieved with high probability, even when $p$ approaches 1.
  arXiv  Detail & Related papers  (2024-08-30T22:12:57Z)
• Graph Spatiotemporal Process for Multivariate Time Series Anomaly Detection with Missing Values [67.76168547245237]
  We introduce a novel framework called GST-Pro, which utilizes a graphtemporal process and anomaly scorer to detect anomalies. Our experimental results show that the GST-Pro method can effectively detect anomalies in time series data and outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-01-11T10:10:16Z)
• Robust Independence Tests with Finite Sample Guarantees for Synchronous Stochastic Linear Systems [0.0]
  The paper introduces robust independence tests with non-asymptotically guaranteed significance levels for linear time-invariant systems. Our method provides bounds for the type I error probabilities that are distribution-free, i.e., the innovations can have arbitrary distributions.
  arXiv  Detail & Related papers  (2023-08-03T21:13:34Z)
• Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution [44.99833362998488]
  We analyze the accuracy and sample complexity of variational Monte Carlo approaches to simulate quantum systems classically. We prove that the most used scheme, the time-dependent Variational Monte Carlo (tVMC), is affected by a systematic statistical bias. We show that a different scheme based on the solution of an optimization problem at each time step is free from such problems.
  arXiv  Detail & Related papers  (2023-05-23T17:38:10Z)
• Kernel-based Joint Independence Tests for Multivariate Stationary and Non-stationary Time Series [0.6749750044497732]
  We introduce kernel-based statistical tests of joint independence in multivariate time series. We show how the method robustly uncovers significant higher-order dependencies in synthetic examples. Our method can aid in uncovering high-order interactions in data.
  arXiv  Detail & Related papers  (2023-05-15T10:38:24Z)
• Identifiability and Asymptotics in Learning Homogeneous Linear ODE Systems from Discrete Observations [114.17826109037048]
  Ordinary Differential Equations (ODEs) have recently gained a lot of attention in machine learning. theoretical aspects, e.g., identifiability and properties of statistical estimation are still obscure. This paper derives a sufficient condition for the identifiability of homogeneous linear ODE systems from a sequence of equally-spaced error-free observations sampled from a single trajectory.
  arXiv  Detail & Related papers  (2022-10-12T06:46:38Z)
• Learning the Dynamics of Autonomous Linear Systems From Multiple Trajectories [2.2268031040603447]
  Existing results on learning rate and consistency of autonomous linear system identification rely on observations of steady state behaviors from a single long trajectory. We consider the scenario of learning system dynamics based on multiple short trajectories, where there are no easily observed steady state behaviors. We show that one can adjust the length of the trajectories to achieve a learning rate of $mathcalO(sqrtfraclogNN)$ for strictly stable systems and a learning rate of $mathcalO(frac(logN)dsqr
  arXiv  Detail & Related papers  (2022-03-24T01:29:53Z)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  We consider causal discovery in continuous-time for the study of dynamical systems. We propose a causal discovery algorithm based on penalized Neural ODEs.
  arXiv  Detail & Related papers  (2021-05-06T08:48:02Z)
• Data-driven learning of non-autonomous systems [4.459185142332526]
  We present a numerical framework for recovering unknown non-autonomous dynamical systems with time-dependent inputs. To circumvent the difficulty presented by the non-autonomous nature of the system, our method transforms the solution state into piecewise of the system over a discrete set of time instances.
  arXiv  Detail & Related papers  (2020-06-02T15:33:23Z)

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.