Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory

• URL: http://arxiv.org/abs/2102.11822v1
• Date: Tue, 23 Feb 2021 17:48:39 GMT
• Title: Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory
• Authors: Navid Reyhanian, Jarvis Haupt
• Abstract summary: We show that if the unknown weight matrices describing the system are in Brunovsky canonical form, we can efficiently estimate the ground truth unknown of the system. Specifically, by deriving concrete bounds, we show that SGD converges linearly in expectation to any arbitrary small Frobenius norm distance from the ground truth weights.
• Score: 1.52292571922932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work investigates the problem of estimating the weight matrices of a stable time-invariant linear dynamical system from a single sequence of noisy measurements. We show that if the unknown weight matrices describing the system are in Brunovsky canonical form, we can efficiently estimate the ground truth unknown matrices of the system from a linear system of equations formulated based on the transfer function of the system, using both online and offline stochastic gradient descent (SGD) methods. Specifically, by deriving concrete complexity bounds, we show that SGD converges linearly in expectation to any arbitrary small Frobenius norm distance from the ground truth weights. To the best of our knowledge, ours is the first work to establish linear convergence characteristics for online and offline gradient-based iterative methods for weight matrix estimation in linear dynamical systems from a single trajectory. Extensive numerical tests verify that the performance of the proposed methods is consistent with our theory, and show their superior performance relative to existing state of the art methods.

Related papers

• Quantum Algorithms for Nonlinear Dynamics: Revisiting Carleman Linearization with No Dissipative Conditions [0.7373617024876725]
  We explore the embedding of nonlinear dynamical systems into linear ordinary differential equations (ODEs) via the Carleman linearization method. Our analysis extends these findings by exploring error bounds beyond the traditional dissipative condition. We prove how this resonance condition leads to a linear convergence with respect to the truncation level $N$ in Carleman linearization.
  arXiv  Detail & Related papers  (2024-05-21T12:09:34Z)
• Learning Linearized Models from Nonlinear Systems with Finite Data [1.6026317505839445]
  We consider the problem of identifying a linearized model when the true underlying dynamics is nonlinear. We provide a multiple trajectories-based deterministic data acquisition algorithm followed by a regularized least squares algorithm. Our error bound demonstrates a trade-off between the error due to nonlinearity and the error due to noise, and shows that one can learn the linearized dynamics with arbitrarily small error.
  arXiv  Detail & Related papers  (2023-09-15T22:58:03Z)
• A New Approach to Learning Linear Dynamical Systems [19.47235707806519]
  We provide the first time algorithm for learning a linear dynamical system from a length trajectory up to error in the system parameters. Our algorithm is built on a method of moments estimator to directly estimate parameters from which the dynamics can be extracted.
  arXiv  Detail & Related papers  (2023-01-23T16:07:57Z)
• Generalized Quadratic Embeddings for Nonlinear Dynamics using Deep Learning [11.339982217541822]
  We present a data-driven methodology for modeling the dynamics of nonlinear systems. In this work, we propose using quadratic systems as the common structure, inspired by the lifting principle.
  arXiv  Detail & Related papers  (2022-11-01T10:03:34Z)
• 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)
• A Priori Denoising Strategies for Sparse Identification of Nonlinear Dynamical Systems: A Comparative Study [68.8204255655161]
  We investigate and compare the performance of several local and global smoothing techniques to a priori denoise the state measurements. We show that, in general, global methods, which use the entire measurement data set, outperform local methods, which employ a neighboring data subset around a local point.
  arXiv  Detail & Related papers  (2022-01-29T23:31:25Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Supervised DKRC with Images for Offline System Identification [77.34726150561087]
  Modern dynamical systems are becoming increasingly non-linear and complex. There is a need for a framework to model these systems in a compact and comprehensive representation for prediction and control. Our approach learns these basis functions using a supervised learning approach.
  arXiv  Detail & Related papers  (2021-09-06T04:39:06Z)
• Fluctuation-dissipation Type Theorem in Stochastic Linear Learning [2.8292841621378844]
  The fluctuation-dissipation theorem (FDT) is a simple yet powerful consequence of the first-order differential equation governing the dynamics of systems subject simultaneously to dissipative and forces. The linear learning dynamics, in which the input vector maps to the output vector by a linear matrix whose elements are the subject of learning, has a verify version closely mimicking the Langevin dynamics when a full-batch gradient descent scheme is replaced by that of gradient descent. We derive a generalized verify for the linear learning dynamics and its validity among the well-known machine learning data sets such as MNIST, CIFAR-10 and
  arXiv  Detail & Related papers  (2021-06-04T02:54:26Z)
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms [74.17312533172291]
  We describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding) We then explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation)
  arXiv  Detail & Related papers  (2020-12-12T00:01:10Z)
• Active Learning for Nonlinear System Identification with Guarantees [102.43355665393067]
  We study a class of nonlinear dynamical systems whose state transitions depend linearly on a known feature embedding of state-action pairs. We propose an active learning approach that achieves this by repeating three steps: trajectory planning, trajectory tracking, and re-estimation of the system from all available data. We show that our method estimates nonlinear dynamical systems at a parametric rate, similar to the statistical rate of standard linear regression.
  arXiv  Detail & Related papers  (2020-06-18T04:54:11Z)

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.