Exact Recovery for System Identification with More Corrupt Data than Clean Data

Overview

• This paper investigates the problem of system identification for linear discrete-time systems under adversarial attacks.
• The authors analyze two lasso-type estimators and examine their asymptotic and non-asymptotic properties under different attack models.
• Since the data samples are correlated, the existing results on lasso do not apply, and the authors provide new theoretical guarantees.
• The paper shows that the sample complexity for exact recovery of the system dynamics is linear in the state dimension when attacks are periodic, and polynomial in the state dimension and attack probability when attacks are stochastic.
• The estimators can still learn the true system dynamics even when more than half the data is compromised by attacks.

Plain English Explanation

This paper looks at the problem of system identification for linear, discrete-time systems when there are adversarial attacks on the data. The researchers analyzed two different types of estimators, called "lasso-type" estimators, to see how well they can recover the true system dynamics in the presence of these attacks.

Normally, the existing results on lasso estimators wouldn't apply here because the data samples are correlated, meaning they're related to each other. But the authors were able to provide new theoretical guarantees on the performance of their estimators.

They considered two different scenarios for the attacks: one where the attacks happen periodically, and one where they occur randomly at each time point with a certain probability. In the periodic case, they showed that the number of samples needed to exactly recover the system dynamics is proportional to the number of state variables. In the random case, the required number of samples scales polynomially with the state dimension and the attack probability.

Interestingly, the researchers found that their estimators can still learn the true system correctly even when more than half the data is compromised by the attacks. This is an important result, as it means these techniques could be useful in situations where there is a lot of noisy or corrupted data.

Technical Explanation

The paper investigates the system identification problem for linear discrete-time systems under adversarial attacks. The authors analyze two lasso-type estimators and examine their asymptotic and non-asymptotic properties in two scenarios: deterministic and stochastic models for the attack times.

Since the data samples are correlated, the existing results on lasso do not apply. The authors prove that when the system is stable and attacks are periodic, the sample complexity for exact recovery of the system dynamics is linear in the state dimension. When attacks occur stochastically at each time with probability p, the required sample complexity scales polynomially in the state dimension and p.

This implies almost sure convergence to the true system dynamics under the asymptotic regime. Importantly, the estimators can still learn the system correctly even when more than half the data is compromised by attacks.

The authors highlight that the attack vectors are allowed to be correlated, while making some assumptions about the attack times. This paper provides the first mathematical guarantees on learning from correlated data for dynamical systems in the case where there is less clean data than corrupt data.

Critical Analysis

The paper provides strong theoretical guarantees for the performance of lasso-type estimators in the presence of adversarial attacks on linear, discrete-time systems. The authors' ability to handle correlated data samples and provide non-asymptotic bounds is a significant contribution.

However, the paper does make some assumptions, such as the periodic or stochastic nature of the attacks. In practice, the attack patterns may be more complex and harder to model. Additionally, the paper does not consider the case where the attack vectors are not correlated, which may be an important scenario to investigate.

Further research could explore the robustness of these estimators to more general attack models, as well as their performance in the presence of model misspecification or other sources of noise. Algorithmic approaches to recovering coefficients of linearizable differential equations may also provide useful insights for this problem.

Overall, this paper represents an important step forward in the field of system identification under adversarial attacks, and the insights and techniques developed here could have significant practical implications.

Conclusion

This paper tackles the problem of system identification for linear, discrete-time systems under adversarial attacks. The authors analyze two lasso-type estimators and provide theoretical guarantees on their performance, even when a majority of the data is compromised.

The key findings are that the sample complexity for exact recovery of the system dynamics is linear in the state dimension for periodic attacks, and polynomial in the state dimension and attack probability for stochastic attacks. These results have important implications for learning from corrupted data in dynamical systems, which is a significant challenge in many real-world applications.

Overall, this work represents an important contribution to the field of system identification and control under adversarial conditions, and the techniques developed here could inspire further research in this direction.