Exact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Adversarial Attacks

Authors: Haixiang Zhang, Baturalp Yalcin, Javad Lavaei, Eduardo Sontag
Primary area: learning on time series and dynamical systems
Keywords: System identification, robust control, exact recovery

Abstract:
In this work, we study the system identification problem for parameterized nonlinear systems using basis functions under adversarial attacks. Motivated by the LASSO-type estimators, we analyze the exact recovery property of a nonsmooth estimator, which is generated by solving an embedded $\ell_1$-loss minimization problem. First, we derive necessary and sufficient conditions for the well-specifiedness of the estimator and the uniqueness of global solutions to the underlying optimization problem. Next, we provide exact recovery guarantees for the estimator under two different scenarios of boundedness and Lipschitz continuity of the basis functions. The non-asymptotic exact recovery is guaranteed with high probability, even when there are more severely corrupted data than clean data. Finally, we numerically illustrate the validity of our theory. This is the first study on the sample complexity analysis of a nonsmooth estimator for the nonlinear system identification problem.

Decision: reject
Reviewer scores: 6, 3, 5, 6

Reviews and discussion:
<thread>
creation date:
1730192084553

thread_type:
official_review

<thread_object>
creator: reviewer_msza

<content>
summary:
This paper analyzes the exact recovery properties of a nonsmooth estimator for nonlinear dynamical system identification problem under adversarial attacks. The authors derive necessary and sufficient conditions for the optimality and uniqueness of the ground truth solution to the formulated problem. Additionally, they provide sample complexity bounds for the exact recovery of model parameters using bounded basis functions and Lipschitz basis functions, respectively.

strengths:
**Originality**

Strengths:
- The paper provides necessary and sufficient conditions for the ground truth to be optimal and unique for the formulated problem. 
- The paper derives sample complexity bounds that ensure these conditions are satisfied with high probability for bounded basis functions and Lipschitz basis functions under certain assumptions.
- The paper for the first time studies the sample complexity analysis of a nonsmooth estimator for the nonlinear system identification problem.

**Quality**

Strengths:
- The results of numerical experiments are consistent with the theoretical analysis. 
- The formulated problem can be solved using the CVX solver.

**Clarity**

Strengths:
- The paper is generally well-written and easy to follow. Key technical concepts are explained clearly.

**Significance**

Strengths:
- Nonlinear dynamical system identification is an important problem for the areas of sequential decision-making, reinforcement
learning and control theory. Hence, deriving sample complexity bounds  for the exact recovery of bounded basis functions and Lipschitz basis functions are noteworthy.

weaknesses:
1. The simulation problems are relatively small-scale.
2. Some of the mathematical notation and concepts may be difficult to follow.

questions:
1. Some notations are confusing. For example, what is the definition of $\theta()$ in line 280 and $\theta[]$ in Equation (3)? Additionally, how is the matrix in equation 12 constructed?
2. I did not understand the proof of Corollary 3. Could the authors explain it more clearly?
3. Generally, the noise level can affect the accuracy of identification results. Therefore, I suggest that the authors show the identification results under different noise levels.
4. What are the basis functions used in the experiment?
5. In many cases, $A$ has a sparse topology. Empirically, solving problem 2 cannot accurately learn sparse $A$, particularly under high noise levels. However, the theoretical analysis does not depend on the topology of $A$. Hence, could the authors conduct the experiments with a sparse $A$ and explain the corresponding results?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730404106383

thread_type:
official_review

<thread_object>
creator: reviewer_hkkd

<content>
summary:
The paper investigates the system identification problem for nonlinear, parameterized systems under adversarial attacks, where for time steps $t=1,...,T$ one observes $x_{t+1} = \bar{A} f(x_t) + {\bar{d_t}}$, with $f$ a known, possibly nonlinear function, $\bar{A}$ the unknown "system dynamics" matrix, and $\bar{d_t}$ the unknown "disturbance" vector, which is adversarially chosen. The class of estimators considered are of the form $\hat{A} = \{argmin} \sum_{t=1}^T \|x_{t+1} - A f(x_t)\|_2$. The nonlinear functions studied in specificity are the class of bounded functions and Lipschitz functions. The paper establishes rigorous theoretical results for exact recovery in nonlinear system identification under adversarial attacks, providing necessary and sufficient conditions for both global optimality and uniqueness of solutions and gives sample complexity upper- and lower-bounds. The authors provide numerical experiments that support the theoretical results.

strengths:
The presentation is overall strong. The paper is well-written and the results are easy to follow, barring the overly wooly introduction/literature treatment (see weaknesses). I think the setting is interesting. The paper is well-structured and the results are clearly presented. I especially appreciate the clarity of the proofs, which are well-structured and easy to follow.

weaknesses:
*Unclear and ambiguous writing in the introduction and lack of coherent literature overview*: The abstract and introduction lack clarity in conveying the actual problem studied, making it difficult for readers to grasp the work's focus early on. The initial (long) paragraphs and literature overview are somewhat vague, imprecise and seem to contribute little to the understanding of the work. Additionally, the literature review extends into the appendix, but it would be more cohesive if integrated into the introduction. This would allow the authors to eliminate ambiguous sections while simultaneously introducing the problem and discussing prior research on different versions of it, providing readers with a clearer understanding the paper’s contributions. Overall, I would like to see more comparison of the estimator studied by the authors with the LSE estimator. The author's contribution becomes difficult to judge because of the lack of context provided.

*In the stochastic adversarial noise case, the authors seem to make some seemingly very strong assumptions on $\hat{d}_t$*. The authors say about Assumption 2 (Stealthy condition) that "If an attack is not stealth, the operator can quickly detect and nullify it". Can the authors formally explain how this would work, and what "quickly" means in this context? Similarly, I am not convinced that the zero-mean, sub-Gaussianity assumption on the disturbance makes sense in this context. In what sense is the disturbance still adversarial in this case? The authors should provide a comparison with the case where $\hat{d}_t$ is just sub-Gaussian observational noise.

questions:
Could the authors comment more on the gaps between Theorem 3 and 4? Particularly in terms of its implications for practical applications? For instance, are there cases where the current bounds could be tightened, or would further assumptions (e.g., regarding the nature of the adversarial noise) be required to bridge this gap? Additionally, are there insights on whether this gap reflects fundamental limitations or merely theoretical conservatism, based on the simulation findings?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730571636893

thread_type:
official_review

<thread_object>
creator: reviewer_vty1

<content>
summary:
This paper studies the problem of learning the dynamical system x_{t+1} = Af(x_t) + d_t where A is unknown, f is known, and d_t is adversarial but often 0 (from a single trajectory). The main results study the estimator argmin_{A'} sum_t ||x_{t+1} - A'f(x_t)|| in two settings:
1) f is bounded; the times when d_t is nonzero are i.i.d. with some probability p; there is some non-degeneracy in the directions of the adversarial noise; and the direction of the adversarial noise is mean-0. Under these assumptions, it's shown that with a poly(dimension, condition number, 1 / p(1-p)) length trajectory, the above estimator has a unique optimum at A. A matching lower bound is also shown.
2) f is Lipschitz; same non-degeneracy condition as above; the adversarial noise has mean-0 direction and is sub-Gaussian; and the system is stable. Again under these assumptions a similar upper bound on the length of the needed trajectory is shown.

strengths:
Learning non-linear dynamical systems is an interesting problem. The paper is written clearly.

weaknesses:
For a paper that purports to study an adversarial-noise setting, the assumptions seem absurdly strong.
- Why should the direction of the adversarial noise be mean-0? The paper gives some justification that otherwise it wouldn't be "stealth" and that the operator could detect and nullify such noise, but this is not at all clear to me. How would d_t be detected if it were not mean 0? We only see one trajectory. How are the mentioned references related? I did not see a comparable assumption in those works. Also, why mean-zero direction instead of unnormalized mean-zero?
- Why is Assumption 3 reasonable (that the attacks have non-degenerate directions)? 

In some ways it seems that the goal of unique recovery of A is far too strong. Presumably it would be more reasonable to ask to learn any equivalent dynamics?
- This might get rid of the non-degeneracy assumption
- Also, the main results **get worse as the fraction of adversarially-affected time-steps decreases**. This is completely absurd and suggests that the problem should be set up differently.

Finally, all of the results and lower bounds are specific to the proposed autoregressive least squares estimator. Could there be a better estimator? This paper does not seem to address that question.

questions:
See above
</content>
</thread_object>

</thread>
<thread>
creation date:
1731245607180

thread_type:
official_review

<thread_object>
creator: reviewer_chm8

<content>
summary:
The paper studies a (nonlinear) system identification problem. The authors prove necessary and sufficient conditions for optimality in the general case (when the data is corrupted by an adaptive adversary, assuming that not all the samples are corrupted), and study a random version of the problem, when the corruptions are zero or nonzero independently from each other.

strengths:
The problem seems to be much more general than the version studied before in literature (e.g. [Yalcin et al. (2023)] or [Feng & Lavaei (2021)]). This generalization looks interesting and non-trivial to me, and the results are strong.

weaknesses:
I didn't find major weaknesses, but since the results are on a generalization of the (liner version of the) problem that was studied before, I would like to see a more detailed comparison with the analysis from prior work. While the authors provided some insights on pages 2 and 4, it is not very clear to me what is the technical contribution of the paper.

questions:
**Typos:** line 696, Farks’s -> Farkas'

**Questions**:

In line 229 you compare your result with [Yalcin et al. (2023)], Figure 1 from their paper. Since your result is theoretical, and you simplify it for large $\Delta$ for this comparison, could you compare it not with the table of values, but with their theoretical guarantees?

Also, your randomized version of the problem looks very similar to linear regression with oblivious adversary (see, for example [1] and [2]), and your Assumption 3 reminds the strong convexity assumption from [2]. Could you please check if the models or their analysis of those papers have any connection to your result? If it is the case, it might be nice since their results were generalized to sparse regression and other problems (see [3], they used the symmetry assumption that is somewhat similar to your stealthy condition), so it might be interesting if there exists a general framework that captures also your problem.

One other question (somewhat related to the previous one): you have a $\log m$ factor in Theorem 3. Do you think it is an artefact of your proof, or do you expect it to be inherent?

[1] Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, Prateek Jain. Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression.

[2] Tommaso d'Orsi, Gleb Novikov, David Steurer. Consistent regression when oblivious outliers overwhelm.

[3] Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer. Higher degree sum-of-squares relaxations robust against oblivious outliers.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732141850097

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Checking In Regarding Rebuttals

comment:
Since the discussion period would end in a week, could you please read our rebuttal and let us know if you have any further concerns or comments? We provided extensive answers to your previous comments and hope to discuss them with you during this discussion period. We appreciate your time and effort.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The reviewers on this paper are rather mixed, with a number of positive and negative points being raised.  However, two reviewers still have non-minor concerns about the justification of the problem formulation and its assumptions.  I tend to agree that these are non-minor.  For example, even in the newly added (blue) text, some important unsubstantiated claims are made like “has been commonly used in real-world systems” and “have appeared in different parts of the world”.  I can also appreciate, for example, the significant concern that "the main results get worse as the fraction of adversarially-affected time-steps decreases", which raises significant doubts on whether this should really be viewed as "adversarial".  The authors gave some explanation and argued that some of these assumptions are needed to obtain the results.  But that is not necessarily a convincing justification, as it can raise broader doubts about the theoretical model itself.