CS Paper Radar

On Sample Complexity Bounds for Frequency-Domain System Identification

Arya Honarpisheh, Mario Sznaier

eess.SY ·submitted 2026-10-22 22:09 UTC · v1
theory

Abstract

We study the sample complexity of frequency-domain system identification with bounded measurement noise. We focus on interpolatory identification algorithms, which return models consistent with both the data and a priori constraints. For equally spaced samples, we sharpen previous worst-case bounds on the consistency-set radius. Its excess above the noise level decays as $N^{-2}$, where $N$ is the number of samples, and a matching lower bound shows that this rate is tight. We then examine whether bounded stochastic noise allows identification below the noise level. We show that high-probability error bounds can converge to zero. Their convergence rate depends on how strongly the noise distribution is concentrated near the boundary of the noise set. For example, noise uniformly distributed on a disk gives an upper bound of order $(\log N/N)^{2/3}$. Numerical experiments examine these convergence rates and the effect of the noise distribution on the identification error.

Closest papers

Nearest neighbours by meaning across the whole index.

From PAC bounds on the generalization error to PAC bounds on the parameter estimation error

cs.LG ·2026-11-06 ·Mihaly Petreczky, John Leth, Emma Lukacs, Balint Daroczy
similarity 0.64
Abstract · 10 pages, 0 figures, under submission to SysID2027

Probably Approximately Correct (PAC) bounds on the generalization error (the difference between the empirical prediction error computed on the training data and its expectation) are an established tool in statistical machine learning, and there have been several extensions of these bounds to dynamical systems. In parallel, in recent years, there has been growing interest in finite-sample bounds for parameter estimation error in system identification. The latter bounds tend to be algorithm-specific, relying on reformulating the identification algorithm as a least-squares regression problem. This is in contrast to classical PAC bounds, which are algorithm-agnostic and can be applied to any identification algorithm based on minimizing a cost function involving the empirical loss. In this paper, we show how oracle bounds derived from PAC bounds can be used to derive finite-sample bounds for dynamical systems. As an illustration of this approach, we present finite-sample parameter-estimation bounds for linear and bilinear systems with bounded inputs and noise. These bounds apply to identification algorithms based on minimizing a regularized empirical loss function. The key ingredient is to establish an oracle inequality, i.e., an inequality between the true prediction error of the learned model and the minimum achievable true prediction error, and then use either the convexity of the true loss or system-theoretic properties of the loss function to derive bounds on the parameter estimation error. We also analyze the rates of the obtained bounds and compare them with those of classical asymptotic results.

0.11

Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory

cs.LG eess.SY ·2026-09-30 ·Xiaomian Yang, Sungho Shin
similarity 0.63
Abstract

We establish non-asymptotic sample complexity bounds for the least-squares estimation of vector autoregressive models for exponentially stable systems with heavy-tailed noise based on a single observed trajectory. By assuming i.i.d. noise, bounded noise covariance, and persistent excitation, we show that the estimation error is $\widetilde{\mathcal{O}}(r^{1/2}T^{-1/2+1/p})$ under bounded $p$th moment for $p > 2$, where $T$ is the number of samples, $r$ is the noise dimension, and $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic terms. We also introduce a unifying approach to sample complexity analysis applicable to broad classes of noise distributions and showcase this by deriving error bounds for sub-exponential and sub-Gaussian noise distributions. Finally, we specialize our analysis to autoregressive models with exogenous inputs and show that the dimension factor of the error bound is independent of the model order.

0.20

PAC-Bayesian Bounds for Learning Partially Observed Stochastic Linear Time-Invariant State-Space Systems with Inputs and Sub-Gaussian Noise

cs.LG math.OC ·2026-09-08 ·Mihaly Petreczky, Mohamad Al Ahdab, John Leth
similarity 0.59
Abstract

In this paper we derive a Probably Approximately Correct (PAC)-Bayesian error bound for partially observed linear time-invariant (LTI) stochastic dynamical systems in state-space form with inputs and sub-Gaussian noise. Such bounds are widespread in machine learning, and they are useful for characterizing the predictive power of models learned from finitely many data points. The bound derived in this paper relates the expectation of prediction errors with the prediction error generated by the model on the data used for learning. In addition, we show that it can also be used to derive bounds for the parameter estimation error. In turn, this allows us to provide finite-sample error bounds for the prediction error and parameter estimation error for a wide class of system identification algorithms. Furthermore, as LTI systems are a sub-class of recurrent neural networks (RNNs), these error bounds could be a first step towards PAC-Bayesian bounds for RNNs.

0.49

Finite-Sample LTI System Identification from a Misspecified Finite Model Set

eess.SY math.OCstat.ML ·2026-10-29 ·Nicolas Chatzikiriakos, Andrea Iannelli
theory similarity 0.58
Abstract

We consider the problem of finite-sample identification of an unknown LTI system from a finite hypothesis class. In contrast to existing results that assume the hypothesis class contains the true system, we consider the misspecified setting, where the true system does not belong to the hypothesis class. We first characterize the resulting estimation target and its dependence on the data-generation scheme. We then establish a finite-sample lower bound on the failure probability that any identification algorithm must incur. Finally, we analyze the robustness of an existing exponential weighting-based identification algorithm to the misspecification and derive a finite-sample upper bound on its failure probability. Our results illustrate when using a misspecified finite hypothesis class can provide an advantage over identification without prior knowledge of the candidate systems.

0.34

High Probability Streaming Lower Bounds for $F_2$ Estimation

cs.DS ·2026-09-15 ·William Swartworth, David P. Woodruff, Samson Zhou
theory similarity 0.58
Abstract · RANDOM 2026

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $δ$ remained open. We close this gap by proving a tight high-probability lower bound of $Ω\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\,\log\frac{\varepsilon\sqrt{n}}{\log(1/δ)}\right)$ for $(1\pm\varepsilon)$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $Ω\left(\frac{m}{t}\log\frac{1}δ\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log(1/δ)$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log(n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log\log m$ dependence on stream length.

0.35

Optimal spectrum estimation

cs.CC quant-phcs.DS ·2026-09-24 ·Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
theoryhighly cited similarity 0.57
Abstract · 37 pages

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

0.35

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

cs.CC math.OCcs.LG ·2026-08-10 ·Jikai Jin
theory similarity 0.57
Abstract

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

0.38

Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

cs.LG cs.AIstat.ML ·2026-10-02 ·Khang Luong, Dinh Thai Son, Hoang Ta, Hung The Tran, Tuan Quang Dam
top venuetheory similarity 0.57
Abstract · To appear in Advances in Neural Information Processing Systems 39 (NeurIPS 2026, Spotlight)

We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is no longer available and clipping becomes unavoidable. We first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime $(ε,δ)$-PAC guarantee, while a phased adaptive-clipping algorithm matches the clipping level to the current resolution and yields a gap-adaptive sample complexity. We also prove a $K$-arm worst-case information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic. This bound matches the leading dependence of the phased algorithm up to lower-order $\log\log$ factors.

0.40