CS Paper Radar

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

Mihaly Petreczky, John Leth, Emma Lukacs, Balint Daroczy

cs.LG ·submitted 2026-11-06 17:29 UTC · v1

Abstract

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.

Comment
10 pages, 0 figures, under submission to SysID2027

Closest papers

Nearest neighbours by meaning across the whole index.

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.78
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

On Sample Complexity Bounds for Frequency-Domain System Identification

eess.SY ·2026-10-22 ·Arya Honarpisheh, Mario Sznaier
theory similarity 0.64
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.

0.20

Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification

cs.LG math.OC ·2026-10-15 ·Nina Maria Gottschling, Jakob Gawlikowski, Michele Caprio
similarity 0.64
Abstract

Data-driven approaches often face ambiguity in datasets due to sensor or target noise, insufficient information, and noise in the input data. While best-fit machine learning methods can accommodate such noise through uncertainty estimates, they are prone to overfitting and it is challenging to quantify ambiguity of the relation between inputs and targets. We introduce a geometric framework that quantifies this ambiguity through the average kernel size, computed with data-dependent, i.e. model-independent, feasible sets derived from worst-case input and target noise. The framework provides computable, deterministic, non-asymptotic bounds on the best achievable empirical error and accuracy for a finite, constructed dataset, independent of the predictive model class, and applies to regression and classification with pseudo-metric input spaces and metric target spaces. The ambiguity of the input-target relation implies three consequences: an empirical error floor, an accuracy-stability trade-off, and, under standard probabilistic assumptions, a strictly positive distribution-training error gap when training below the accuracy bounds. Under standard Borel assumptions for Euclidean norms, the distributional analogue of the average kernel size is related to Bayes risk as it reduces to the optimal distribution root-mean-squared error times the square root of two. Experiments spanning tabular regression, image regression and classification datasets yield nontrivial bounds on the best achievable empirical error and accuracy on a constructed dataset, alongside descriptive comparisons with model performance on the original datasets. The bounds provide a computable, model-independent reference scale on the constructed dataset and comparisons with model performance on the original dataset are descriptive.

0.23

Learning structured linear dynamical systems from missing observations

cs.LG stat.MLeess.SYmath.OC+1 ·2026-10-08 ·Aravinda Kanchana Ruwanpathirana, Hemant Tyagi, Sunny G. W. Wang
similarity 0.62
Abstract · 62 pages, 3 figures

We consider the problem of learning structured linear dynamical systems over convex sets $\mathcal{K}$, where only a small subset of the observations are available at each time point. An estimator which minimizes a bias-corrected, potentially non-convex objective function is proposed. Non-asymptotic bounds are obtained for the statistical error, which depend on the local complexity of $\mathcal{K}$, the trajectory length $T$, and the sub-sampling probability $p$. Convergence of the projected gradient descent algorithm is also established. The general theory is applied to settings where (i) $\mathcal{K}$ is a subspace, (ii) $\mathcal{K}$ is the set of bi-isotonic matrices, and (iii) $\mathcal{K}$ is the set of matrices whose rows are formed by sampling Lipschitz functions. We show meaningful recovery of the transition matrix is possible for values of $T$ much smaller than what is required in the unconstrained case, and for $p = o(1)$.

0.18

Generalization as a robust performance property of learning-enabled dynamical systems

eess.SY cs.LGmath.OC ·2026-08-31 ·Filippo Fabiani
similarity 0.61
Abstract

By focusing on algorithmic stability as a means of establishing out-of-sample bounds, we provide a system-theoretic interpretation of generalization in learning-enabled dynamical systems arising in data-driven optimization and feedback control approximation. Given two neighboring datasets, we specifically model sample replacement as an exogenous disturbance acting on a sensitivity system, while the incremental behavior of the data-dependent operator is encoded through an integral quadratic constraint. By relying on dissipativity arguments, we establish a matrix inequality-based certificate and a uniform stability bound that separates the one-sample sensitivity of the learned operator, and an algorithm-dependent dynamical gain. The latter can then be optimized, offering a tractable tool for certifying and comparing generalization capabilities of learning dynamics. We show that our results recover classical ones for gradient descent, apply naturally to momentum-based methods such as heavy-ball and Nesterov acceleration, and extend to data-driven control.

0.20

On the Structural Limits of Machine Learning Decision Systems: An Information-Theoretic, Interaction-Based, and Stochastic-Dynamical Perspective

cs.LG math.ST ·2026-08-13 ·Nestor R. Barraza, Gabriel Pena
published similarity 0.61
Abstract

Machine learning procedures are commonly evaluated in terms of predictive accuracy and computational efficiency. However, their achievable performance is fundamentally constrained by structural properties of the underlying data-generating process, which are formalized in terms of informational bounds. In this work we examine intrinsic limits of data-driven decision systems from an information-theoretic and interaction-based perspective. We analyze minimal achievable error in classification through Fano-type bounds and precision limits in parametric estimation via the Cramér-Rao inequality, emphasizing that such limits depend on the underlying model rather than on algorithmic sophistication alone. We further discuss how implicit assumptions, such as independence, ergodicity, and distributional stability, affect the validity of inferential procedures. Building on interaction-based modeling principles, we review typical frameworks such as Markov Random Fields and potential based representations for encoding dependence mechanisms. We also describe decision systems, including LLM-integrated agent architectures, as feedback-driven stochastic processes where state-dependent dynamics may induce emergent macroscopic behavior. This perspective highlights the importance of having adequate models for the data as a prerequi- site for expanding predictive capability, and situates algorithmic learning within the informational limits imposed by the models.

0.28

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.61
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

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.60
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