Learning Networked Linear Dynamical Systems under Non-white Excitation from a Single Trajectory

• URL: http://arxiv.org/abs/2110.00852v1
• Date: Sat, 2 Oct 2021 17:33:16 GMT
• Title: Learning Networked Linear Dynamical Systems under Non-white Excitation from a Single Trajectory
• Authors: Harish Doddi, Deepjyoti Deka, Saurav Talukdar and Murti Salapaka
• Abstract summary: We study the problem of learning the underlying graph of interactions/dependencies from observations of the nodal trajectories over a time-interval $T$. We present a regularized non-casual consistent estimator for this problem and analyze its sample complexity over two regimes.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a networked linear dynamical system with $p$ agents/nodes. We study the problem of learning the underlying graph of interactions/dependencies from observations of the nodal trajectories over a time-interval $T$. We present a regularized non-casual consistent estimator for this problem and analyze its sample complexity over two regimes: (a) where the interval $T$ consists of $n$ i.i.d. observation windows of length $T/n$ (restart and record), and (b) where $T$ is one continuous observation window (consecutive). Using the theory of $M$-estimators, we show that the estimator recovers the underlying interactions, in either regime, in a time-interval that is logarithmic in the system size $p$. To the best of our knowledge, this is the first work to analyze the sample complexity of learning linear dynamical systems driven by unobserved not-white wide-sense stationary (WSS) inputs.

Related papers

• The Optimization Landscape of SGD Across the Feature Learning Strength [102.1353410293931]
  We study the effect of scaling $gamma$ across a variety of models and datasets in the online training setting. We find that optimal online performance is often found at large $gamma$. Our findings indicate that analytical study of the large-$gamma$ limit may yield useful insights into the dynamics of representation learning in performant models.
  arXiv  Detail & Related papers  (2024-10-06T22:30:14Z)
• Joint Learning of Linear Dynamical Systems under Smoothness Constraints [5.2395896768723045]
  We consider the problem of joint learning of multiple linear dynamical systems. In particular, we show conditions under which the mean-squared error bounds on the mean-squared error (MSE) converges to zero as $m$ increases.
  arXiv  Detail & Related papers  (2024-06-03T08:29:42Z)
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks [69.38572074372392]
  We present the first results proving that feature learning occurs during training with a nonlinear model on multiple tasks. Our key insight is that multi-task pretraining induces a pseudo-contrastive loss that favors representations that align points that typically have the same label across tasks.
  arXiv  Detail & Related papers  (2023-07-13T16:39:08Z)
• 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)
• Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems [45.17023170054112]
  We consider the setting of vector valued non-linear dynamical systems $X_t+1 = phi(A* X_t) + eta_t$, where $eta_t$ is unbiased noise and $phi : mathbbR to mathbbR$ is a known link function that satisfies certain em expansivity property.
  arXiv  Detail & Related papers  (2021-05-24T22:14:26Z)
• Improved rates for prediction and identification of partially observed linear dynamical systems [4.68299658663016]
  Identification of a linear time-in dynamical system from partial observations is a fundamental problem in control theory. We propose an algorithm that learns such systems with non-asymptotic statistical rates depending on the inherentity $d$ of the system. Our algorithm is based on multi-scale low-rank approximation SVD applied to Hankel matrices of increasing sizes.
  arXiv  Detail & Related papers  (2020-11-19T18:04:18Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  We introduce algorithms for learning nonlinear dynamical systems of the form $x_t+1=sigma(Thetastarx_t)+varepsilon_t$. We give an algorithm that recovers the weight matrix $Thetastar$ from a single trajectory with optimal sample complexity and linear running time.
  arXiv  Detail & Related papers  (2020-04-30T10:42:48Z)
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems [34.394552166070746]
  We study gradient based algorithms to learn the system dynamics $theta$ from samples obtained from a single finite trajectory. Unlike existing work, our bounds are noise sensitive which allows for learning ground-truth dynamics with high accuracy and small sample complexity.
  arXiv  Detail & Related papers  (2020-02-20T02:36:44Z)

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.