Exact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Sparse Disturbances or Semi-Oblivious Attacks
Authors: Haixiang Zhang
Baturalp Yalcin
Javad Lavaei
Eduardo Sontag
Venue: Accepted by TMLR ()

Abstract: In this work, we study the problem of learning a nonlinear dynamical system by parameterizing its dynamics using basis functions. We assume that disturbances occur at each time step with an arbitrary probability $p$, which models the sparsity level of the disturbance vectors over time. These disturbances are drawn from an arbitrary, unknown probability distribution, which may depend on past disturbances, provided that it satisfies a zero-mean assumption. The primary objective of this paper is to learn the system's dynamics within a finite time and analyze the sample complexity as a function of $p$. To achieve this, we examine a LASSO-type non-smooth estimator, and establish necessary and sufficient conditions for its well-specifiedness and the uniqueness of the global solution to the underlying optimization problem. We then provide exact recovery guarantees for the estimator under two distinct conditions: boundedness and Lipschitz continuity of the basis functions. We show that finite-time exact recovery is achieved with high probability, even when $p$ approaches $1$. Unlike prior works, which primarily focus on independent and identically distributed (i.i.d.) disturbances and provide only asymptotic guarantees for system learning, this study presents the first finite-time analysis of nonlinear dynamical systems under a highly general disturbance model. Our framework allows for possible temporal correlations in the disturbances and accommodates semi-oblivious adversarial attacks, significantly broadening the scope of existing theoretical results.

Published in Transactions on Machine Learning Research (07 (0/5))
Exact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Sparse Disturbances or Semi-Oblivious Attacks
Haixiang Zhang
haitiang ceaeiiigg_hhnn@@Bbbeelee.....e. edu
Department of Mathematics University of California, Berkeley
Baturalp Yalcin
bttrmlp__alccin@beeeeee.. edu
Department of IEOR Universily of California, Berkeley
Javad Lavaci
laweei@berkeley.cco edu
Department of IEOR
University of California, Berkeley
Eduardo Sontag
sontay@gmaaii com
Department ECE and BioE
Northeastern University
Reviewed on OpenReview: https: // openreview. net/ forum? id= c909UAm33r
Abstract
In this work, we study the problem of learning nonlinear dynamical system by param- eterizing its dynamics using basis functions. We assume that disturbances occur each time step with an arbitrary probability p, which models the sparsity level of the disturbance vectors over time. These disturbances are drawn from arbitrary, unknown probability distribution, which may depend on past disturbances, provided that it satisfics zero-mean assumption. The primary objective of this paper is to learn the system's 's dynamics within a finite time and analyze the sample complexity as function of p. To achieve this, we exam- LASSO-type non-smooth estimator and establish necessary and sufficient conditions for its seel-ppecifsdnnes and the uniqueness of the global solution to the underlying opti- mization problem. We then provide exact recovery guarantees for the estimator under two distinct conditions: boundedness and Lipschitz continuity of the basis functions. We show that finite-time exact recovery is achieved with high probability, even when p approaches 1. Unlike prior works, which primarily focus on independent. and identically distributed (i..d.) disturbancos and provide only asymptotic guarantoes for system learning, this study presents the first finite-time analysis of nonlinear dynamical systems under a highly general disturbance model. Our framework allows for possible temporal correlations in the distur- bances and accommodates semi-oblivious adversarial attacks, significantly broadening the scope of existing theoretical results.
1 Introduction
Dynamical systems serve as the foundation for several fields, including sequential decision-making, rein- forcement learning, control theory, and recurrent neural networks. They are essential for analyzing and controlling the behavior of real-world physical systems. However, accurately modeling dynamical systems is challenging due to their complexity and the large-scale nature of modern systems. The problem of estimat- ing learning system's dynamics from past observations is known the system identification problem.

---

Published in Transactions on Machine Learning Research (07/2025)
This problem is extensively studied in the control theory literature, typically under the restrictive assump- tion that disturbances are small in magnitude and follow an independent and identically distributed (i..d.) probability distribution, accounting for modeling errors, measurement noise, and sensor inaccuracies. In contrast to the conventional small-value, dense-over-time i.d. disturbance model, this paper considers a sparse-over-line, large-value, and temporally correlated dist urbance model. Specifically, we analyze settings where the disturbance is often zero, but when nonzero, can take large values and exhibit correlations with past disturbances.
The primary motivation for this work arises from emerging safety-critical applications, such smart grids, autonomous vehicles, and unmanned acrial vehicles, which require robust estimation of system dynamics in the presence of sparse but large and potentially adversarial disturbances. While machine learning techniques have demonstrated significant success in various domains, such as computer vision and natural language processing, their application to safety-critical systems remains limited due to a lack of theoretical guarantees. This paper addresses this gap by providing strong theorctical results for learning dynamical systems using machine learning techniques.
As motivating example, we consider the dynamical system associated with power grid, such as the U.S. electrical grid or a regional interconnection. The system states capture various physical parameters, includ- ing voltage magnitudes and frequencies across different parts of the network. To enhance the sustainability, resiliency, and efficiency of energy systems, modern power grids integrate large volumes of renewable energy sources, such as wind turbines, solar panels, and electric vehicles. The operation of power systems has become increasingly complex due to the active participation of consumers, who strategically respond to electricity prices by adjusting their consumption based on price signals. Simultancously, the widespread deployment of sensors across the grid has enabled data-driven grid operation by continuously collecting and analyzing system data. However, this advancement introduces a significant vulnerability: even a tiny, strategically executed data manipulation could mislead power suppliers, causing them to overestimate or underestimate cloctricity demand. Such miscalculations could result in severe consequences, including system-wide black- outs. This scenario can be modeled as a nonlinear dynamical system in which the system input is subject to semi-oblivious attacks at various locations, resulting in the injection of incorrect electricity values into the grid. Given the integration of a large number of new devicos into the system, coupled with strategic human behavior, power operators lack complete model of the underlying dynamical system. Consequently, they must simultaneously learn the system dynamics and detect potential adversarial attacks to mitigate disrup- tions and restore regular operations effectively. If an input attack remains unaddressed, it can destabilize the system's transient behavior, leading to signal instability and potentially triggering a cascading failure across the grid.
Prior research on robust system learning has primarily focused on unreliable measurements, where the objec- tive is to extract knowledge from noisy and corrupted observations- such as in the matrix sensing problem in machine learning. However, this paper addresses emerging and largely overlooked aspect of robust learning in safety-critical systems, where the system input itsclf is manipulated (potentially by an adver- sary), thereby affecting the system states and inducing instability. Existing results in system identification have concentrated mainly on the asymptotic properties of the least squares estimator (LSE) (Chen & Guo
2012 Ljung et al. 1999 Liung& & Wahlberg, 1992 Bauer et al. 1999.. With the advent of statistical learning theory, rescarch in this area has evolved to study the required number of samples necessary to achieve a given error threshold (Tsimmis et al. 2023). While early non-asymplolic analyses focused on linear time-invariant
(LTI) systems with ii.d. disturbances using mixing arguments (Kuznetsov & Mohri 2017 Rostamizadeh &
Mohri 2007). more recent studies employ martingale and small-ball techniques to derive sample complexity
guarantees for LTI systems (Simchowitz et al. 2018 Faradonbeh et al. 2018 Tsiamis & Pappas 2019
For nonlinear systems, parameterized models have been explored in recent studies (Noël & Kerschen 2017
Nowak 2002 Foster et al., 2020 Sattar & Oymak 2022 Ziemann et al. 2022
demonstrating the conver-
gence of recursive and gradient- gradient-based algorithms to the true parameters with a convergence rate of 1/2
using martingale techniques and mixing time arguments. These results mainly focused the non-asymptotic approzimate recovery of the system. On the other hand, are more interested in the non-asymptotic eract recovery guarantees. As early attempts toward this goal, there has been some progress toward developing non-smooth estimators for both linear and nonlinear systems (Feng & Lavaei 2021 Feng et al. 2023 Yalcin
2

---

Published in Transactions on Machine Learning Research (07/2025)
et al. 2023 particularly in handling large-utt-sparse noise vectors with dependencies. However, robust regression techniques incorporating regularivation (Xu et al. 2009 Bertsimas & Copenhaver 2018 Huang et al. 2016 remain relatively unexplored in the context of dynamical systems, particularly with respect to aon-asympootic sample complexity analysis. This gap is mainly due to the inherent autocorrelation in system samples, making traditiona ional stalistical tools less applicable. more detailed literature review is provided in Section 2
This paper lays the foundation for advancing online optimal control in the presence of large but sparse disturbances, such as specific adversarial attacks. Under safety-critical constraints, it is generally necessary to first learn the system dynamics before applying a control strategy, since applying an inadequate policy could shift the system states beyond safe limits, potentially leading to instability; see Section 2 and Moerland jet al. (023) for more detailed discussions. Therefore, to avoid the potential risks, a crucial first step in achieving the goal of optimal control under adversarial attacks accurately learning the system dynamics. To this end, we focus on the system identification problem for parameterized nonlincar systems, making necessary assumptions about the disturbance model, which will be discussed in later sections. We model the unknown nonlinear functions describing the system via a linear combination of some given basis functions by taking advantage of their representation properties. Our objective is to estimate the parameters of these basis functions, which dictate the updates of the dynamical system. Formally, we consider the following autonomous dynamical system:
On, Li+1 = Af(x)) V IO
(1)
where f Rd + Rd is a combination of m known basis functions and À E R=xm the unknown matrix of system parameters. The system trajectory is also influenced by the disturbance term de T... We consider a sparse-but-large disturbance scenario, where the disturbance is sometimes zero but, when nonzero, takes large values. In the context of an adversarial attack, zero disturbance value for de indicates the absence of attack at time 4, while nonzero disturbance is typically large, designed to maximize the impact of the attack. The goal of the system identification problem is to recover the ground truth matrix À using observations of the system states, i.e,, {xo....,,77 x. The model generating de' 's is unknown to the user; however, to ensure unique recoverability of the system from measurements, we will later introduce necessary assumptions on the disturbance model, referred as semi-oblivious attacks.
Unlike empirical risk minimization problemss, where samples are typically assumed to be i..dd,, the sys- tem states ( ØT) exhibit auto-correlation. As result, the standard i..d. assumption on the data- generating distribution is violated. This auto-correlation introduces significant thcoretical challenges, which we address in this work by proposing a novel and nontrivial extension of exact recovery guarantees to the system identification problem. Since the disturbance de is unknown to the system operator and can take a large value, is necessary to utilize estimators to the ground truth that are robust to variations d, and converge to within finite time horizon T. Our work is inspired by Yalcin et al. (2023) that studied the above problem for linear systems. The linear case is noticeably more straightforward than the nonlinear system identification problem since each observation 2, becomes linear function of previous disturbances. In contrast, for nonlinear systems, the relationship between measurements and disturbances is considerably more complex, requiring substantial technical advancements beyond the methods used in Yalcin et al. (0023).
The existing literature has primarily focused on the smooth least-squares estimator:
T-1
Å E arg min
Σ
|0411 - Af(2))12
(2)
AER
t=
In contrast, motivated by the exact recovery propertics of non-smooth loss functions (e.g., the f--orr and the nuclear norm), we consider the following alternative estimator:
À E arg min AERexm
Σ |041 Af(x))12
We note that the optimization problem remains convex in despite its non-smooth objective function: therefore, it can be solved efficiently by existing optimization solvers. The estimator 3 is closely related
3

---

Published in Transactions on Machine Learning Research (07/2025)
to the LASSO estimator, as its loss function can be interpreted as generalization of the f1-loss function. More specifically, when 1, the estimator (3) simplifies to
A E arg min AER
J++1 Af(xo))
which corresponds to the auto-correlated general linear regression estimator with an f-lloss function. The intuition behind the advantage of the LASSO-type estimator is that the estimator is robust to "sparse" attacks. In our work, the sparsity of attacks is defined through probability (Definition D Suppose that the attack vectors de are nonzero and large for a small number of time indices t. The least-squares estimator ( will generally not be able to exactly recover the undorlying paramcter A since the loss function is smooth with respect to the error term I - A.x)). In contrast, we prove that the LASSO-type estimator 3 is able to ezactly recover the parameter A given a sufficiently large number of time steps. The exact recovery is guaranteed through the nonsmooth loss functioon, which prefers solutions that result in small number of nonzero error terms 2441 - Axz)). This property of the LASSO-type estimator 3 fits better to our setting than the least-squares isatoo (2).
In this work, the goal is to prove the efficacy of the above estimator by obtaining mild conditions under which the ground truth A can be evactly recovered by the estimator 3 More specifically, we seek to address the following key questions:
What are the necessory and sufficient conditions under which Ā is an optimal solution to the optimization problem (3) or the unique optimal solution?
ii) What the minimum number of samples required to ensure that the nccessary and sufficient con- ditions for exact recovery hold with high probability under certain assumptions?
In this work, we provide answers to the above questions. Section 2 presents a comprehensive literature review on system identification and robust estimation problems. In Section 3 we analyze the necessary and
sufficient conditions for the global optimality of A for the problem {3 Furthermore, we establish conditions
under which is the unique solution, thereby addressing Question (i). Next, in Sections 5 and 6 we derive lower bounds the number of samples T required to guarantee that A is the unique solution with high probability. We consider two distinct cases: when the basis function f is bounded when it is Lipschitz continuous. These results provide an answer to Question (ii). In Section we introduce a faster lcarning strategy when nonzero disturbances fail to sufficiently explore the system state space. Finally, in Section we present numerical experiments that support our theoretical findings. This work constitutes the first non-asymptotic sample complexity analysis for exact recovery in the nonlinear system identification problem.
Notation. For a positive integer n, we use O, and I, to denote the n-dimensional vector with all entries being 0 and the n-by-n identity matrix. For matrix Z, || denotes its Frobenius norm and Sp is the unit sphere of matrices with Frobenius norm / 1. For two matrices Z1 and Z2, use (Z,, 72) (r[ Z2) to denote the inner-produs produpp. For vector 2, ||2||2 and || denote its lg- and lo0 -orms,, respectively. Morcover, g is the unit ball fa E ||]|| = 1}. Given two functions f and g, the notation f(x) = 0lg(z))
and [(x) = [[](()] means that there exist universal positive constants 0j and C2 such that (19(x) < f(x) (2g(x) and f(x) 2 cig(x), respectively. The relation f(x) S g(x) holds if there exists a universal positive constant 03 such that f(x) S cag(z) holds with high probability when T is large. The relation f(x) Z g(x) holds if g(x) S f(x). [S] shows the cardinality of given set P(-) and E(-) denote the probability of an event and the expectation of random variable. A Gaussian random vector X with mean μ and covariance matrix Σ is written X X~ N),
2 Literature Overview
Until recently, research on the system identification problem primarily focused on the asymptotic properties
of the least squares estimator (L.FE) (Chen & Guo 2012 Ljung al. 1999 Ljung & Wahlberg 1992
4

---

Published in Transactions on Machine Learning Research (07/2025)
Bauer al. 1999: However, with the increasing prominence of statistical learning theory (Vershynin 2018
Wainwright, 2019. understanding the number of samples required to achieve given error threshold in system identification has become a topic of significant interest. For a comprehensive overview of existing results and proof techniques, we refer the reader to the survey by [Tiamis et al. (202)). The non-asymptotic analysis of system identification has primarily focused on linear time-invariant (LTT) systems under the
assumption of i.i.d. noise. Early research in this area relied on mixing arguments, which heavily depended on system stability (Kuznetsov & Mohri, 2017; Rostamizadeh & Mohrri 2007). More recent studies have employed martingale and small-ball techniques to establish sample complexity guarantees for least squares estimators applied to LTT systems (Simchowitz et al.) 2018: Faradonbeh et al. 2018 Tsiamis & Pappas, 2019). These works demonstrate that the LSE converges to the true system parameters at a rate of T"112 where T denotes the number of samples. Furthermore, these results have been applied to the linear-quadratic regulator problem, where adaptive control techniques leverage system identification results to achieve optimal regret bounds (Dean et al. 2020 JibasiiYadkony & Szopesvári 2011 Dcan et al. 2019).
The nonlinear system identification problem has been extensively studied (Noël & Kerschen 2017 Nowak 2002). However, research on the non-asymptotic analysis of nonlinear system identification remains in its early stages and has primarily focused on paramcterized nonlinear systems. Recursive and gradient-basod algorithms designed for the least squares loss function have been shown to asymptotically converge to the true system parameters at a rate of 7-1/2 for nonlinear systems with a known link function á of the form o(Ax),, using martingale techniques (ooster et al. 2020) and mixing time arguments (Sattar & Oymak, 2022). More recently, [Ziemann et al. (2022) established sample complexity guarantees for nonparametric learning of nonlinear system dynamics, demonstrating convergence rate that scales as 7-1/(2+9), where q depends on the complexity of the function class in which the true dynamics reside. Notably, existing studies on both linear and nonlinear system identification have largely assumed i.i.d. (sub-)Gaussian noise structures, limiting their applicability to more general disturbance models.
Despite the growing interest in non-asymptotic system identification, rescarch on system identification using non-smooth estimators capable of handling dependent and adversarial noise vectors remains limited to linear systems. In addition, the main focus of aforementioned works is on the non-asymptotic approximate recovery of the underlying parameter A. Under safety- crriticl constraints, it is idcal to achieve the non-asymptotic exact recovery of the parameter A, possibly with additional assumptions the adversarial noise. There exist early attempts on the exact recovery guarantees. Feng & Lavaci (2027) and Feng et al. (2023) investigated a non-smooth convex estimator in the form of the least absolute deviation estimator, analyzing the conditions required for exact recovery of system dynamics using Karush-Kinn Kuhn- Kuhn-Tucker (KKT) conditions and the Null Space Property from the LASSO literature. Subsequently, /aalcin et al. (2023) demonsstrtedd that exact recovery of system parameters is achicvable with high probability, even when more than half of the data is corrupted, opening new avenues for adversarially robust system identification. Compared to (aleiin et al. (2023, the presence of nonlinear basis functions in our setting makes it impossible to analyze the optimization problem by explicitly expressing Fı; see the proof of Theorem 2 in Yalcin et al. (2023). Note that when the system is in the form of I++1 = Ar,, then can be written directly as A' and we only need to analyze the eigenvalues of A. For a nonlinear system in the form of d++1 = (xx), writing Ia in terms of ao needs the composition of t functions, and this cannot be done analytically. Unlike linear systems, there is no direct counterpart to cigenvalue analysis for nonlinear systems. This fundamental challenge widely acknowledged in nonlinear systems literature within control theory, and as result, many results known for linear systems do not extend to the nonlinear setting. Consequently, our proof for the bounded case is novel and fundamentally different from the approach in Yalein et al. (023).. Finally, by leveraging the generalized Farkas' lemma, we establish necessary and sufficient conditions in Section 3 that are both novel and stronger than the sufficient conditions provided in Yalcin et al. 2023)
On the other hand, robust regression techniques have been developed by incorporating regularizers into the objective function (Xu et al.) 2009 Bertsimas & Copenhaver, 2018 Huang et al.) 2016). Additionally, the robust estimation literature has introduced several non-smooth estimators, including M-estimators, least absolute deviation estimators, convex estimators, least median squares, and least trimmed squares (Seber &
Lee 2012). The convex estimator in (3) was proposed in Bako & Ohlsson (2016): [ako (2017) in the context of robust regression, demonstrating that exact recovery is achievable given an infinite number of samples.
5

---

Published in Transactions on Machine Learning Research (07/2025)
However, these studies lack non-asymptotic analysis of sample complexity. Furthermore, their analytical techniques are not directly applicable to dynamical systems due to the presence of autocorrelation among samples.
Recent works Wu et al. 2022 Kumar et al. 2022 have focused on reinforcement learning (RL), where the primary objective is to maximize a reward function. In contrast, system identification aims to recover the underlying system dynamics, and in many applications, naturally defined reward function may not exist. Moreover, both of these RL studies assume that perturbations bounded, restrictive assumption that may not hold in real-world scenarios. More importantly, attempting to control system without first learning its dynamics (c.g., using model-free RL techniques) poses significant risks. During exploration, an inadequate policy could shift. the system state beyond safe operational limits, potentially leading to instability; see the survey by Moerland et al. (2023). For safety-critical systems, is typically necessary to first learn the system dynamics before applying control strategy, whether it be a classical optimal control method or an RL-based approach. Our work focuses on learning the system model in the presence of adversarics on its dynamics. Existing RL approaches, including those in Wu et al. (2022) Kumar el. al. (2022), address fundamentally different problem. Additionally, while the field of robust model- based RL is well-developed, our setting involves unknown system dynamics, necessitating the use of model-free RL techniques.
3 Global Optimality of Ground Truth and Uniqueness of Global Solutions
In this section, we derive conditions under which the ground truth A is a global minimizer to the optimization problem Given the system dynamics, this optimization problem can be reformulated as
T-1 Σ ((AA-)) + dell..
min Xm
(4)
where Tu...., are generated according to the unknown system under disturbances. To facilitate the analysis, we define the set of time instances where disturbances are nonzero as K. = {1 de * 0} and introduce the normalized disturbances as
:= delle V.C.C
The following theorem provides a necessary and sufficient condition for À to be a global minimizer of the problem in (4) Theorem 1 (Necessary and sufficient condition for optimality). The ground truth matriz A is global
solution to problem 4 if and only if
Σ LEK
){))( Σ |1) AZ E Raxm
(5)
LEK
where K0 =====00 (0...,, -IVVC denotes the set of time indices where disturbances zero.
Theorem I provides a necessary and sufficient condition for the well-spccifiedness of the optimization problem in (4) Intuitively, the left- hand side of 5 represents the impact of nonzero disturbances, while the right- hand side corresponds to the standard system dynamics. If the disturbances do not dominate the correct system dynamics, then the estimator can successfully recover the ground truth dynamics. The condition in (5) is derived using the generalized Farkas' lemma, which eliminates the need for inner approximation of the ball by an -bll, as in Yalcin et al. (2023). Consequently, the sample complexity bounds obtained in
this work are stronger than those in Yalein ct al. (0023) when applied to the special case of lincar systems.
Further details on these bounds are provided in Sections and 6
Using the condition established Theorem we derive both sufficient and necessary conditions for the optimality of in Corollaries and 2 Corollary 1 (Sufficient condition for optimality). it holds that
12f(z)))2 S Σ [z)(2l) ZZ E Raxm
(6)
KEK
tek

---

Published in Transactions on Machine Learning Research (07 (07/2025)
then the ground truth matriz A is global solution to problem A._
Corollary 2 (Necessary condition for optimality). If the ground truth matrix A is global solution to problem 4 then it holds that
Σ Mar)dT BEK
S Σ (1(2)))
(7)
tEK
In the when 1, condition
is necessary and sufficient.
The proof of Corollary is direct application of the Cauchy-Schwaad inequality and we omit the proof. The proof of Corollary 2 is provided in Appendix B The conditions established above more general than many existing results in the literature; see Examples and 2 in Appendix A for further discussion.
Next, we derive conditions under which the ground truth matrix is the unique solution to the optimization problem in 4 We present the following necessary and sufficient conditions for the uniqueness of global solutions, which extends the result of Theorem
Theorem 2 (Necessary and sufficient condition for uniqueness). Suppose that condition holds. The if and only if the following logical condition holds ground truth is the unique global solution to problem ( for every nonzero Z E Rnxm;
E 1Zf(z))l2
Σ tEK
5. Zf(x.)
Σ 11ff(z))l2.
(8)
TEK
tEKs
which means that whenever the left-hand side equality is satisfied for some nonzero Z, the right-hand side inequality must also hold.
Based on Theorem the following corollary provides sulficient condition for the uniqueness of Ā, which is more practical to verify compared to condition (S). Notably, this corollary also generalizes the sufficiency part of Corollary 2 to the multi-dimensional setting.
Corollary 3 (Sufficient condition for uniqueness). If it holds that
Σ 2f(r)) < Σ [1)(())
E s.t. 7 + 0,
(9)
tEK
SEKs
then the ground truth matrix À is the unique global solution to problem
Proof. The logical condition in S states that whenever the left-hand side equality is satisfied for some
nonzero Z, the right-hand side incquality must also hold. Under the assumption in (9. there is no nonzero
Z satisfying the left- hand-siee equality. This implies that the logical condition in automatically holds and, thus, Theorem implies the uniqueness of A.
Theorem 2 strengthens and generalizes existing results for first-order systems, specificaly Theorem 1 in Feng & Lavaei 2021 For further discussion, see Example in Appendix A
4 Disturbance Model and Semi-Oblivious Attacks
To model sparse disturbances, we consider the frequency at which the system experiences a nonzero distur- bance. This captured by the sparsity probability p, defined as follows:
Definition 1 (Probabilistic sparsity model). For each time instance t, the disturbance vector de is nonzero with probability p E 10, Furthermore, the occurrences of disturbances are independent across time in- stances.
Existing results have predominantly focused on the case where p 1, under which the system dynamics cannot be learned exactly in finite time. To illustrate the impact of sparsity, consider the scenario where d,

---

Published in Transactions on Machine Learning Research (07 2225))
follows Gaussian distribution for all IC and independent of previous disturbances d1:...,d-2 d,-1- When 1, it follows that there exists no finite time T for which the correct dynamics matrix À is solution to the least-square estimator ! almost surely. As an alternative to the exact recovery, existing works have focused on the finitc-time approximate recovery of paramcter A and established the convergence of the estimation
error Noël & Kerschen 2017 Nowak 2002 Foster al. 2020: Sattar & Oymak 2022; Ziemann et al.
2022 See our discussion on the approximate recovery results Section 2 However, the exactly recovery of
the underlying system parameters is possible under suitable assumptions (e.g., Definition 1 and is preferred
since it provides stronger recovery guarantee against adversarial attacks.
Morcover, when p < 1, the LSE also fails to achieve exact recovery even under an i.id zero-mean Gaussian disturbance structure. To illustrate the failure of LSE, we define the following matrices:
Fr (f())
f(x1)
((r-1>) and Xr
[
x2
xT
dr-1], where where Fr, XT E B In addition, we define the disturbance matrix Dj ddo d1
Dr E RRxT Under these definitions, the system updates can be expressed as Xy = AFr + Dr Thus, the closed-form solution of the LSE is given by Å (FrEF)- and the estimation error can be When T is sufficiently large, the matrices Fr and Dr become full-
written as A - A = - rank; consequently, the LSE estimation error, Å - A, never altains zero error. In contrast, the results in conclude that for every E (0, 1), the ground truth matrix A becomes the unique solution
Sections 5 and 6 of the non-smooth estimator (3) provided that T' exceeds a certain threshold. This result represents a highly specialized case of the broader findings presented in this paper and highlights the advantage of incorporating zero disturbances. Specifically, having some instances zero dibanenances enables a transition from asymptotic learning to finite-time learning, demonstrating the efficacy of the proposed approach.
It is important to note that in this work, the disturbance vectors de's 's allowed to be correlated over time. Definition | is only about the times at which disturbances are nonzero. Additionally, we do not assume that the sparsity probability p or the model generating the disturbances is known. Recalling the definition K. == { de + 0}, we observe that with probability at least - expl-O(p7)), the cardinality of IC satisfies [C] = @pp7). When is close to 0, the system is rarely affected by disturbances. The absence of disturbances, however, may lessen the rate of exact recovery due to insufficient exploration of the system space. A potential approach mitigate this issue is outlined in Section 7 Nevertheless, this paper primarily focuses the case where p is close to 1, meaning that the system experiences disturbances at nearly all time steps.
4.1 Non-degenerate Condition
In the following theorem, we demonstrate that in the absence of assumptions the disturbance vectors, estimator reliably learn the system dynamics.
Thcorem 3. Consider the linear system Z++1 = Ax; + de, za = On, together with a linear subspace D C R whose dimension is less than rank of A. Assume that the disturbance de is always chosen from this not-full- dimensional subspace. Then, there does not exist any estimator of the form
ÀT arg min AERaXO
((A;(aa))
that uniquely recovers the matrix À all the time from the states To: .o,, IT no matter how large T is. Here, g(A; (x))T is the function of A that depends on the system states over time.
To avoid the degenerate case, we assume that the norm of basis function is lower-bounded under conditional expectation after a nonzero disturbance.
Assumption 1 (Non-degenerate condition). Conditional on the past information F, and the event that de + On, the disturbance vector and the basis function satisfy
Amin E [f(x dz)((x + d.)T Fr, de + On.] 2 X2, WE
where Amin (F) is the minimal eigenvalue of matrix F and X > 0 is constant.
8

---

Published in Transactions on Machine Learning Research (07/2025)
Intuitively, the non-degenerate assumption ensures sufficient exploration of the trajectory in the state space. More specifically, for the condition in ( to hold, it is necessary that the matrix
[f(x), E tEK E [=
(10)
has rank-m; see the proof of Theorem for further details. The non-degenerate assumption guarantees that the basis function evaluations f(r + d,) spans the entire state space in expectation. As a result, the matrix in [10 full-rank with high probability when the number of samples T is sufficiently large.
4.2 Semi-oblivious Condition
Consider the scenario where the disturbances affecting the system are advesarially designed. In this case, we refer to these disturbances as attacks, with p representing the frequency at which the system under attack. Two key problems arise in the context of attack analysis: (1) attack problem where the adversary aims to design the attack vectors de to maximize the disruption to the system, and (2) defense problem where the system operator seeks to detect any suspicious attack and nullify it. Two common strategies often used in combination to design an effective defense mechanism are (i) inspecting the system imputs to detect anomalies indicative of attacks and (ii) analyzing collected state values to infer whether an al Lack has occurred. Based on Theorem 3 if the attacker has complete freedom in selecting attack values, the most effective strategy is to constrain them to specific subspace where no estimator can function reliably. However, such biased attack strategies are easier to detect using defense strategy (i), as the operator can analyze the statistical behavior of the imputs and identify deviations from natural disturbances, flagging them as attacks. Thus, the risk for attacker employing extreme attacks is that they increase the likelihood of detection and nullification by a well-designed defense mechanism. Consequently, a strategic adversary should avoid highly conspicuous attack patterns and instead focus on attacks that have a lower probability of detection.
As an example, consider the first-order system T++1 = Zz + de where de E R. Suppose this represents a physical system that cannot accept inputs exceeding a given magnitude limit y. The most severe attack in this case would be to set de to be equal to 7 at all times, driving the state to grow as rapidly as possible. However, well-designed defense mechanism could quickly detect this attack by recognizing that the injected input is not natural disturbance but rather a deliberately crafted adversarial input. To evade detection, the attacker must adopt a more subtle approach. Instead of consistently applying the maximum allowable input, the attacker may alternate between positive and negative disturbances, choosing de to be +7 and -7 for some 7 < 7. This strategy achieves two key objectives: (i) avoiding hitting the maximum limit and (ii) making the attack look like a disturbance by having a zero mean. Although this alternating atlack pattern is less detectable, it still has a significant impact on the system. Specifically, it increases the variance of 21, causing oscillatory behavior that can degrade system performance. This example illustrates broader principle: an effective atlack strategy should involve alternating posilive and negalive perturbations ions rather than consistently applying unidirectional inputs. To formally capture this concept, we introduce the notion of attack/ /diiturbaaaceee direction and define a semi-oblivious condition in the attack attack/disturbance /disturbance process. This
condition aligns with existing robustness criteria in the literature (Candès et al. 2011 Chen et al., 2021 To do so, we define the filtration F. := (No, Tt).
Assumption 2 (Semi-oblivious condition). Conditional on the past information F, and the event that de * On, the disturbance direction d, = d./l/d.ll2 zero-mean.
The semi-oblivious condition has been widely studied in real-world systems, particularly the context of stealthy attacks. To illustrate this concept, consider another example from an energy system comprising two nodes: Node represents neighborhood of homes, and Node 2 is power supplier owned by utility company. Every five minutes, Node 1 reports to Node 2 the amount of electrical power required for the next five-minute period. Suppose the neighborhood requires constant power demand of 1 unit for the next five hours. However, an attacker has compromised the communication channel between Node 1 and Node 2, altering the reported demand from 1 unit to either - e or 1 + e every half hour, where e is a large perturbation relative to 1 unit. Since the average of a semi-oblivious attack. However, this manipulation disrupts the power balance: when Node actually requires unit of power, but Node 2 instead generates either 1 1 + e, the resulting mismatch violates
and 1 + e is still 1, this could serve as
9

---

Published in Transactions on Machine Learning Research (07 (07/2025)
the fundamental physical constraints of the grid. Such discrepancies trigger grid instability, potentially leading to large-scale blackouts. Semi-oblivious attacks of this kind have been observed in various parts of the world, resulting in severe power outages. The cyberattack problem in power systems aligns closely with our mathematical models. Notably, power system operators employ hypothesis testing techniques to detect anomalies in reported data. If the injected disturbances exhibit a nonzero mean, they would be flagged as suspicious. However, by maintaining a zero mean, semi-oblivious evade detection while still destabilizing the system.
Due to the poor performance of LSE under the disturbance structure characterized by the semi-oblivious condition and the probabilistic sparsity model, our work focuses on analyzing the LASSO-type estimator and understanding the conditions under which exact recovery is attainable in such settings. We emphasize that this disturbance structure encompasses not only some sparse disturbances but also certain types of attacks. For instance, the disturbance structure may consist of a combination of sparse, zero-mean Gaussian input vectors, denoted as Et, and semi-oblivious attack vectors, fi, both of which satisfy the required assumptions. Suppose the & and Jr follow the probabilistic sparsity model with probabilities p' and p: respectively. In that case, the overall disturbance, given by de Et + ft, is also semi-oblivious and follows the probabilistic sparsity model with probability at most p' + <
In the following two sections, we provide lower bounds on the sample complexity 7 such that the ground truth A is the unique solution to problem ( The following section derives results under Assumption 2 Following that, we extend our analysis to unbounded basis functions, which require Assumption G While Assumption G is somewhat stronger than Assumption 2 it remains a practical assumption. Note that the former assumption requires the disturbance directions to have zero meanwhile the latter assumption requires the disturbance directions to follow uniform distribution. In both cases, the magnitudes of the nonzero disturbances attacks remain unrestricted, meaning that adversaries can inject disturbances of arbitrary values to maximize their impact on the system.
5 Bounded Basis Function
In this section, we analyze the case where the basis function f is bounded. Assumption 3 (Bounded basis function). The basis function R" + Rm satisfies
llf(=))l S
Vx E R".
where B > 0 is a constant.
The following theorem establishes that when the sample complexity is sufficienlly high, the estimator 3 achieves exact recovery of the ground truth matrix A with high probability.
Theorem 4 (Exact recovery for bounded basis function). Suppose that. Assumptions hold and the disturbance vector de is nonzero with probability p 10, Define k B/> 2 For all ó (0,1), if the sample complerity T satisfies
m n²
mK
!
T=Ω
mn log
+ log
(11)
p(1
2)2
p(1
p))
then is the unique global solution to problem with probability at least 1 5.
The above theorem provides a non-asymptotic bound on the sample complexity required for exact recovery with a specified probability of at least 1 1- 5. The lower bound scales m²n, indicating that the required number of samples increases the number of states and the number of basis functions m grow. In addition, the sample complexity increases when B is larger or À is smaller. This aligns with the intuition that B reflects the size of the space spanned by the basis function, and À measures the speed of exploring the spanned space.
Regarding the dependence on the sparsity probability p. the following theorem demonstrates that the scaling factor 1/[p(1 - p)] unavoidable under the probabílistic sparsity model. Furthermore, the theorem also establishes lower bound the sample complexity that depends on m and log(1/8).
10

---

Published in Transactions on Machine Learning Research (07/2025)
Theorem 5. Suppose that the disturbance vector de is nonzero with probability p (0.1) and the sample complenity salisfies
m
T
2p(1 - p)
Then, tions 2 1 hold and the global solutions to problem
there erists basis function I
R and disturbance model such that Assump-
4 are not unique with probability at least max 2cxp (-m/3), p)] Furthermore, given a constant 8 E (0, if
2 2p - p) log(p(1 p)] log (
2
T < max
then the global solutions to problem
4 are not unique with probability at least max {1 2 exp (-m/3), 88.
We note that the result of Theorem 5 in Section 0
hold for both bounded and Lipschitz base functions, which are studied
Remark 1. A key objective of this paper is to show that the ezact recovery in finite time is achievable when p is close to 1, indicating that the system operates under semi-oblivious allacks most of the time. In Theorem 4 we establish an upper bound on the required time horizon for eract recovery, a result with significant implications for real-world systems. Conversely, the lower bound derived in Theorem 3 serves primarily as a theoretical result. Unlike large-scole machine learning problems, where the problem size can reach tens of millions, real- world dynamical systems typically have far fewer states, often fewer than several thousand. As resull, our upper bound already provides a practical estimate of the required sample complexity. While further tightening the lower bound remains relevant and theoretically interesting problem, its practical impact is likely to be marginal, given that the current upper bound is already within feasible range for real-world applications.
6 Lipschitz Basis Function
In this section, we consider the case when the basis function f(x) is Lipschitz continuous in z. Specifically, we make the following assumption.
Assumption 4 (Lipschitz basis function). The basis function f R" + R satisfies
f(O,.) Om and llf()) f(vill2 & L|[e vlla, Ve,ye where L > O is the Lipschitz constant.
As special case of Assumption the basis function of linear system is f(x) = x, which satisfies the Lipschitz condition with 1.
Remark 2. It is important to note that the assumptions of boundedness or Lipschitz continuity are always satisfied in dynamical systems, as the user has the fleribility to select oppropriate basis functions to ensure these properties. Specificully, the user can choose an arbitrary set of basis functions approrimate the unknown function as linear combination of these bases. This setting differs from classical machine learning problems, where the model is trained to learn an unknown function, and there is no direct control over its Lipschitz continuity. Conversely, in dynamical systems, the user impose constraints functions to ensure desirable mathematical properties. However, if unbounded basis funclions or funclions with high Lipschitz constants are restricted, laryer number of basis functions may be required to achieve an accurate approzimation of the unknown function. Moreover, many real-world dynamical systems, ranging from robotics to energy systems, inherently exhibit smooth and well- behaved dynamics due to their foundation physical lawss, such as Newtonian mechanics and Kirchhoff 's circuit laws. This stands contrast to various machine learning problems, where the optimol policy may be inherently non-smooth and highly complea, making function approzimation significantly more challenging.
the basis
Additionally, we assume that the spectral norm of Ā is bounded to ensure system stability.
11

---

Published in Transactions on Machine Learning Research (07 (07/)025)
Assumption 5 (System stability). The ground truth A satisfies
p p: = A L
Assumption is related to the asymptotic stability of the dynamical system and is sufficient to prevent the finite-time divergence of the system trajectories. In Theorem 7 we demonstrate that this stability condition may also be necessary for exact recovery. Finally, we make the additional assumption that each bance follows a Gau-Gaussian distribution.
Assumption 6 (Sub-Gaussian disturbances). Conditional on the filtration F. and the event that de + On, the disturbance vector d, is expressed as the product E where
1. de E RD and l E IR are independent conditional on Ft and de + On;
2. de is a zero-mean wnit vector, nomely, E(de | FF, de + On) = O, and lidella = 1;
3. & is zero-mean and sub-Gaussion with parameter o.
As special case, the nab-Gaussian assumption is guaranteed to hold if there is an upper bound the magnitude of each disturbance. To be more specifie, suppose that ||d:|l2 S B for all t. In this case, we have & S B for all t and thus, the magnitude & is sub-Gaussian with parameter o = B. The bounded disturbance case is common in practical applications since real-world systems do not accept inputs that are arbitrarily large. For example, physical devices have a clear limitation on the input size, and the disturbances /aarrbaann////taakks//s /ttacks cannot exceed that limit. In Assumption 6. the components de and 4, respectively represent the direction and intensity (such as magnitudo) of cach attack ddisturancee While the intensity parameters 4 could be correlated over time, both de and E, are assumed to be zero-mean, aligning with the cemi-oblivious condition stated before.
Under these assumptions, we can establish that high-probability exact recovery achievable, provided that the sample size T is sufficiently large.
Theorem 6 (Exact recovery for Lipschitz basis function). Suppose that Assumptions i6 hold and the disturbance vector de nonzero with probability p E (0, 1). Define k =- oL/ / 1. If the sample complexity T satisfies
K 10
1
T= Ω max
men ma log ( (i1-pL)mu( pL)xp(1 m3) + log (
(12)
(1- (1- pL)
2)2
p(1
then À is the unique global solution to problem
(4) with probubility at least 1 - 8.
f provides non-asymplolic sample complexity bound for the case where the basis function is Lipschitz continuous. As a special case, when the basis function is linear, i.e., f(z) = and the attack/ attack/disturbae ddisturaaccc vector d, follows the Gaussian distribution (V0,,, o2I,) conditional on Fe, we have K = 1. Compared to Theorem X the dependence on the nonzero disturbance probability p is improved from 1/1p(1 - p) to 1/(p(1 p)). a consequence of the stability condition (Assumption 5 In addition, the dependence on the dimension m improved from m² to m. Intuitively, the improvement is achieved by improving the upper bound on the norm [x)(2)) In the bounded basis function case, the norm is bounded by vmB, while in the Lipschitz basis function case, the norm is bounded by aT, with high probability, which is independent of the dimension m. Finally, the sample complexity bound grows with the parameter k = oL/ and the gap 1 pL, which is also consistent with the intuition.
Theorem
Conversely, we can construct counterexamples demonstrating that when the stability condition (Assumption is violated, exact recovery fails with probability at least p.
Thcorem (Failure of exact recovery for unstable systems). There crists a system such that Assumptions
and o are satisfied, but for all T 2 1, the ground truth is not a global solution to problem 4 with probability at least pl1 (1 - T1]-
12

---

Published in Transactions on Machine Learning Research (07/2025)
7 Absence of Semi-Oblivious Attacks
5 and G we derived the required number of samples for exact recovery in the presence of sparse and semi-oblivvous disturbances using bounded and Lipschitz basis functions. For bounded basis functions, the sample complexity scales as p p= p))- in terms of the nonzero disturbance probability, up a logarithm factor, as stated in Theorem | Similarly, Theorem
In Sections
@ established that, for Lipschitz
basis functions, the sample complexity scales as max p)-² p p1 p) '} with respect to the nonzero disturbance probability. Although the theoretical results in these sections are quile promising whenever nonzero disturbance probability 0.5, it may seem counterintuitive that the sample complexity increases as decreases and approaches zero, given that a smaller p implies fewer nonzero disturbances and attack injections into the system. This phenomenon can be explained through the concept of exploration. When p is small, the lack of disturbances reduces the rate at which the system state space is explored, thereby increasing the number of samples required for exact recovery. Numerical experiments further support this theoretical observation, the results of which are presented in Appendix C
It is well-known that random excitation signals into dynamical system can accelerate convergence in system identification problems. To leverage the sample complexity bounds derived in earlier sections and enhance the learning rate, we define the disturbance vector de as a combination of the random input vectors injected by the controller, ét, and the semi-oblivious attacks designed by an adversarial agent, fi, such that de = 6 + ft. In the absence of random excitation input injections from the controller, we have de = ft. In this case, as the nonzero attack disturbance probability p approaches zero, attaining exact recovery requires more samples. The controller can counteract this trend by injecting random zero-mean i..d. Gaussian inputs into the system following the probabilistic sparsity model with probability p'. Under this formulation, de as the combination of é and ft continues to satisfy the assumptions required for Theorem 4 and Theorem 6 The nonzero disturbance probability for de becomes at most p' +p, and the exact recovery remains achievable as long as there exist sufficient time periods when both vectors e₁ and ft are zero, i.e., p' +p<
For the bounded basis functions, the sample complexity is minimized when the nonzero disturbance prob- ability p is set to p" 1/3, as the bound in Theorem 4 scales with p p-1(1 p)-2 As result, it is optimal to inject zero-mean i.i.d Gaussian inputs with probability p' =/= = p" = 1/3 as this value minimizes the sample complexity bound. Furthermore, for Lipschitz basis functions, the sample complexity scales as max p (1-p)) (1]-)) according to Theorem 6 In this case, the optimal p' value is p" = =1/2, mean- ing that it is preferable to inject random excitations approximately half of the time when the semi-oblivious attacks are nearly absent, L.e,, p ss O. Finally, although p is unknown to the controller when the probability of allacks is lower than p" values specified above for bounded and Lipschitz basis functions, injecting excitation signals with zero-mean i.id Gaussian inputs at a probability of p' p" - p will accelerate the exact recovery rate of the system dynamics.
8 Numerical Experiments
We conduct numerical experiments for both the bounded and Lipschitz continuous basis function cases to validate the exact recovery guarantees presented in Sections and Specifically, we examine the convergence behavior of the estimator in (3) under varying values of the sparsity probability p and problem dimensions (n, m). Additionally, we mumerically verify the necessary and sufficient conditions established in Section 3.
Further mumerical experiments exploring additional problem parameters are provided in Appendix C
Evaluation metrics. Given trajectory .r..,, we compute the estimators
AT E arg min gr VI' E (1....,T), AER
where the loss function is defined as gr (r)(())))))))))))) (A)== convex optimization problem using the CVX solver Grant & Boyd 2014]. To evaluate the recovery quality of the estimator for each T', we consider the following three metrics:
ET | - fz122)1l2 In our experiments, we solve the
-
The Loss Gap is defined as gr gr (A) - gr (Ar:). The ground truth is a global solution if and only if the loss gap is 0.
13

---

Published in Transactions on Machine Learning Research (07/2025)
The Solution Gap is defined as |A- - I|. The ground truth A is the unique solution only if the solution gap is 0.
The Optimality Certificate is defined as
min ZER
Σ
112f(x))122 Ea s.t. || 1,
tEK
which convex optimization problem that can be solved using the CVX solver. The ground truth is global solution if and only if the optimality certificate is O.
We evaluate these metrics to assess the performance of the estimator (3) and validate the proposed optimality conditions. For each parameter setting, we independently generate 10 trajectories using the system dynamics in ① and compute the average of the three metrics.
Since need to solve estimator (3) many times (for different trajectories and steps T"), , we consider relatively small-scale problems. In practice, the estimator (3) is only required for T" = T, and we only need to solve single optimization problem. As a result, estimator (3 can be solved for large-scale real-world systems since it is convex and should be solved only once. We provided experiment results for largo-scale systems in Appendix C Next, we explain the experiment selup and the numerical results for the bounded basis functions.
Bounded basis function. Given a state space dimension n, we set 5n and define the basis function as
f(11)
sin(y)
f(x)
where f(y)
E y R.
sin
The basis function satisfics Assumption 3 with B = 1. For each time instance t E K. and for cach i E (I,...,n), the disturbance de, is independently generated by
de, ~ Uniform (-,4)) where c, := min (aa. 0.1),
Here, di, and Te,i denote i-th components of d, and zt, respectively. Since the disturbance distribution is symmetric about the origin, it satisfies Assumption 2 are linearly independent, the non deg-negeyyrycy condition (Assumption is satisfied. Finally, the ground truth matrix is constructed such that
Additionally, the sine functions sin(y), (in())..,,,s(((5))
Eimn π1 sin(kar)
Af(x)
E an,t sin(kr,))
where the coefficients are sampled independently
Ltd. 0, Uniform(- - 1000 100), Vi (L.....nk) n), , k E {l,...,5).
We choose large upper bound for the coefficients 0i (i.e., greater than 1) to illustrate that the stability condition (Assumption 5) is not required in the case of bounded basis functions.
We first compare the performance of estimator Specifically, we set T = 500, n 1 and p (0.7, 0.85). The results, presented in Figure I align with the Theorem 4 In particular, the optimality certificate accurately reflects the exact recovery of the estimator in and the required sample complexity increases as the attack/ woockk/disubbanegg probability grows.
under different nonzero disturbance probabilities p.
Next, we analyze the estimator's performance across different problem dimensions (n, m). We set T 500, = 0.7, and evaluate the cases where n E {1,2,4) 43. The results are plotted in Figure 2 demonstrate that exact recovery requires more samples as (n, m) incrcases, further validating the thooretical results established Theorem 4 After verifying the behavior of the estimator for bounded basis functions, we proceed to simulate its performance using Lipschitz continuous basis functions.
14

---

Published in Transactions on Machine Learning Research (07 (025)
Loss Gap
Solution
Optimality Certificate
109
104
10-1
10-1
-2
-4
10-5
-6-
0.85
10-7
p 0.80
10-4
0.70
-B
0
500
100
500
100
300
500
Loss gap, solution gap and optimality certificate of the bounded basis function case with at- lack/ disturbance probability p 0.7, 0.8 and 0.85.
Figure 1:
Loss Gap
Solution Gap
Optimality Certificate
10a
109
109
10-2
10-2
-10-
4
10-4
-15
(n, m) [1,
10"1
[n, 10)
(n, m) 14, 20)
10-4
0
300
Figure 2: Loss gap, solution gap and optimality certificate of the bounded basis function case with dimension (n, m) = 5), (2, 10) and 24)..).
Lipschitz basis function.
Given state space dimension n, we set m n and define the basis function
VII x 1 +
/ |
+1
f(x)
Va E R",
Vn
V1I In +1
v 1 +1
where I1,....,,, E RR are i.i.d. standard Gaussian random vectors. We can verify that the basis function is Lipschitz continuous with a Lipschitz constant of = 1, thus satisfying Assumption For each time instance t X, the disturbance de is generated by
d= Edd,, where & ~ NNO, of), d, uniform(s*' la and de are independent.
Here, we define of = min min(1]=; 1/n). We verify that the random variable & is zcro-mean and sub-Gaussian with parameter o = 1. Additionally, since the random vector de follows uniform distribution on the unit sphere Sn-1, Assumption X is satisfied. Note that do....,dy_ are correlated, violating the i.i.d. assumption commonly made in the literature. Our disturbance model further implics that the intensity of a disturbance vector (represented by 4,) depends on the current state, which itself influenced by previous disturbances Since the points II are randomly generated, the multiquadric radial basis functions are linearly independent] with probability 1. Thus, the non-degencracy condition (Assumption 1 is satisfied. Finally, the ground truth matrix Á is constructed as UEVT, where U, V E Raxn are random orthogonal matrices and Σ diag(øi,.... an) is diagonal matrix. The singular values a; are independently drawn from a uniform distribution:
Lid. ~ uniform(0, p), Vi (I,...,n)
where p > 0 is the upper bound on the spectral norm of
Functions (1())...... gu are said to be linearly independent if there not exist constants Ci.... such that Et (g)( for all y-
15

---

Published in Transactions on Machine Learning Research (07 (07/202) (025)
Loss
Solution Gap
Optimality Certificate
10
107
Lom
10"1
10"
-0.5
-1.0
10-4
-1.
10
-2.0
0.85
10
10"7
-2.5
1111
y 0
p
10-4
300 500
200
400
100
300
400
Figure Loss gap, solution gap and optimality certificate of the Lipschitz basis function case with at- tack/ disturbance probability p 0.7, 0.8 and 0.85.
Loss Gap
Solution Gap
Optimality Certificate
0.00
10"
10"
-0.25
10-1
10-2
-0.50
10-2
-0.75
10 3
10
On, (3,
10-4
(n. ml 51
(n.
-1.50
0
100
200
300
400
500
100
200
300
400
500
100
200
300
400
300
Figure 4: Loss gap, solution gap, and optimality certificate of the Lipschitz basis function case with dimension (n, () (3,3), (5, and 7).
We first. evaluate the performance of the estimator in under varying values of the sparsity probability p. We set T' 500, n 3, and consider p {0.7, 0.8, 0.85). Additionally, set the upper bound p to be 1, which guarantees the stability condition (Assumption 5). The results are plotted in Figure 3 The results demonstrate that both the loss gap and solution gap converge to zero as the number of samples 7 increases. This implics that the estimator in ( achieves exact recovery of the ground truth matrix A when a sufficient number of samples is available. Furthermore, the optimality certificate also converges to zero simultaneously with the solution gap, thereby confirming the validity of the necessary and sufficient conditions established in Section 3. Additionally, we observe that the required number of samples increases with the nonzero disturbance probability p, which is consistent with the upper bound derived in Theorem D
Next, we evaluate the performance of the estimator in (3) across different problem dimensions (n, m). Specif- ically, we set T' = 500, = 0.75, and 1, while varying n E {,,5,7} The results are presented in Figure We obscrve that as the problem dimension (n, m) increases, a larger number of samples is required to ensure exact recovery. This finding aligns with the theoretical bound established in Theorem
9 Conclusion
This paper addresses the problem of parameterized nonlinear system identification in the presence of sparse- but-large disturbances or semi-oblivious attacks. The non-smooth estimator 3 utilized achieve the exact recovery of the underlying parameter A. First, establish necessary and sufficient conditions for the well-specifiedness of the estimator (3) and the uniqueness of optimal solutions the embedded optimization derive sample complexity bounds for the exact recovery of A under two different conditions: bounded basis functions and Lipschitz basis functions. For bounded basis functions, the sample complexity scales as mn h in terms of the problem dimension and as p1 p)) in terms of the nonzero disturbance probability, up to a logarithm factor. For Lipschitz basis functions, the sample complexity scales as mn in terms the problem dimension and as max -p) p- p) -)11} in terms of the nonzero disturbance probability, up to logarithm factor. Furthermore, we establish that if the sample complexity scales at order smaller than --1 p)- high-probability exact recovery is unattainable.
problem (4). Subsequently,
16

---

Published in Transactions on Machine Learning Research (07/2025)
This result implies that the term p1 p)- in our bounds is fundamental and unavoidable. Finally, we validate our theoretical findings through numerical experiments.
Acknowledgment
This work supported by the U.S. Army Research Laboratory and the U.S. Army Research Office under Grant W911NF2010219, the Office of Naval Rescarch under Grant N000142412673, AFOSR, NSF, and the UC Noyce Initiative. Eduardo Sontag was supported by AFOSR PA9550-21-1-0289.
References
Yasin Abbasi-Yadkori Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 1-26. JMLR Workshop and Conference Proceedings, 2011.
Laurent Bako. On a Class of Optimization- Based Robust Estimators. TEEE Transactions on Automatic Control, 62(11):5990 5997, November 2017. ISSN 0018-9286, 1558-2523. doi: D0.1109/AAC:2011.27700000
Laurent Bako and Henrik Ohlsson. Analysis of nonsmooth optimization approach to robust estimation. Automatica, 66:132-145, 2016.
Dietmar Bauer, Manfred Deistler, and Wolfgang Scherrer. Consistency and asymptotic normality of some subspace algorithms for systems without observed inputs. Automatica, 35(7):1243-1255 1254, 1999.
Dimitris Bertsimas and Martin S. Copenhaver. Characterization of the equivalence of robustification and regularization in linear and matrix regression. European Journal of Operational Research, 270(3):931 942, November 2018. ISSN 0377-2217. doi: 01001//..joor2201....00..
Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37 37,, 2011.
Han-Fu Chen and Lei Guo. Identification and stochastic adaptive control. Springer Science & Business Media, 2012.
Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Bridging convex and nonconvex optimization in robust PCA: Noise, outliers, and missing data. Annals of statistics, 49(5),2948, 2021.
Christian Clason. Nonsmooth analysis and optimization. arXiv preprint arXiv:1708 141.:100000001800 2017.
Sarah Dean, Stephen Tu, Nikolai Matni, and Benjamin Recht. Safely learning control the constrained linear quadratic regulator. In 2019 American Control Conference (ACC), pp.
TEFF, 2019.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-61) (79-633--79, 2020.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time identification in unstable linear systems. Automatica, 96:342 353, 2018.
Han Feng and Javad Lavaci. Learning of dynamical systems under adversarial attacks. Tn 2021 60th TREE Conference on Decision and Control (CDC), pp. 3010 3017, 2021. doi: 10.109/CDDC4548422211..oo 968344
Han Feng, Baturalp Yalcin, and Javad Lavaei. Learning of dynamical systems under adversarial attacks null space property perspective. In 2023 American Control Conference (ACC), pp. 4179 4184, 2023. doi: 10.23919/AAe ACC55779.2022 201179991.222..11111666 10156016.
Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Learning nonlinear dynamical systems from single trajectory. In Learning for Dynamics and Control, pp. 851-861 861. PMLR, 2020.
Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. https://cvxzr com/cvx/ March 2014.
17

---

Published in Transactions on Machine Learning Research (07/2025)
Dong Huang, Ricardo Cabral, and Fernando De la Torre. Robust regression. IEEE Transactions Pattern Analysis and Machine Intelligence, 38(2):363-33) -75,, 2016. doi: 10.
A Kumar, A Levine, and S Feizi. Policy smoothing for provably robust reinforcement learning. In International Conference on Learning Representations (ICLR), 2022.
Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for non-stationary mixing processes. Machine Learning, 106(1):98-117, 2017.
L Ljung, R. Pintelon, and J Schoukens. System identification: Wiley encyclopedia of electrical and electronics engincering. In System identification: frequency domain approach, pp. 1-19. John Wilcy & Sons Cham, 1999.
Lennart Ljung and Bo Wahlberg, Asymptotic properties of the least-squares method for estimating transfer functions and disturbance spectra. Advances in Applied Probability, 24(2):412 140411224001101 1992.
Thomas M Moerland, Joost Broekens, Aske Plaat, Catholiju M Jonker, et al. Model-based reinforcement learning: A survey. Foundations and Trends in Machine Learning, 16(1):1 118, 2023.
Jean-Philippe Noël and Gaëtan Kerschen. Nonlinear system identification in structural dynamics: 10 more years of progress. Mechanical Systems and Signal Processing, 83:2 35, 2017.
Robert D Nowak. Nonlinear system identification. Circuits, Systems and Signal Processing, 21:109-122 2002.
Afshin Rostamizadeh and Mehryar Mohri. Stability bounds for non-iid processes. In Neural Information Processing Systems (NIPS), 2007.
Yahya Saltar and Samet Oymak. Non-asymptotic and accurate learning of nonlinear dynamical systems.
Journal of Machine Learning Research, 23(10)):1-45 49, 2022.
George AF Seber and Alan J Lee. Linear regression analysis. John Wiley & Sons, 2012.
Max Simchowitz, Horia Mania, Stephen Tu, Michael Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. In Conference On Learning Theory, pp. 439-473. PMLR, 2018.
Anastasios Tsiamis and George J Pappas. Finite sample analysis of stochastic system identification. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 3648 3354.. IEEE, 2019.
Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J. Pappas. Statistical learning theory for control: finite-sample perspective. IEEE Control Systems Magazine, 43(6) 2023. doi: 10.1109/ (CCS.203333310444
Roman Vershynin. Hligh-Dimensinn Probability: An Introduction with Applications Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi:
10.1017/9781 10.0017/97810082115666 108231596.
Martin J. Wainwright. High- Digeeniimnnii Statistics: A Asy-toymito Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/978110862277
Fan Wu, Linyi Li, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. Crop: Certilying robust policies for reinforce- ment learning through functional smoothing. In International Conference on Learning Representations, 2022.
Huan Xu, Constantine Caramanis, and Shie Mannor. Robustness and Regularization of Support Vector Machines. Journal machine learning research, 10(7), 2009.
Baturalp Yalcin, Javad Lavaei, and Murat Arcak. Exact recovery for system identification with more corrupt data than clean data. arXiv preprint arXiv:2305.10506 2023.
Ingvar M Ziemann, Henrik Sandberg, and Nikolai Matni. Single trajectory nonparametric learning of non- linear dynamics. In conference Learning Theory, pp. 3333 3364. PMLR, 2022.
18

---

Published in Transactions on Machine Learning Research (07 (075)
A Comparing Results to Existing Work
Example 1 (First-order systems). In the special case when m 1 and the basis function f(x) I,
condition
reduces to
Edito d S
|acbb
YEE
tEA
which is the same as Theorem in Feng & Lavaci 2021
Example 2 (Linear systems). We consider the case when also assume the A-ppced disturbance model; see the definition in Yolcon et al. (2023). By considering the disturbance period starting at the time step t,, a sufficient condition to guarantee condition is given by
and the basis function is f(z) We
2-2
2' de, S
Σ 2AA'd 11, t=
AA E R
(13)
where denote d : de, for simplicity. Let D E (ax(n-1) be the matria of orthonormal bases of the orthogonal complementary space of f, namely, DT = 0, DTD In-1, and DDT I, 5.-de -dddd Then, colculate that
2 11 (ZA'dr)) dd (ZA'd.,)
where the equality holds when DJ 7 0, i.e., ZA is parallel with d. Therefore, for condition hold, is equivalent to consider Z with the form dzl for some vector 2 R". In this case, condition
13
13
reduces
2 A dr, I
Σ 2 |=T''de,, E
(14)
Condition 14) leads to a better sufficient condition than that in Yolcin et al. (202)). To illustrate the improvement, we consider the special cose when the ground truth matria is A AI, for some X e TR. Then, condition becomes
A 1-
1 A
which further equivalent to [ + + 2,
which is stronger condition than that in Yalcin et al. 2023 When the disturbance period A is large, approzimately have |\| 2- which is better condition than that in Figure 1 of Yalcin et al. (2023).
Example 3 (First-order linear systems). In the case when m and f(x) x, our results state that the uniqueness of global solutions is equivalent to
Σ de
<
lxcl-
(15)
KER
tEKo
As comparison, the sufficiend condilion in Theorem 1 in Feng & Lavuei 2021 is
Σ
[z1).
tEk
tEk
Since (d = for all E K,, our results in Feng 8 Lavaed 2021))
15
as well Theorem are more general and stronger than that
19

---

4 is convex in A, the ground truth matrix A is global optimum if Published in Transactions on Machine Learning Research (07 (07/202) 2025)
B Proofs
B.1 Proof of Theorem 1
Proof of Theorem 7 Since problem and only if
0E Σ *EK
f(x)) @ 0ll0,112 - Efai) @ dr.
(16)
tEK.
See Theorem 4.5 in Clason subgradient of the zo-nor,, condition [6) holds if and only if there exist vectors
(2017) for the proof of the above optimality condition. Using the form of the
9t E ER, E 10
such that
E (at)ge + E((x) Onxmi tE
1lal 11,
Vt V
(17)
Define the matrices
B [f(a)) VE E E (T V := [f(x)) WEE R=
= [gt VE E E (X)
F: [d. At K] E RTx
Condition 17 can be written as a combination of second-order cone constraints and linear constraints:
3G (x E s.t. BG VFT 0mxn:
|Ga S 8, Vt,
str= 8, 8,
(18)
where G. the t-th column of G for all Ee fl..... T | We define the closed convex cone
S : SER (T-
Σ (r- -10ett S SIT-IDD)+ Vt E (O. | - 1},
2 -KInn++++ 2(T [K1]n++ 2 0
and we define the matrix and vector
(VFT)
(VFT) ),,
Ia
B
0
0
A
R
b
R mm=+1
0
1 1
(VFT)
where (VFT).s Ja is the i-th column of V. Then, condition 18 can be equivalently written as
3s E T (T-1a)++2 s.t. A= E.
(19)
Since the cone is closed and convex, we can apply the generalized Farka 's lemma to conclude that condition 19h is equivalent. to
Vy E mn--1
Y - bb220)
(20)
20

---

Published in Transactions on Machine Learning Research (07/2025)
where S is the dual cone of S. It can be verified that the dual cone is
T- K
8" E RTT--K]]44
Σ
(r- [0]]itt S ( (h
1K 20
2=
We can equivalently write condition
20
VZ R=x PEE. R,
(1ZBI12.1 P. P20 D20=(VF',2) sp)
By climinating variable p, we get
(VFT, _ S | 2,1,
VZ e Raxm 2,1,
where the form is defined as
m
M =
M
VM E
The above condition is equivalent to condition 5 and this completes the proof.
B.2 Proof of Corollary 2
Proof of Corollary
2 We choose
Z: ΣnEK Eiexdef(xx)) dxz( Lrex des( F
Then, condition 5
implies
Σ [xx)dd
Σ d. 25(x)) Σ 11 S I1Saa))
BEX
LEK
EEKc
SEKe
where the last step is because case, have
1/||2 5 || F 1. Now, suppose that the basis dimension is 1. In this
Σ J Zf(xi)
Σ fls)dd
z = Σ
f(xr)d
11
tEK:
MEE
IEK
Σ 11 Σ
Σ
tEK
LEK
tEK
Combining the above two incqualitics shows that condition
7 is also a sufficient condition.
B.3 Proof of Theorem 2
We establish the sufficient and the necossary parts of Theorem 2 by the following two lemmas.
Lemma 1 (Sufficient condition for uniqueness). Suppose that condition 5 holds. If for every nonzero Z E Iaxm such that
Σ tEK
d. Zf(x)) Σ [12l(22
tEk
it holds that.
d.. 2f(xe)
Σ (Zf(zi)2
KEK.
tEK
Then, the ground bruth matrir A is the unique global solution to problem
21

---

Published in Transactions on Machine Learning Research (07/2025)
Proof. The ground truth A is the unique solution if and only if for every matrix A E R= such that A # A. the loss function of A is larger than that of A, namely,
Σ EER
||dll2 < Σ I(A ()f()))
Σ
II(A ()f(xx) + dell2.
(21)
rEKe
tEK
Denote
Z A A A"R=
The incquality
21 becomes
-1- + Σ (11 Zz(zz) + +dell - lidella) > 0.
(22)
tE
tEK
Since problem (4) is convex in A, is sufficient to guarantee that A a strict local minimum. Therefore, the uniqueness of global solutions can be formulated as
condition 22 holds,
ZA
R s.L. 0 < | e,
(33)
where 6 a sufficiently small constant. In the following, we fix the direction and discuss two different cases.
Case I. We first consider the when condition 5 holds strictly, namely,
Σ
1Zf(r))
-
d. 2f(zz)) >0. 0.
KE
rek
Since the f--nom is a convex function, it holds that
|| - 2f()) + d,l22 |1 2 (811dell2 -Z((z)) -d, (5(x)).
Therefore, we get
Σ -1 Zf(x))l2++ + Σ (1I - Zzxz)) + +2ll2 -1dbll2) 2 Σ - 2f(x)l22+ + Σ -J 2f(xt) >0 0.
tEA0
tE
te
AEK
which exactly leads to inequality
22
Case II. Next, we consider the case when
= Σ [z
Σ tEK
J zf(ztt)
< Σ
12f(2))ll2
(24)
tEK
teke
tEK
Since e is a sufficiently small constant, we know
a==o 00, Va E [0.
and the norm is socond-order continuously diffcrentiable in an open set that contains the line. Thercfore, the mean value theorem implies that there exists a [0, 1] such that for each t e K,, it holds
- 2fxx) + dell2 l|de l2 = (dc. 2 1- (-Zz(zz)]]
I
de (dit)
[- 7f(xx)))
(25)
| 1
We can calculate that
de
(
T
(de Zf(x)))
[-Zf(xx)]
| Z (x,))
0.
(26)
||0
|| 3|
||d%
d 18
22

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where the equality holds if and only if (x))) is parallel with di. By the definition of dž, the equality holds if and only if (xx)) is parallel with d,, which is further equivalent to
(d.zf(e))) 2 2
Substituting 25 and 26 into [22]
we have
Σ1 AEK
11 + Σ (1 =f(x)) + -
2 Σ
12f(at))l2- (de, =0,
tEK
tEK
where the equality holds if and only if
K 2 =12
W
Considering the second condition (2), the above equality condition is violated by some E Therefore,
we have proven that condition (22) holds strictly.
Combining the two cases, complete the proof.
Next, we prove that the condition in Lemma also necessary for the uniqueness.
Lemma' 2 (Necessary condition for uniqueness). Suppose that condition A is the unique global solution to problem then for every nonzero Z E Raxm we have
5 holds. If the ground truth matrix
Σ d, Zf(x)) t
[zf(z))l2
Σ tEk
d. 2f(aa)
(27)
tEK
tel
Proof. Assume conversely that there exists a nonzero Z E Ruxm such that
Σ Ed Σ |Zff(z))l2
Σ
J7 Zf(x)))) = E12zf(x)12
(28)
IeK
tEK
tEK
Without loss of generality, we assume that
0
7 2 Sc
for sufficiently small e. In this case, the second condition in 28 implies that
JJ 2f(=)) [zx)ll),,. and
Zf(xt) is parallel with de Vt K.
Therefore, when is sufficiently small, equations
26 and 24 lead to
- Zf(x) + del12 - ||da (de, zf(a) V.
We now show that condition (22 fails:
Σ 11-2f(r)le + Σ (11 Zz(z)) + dell2 -112l12) = Σ > (dr, - Σ E(át (d. (f(x)))))) 0.
tEK
tER
tEk
This contradicts the assumption that is the unique solution to the problem
Combining Lemmas and 2 we have the following necessary and sufficient condition for the uniqueness of the ground truth solution A.
23

---

Published in Transactions on Machine Learning Research (07 (07/2025)
B.4 Proof of Theorem 3
Proof. Without loss of generality, can assume that is full-rank. Otherwise, the system space can be reduced to the subspace spanned by A. Similarly, we assume that A is diagonalizable, such that A = PAP-1. If this not the case, define A = A + cI, for a sufficiontly small c to ensure diagonalizabilit. Taking the limit as e + preserves the validity of the argument.
We redefine the linear system updates 2++1 Ar, de as follows:
J++1 Az, + de + u Ad; +d,
where ā. = P- and = P-1d. This transformation can be thought of as coordinate transformations in n dimensional space. Thus, we can establish the result for the LTT systems with a diagonal ground truth matrix A, whose diagonal entries are AI..... An. this case, the system update equations decompose into n separate equations of the form: E1+1 X + di Vi .n...,n were i is the i-th element of the system state at time in the new coordinate system.
Now, suppose that the nonzero disturbance vectors are chosen from the subspace D ;- {d: Pd DJ where D = fd d= P p d = -}. Due to the constraint on the first entry of the d, d', the subspace D has dimension less than n. Consequently, since p-1x- = =i = 0, it follows that o = 0, Vt 2 0. Note that setting the first entry to zero done without loss of generality, as this argument applies to any coordinate or any subset of coordinates.
Next, define Å the diagonal matrix with diagonal entries (2,, Ag,..,,...... An)) where Å λ1, where all the diagonal entries identical to those of A except for the first one. Suppose that start two dynamical systems with ground truth matrices Ā = PAP-1 and Å PAP-1, where the nonzero disturbances (de 2--1 are chosen from D. Since ž = 0, vt 2 0 in both systems, their trajectories over time must be identical, i.e., {ielT=o the same for both systems.
Suppose, for contradiction, that there exists an estimator that uniquely recovers À finite time T, given by:
A E arg min g(A; o2 AeDing(n)
where the docision variable A is restricted to be a diagonal matrix. Since À is the unique solution, we must have
eA1 (a))_0)) o(Ā; (z))
However, since the objective function g(A; (T depends solcly on the system state over time, and these states identical for both systems, it follows that g(Ā; (2,)E=)) g(A: (o))))) This contradicts the uniqueness assumption of the solution, which concludes the proof.
B.5 Proof of Theorem 4
Proof of Theorem Since both sides of incquality 9 affine in Z, it suffices to prove that
IP [z) dz(2) O, ZZ E Sp] 1 1-
(29)
where Sy is the Frobenius unit sphere in a and
d dz)z) = E(z ((x))d))) dz(2)== == Σ [15((z)]22
TEX
LEK
The proof is divided into two steps.
Step 1. First, we fix the vector Z E Sr and prove that
P (Z) dz(Z) -0] 1 1-
24

---

Published in Transactions on Machine Learning Research (07/2025)
holds for some constant 0 >> 0. Using Markov's incquality, it is sufficient to prove that for some 0, it holds that
exp (v - & cxp(-v0)6.
E
(30)
We focus the when K. is not empty, which happens with high probability. The proof of this step is also divided into two sub-steps.
Step 1-1. We first analyze the term (Z). Let T" be the last nonzero disturbance time instance, i.e.
T' = max(t LEK).
Then, we have
E exp udi (2)
=E exp Σ (ERMTT
(z (o)a)) E exp ( (ZT, ((rr)))))))))) Frr
[oxp
(31)
According to Assumption 2 the direction dr is unit vector. Since
[2f((T))] dr s [Zf((r)) - fllT) s / vmB,
the random variable [Zf(xr))] dy. is sub-Gaussian with parameter mB². Therefore, the property of sub- Gaussian random variables implies that
22² (=--²) mBB exp
p (z
(zTT ((TT)ddT)))
|
exp
2
Substituting into
31 we gel
(3. (..oaaa
(22 mB2
E exp
pd (2)
5 E
exp V BEKA(TT)
Σ
exp
Continuing this process for all t K,, it follows that
112 m...BaI
E exp vd
(2)]
S exxp
(32)
Step 1-2. Now, consider the second term in 30 namely, -dz(2). Define
K²: = (1 |1sIST, LEKE 1- EE
With probability at least - exp(- - p)T]} we have
|K'| = 0 - T)
Therefore, K' is non-empty with high probability. Since f 2 0 for all t E 109, we have
(xx()))) ]
E exp
L-dz (2)
< E exp -v Σ
(33)
IEK'
=F exp
Σ
||(s(x)]]2
x E [exp (-ull )112) Fro
(EX"((T)
25

---

Published in Transactions on Machine Learning Research (07 2025)
where T is the last time instance in K', namely,
T' := max I E K').
By Bernstein's inequality
(Wainwright 2019
we can estimate that
v²
E (exp (- Fr] S exp
-/E (IIZf(ET))le Fri) |
- (l22((ITT) 1 Fr.)
2
+ v²
< eexp
E (11 > 12 Fr)
B [ (T 113 11
vmB
2
where the last incquality is from Assumption implies that
[ff S VmB.
E ((I Fr.) (77 ((TT))((T)) Frr) 2 2 = 22
If we choose v such that
0< 2
(34)
vmB
we have
)
[epp ZfTT)
[ri] S exp
sxxp
vmB
Substituting into inequality
33 it follows that
122 -
E
exp
(udd(2))
< E exp
Σ [13s(z))]22
x exp
v
12
/mB
TEAT((T))
Continuing this process for all t K,, we have
[(-
12 -
E
exp
- vdg (2)
$ exp
(35)
VmB
Combining the inqqualities
and 35
we have
my B²
/ 222
E
exp v
[z) dz(() ds(())) s exp
|C] +
x21131
2
vmB
We choose
= p2p(1 - P)T
4/mB
In order to satisfy condition (30), it is equivalent to have
2 B²
(v²
X²vp(1 PTT
|C
X x211'1
I sog(()) (6)
(36)
2
vmB
4/mB
Now, consider the fact that K. is generated by the probabilistic sparsity model. Using the Bernoulli bound, it holds with probability at least 1 - exp(-O(p(1 T]] that
KK'| > p(1 - T)
[C| < 2pT,
(37)
2
26

---

Published in Transactions on Machine Learning Research (07 (07/2023) /025)
Thus, with the same probability, we have the estimation
mu² B²
v² 2
XPrp(1 p)T
mv² B
2 2pT + (v²
( 122
p(1 P)T
|0 +
VmB x
X².
2
4/mB
2 2/mB
2
Note that the inequality holds for the term containing K' since the coefficient is negative under condition Choosing
34
A² p)
v =
2 2/mBl4mBB B² + A2 p)]
get
mw² B
22
XZrp(1 D)T
p(1-p} T 16mm (4mmx2 + +1-p) p)
110 +
X2 K2
VmB
4/mB
where we define : B/X 2 1. Note that our choice of satisfies the condition inequality 336 to hold, the sample complexity should satisfy
(34). Therefore, in order for
16mx 16mx²(44m* (4mx² + p)
log T
p p)
By considering the Bernoulli bound
37
the sample complexity bound becomes
mx² (mx² +1 - p)
p(1 p) log 1
T = Ω max
(38)
p(1
p)2
m 2
?
log
pp1 (1
2)
Step 2. Next, establish the bound 29 by discretization techniques. More specifically, suppose that
0 is constant and ( zNJ Sp is an e-net of the sphere Sy under the Frobenius norm, where can bound
log(N) S mn log 1 11+2)
Then, for every 7 E Sr, we can find a point in the enet, denoted as Z', such that
2 Z'I <.
Now, we upper bound the difference f(Z) - f(Z',, where we define the function
f(2) = (z) dz(2), VZ ma
We calculate that.
= Σ dglz -Z')f(2)) - Σ (1Zff(z))lz ((x))l))
tEK
tEK.
Σ
delz Z))((z)) + Σ
I1( - 22))(xx)l
tEK
teKs
Σ 1| - 2(11 Il
Σ
2 - (>1))
TEK
LEK
Σ 11 - Z'Il=llf(zallla +
Σ
2 2'11)11f<x)lll
tEK
tEK
TT.cmmB- C.
T
We choose
p(1 - p)
6= VmTB
mn?
27

---

Published in Transactions on Machine Learning Research (07 (07/202) /025)
Therefore, under the event that
f(Z)) -0, vi= N,
(39)
have
f(2) - VmTB.c=0, ZA E Sp.
Hence, it suffices to estimate the probability that event (39 happens. To bound the failing probability, we replace with 6/N in (38) and follows that
5 N P P[J(Z') < -6] 21
=i= 1...,...,N N.
Applying the union bound over all i e , N), the event namely,
39
happens with probability least
P [f(Z') 0 Vi 1, M 2 1 - 8.
With this choice of 8, the sample complexity should be at least
=²k4
N
m m²
MK
T = Ω
log
Ω
mm log
+ log
p(1 2)2
p(1 p)²
p(1 ((1-2)
This completes the proof.
B.6 Proof of Theorem 5
Proof of Theorem We only need to show that condition We choose the matrix
S fails with probability at least 1 - cxp(-m./p))
1
0 01x(m-1)
=
E R=
On-1
O(n- ((=-1)x(m-1)
As result, the last n 1 elements of Af(z) are zero for every state E IR.. Moreover, we will choose the basis function f such that its values will only depend on the first element of state x E R With these definitions, the dynamics of x, reduces to the dynamics of its first element (It)1. Hence, we can assume without loss of gencrality that n in the remainder of the proof.
We define the basis function ʃ IR + R as
f(x)
1 sin(T) s2x)
sin((m- - 1)xr] Vo E R.
Under the above definitions, it is straightforward to show that the following properties hold, and we omit the proof:
f(0) = Oms f [AA(=)] = f(x), Vr E.
(40)
Finally, the attack attack/disturie disturbace vector defined as
F.F. ~ Uniform [[-(1z]] + 2x), - (13,1 + T)] U [[xd + n, lxell + 2m/h, Vt K.
The remainder of the proof is divided into three steps.
Step In the first step, we prove that Assumptions 1 hold. By the definition of f(x), we have
[xxx)) max [ac|
max {[z], 13 sin(2)), |sin((m ())]] $1, Yo R
which implics that Assumption 3 holds with B 1. Morcover, the semi-oblivious condition (Assumption is result. of the symmetric distribution of F.F.F.
28

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Finally, prove that Assumption I holds. For the notational simplicity, in this step, omit the subscript 4, the conditioning on the filtration Ft, and the event t E K. The model of disturbance vector d implies that
I d
ld]
|
TT>
Therefore, we have
f(z d)
xtd b+d
sin[(x d)]
sin((m 1) + +d]]]
For any vector V E R", we want to estimate
+ d v1
m-
-=
U41 aili(( d)]
x d
First, can calculate that
E
V1
+ d + d
2
u2, E | sin[i(<r + d)]] 1221 '2'
1
vi (l....,m-11
(41)
Then, for every i e {1.....
1}. we have
E
+
Vi+1 sin[i(a + d)]
(42)
[x|
x + d
flaltex x +
=/14
sin sin(i(2: d)] dd + |ul+x I d
sin [n[i(x + d)) dd
1x x + d
|0|-n
sin|i(( - d)] dd + platee
=1/1/11
sinfi(r + d)] dd 0.
1lx|-2x
|2|+x
For every i,j E {1...., m 1} such that + j. it holds that
E [14+1 sin[i(x + d)] 15+1 sinlj(x + d)]] -V4114++1
sin|i(æ + d)] sinlj(æ + d)] dd
(43)
1m)-2r 2x
glultan
sin[i(x dd) + d)) dd
Combining equations 41
43 it follows that
[[ d)5(s +d) 1=
Σ iml
u 2 |0
which implies that Assumption holds with X² 1/2.
Step 2. In this step, prove that the linear space spanned by the set of vectors
F == ( (tEr)
has dimension at most m 1 with probability at least - 5. By the second property in 40 the subspace spanned by F is equivalent to that spanned by
F' = (1 ((EK))
where we define
K' = -'= (ek]), Therefore, the dimension of the subspace is at most IC'
29

---

Published in Transactions on Machine Learning Research (07 (07/2025)
To estimate the cardinality of K', we divide K into the following two disjoint sets:
Ki (2t 1 2t K, 28 +11E,") := (2t 2t 1 E K, 2t E k.)
The size of K2 is the sunmation of [2/ independent Bernoulli random variables with parameter p(1 p). Therefore, the Chernoff bound implics
T
p p(1-p) p) 3
T 2
P
| 2p(1 p)
1 exp
(44)
Similarly, the size of KY is the summation of [T/2] independent Bernoulli random variables with parameter p(1 - p). Therefore, the Chernoff bound implies
T
p(1 p)
T
P
2p(1 p)
exp
(45)
3
2
Combining the bounds
44 and 45 and applying the union bound, it holds that
p(1 p)
T
p
T
P[KK'| < 2p(1 p]T]
exp
exp
3
2
p(1 p)T
exx
where the last inequality is because
[T/2] [T/2] < T. Since
T 2p - p)
know
P PIKK < m] 2 - exp (-m/3).
(46)
In addition, when IC is the empty set the full set {0..... --1 the set K' is an empty set, which implies that [C'] is smaller than This event happens with probability
1}.
+ (1 p)_ 2 2[p(1 p/)
p
Combining with inequality 46
we get
{ - 2exp (-m/3), 2/)(1-
P [[Cc < m] 2 max
Step 3. Finally, we prove that if the dimension of the subspace spanned by F is smaller than m, the condition (8) cannot hold. Since the dimension of the subspace is at most 1, there exists Z E Im such that
2f(z,) = 0, Vt E K.
With this choice of Z, the condition the left-hand-side of g holds while the strict incquality the right-hand-side fails. Therefore, know that A is not the unique global solution to 44
B.7 Proof of Theorem 6
Proof of Theorem The proof is similar to that of Theorem Since both sides of inequality 9 are affine
in Z, it suffices to prove that.
IP -Z) dz() < O, VZ E Sr] 2 21
where Sy is the Frobenius-norm unit sphere in a and
dz) : Σ T (T, s(x))d)) dz(2) = Σ |1Zf(x;)12
EEK
tek
The proof is divided into two steps.
30

---

Published in Transactions on Machine Learning Research (07 (07/2023) 2025)
Step 1.
First, we fix the vector Z E SF and prove that
P (Z) - dz(z) < -0) 21
holds for some constant 0 > 0. The proof of this step is divided into two steps.
Step 1-1. We first analyze the term dz( For each Is E K, we define the following disturbance vectors:
de it v fo...., T-1,
d
On otherwise,
Then, we define the trajectory generated by the above disturbance vectors:
z 0m
o Af(xt) di, Vt T 17.
Let
==
where the elements are sorted as k, h2 ... kpp. Under the above definition, know x, Api all t. We define
23 for
ge #i (
if 1, i
Ve (K,....,KII}
We note that g. is measurable Fky Using these introduced notations, we write (Z)
|K
K
d - Σ f(z,
)ol,
Ri 9kg
Zo
1=1
t=1
E=lj=tt
Then, Assumption 6 implies that d, is sub-Gaussian with parameter conditional on F, Now, estimate the expectation
E exp pdd [2)]]
where E R is an arbitrary constant. First, for each E {l,..., |K| - 1}, we estimate the following probability:
KC
IP
Zgke
2 Fir
j=t+1
Since de, is unit vector and ||||| = 1, we know
[ =,, - |1 11a11 S 1122 1.
(47)
Moreover, we can estimate that
g || [( - f(2k) ke- 1//
$ <L -
Ikb k ||
(48)
- ||A|| [5 [f( (o -
ke
-)1 S pllll (=)tr-) - { ke
2
W <(pL)) | - =k -1
he-1
11
S ... S L(pL) -ke-1
- kkst1
kz-
kk++1
- 110kl11ckell 12.
31

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where the first inequality holds because has Lipschitz constant L, the second inequality is from ||A||2 S p and the last equality holds because
k2 + dee: Aʃ (Th2
ke = AS (Tke :) xk++1
As
ke (Tks)
By the nub--Gussian assumption (Assumption G). it holds that
1/²
IP
| 12 2 1)
Fice < 2exp
bn 2 O.
(49)
2
Combining inequalities
47
49
we get
K
P
Σ j=L+1
d
z
ke 9kg
2
Fkg
SP
Σ
9kj
2c
c
Fka
2
1=t+1
S
Σ
L(pL)
11 2e e Fke
he-
1=t+1
(1 - 1-pT)2e2
TP
| 2 Fike $ 2exp
(50)
1 PL
20 L22 (pLp))
where Aj kg ---11 and the second last incquality is from
[C
L(pL)' L(pl) 1 PL
Σ
((pL)
1=1+1
i
Since
K dky
E
ZyNs
Five = 0,
j=t+1
incquality 150 implics that the random variable Ej or. TT kr is zero-mean and mub-Gaussian with 9k, parameter Lf pT)) conditional on Fkg- By the property of sub-Gaussian random variables, have
E
exp
dky
Re go
FRe
S exp
Vv 2 0.
2(1 - pL)2
j=t+1
Finally, utilizing the tower property of conditional expectation, we have
1K|-2
[C
K
E
exp pdg (Z)
= E
exp
ki Zg
E
exp
J
ks Zgks
FRINI-1
(51)
E=1
j=t+1
|=
1 [K]
22202L² (pL
< EE
exp
Σ f=1 j=t+1
Jz. Zgkz
exp
2(1 -p
1202L2
< ... < exp
Σ jEK
(BL)20/
V. 0.
2(1 pL)²
Since the random variable (pL) is bounded in [0,1] and thus, is sub-Gaussian with parameter 1/2. Therefore, with constant number of samples, the mean of (pL)24; will concentrate around its expectation, which is approximately
Σ p(1 - 2(1-
1- (1 (pL) S p
p
1-
32

---

Published in Transactions on Machine Learning Research (07 (07/202) 2225)
Then, the bound in 51 becomes
E exp pdg (2)] 2 exp
44 2 0.
(52)
2(1 pL)3
Applying Chernoff's bound
52 we get
P (Z) S 2 exp
(1 (1- pl.js
.2) |
VC 0.
(53)
20 2002LppKK]
Step 1-2. Next, we analyze the term dz(Z). Define the
:= = {1 11SIsT LEK' L- EEK
With probability at least - exp(- - p]T]], we have
|C'| 0pp(1 p)]]
Therefore, K' is non-empty with high probability. Since [x 2 0 for all t e ICS, we know
dz(Z) Σ [z)(2))
To establish bigh-probability lower bound of (z) we prove the following lemma.
Lemma 3. For each E K', it holds that
P Plff(Ez)ll
2 2
L'LA
where 1/1058 is absolute constand.
ext For each K", let 1, be the indicator of the event that []] || larger than the
o' -qu--iueeele condit ional
Fr, Then, holds that
P(1. = 1 Fi) = P(1, = Fi) 04L4
Therefore, we know
cx* o+ 1, - l lEK]
is a martingale with respect to filtration set (Fr, i E K'}. Applying Azuma's inequality, it holds with probability least - expp- (x)))) that
Σ1 1 c\'KK" TEX' 20
cx1jK"| 2 elements in K", the event that || [z (2;) ||2 is larger than the o quantile
which means that for at least conditional on Fe happens. Using the lower bound on the quantile in Lemma we know
cA4K31 X + (I3) |Zf(r)))2>
cA5
20- -0 = 40
(54)
2 2
KEK!
holds with the same probability. Combining inequalities
(53
and
54
we get
(1 - 3
)
PP
f(Z) Sc
2 - exp
-exp -
1,4
20
33

---

Published in Transactions on Machine Learning Research (07 2025)
where we define - dz( Choosing
c1 c
:: 80
it follows that
cX21K31
(1 (1- _
-o
I
f(2) - 84
2 1 - exp -6)
11 1
exp
(55)
By the definition of the probabilistic sparsity model, it holds with probability at least 1 exexp/- that
p)
T]]
p(1 - -PP |C|
[C| S 2yT,
(56)
2
Therefore, the probability bound in 55
becomes
P ([112)s- cAºp(1 p)T
(1 - 21) -D)PT) )
21 -epp
exp
-
160 L
o 110
(N'(1- - p)T
] expl exppp-Opp(1 -p]]]]]]]]
-
cxp
L+
Now, if the sample complexity satisfies
10
a² - p) p(1 - p) { log (
T = Ω max
(57)
(11
we know
P[[(2) S -0] 2 1-
(58)
where we define
aL. 0: c1 PTT
16
Step 2. In the second step, we apply discretization techniques to prove that condition 58 holds for all
Z E Sp. For a sufficiently small constant > 0, let
|z !Z.....ZZN
be an e-cover of the unit ball Sp. Namely, for all Z E Sp, we can find r E (1,2...., N) such that |Z-2""l s It is proved in Wainwright (019)) that the number of points N can be bounded by
log(N) < mn log (1 1 2)
Now, we estimate the Lipschitz constant of f(Z) and construct a high-probability upper bound for the Lipschitz constant. For all Z, Z' E paxm we can calculate that
(ZZ))((z))
Σ (2 ,((:))d))
Σ (lIz((z))l2 - -1z' ((x))l2)
tEt
tER
$ Z 1 FF Σ
f(xr)d
+ +1 Zlll2 Σ l1f(2z))22
tEk
tek
$ < Z Σ |=
(59)
34

---

Published in Transactions on Machine Learning Research (07 (025)
Using the decomposition in Step 1-1, we have
(wx) Σ
9t
where ky is the maximal element in K such that hg < t. Therefore, we can calculate that
T-1
K
Σ
(60)
j=1 x
For each E {I...., [K]], we can prove in the same way as
48 that
Ry gt
s -(pL))---1111 Id 11a,
vt ky-
Substituting into incquality 66
follows that
T-1
[4
L
- ll2 1
|| d 1la.
PL
j=1
Using Assumption and the same technique as in 51 we know
AC
P
dd lla Sn 21 - eexp
2 21 - 1-2exp
20
4022p
where the second inequality is from the high probability bound in
56 Hence, it holds that
172 pL)
PP Σ lf(x)))l2 =n
2 21- 2exp
(61)
40 L2pT
Choosing
= 2
the bound in 61 becomes
0
(1 pL)
IP
Σ 11(x)))
2 2exp
40 Lo 0²)
(62)
26
(1- pL)²
(A-p(l- p)T
2exp
4a T.2T22
(1 pL) 10 p(1 - pp
2exp
22
We set
c θ [/)1-p])3300(1 ppp
Then, it follows that
[1 2 2=200ppp 2T
exp ( S c
exp
2
35

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where the last inequality is from the choice of T in
57
Substituting back into 62 get
0
P Σ
(l S
663)
2c
2
Under the event in 63 for all Z E SF, there exists element Z" in the e-net such that
f(z) - f(z'(())))))))))r)) te Ellf(a)l $ f(Z)) 2
1=
If we replace 8 with 6/(2N) in 58 and choose 7 = z" for all E ,I,...,,, NJ, the union bound implies that
=f((z) -0, r 1...., N 2 1 2
(64)
Under the above conditions, we have
f(2) - f(Z") +
2 5 2
< 0.
To satisfy condition
64
the sample complexity bound
57
becomes
10
A: log
2N
T = Ω max
pL) p)2² p(1 p)
8
10
(1 pL))xp(1 p) + log {
θ max
(1 (1- pL) 2)2² p(1 p)
x
mn log
which is the desired sample complexity bound in the theorem.
Lower bound of k. Before close the proof, provide lower bound of oL/A. Equivalently, we provide an upper bound on X2 which is at most the minimal eigenvalue of
E [f dof(x dd) Fr, Fi,ds + 0,.
Let E _e be a vector satisfying
|1/|2= (T)())=0 =0.
Then, we know
v ((x+d))(() v= T [f(x de) f(x)] [f(x + de)- - f(x)]
(65)
= =[1s(z + (c) f(x)) u] z 1 + di) f()=)(=)133
< <1.1i
where the last inequality is from the Lipschitz continuity of f. Using the sub-Gaussian assumption, it follows that
E |1 Fr, de + 0. 50²
(66)
where we utilize the fact that the standard deviation of sub-Gaussian random variables with parameter o is at most a., Combining inequalities (65 and 66 it follows that
V
R
[ d))(d))((0 + d.)
Fr, de + 0n] u S
Therefore, it holds that
x2 Amnn
[f d.)
Fr, # 0m]1 5 00L2 V
which further leads to This completes the proof.
1. 1.
x
36

---

Published in Transactions on Machine Learning Research (07 (025)
B.8 Proof of Lemma
Proof of Lemma Let
cx*
8 o L
:::=
==
We finish the proof by discussing two cases.
Case 1. We first consider the case when
2
02 2 +
202
2
1-
Using the Lipschitz contimuity of f, we have
|Zff(x)]l2 [zf(xe) 2" [Af([(]]]]]]]]] + [Af [Af(#:
(67)
2 /f [Af -1 2z [Af(xz-))] 2
2 01 - || |I f (f [AA(x=]))]
2 || P- -||de| || 2 0, dellz
By Assumption we know ||dell2 Lel and it follows that
(- (-22)
P ([]d 2 c Fi) s 2exp
202 202
We 120 O.
Therefore, we get the estimation
(IZ]( -
Fr Fi
< P
0r L
1|1de
112
S 2
2
0--1/2
|1dell2 2
L
2
P
| l12 2
20 2222 log
1 1-8)
Fr
s
-1-6 5.
Therefore, we have proved that
[2](x))]22
Fr F1)26. 26.
2 2
Case 2. Then, we focus on the case when
A +
2
0, -
202
20
(68)
1-8
Assune conversely that
P [2f 2 A Fr <a. 8.
(69)
Similar inequality
67
the Lipschitz continuity of implies
|| s 0, + L |dell.
37

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Therefore, by applying Assumption 6 get the tail bound
(1
28 Fi) SP (0. +
1|dell2 2 8 1i)
(lātl)
2 8- 02
(0 - -0-0))²
=P
Fo Fr)
v exp
40 2 8,.
L
20
Define (z)+ = max 0}. The above bound leads to
(0- (0)
P ((I 2 0 Fi) - 2 exp
40 e R.
(70)
2.
Using the definition of expectation, we can calculate that
[1
Fi]
20 20-
Zf(x )22 2 0 Fil d8
X
/ 20 P
+
7f()))] 2 0 Fi)
d0.
4
A/2
By condition 169
we get
A
A 2
P FIIZf(()) 2 0
S
[2f(x)))22
2 2
Fc 50,
40
z
Combining with inequality
70
it follows that
22
(0 - 0,)
}
E
12
Fi
+
20
min
8,2 2cpp
dB
(71)
4
A/2
20 L2
X²
X2
0
(0 02)
07
+
exp
d0,
4
0
20
where we define
>
(2) 2202 1og log
01
2: 0c +
2 O,.
Using condition 68
we know
2
2 ④
0 <
2 1
+
20
11-8
+
20 L2 log
(72)
2 -
2
+
2
20 log
2 +
160 26 L log
2
where the last incquality is from Cauchy's incquality. Moreover, we can estimate that
(0 02)
(0-0,)² 0,)
40 exp
db <
40 e0e
d8
(73)
20
202L2
(0- 0
[00 (0-0,) 0,)
40, exp
d0 +
4(0 - 0c) exp
202
20 12
0g
(0- 2,
40, exp
d0 + 22
20
where we denote 02 = 0, V 202 log (3) < 5. Utilizing the following bound on the curulaativ densily
function of the standard Gaussian distribution:
[ e
+ dx S
- 4, vn > 0.
38

---

Published in Transactions on Machine Learning Research (07 2025)
have
(0 (0--8) -.)
8
40, exp
d8 W 40,
S 228, V2,, L
02
20 I
2og (2)
2
Combining with 73 it follows that
(0-0:) 02) 22
40 exp
d0 S 220 80 + 2002 S 4507 L.,
(74)
where the last inequality from Cauchy's inequality. Substituting inequalities 72 and
74 back into
71
we get
X²
2 σ
E
Fi.
+
8
+ 160 L2 log
+ 480; + 22
4
4
2
(1 + 6)
A
2
4
16 .
+ 8
2
+
V.
2202 22 log
1-
+ +5002 L
(1 + 6)A²
2
2
16002 1.2 .log
+
40
ôlog
+
18021?
4
2
(1 + 38)
2
+ 240 L log
where the second incquality is from 68 and the last incquality from Canchy's incquality and < 1/2. On the other hand, Assumption implies that
E (1 F.) = (zzT, E (())))()))) T
[F]) 2 1711Z X².
Combining the last two inequalities, get
X² (1 + 35)
2
+ 24 olog
which is equivalent to
2 (3 - 35)
X
log
2
8
9602 L
23
For all x E (0, 1), it holds that x log(2/x) < v 2r. Hence, we have
X²
v25
2302
which contradicts with our assumption 669
B.9 Proof of Theorem 7
Proof of Theorem 7 In this proof, we focus on the case when m n, and the counterexample can be casily extended into more general cases, We construct the following system dynamics:
:==plm f(x): = Va E RR"
where p > 2 a constant. One can verify Assumption 4 holds with Lipschitz constant 1. Therefore, the stability condition (Assumption 5 is violated since p > 1/T. The system dynamics can be written
0² d Vt E (O....,
(75)
kEK.R<t
39

---

Published in Transactions on Machine Learning Research (07 (025))
Conditional on F, and & KC the disturbance vector is generated as
de Uniform(S"~1).
where 1 is the unit ball {d R ||d||2 1)- The attack attack/disture disturbance model satisfies Assumption 1 with
A = 1/vn and Assumption 6 with 1/ //. Define the event
: (T 1E K, 11
By the definition of the probabilistic sparsity model, can calculate that
P(E) - (1
Our goal is to prove that
P
>0 =1
where we define
dz) = Σ I [( f()i)d))))) dz(z) = Σ
1zf
TEK
tEks
Then, by Theorem we know that Å not a global solution to problem with probability at least
p -1 (1- (1-)
Let t be the smallest element in XC, namely, the first time instance when there nonzero disturbance. Under event E, it holds that t - 1. We first prove that
2t + On: E E {t1 + T....,T--I,,
By the system dynamics 75 and the triangle incquality, we have
| 2 p 1 de, 1|
E
P 1- :p p
Σ p p
kEK.,
kEK,t
t-t1-2
p¹
2p- 11
0,
p
where the last inequality holds because p> 2. Then, we choose
7: xT- 1 1==-r-107-- # O.
It follows that
di(z)= = Σ ( 2T (2,,f(zi ((x))dd
ØT 12T--1d7 dJ 12
Σ
tEt
AEK,ATT-1
111
|2T-1111 11221111/lll2
AEK,IKT-1
dz(Z)= = Σ |Zf(x))l12 = Σ
1 Σ
112
tE
tEK
tEx
Combining the above two inequalities, we get
T-2 Σ
T-2
á(z)) dz(2) S | ||TT-111=
| = -
|1TT-1l2=
Σ
l
1=0
t=
40

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where the last equality holds because 2, O,, for all t t1. Since |ær-1ll2 > O, it is sufficient to prove that
T-2
1
(76)
1=
Considering the system dynamics
75
and the fact that Iidx 12 = 1 for all k E K. we have the estimation
Σ
S 1xel22 S Σ
kEN, <lect
kER,
The desired inequality
76 holds if we can show
T-2
0 T-1-6--1
Σ
0 T-1-k-1,
E
Σ
Σ
1= keK,k<t
which is further equivalent to
T-1
2p 22
Σ
Σ p i-
T-1 1-1
T-1
p p p- TT p- (T-0T-
(T- - 1)(p - 1)
= -
Σ
p p-1
(p-1)²
+fi+1k=b k=
t=t+1
T-h
- 2p
0² 4p 2 p 2 2+ V6.
1)2
By our choice of p, we know condition 76 holds, and this completes our proof.
C Extensions of Numerical Experiments for Different Problem Parameters
C.1 Numerical Experiments Spectral Norm of Ā
In this section, use the same experimental setup in Section S for Lipschitz continuous basis functions. We examine the relationship between sample complexity and the spectral norm Specifically, we set T 100, 0.75, and = 3. To eliminate randomness in the spectral norm ||A|2, we assign the singular values of as = ... = on As where p E (0.5, 0.95, 1.5). In the case where p 1.5, we terminate the simulation when | ll2 2 1014, as this indicates that the trajectory diverges to infinity, causing numerical issues for the CVX solver.
The results, presented in Figure 5. reveal that the required sample complexity increases slightly as p increases from 0.5 to 0.95, which is consistent with Theorem G In addition, when 1.5, the system is not asymptotically stable, violating Assumption 5 The resulting divergence of the system state ([|æ=|12 - xo) leads to numerical instabilities in computing the estimator
(3). However, it is possible that the estimator in 3 could still achieve exact recovery for large values of if a numerically stable method is employed for optimization. This does not contradict our theoretical findings, as Theorem s provides only a sufficient condition for exact recovery rather than a necessary one.
C.2 Numerical Experiments with Small Probabilistic Sparsity Model
In this section, we repeat the experiments in Figure 3 with p e {0.001, 0.1, and n 5. The results are presented in Figure D We observe that the prodictor fails to recover the ground truth within 500 steps when p 0.001, whereas it successfully converges when p 0.1 and 0.3. Notably, both the loss gap and the optimality certificate equal to zero in the case of p 0.001. This occurs because multiple global
41

---

Published in Transactions on Machine Learning Research (07 (025)
Loss
Solution Gap
Optimality Certificate
10
109
10r
10"
30"2
10a
mo 0.50
10
10-4
200
300
500
200
400
500
-40
100
400
1'
Figure 5: Loss gap, solution gap and optimality certificate of the Lipschitz basis function case with spectral norm p = 0.5, 0.95 and 1.5.
Loss Gap
Salution Gap
Optimality Certificate
107
0.00
10
10
10
10-3
p 0.300
10
p 0.100
0.001
y
0 100
700
300
400
500
100
200
300
400
500
100
200
300
400
500
Figure 6: Loss gap, solution gap and optimality certificate of the Lipschitz basis function case with at- tack/ dicc/distrbbace probability p p= 0.001, 0.1 and 0.3. Note that the loss gap and the optimality certificate for the case when 0.001 is always equal to 0.
solutions exist, causing the estimator to fail in recovering the unique ground truth solution within 500 iterations. However, given a larger number of samples, the algorithm will eventually converge to the correct solution. That said, the primary focus of this paper is the regime where p > 0.5. When p is very small or zero, learning the system falls within the classical control theory framework, where it is well established that an artificial excitation signal must be introduced to facilitate learning. The necessity of excitation signals in nearly deterministic systems is well documented in the control literature. For example, consider the linear system Z++1 = Axt, where the objective is to learn A from observations of z4. If the initial condition zo is zero, then V, remains zero for all 6, making it impossible to infer A. To circumvent this issue, an artificial excitation signal typically introduced, yielding a system of the form It+1 = Az, + wa where w, is, for instance, Gaussian noise. Interestingly, when p is sufficiently large, the adversarial attack itself serves as an effective excitation signal, aiding the learning process by introducing necessary perturbations into the system.
C.3 Numerical Experiments with Sparse
In this section, we replicate the experiments presented in Figure Specifically, we generate a sparse matrix A as a tridiagonal matrix, where each entry A., is set to zero whenever i j jl > 1. We conduct the experiments for Lipschitz basis functions with nonzero disturbance probabilities p E 0.7,0.8, 0.85 and system dimension n 10. Additionally, we extend the simulation period to T 1000, compared to T 500 in the previous experiments. To improve computational efficiency, solve the optimization problem (3) every 10time steps. Consequently, the plots exhibit discrete jumps corresponding to time periods that are multiples of ten. The loss gap is omitted from the figures since the estimator computed only at a subset of time points. Figure 7 suggests that exact recovery is achieved despite the sparse structure the ground truth matrix A. This result is expected, as our theoretical analysis does not impose any dependency on the sparsity structure of A. Beyond demonstrating robustness, the non- smooth objective function in 3 also acts as an implicit regularization mechanism that aligns with the specific matrix structure.
3 using a sparse ground truth matrix Á.
42

---

Published in Transactions on Machine Learning Research (07/202) /025)
Solution Gap
Optimality Certificate
0.0
10
-0.5
-1.5
-2.0
10-1
0.850
-25
0.800
0.700
10
0
200
400
600
800
1000
200
400
600
800
1000
Figure 7: Solution gap and optimality certificate of the Lipschitz basis function case with p E (0.7,0.8,..33 and 10.
C.4 Numerical Experiments with Larger Order Systems
In this section, we extend the experiments presented in Figure 1 to significantly higher-order dynamical systems and a larger number of basis functions. Specifically, we consider system dimensions and basis function counts of (n, m) 20), (25, 50), (50, 100). The probability of a nonzero disturbance occurring is set p 0.6. Additionally, we increase the simulation period solve the optimization problem (3) every 100
1100, compared T 500 in the
previous experiments. To optimize computational efficiency, time periods. As result, the plots exhibit discrete jumps corresponding to time periods that are multiples of 100. Due to this sampling strategy, the loss gap is omilted from the ligures, as the estimator is computed only at subset of time points.
In Figure g we observe that exact recovery is achieved even for large-scale system identification problems, where both the system dimension and the number of basis functions are significantly high. However, achieving exact recovery requires the system evolve over a sufficiently long time horizon, as indicated by our theoretical results.
Solution Gap
Optimality Certificate
10
-0.5
10
10
(n, m) (10, 20) (n. m) (50, 100) y
1.5
10
10-(
1000
Figure 8: Loss gap, solution gap, and optimality certificate of the Lipschitz basis function case with dimension (n, m) = (1), (25, 50) and (50, 100).
43


Reviews:
[{"review_id": "ZriyXsnzr6", "reviewer": "Reviewer_d1h4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-----------------\nStrengths\n-----------------\n\n1.  The paper is written well overall. The problem is well-defined, and a good overview of the literature on system identification is provided. The presentation of the results is clean and is easy to follow for the most part. \n\n2.  While there are many recent results on finite-time guarantees for system identification, most of them are for linear systems. The present work considers non-linear systems but is also focused on a particular setup where the disturbances are sparse, i.e. the number of non-zero disturbances are small. This enables them to derive exact recovery guarantees for $\\bar{A}$ provided T is sufficiently large.  In contrast, existing results typically assume the disturbance (or “excitation”) to be zero-mean subgaussian vectors with unit-variance entries and analyse the ordinary least squares estimator. So, the results therein involve approximately recovering the system matrix, with error rates of the order $T^{-1/2}$. I found the results in this work interesting and conceptually different from most existing results, barring the work of Yalcin et al. (2023) which studied this problem for linear systems.\n\n3.\tThe theoretical results themselves are quite thorough and appear to be correct in general. I do have some questions from the proofs which are outlined later below.\n\n--------------------\nWeaknesses\n-------------------\n\n1.\tIn terms of the exposition, I feel that the comparison with existing finite-time system identification results for LTI systems could be written more clearly and might be somewhat confusing for readers not familiar with the literature. In particular, the setting there considers the excitation term (referred to as “disturbance” in the present work) to be zero-mean subgaussians with unit variance entries. The unit variance is actually w.l.o.g for LTI systems due to a scaling argument, as noted in (Simchowitz et al. 2018).  So that stochastic model is more general than the one in the present work (when $f$ is identity) and one cannot obtain exact recovery results in that setup (but rather, only approximate recovery is possible). The sparse disturbance model is quite specific and allows for exact recovery results. This distinction between “finite-time exact recovery” and “finite-time approximate recovery” can be highlighted in a clear manner, especially in the introduction and also on page 7 (Section 4) where the notion of finite-time learning seems to implicitly consider only exact recovery of $\\bar{A}$ (which I think is incorrect). \n\n2.\tThere are some technical arguments in the proofs and at other places which I could not understand, I have listed them later below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the system identification problem where the system dynamics are considered to be non-linear, and the sequence of disturbances across different time-steps is sparse (i.e., non-zero at only a few time-steps). The non-linearity is modelled via a collection of $m$ known basis functions, hence estimating the system boils down to learning the coefficient matrix, denoted by $\\bar{A}$. The focus is on exact recovery of $\\bar{A}$ from an observed trajectory of length $T$. In this regard, a LASSO-type estimator of $\\bar{A}$ is proposed which seeks to minimize a sum of $\\ell_2$ norm error terms for robustly recovering $\\bar{A}$. The following theoretical results are then shown.\n\n1.\tFirstly, necessary and sufficient conditions are established under which $\\bar{A}$ is: a global solution (Theorem 1) and, a unique solution (Theorem 2) of the proposed optimization problem. These are established using standard first order optimality conditions for convex problems, using the generalized Farkas lemma. These results do not make any stochastic assumption on the disturbances.\n\n2.\tSecondly, conditions on $T$ are derived for exact recovery of $\\bar{A}$, under a stochastic disturbance model where the disturbance at each time $t$ is non-zero with probability $p \\in (0,1) $. For this model, it is shown that the proposed estimator recovers $\\bar{A}$ exactly provided $T$ is suitably large (depending polynomially on the system parameters). This is shown in Theorem 4 for bounded basis functions, and Theorem 6 for Lipschitz basis functions for stable systems. \n\n3.\tTheorem 5 shows that if $T$ is smaller a threshold, then under the assumptions of Theorem 5, the proposed optimization problem does not have a unique solution. Theorem 7 shows that if the system is not stable, then under the other assumptions of Theorem 6, $\\bar{A}$ is not a solution of the proposed optimization problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have some comments/queries which are outlined below.\n\n1.  The proof of Corollary 1 is trivial and could just be omitted with a remark that Cauchy-Schwartz inequality is used.\n\n2.  In the statement of Corollary 3, isn’t the requirement that (5) holds redundant since (9) implies (5)? \n\n3.  I may be missing something but in the proof of Corollary 3 I do not understand the final sentence. If (9) holds then how does it imply the logical condition in (8)?\n\n4.  [Section 4, page 7]: As mentioned earlier, the two paragraphs following Definition 1 can be made more precise. For e.g. when p = 1 and $f$ is identity, finite-time (approximate) recovery of $\\bar{A}$ is possible via the OLS, and is also the subject of recent results. If $f$ was not the identity, but of the form as in the present work (defined using known basis functions), then I suppose OLS could still be shown to yield approximate recovery results (but this should be checked).\n\n5. In Theorem 4, it’s interesting that no assumptions on stability are needed for $\\bar{A}$. Can this be explained conceptually? I guess the setting of Theorem 4 is a bit stringent as it disallows the linear case where $f$ would be identity. \n\n6. In Theorem 4 (and elsewhere), I think $T = \\Theta()$ should be replaced with $T = \\Omega()$ since the latter symbol is the appropriate one for lower bounds. \n\n7. [Appendix B.3]: In the proof of Corollary 2, in the equation immediately following the sentence “Then condition (5) implies that…”, I do not understand why the first equality holds.\n\n8. [Appendix B.6]: In (37) a lower bound on $|\\mathcal{K}’|$ is written but don’t we need an upper bound here?", "broader_impact_concerns": "I do not have any concerns on the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DthzVMhqHd", "reviewer": "Reviewer_8ZXG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength\nIn this paper, an all-round theoretical analysis is provided. The authors first provide a necessary and sufficient condition (Theorem 1) for exact parameter recovery. Moreover, a sample complexity lower bound (Theorem 5) is provided and two sample complexity upper bounds in two scenarios are provided. The theoretical assumptions and results are discussed in details. The effectiveness of the algorithm is verified by simulations. \n\n### One main weakness\nOne major weakness of the lies in the flow of Section 4. Theorem 3 shows that when the system is not fully excited. However, the authors later introduced an assumption (Assumption 1) that the noises are zero-mean, which doesn't have anything to do with the intuition Theorem 3 provided. The reviewer strongly recommend the authors reorganize this secion. The reviewer can even consider removing Theorem 3, as it is well-known that learning the system is not always possible when the system is not fully excited.\n\n### Minor weaknesses\n- At the end of page 2, the paper writes that \"A crucial first step in achieving this goal is accurately learning the system dynamics\". I suggest revise the sentence since there exist some model-free control algorithms. \n- In Assumption 5, should $L>1$?\n- In proof of Theorem 1, the reviewer strongly recommend the authors to derive Equation (16) or cite related literature that contains the derivation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on identifying nonlinear systems, where the dynamics is parametered as linear combinations of some known basis functions and the state observations are corrupted by sparse-but-large disturbances. The non-smooth $l_2$ loss estimator is studied, and a ncecssary and sufficient trajecotry-dependent condition for exact recovery is provided. The authors then go on to provide sample complexity results for exact parameter recovery using this estimator under various conditions. In the first case, the nonlinear basis functions are assumed bounded and the noises are zero-mean. In the second case, the nonlinear basis functions are Lipschitz, the noises are sub-gaussian and the system is assumed stable. Utilizing more problem structure in the second case, a better sample complexity is achieved.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It is critical to fix the main weakness mentioned. For other minor changes, please refer to the \"Minor weaknesses\" section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "f1ho3hPXJY", "reviewer": "Reviewer_T8Dq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. The paper is well-written and easy to follow. \n\n2. The theoretical contributions are clearly stated. \n\n3. The paper gives non-asymptotic finite time analysis for the nonlinear identification system under a general disturbance model.\n\n\nWeakness: \n\n1.The given bound is not tight.\n\n2. The attack type investigated in this paper is kind of confusing.\n\n3. The essense of the recovery ability of the proposed method has not been discussed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper designs a LASSO-type estimator for the nonlinear system identification problem. The proposed approach could recovery the ground truth exactly with a finite time.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have some questions and suggestions. I would appreciate it if the authors could handle them.\n1. Theorems 4-6 are not self-contained since the definition of $p$ is not clearly stated.\n2. Why can a LASSO-type estimator help you recover the estimator? Could the author give some intuition? \n3. It is well known that LASSO estimator improves the estimator performance when the ground-truth parameter is sparse. In this paper, the sparsity of the disturbance is assummed. Any relationship between these two, i.e., the sparsity of parameter and sparsity of disturbance?\n4. In adversarial training, the standard assumption is that the magnitude of the attacks are bounded. The assumptions in this paper, like the zero mean and gaussian distribution, are not convincing enough.\n5. Is the lower bound in Theorem 5 applied to both bounded and Lipschitz base functions?  Is it possible to derive the bound in terms of the parameters of the $\\kappa$?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)