Identification of Analytic Nonlinear Dynamical Systems with Non-asymptotic Guarantees

Summary

This paper studies the problem of identifying an observable stochastic nonlinear dynamical system, in case the transition function is linearly parametrized and the noise is additive. The authors assume that the feature functions are analytic, and both the inputs and the noises are i.i.d., bounded, semi-continuous and have nonvanishing variances in each coordinate direction. It is also assumed that the system is locally input-to-state stable. Two kinds of estimation methods are studied: the classical least-squares estimate (LSE), which provides point estimates, and a set membership method, which provides region estimates. Finite sample bounds for the performance of LSE are proved, based on a block-martingale-small-ball condition, for both the open-loop and the close-loop cases. The sample complexity of the set membership method is studied under an additional assumption (tight bound on disturbance) and only for open-loop (i.i.d.) inputs. Finally, the authors present some numerical evaluations of LSE and set membership methods on pendulum and quadrotor examples to empirically illustrate their convergence rates.

Strengths

- The presentation is clear, the paper is well-structured, the need assumptions are precisely stated. - The LSE are widely used, and the set membership approach is also reasonable and practically relevant. - Sample complexity analysis of system identification methods for nonlinear systems is an important problem. On the other hand, it is more relevant for control theory than to machine learning. - Finite sample error bounds are provided for both methods under the assumption that the features are analytic. This approach seems original and could be interesting for the community. - The examples illustrate well the theoretical viability of the analytic features assumption.

Weaknesses

- Many of the assumptions are restrictive, such as bounded noises and inputs. Moreover, the inputs should also be i.i.d. (or should have an additive i.i.d. exploration noise, for the closed-loop case) which is unrealistic. - The error bounds contain terms which are unknown in practice, such as s_\phi. - Corollary 1: the controller for the closed-loop case also contains an additive noise term that satisfies the assumptions for the open-loop inputs, and the system with the controller satisfies the stability assumption, in which case the statement becomes a simple consequence of Theorem 1. A case without additional noises on the inputs would have been much more interesting. - The figures do not show the actual bounds deducted by the paper, they only illustrate the empirical performance of LSE and set membership identification, which is a bit pointless, as they are classical, well-studied methods. I understand that the bounds of the paper are theoretical in nature, so they are conservative and mostly just give the convergence rate, still showing them (for example, on a logarithmic scale) would have been informative. - The title could be misleading, as the word "analytic" should refer to the feature vectors, but in the current title the term "analytic system identification" could also be understood in a way that the obtained solution is analytic.

Questions

- What is the intuitive meaning of Assumption 5 (tight bound on disturbance)? This should be explained in the paper.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

There is a section dedicated to the limitations of the work, which is a good thing. On the other hand, this section did not mention some key limitations, such as bounded noises, bounded and i.i.d. inputs, as well was fully observable states.

Summary

The manuscript provides theoretical guarantees for nonlinear system identification using non-active i.i.d. noises, extending from linear systems to linearly parametrized nonlinear systems with analytic feature functions. The findings demonstrate that non-active i.i.d. noises are capable of efficiently learning these systems with a non-asymptotic convergence rate.

Strengths

Training data selection is a crucial factor in ensuring the generalizability and robustness of identification algorithms. This is particularly important to linearly parametrized nonlinear systems, as there is still a theoretical gap regarding the effectiveness of non-active i.i.d. noise exploration. The study is well-motivated and has great potential for practical application. The authors establish conditions on noise that guarantee probabilistic persistent excitation for nonlinear dynamical systems, as defined by the BMSB condition. The findings in this study provide theoretical support for designing training data and identifying nonlinear systems.

Weaknesses

Although the authors present an interesting idea, the manuscript could be improved by addressing the following concerns: 1. It is suggested to discuss the potential limitations of the non-asymptotic convergence rate in practical applications. 2. The analysis of the numerical experiments lacks depth. Could the authors further explore the convergence characteristics and the advantages and disadvantages of using i.i.d. noise for excitation? 3. The proof sketches could benefit from additional clarifications to enhance readability. For example, in line 234, the meaning of $\delta$ and $\bar{b}_\phi$ could be re-mentioned.

Questions

Can the authors please clarify the implications of the assumptions regarding bounded noises in more practical scenarios? It would be highly beneficial to delve deeper into the impact of these theoretical assumptions on real-world applications.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

It is recommended to further explore the potential limitations of this theoretical guarantees in practical applications. For instance, whether non-asymptotic convergence implies reduced data collection efficiency for some high-dimensional systems, and whether it is still preferable to actively design experiments in certain scenarios.

Summary

The authors study the problem of system identification from a trajectory generated by an unknown linearly parametrized nonlinear system whose nonlinearity is an analytic function. Specifically, they theoretically analyze to estimators: the least squares estimator, and the set membership estimator. Both estimators, while being widely used in practice, do not have theoretical guarantees in many of the settings in which they are applied. The authors give such guarantees, and also conduct numerical experiments on certain nonlinear systems.

Strengths

The authors provide non asymptotic theoretical guarantees for common system identification estimators in settings more broad than those covered by existing theoretical results. As far as I can tell the results are new and the argumentation is sound. They also conduct experiments which verify that such estimators converge to the true system parameters in practice.

Weaknesses

While the theoretical arguments presented seem sound, I am not sure that the extension of system identification results to the case of linearly parametrized smooth nonlinear systems is sufficiently significant from a theoreitcal perspective.

Questions

If instead of assuming that the nonlinearity is analytic, one assumed directly that there does not exist an open set on which it vanishes identically, would the proof carry through?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors adequately adress the limitations of their work.

Summary

The authors extend the work of Simchowitz et al. (2018) [linear] and Sattar et al. (2022) [bi-linear] to linear in the parameters but analytic nonlinear features showing that PE of inputs still results in PE of the states which for general nonlinear systems is not true. From this result LSE results like those originally in Simchowitz et al. (2018) are recovered for this new class of systems and SME results like those in Li et al. (2023a) are recovered for this broader class of systems.

Strengths

- originality: original part is recognizing that analytics functions are only bad in finite number of spots and are otherwise "nice" functions - quality: yes rigorous math - clarity: well written - significance: greatly extends the original results to a much larger class of systems

Weaknesses

- the biggest weakness of the paper is that very little time is spent on the analysis in the main text. yes their is a proof sketch for the main theorem, but it would be nice to get more intuition from the main text.

Questions

- I would much prefer the simulations in the appendix and the inclusion of the entirety of the proof of the main theorem in the main text with clear exposition of how the properties of analytic functions can be exploited to prove PE of u results in PE of x for these systems. This paper is not as bad as others where the main text is only an advertisement of the main result, but it would be a much tighter and more useful paper if this was done. This reviewer may be an outlier though as it seems the trend in these conferences is to do just the opposite of what I have suggested.

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

limitations are discussed

Author-reviewer discussion

Dear reviewers, Thank you for your insightful feedback during the initial review. Kindly ensure that you review the author's rebuttal and, if necessary, engage in scientific conversation with them (the discussion period ends on Aug 13th). If the authors have satisfactorily addressed your concerns, please consider adjusting your scores. This is also an opportune moment to review feedback from other reviewers. Even if you find that your score remains unaltered, I would appreciate it if you could acknowledge reviewing the author's responses. Once again, I truly appreciate your time and attention. Best regards, Area Chair

Official Comment by Reviewer wxwx

Thank you for the detailed responses and the additional simulation. The responses have addressed most of my concerns. I believe my initial rating still reflects my overall assessment, so I will leave it as is.