Robust System Identification: Finite-sample Guarantees and Connection to Regularization

Authors: Hyuk Park, Grani A. Hanasusanto, Yingying Li
Primary area: learning on time series and dynamical systems
Keywords: dynamical system, time series, system identification, optimization

Abstract:
We consider the problem of learning nonlinear dynamical systems from a single sample trajectory. While the least squares estimate (LSE) is commonly used for this task, it suffers from poor identification errors when the sample size is small or the model fails to capture the system's true dynamics. To overcome these limitations, we propose a robust LSE framework, which incorporates robust optimization techniques, and prove that it is equivalent to regularizing LSE using general Schatten $p$-norms. We provide non-asymptotic performance guarantees for linear systems, achieving an error rate of $\widetilde{\mathcal{O}}(1/\sqrt{T})$, and show that it avoids the curse of dimensionality, unlike state-of-the-art Wasserstein robust optimization models. Empirical results demonstrate substantial improvements in real-world system identification and online control tasks, outperforming existing methods.

Decision: accept (poster)
Reviewer scores: 5, 8, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730186966815

thread_type:
official_review

<thread_object>
creator: reviewer_px9e

<content>
summary:
This paper introduces a robust least squares estimation (LSE) framework that combines robust optimization with the LSE approach to learn nonlinear dynamical systems from a single sample trajectory, demonstrating its equivalence to regularizing LSE with a general Schatten 
p-norm. For the linear case, the authors provide non-asymptotic performance guarantees of the framework under certain conditions and show that the error rate is invariant to system dimensionality.

strengths:
The authors propose a robust LSE framework to learn nonlinear dynamical systems and demonstrate its equivalence to the LSE problem regularized by the Schatten p-norm. They also provide theoretical performance guarantees for the framework applied to linear dynamical systems under certain conditions。

weaknesses:
While the paper considers nonlinear dynamical systems, the theoretical results on convergence are limited to linear cases. Additionally, the paper lacks comparisons with other classical methods, such as LSE regularization with special cases of the Schatten 
p-norms mentioned in line 54 and the Wasserstein robust optimization discussed in line 59.

questions:
1. In line 162, the authors state that they can express the true LSE problem by substituting $\hat\Omega_T$ in equation 3 with its expectation. Is there any literature to support this? What do you mean by "the true LSE problem"? In my opinion, it is more reasonable to obtain the true LSE problem by substituting $x$ and $\phi$ in equation 2 with their expectation. 
2. How do the authors prove that the optimal solution to equation 5 is $\theta^*$?
3. The proposed robust LSE framework is closely related to the Schatten p-norm. Hence, what is the value of p in your experiments? In particular, it is necessary to show the performance of the robust LSE across different norms.
4. In Sections 5.1 and 5.2, the authors only compare the proposed method with the LSE. Comparisons with other classical methods are highly recommended, such as LSE regularization with special cases of the Schatten p-norms mentioned in line 54 and the Wasserstein robust optimization discussed in line 59.
5. It seems that the definition of $\Sigma_\omega$  in equation 9 is missing.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730588109870

thread_type:
official_review

<thread_object>
creator: reviewer_x6xt

<content>
summary:
1. An equivalent SDP formulation for robust LSE with Schatten p-norm regularization 
2. finite-sample guarantees for system identification with single trajectory

strengths:
1. very nice and solid theory
2. provide theoretical guarantees for a hard system identification problem

weaknesses:
1. Is single trajectory a common case in real applications, although it might be an interesting theoretic topic? Could you please provide more motivate examples? Online control of linear system might be one, however the existing works most focus on learning a controller directly rather than following the conventional pipeline (i.e. system identification and then model-based control). What is the advantage of conventional pipeline in the low data region?
2. The authors claim that unlike the SOTA Wasserstein robust optimization, their approach can avoid the curse of dimensionality. However, no comparison study w.r.t. the SOTA method is provided in the paper. And the examples are of very low dimension. The largest linear model is in Sec. 5.2 with $\theta \in \mathbb{R}^{5\times 10}$.
3. Very strong theory but very weak experiments. Most of them are either synthetic or low-dimension datasets. 
4. The results in Sec.4 rely on strong assumptions. For example, if the application is online control or wind prediction, then A2 and A6 do not hold.

questions:
1. Due to the setup (perfect state measurement and known model $\phi$), Thm. 1 holds with no significant difference for linear and nonlinear $\phi$. What if the case where only $y_t=x_t+v_t$ is available or $\phi$ has some uncertainty? For simplicity, we can assume that $\phi$ is linear.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730677363236

thread_type:
official_review

<thread_object>
creator: reviewer_jzsq

<content>
summary:
The authors study the problem of identifying non-linear system dynamics from a single trajectory. They introduces a robust framework for system identification and reveal the connection to regularized empirical risk minimization. They provide non-asymptotic guarantees for linear systems and demonstrate an improved error rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$, which the authors claim avoids the curse of dimensionality faced by other robust methods such as Wasserstein robust optimization. Empirical results validate the effectiveness of robust LSE in system identification and online control tasks.

strengths:
**Clarity of exposition:** The paper is well-written and identifies the limitations of the standard LSE in system identification under limited data or misspecified models, providing motivation for the proposed robust LSE.
    
**Theoretical contribution:** The paper presents non-asymptotic error bounds that establish the effectiveness of Schatten $p$-norm regularization, positioning the method as a theoretically grounded alternative to Wasserstein robust optimization.

**Empirical Validation:** Several numerical experiments are conducted, including tasks in wind speed prediction and online control, with substantial improvements over classical LSE.

weaknesses:
**Discussion of the theoretical results:** The authors very briefly discuss their main results and the implications of the regularization term in their bounds. In particular, it is important to note that $T$ still scales with the system dimensions, i.e., $n+m$ in Theorem 2. It is important to make clear the difference between the curse of dimensionality and the unavailable dependence of the system dimension in the burn-in.

questions:
1) The authors mention the use of different Schatten norms but does not provide insight into the practical or theoretical consequences of varying $p$. Could the authors expand more on this?

2) Could the authors provide more intuitions on the key factors for avoiding the course of dimensionality in their results? The way the error bounds is presented in Theorem 2 it is not clear the benefit of the regularization term.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730697247403

thread_type:
official_review

<thread_object>
creator: reviewer_wdgh

<content>
summary:
In this paper, the authors propose a novel estimator for discrete-time, single-trajectory system-identification via Schatten-norm regularization. The authors claim that the proposed estimator combines the desiderata of rate-optimal guarantees of the standard least-squares estimator and robustness to misspecification a la Wasserstein robustness. The authors support their claims on some numerical experiments, demonstrating that in the presence of misspecification (e.g. from nonlinear dynamics), the proposed estimator has better convergence properties than the standard LSE.

strengths:
The paper is in general well-written and straightforward to understand. The method derivation is quite clean, demonstrating that min-max robust LSE can be turned into an semi-definite program, which can then be reduced further to an unconstrained Schatten-norm-regularized least-squares problem. Something of note is that the proposed SDP only interacts with the trajectory through the empirical Gram matrix, and thus does not need to scale with the length of the trajectory. The theoretical guarantees of the estimator also demonstrate the rate-optimality of the procedure, which is otherwise not true for out-of-the-box guarantees of Wasserstein robust estimators. Numerical experiments demonstrate that not only is the estimator performant compared to LSE, it can be slotted into various online control frameworks to great effect.

I think the paper is good enough for acceptance; I have bumped my score up after the author's response.

weaknesses:
Since the proposed method is a regularized version of the least-squares estimator, it inherently has an additional moving part in the regularization parameter. In theory, for the robustness set to cover the population Gramian with high probability, the regularization parameter is determined by the convergence rate of the empirical Gramian to the population one, and thus can only be as good as the (typically conservative) upper bounds. Therefore, the authors propose as a heuristic to determine the best scaling of the regularization parameter via cross-validation, and demonstrate that this tuned method outperforms LSE by a large relative amount. However, this is somewhat unenlightening, as this is comparing a fine-tuned algorithm to *the* base estimation algorithm (which is technically subsumed by the proposed class of estimators). It would be more informative if the comparison were to a different class of (fine-tuned) robust estimators.

The paper also assumes strict stability. While this is likely for technical reasons in the proof, as the authors follow Jedra and Proutiere's (2020) Hanson-Wright approach, something that is left wanting in this paper is whether proposed estimator also performs better in the face of (near) marginal stability, since the authors point out in Section 5.2 that the estimator actually performs relatively better in the very-stable regime. In the same vein, it would be more enlightening to see stabilization rate of synthesized controllers from the estimated matrices $\hat A, \hat B$ as a function of data, e.g. via certainty-equivalent LQR, as this is a more practical notion of estimator robustness.

The paper also contains a few confusing parts. Most notably, the uncertainty level $\epsilon(\delta)$ in (11) is set with minimal details on the parameters therein. Since this quantity shows up in the error bound in Theorem 2, it would be good to at least show the valid upper bound on $\epsilon(\delta)$ derived in the appendix, since the main paper suggests $\epsilon(\delta) = \tilde{\mathcal O}(1/\sqrt{T})$ is the quantity up to universal constants, while in reality it contains some (rather important) system-dependent quantities.

**Minor comments**
- Should provide mathematical definition of subgaussianity in the assumptions.

- Should define what $\|\nabla_\theta \|\mathbf A(\theta^\star)\|_q\|$ is in (12). Also, this seems to differ from the quantity in the appendix proof (42).

Jedra and Proutiere, "Finite-time Identification of Stable Linear Systems Optimality of the Least-Squares Estimator", 2020.

questions:
Please see the above Weaknesses section for areas to clarify.

Also, it would be good to expand on the comparison to the DRO literature. Notably, why is (Gao, 2023) not applicable to even the iid version of this least-squares problem? For example, if we instead pretend to draw each point of the trajectory from its marginal distribution and apply a beta-mixing blocking argument, would (Gao, 2023) be applicable to the independent process?

Rui Gao, "Finite-sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionality", 2023.

Kuznetsov and Mohri, "Generalization bounds for non-stationary mixing processes", 2016.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730820538583

thread_type:
official_review

<thread_object>
creator: reviewer_q1qq

<content>
summary:
Building on recent work by authors such as Simchowitz, Jedra and others, this paper
studies system identification for linear systems in the one trajectory setup,
showing that a regularized form of least-squares estimation (LSE)---with the
regularization being a Schatten $p$-norm---has favorable nonasymptotic convergence,
and (empirically) outperforms unregularized LSE on some standard benchmarks.

strengths:
The problem is a significant one, and the theoretical results presented by the authors are nicely executed and nicely presented.

weaknesses:
Clearly it's appropriate to regularize least-squares estimators in settings in
which there isn't much data, and for matrix estimands a standard matrix norm such
as the Schatten $p$-norm is a natural choice.  This would have seemed to be a
reasonable starting place for the paper.  But, instead of just starting with this
(statistical) perspective, the current paper starts with a robust optimization
(minimax) perspective.  In the authors' words, "seeking the best system parameter
against the worst-case realizations of the data."  But the latter motivation is
rather different from the motivation of small data sets, and it's a bit odd to
start with robustness if the focus is small samples.

The authors do show that the minimax perspective yields the Schatten $p$-norm
regularization.  Perhaps this is just a matter of taste, but this sequence of
logic doesn't make much conceptual sense to me.

A robustness perspective would seem to make sense if the issue is one of misspecification,
and indeed the authors state that "it [the LSE] suffers from poor identification
errors when the sample size is small or the model fails to capture the system's true
dynamics."  It's the latter statement that seems well aligned with the robustness
motivation.  But the paper doesn't seem to follow up on this issue, either theoretically
or empirically (e.g., by considering misspecification).

With respect to the theoretical results, they are indeed very nicely executed and presented,
but I'm not sure how much novelty there is.  My sense is that this is a redeployment of tools
from the papers of Simchowitz, Jedra and others; I'd be happy to stand corrected if that's not the case.

questions:
My main question is regarding the extent to which there is novelty in the proof of the main theorem (Theorem 2).
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces finite-sample guarantees for a robust optimization procedure for estimation in linear dynamical systems. The strengths are
(1) the method givens a clear and concise mathematical analysis of the method, demonstrating consistency
(2) The method demonstrates improvements over standard LSE on low data regimes
Weaknesses include
(1) there is no *theoretical justification* for the improvements of robust LSE over the standard LSE. Consequently, all benefits are purely empirical. 
(2) given that the benefits are purely empirical, more experimentation would be preferrable. 
(3) one of the reviewers noted that the authors do not extend their findings to misspecified models, which is one of the motivations for robustness.

Ultimately, this paper crosses the acceptance threshold, but its limitations preclude nomination from any special designation.