Linear Systems can be Hard to Learn
- URL: http://arxiv.org/abs/2104.01120v1
- Date: Fri, 2 Apr 2021 15:58:30 GMT
- Title: Linear Systems can be Hard to Learn
- Authors: Anastasios Tsiamis and George J. Pappas
- Abstract summary: Statistically easy to learn linear system classes have sample complexity that is with the system dimension.
Statistically hard to learn linear system classes have worst-case sample complexity that is at least exponential with the system dimension.
- Score: 12.834033463883085
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we investigate when system identification is statistically
easy or hard, in the finite sample regime. Statistically easy to learn linear
system classes have sample complexity that is polynomial with the system
dimension. Most prior research in the finite sample regime falls in this
category, focusing on systems that are directly excited by process noise.
Statistically hard to learn linear system classes have worst-case sample
complexity that is at least exponential with the system dimension, regardless
of the identification algorithm. Using tools from minimax theory, we show that
classes of linear systems can be hard to learn. Such classes include, for
example, under-actuated or under-excited systems with weak coupling among the
states. Having classified some systems as easy or hard to learn, a natural
question arises as to what system properties fundamentally affect the hardness
of system identifiability. Towards this direction, we characterize how the
controllability index of linear systems affects the sample complexity of
identification. More specifically, we show that the sample complexity of
robustly controllable linear systems is upper bounded by an exponential
function of the controllability index. This implies that identification is easy
for classes of linear systems with small controllability index and potentially
hard if the controllability index is large. Our analysis is based on recent
statistical tools for finite sample analysis of system identification as well
as a novel lower bound that relates controllability index with the least
singular value of the controllability Gramian.
Related papers
- A least-square method for non-asymptotic identification in linear switching control [17.938732931331064]
It is known that the underlying partially-observed linear dynamical system lies within a finite collection of known candidate models.
We characterize the finite-time sample complexity of this problem by leveraging recent advances in the non-asymptotic analysis of linear least-square methods.
We propose a data-driven switching strategy that identifies the unknown parameters of the underlying system.
arXiv Detail & Related papers (2024-04-11T20:55:38Z) - On the Hardness of Learning to Stabilize Linear Systems [4.962316236417777]
We study the statistical hardness of learning to stabilize linear time-invariant systems.
We present a class of systems that can be easy to identify, thanks to a non-degenerate noise process.
We tie this result to the hardness of co-stabilizability for this class of systems using ideas from robust control.
arXiv Detail & Related papers (2023-11-18T19:34:56Z) - 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 to Control Linear Systems can be Hard [19.034920102339573]
We study the statistical difficulty of learning to control linear systems.
We prove that learning complexity can be at most exponential with the controllability index, that is the degree of underactuation.
arXiv Detail & Related papers (2022-05-27T15:07:30Z) - Sparsity in Partially Controllable Linear Systems [56.142264865866636]
We study partially controllable linear dynamical systems specified by an underlying sparsity pattern.
Our results characterize those state variables which are irrelevant for optimal control.
arXiv Detail & Related papers (2021-10-12T16:41:47Z) - 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) - Controlling nonlinear dynamical systems into arbitrary states using
machine learning [77.34726150561087]
We propose a novel and fully data driven control scheme which relies on machine learning (ML)
Exploiting recently developed ML-based prediction capabilities of complex systems, we demonstrate that nonlinear systems can be forced to stay in arbitrary dynamical target states coming from any initial state.
Having this highly flexible control scheme with little demands on the amount of required data on hand, we briefly discuss possible applications that range from engineering to medicine.
arXiv Detail & Related papers (2021-02-23T16:58:26Z) - Theoretical Insights Into Multiclass Classification: A High-dimensional
Asymptotic View [82.80085730891126]
We provide the first modernally precise analysis of linear multiclass classification.
Our analysis reveals that the classification accuracy is highly distribution-dependent.
The insights gained may pave the way for a precise understanding of other classification algorithms.
arXiv Detail & Related papers (2020-11-16T05:17:29Z) - Learning Partially Observed Linear Dynamical Systems from Logarithmic
Number of Samples [4.7464518249313805]
We study the problem of learning partially observed linear dynamical systems from a single sample trajectory.
Our result significantly improves the sample complexity of learning partially observed linear dynamical systems.
arXiv Detail & Related papers (2020-10-08T14:23:48Z) - 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.