CS Paper Radar

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

Nestor R. Barraza, Gabriel Pena

cs.LG math.ST ·submitted 2026-08-13 17:34 UTC · v1
published

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.

Journal ref
JAIIO 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Speed limits for information acquisition in stochastic learning dynamics

cs.LG cond-mat.stat-mechstat.ML ·2026-09-08 ·Shuta Kobayashi, Andreas Dechant
theoryhot direction similarity 0.66
Abstract · 15 pages, 4 figures

Neural networks acquire internal representations through learning. In this work, we formulate stochastic gradient descent (SGD) as a Markovian stochastic process and derive a Fisher-information flow speed limit that bounds the rate at which trainable parameters can acquire information about data-generating parameters. The resulting inequality decomposes the upper bound on the information flow into drift and noise contributions, thereby quantifying the roles of deterministic learning forces and SGD-induced fluctuations from an information-theoretic perspective. We verify the bound in analytically tractable basis-function linear regression, where the information budget predicted by the bound reproduces the ordering and characteristic time scales with which different data-generating parameters are encoded in the learned parameters. These results establish Fisher-information speed limits as a quantitative framework for understanding which properties of the data-generating process are acquired, in what order, and how rapidly they can be encoded in the trainable parameters.

0.33

Non-parametric Formal Synthesis of Unknown Stochastic Systems: Asymptotic Convergence Guarantees

eess.SY ·2026-09-05 ·Zhi Zhang, Sadegh Soudjani
theory similarity 0.65
Abstract

Data-driven techniques have shown promising potential for checking behavior of complex systems operating in safety-critical domains against safety and other temporal requirements. This paper studies a class of data-driven techniques that are based on learning a representation of the system from data using non-parametric estimation. The proposed approach is able to formally verify discrete-time stochastic dynamical systems against temporal logic specifications only using observation samples and without the knowledge of the model, and provides a probabilistic guarantee on the satisfaction of the specification. We first consider finite abstract representations of the system in the form of Markov decision processes (MDPs) and derive asymptotic convergence guarantees between the transition probabilities of the abstract MDP and their estimation using Bernstein's inequality and statistical properties of non-parametric estimators. We then propose theoretical results for estimating the asymptotic upper bound of the \emph{Lipschitz constant} (LC) of the stochastic system, which can determine the size of the finite abstract MDP for a given precision error. Under appropriate assumptions, our results prove that the asymptotic convergence rate of the estimations is $O(n^{-1/(3+d)})$ for both the transition probabilities and the LC, where $\mathsf d$ is the dimension of the system and $n$ is the data scale. By integrating these results, we can guarantee the asymptotic closeness in formal verification and policy synthesis performed on the original system and its finite abstraction based on the size of the dataset. Multiple case studies are presented to validate the effectiveness of the proposed method.

0.26

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

eess.SY cs.LGmath.OC ·2026-08-31 ·Filippo Fabiani
similarity 0.63
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

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

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

Fundamental Limits of Data-Driven Predictive Control

eess.SY ·2026-11-11 ·Jiabao He, Feiran Zhao, Yushan Li, Yue Ju, Florian Dörfler +1 more
benchmarktheoryhot direction similarity 0.60
Abstract

Data-driven predictive control (DDPC) has attracted substantial interest, and many variants have been proposed; however, comparatively less is known about the statistical closed-loop performance of these methods and the fundamental limits they are subject to. In this contribution, we apply the statistical decision framework developed in our earlier work to study fundamental limits of DDPC. The performance of a data-driven controller is measured by its risk, the expected deterioration in control performance relative to an oracle model-based controller at a given system, and by its total risk that measures the overall performance across all systems of interest. Lower bounds on these risks are derived using the bias-variance decomposition and the Cramer-Rao inequality. In particular, a lower bound on the total risk is obtained by a calculus-of-variations method. This bound applies to any DDPC design, thereby quantifying unavoidable performance limitations and providing a benchmark for assessing existing DDPC methods. In an illustrative example, we compare the risks of certainty-equivalence model predictive control, subspace predictive control, and data-enabled predictive control with the derived lower bounds, providing a quantitative performance assessment of these methods and some guidance on tuning regularization parameters in DDPC.

0.26

Finite-Sample Limits of Entropy-Based Structure Identification in Discretized Nonlinear Systems

eess.SY cs.IT ·2026-09-02 ·Pratishtha Shukla, James Nutaro
similarity 0.60
Abstract

Discretization fundamentally limits structure identification in stochastic systems. When system stochasticity exceeds the discretization resolution, entropy-based methods lose their ability to distinguish which input drives the output. We study this in Fuzzy Inductive Reasoning (FIR), a nonparametric framework for learning dynamical systems from discretized measurements, where the choice of input variables determines both predictive accuracy and the interpretability of the learned input--output relationships. Entropy-based selection targets explainability, i.e., identifying which variables causally drive the output, while mean-squared-error-based selection targets prediction. We introduce a resolution-stochasticity ratio that governs when entropy-based selection is reliable. Three results follow. First, entropy-based selection is consistent below this threshold but loses discriminative power above it, regardless of sample size. Second, using the entropy-selected variables for prediction instead of the MSE-selected ones incurs a closed-form excess prediction risk that grows with input complexity and shrinks with sample size. Third, reliable identification of the causally relevant inputs requires data that scales with the number of input combinations and inversely with the strength of the entropy signal. The theory is validated on a two-state Markov model and demonstrated on a distribution grid reliability dataset analyzing the impact of infrastructure investment, where the goal is to explain which investments drive reliability improvements rather than merely predict outcomes.

0.44

I Act Therefore I Am: When Is JEPA's Action-Conditioning Enough to Learn Causal Mechanisms?

cs.LG ·2026-09-25 ·Yuhang Liu, Zhuo Huang, Javen Qinfeng Shi
similarity 0.60
Abstract

Recent empirical and theoretical advances suggest that joint-embedding predictive architectures (JEPAs) may learn meaningful representations for action-conditioned prediction of future outcomes, thus becoming one of the foundational structures for world models. However, accurate prediction does not, in general, necessarily imply recovery of underlying causal states that give rise to the observed dynamics. This work investigates when and how JEPAs can recover the underlying causal states from observations. We first introduce a latent variable model, in which high-dimensional observations are generated from latent causal states whose dynamics are governed by action-conditioned transition mechanisms. Based on this formulation, we develop a general information-theoretic objective that combines conditional likelihood maximization for learning transition dynamics with entropy maximization for preserving latent state information. We then establish identifiability conditions under which representations learned by this general objective recover the underlying latent causal states up to component-wise invertible transformations and permutation. One key condition for such identifiability is sufficient action-induced variation in the transition mechanisms. Guided by this finding, we instantiate the general objective with an action-modulated Gaussian additive-noise model, yielding action-modulated JEPA (A-JEPA). Experiments on synthetic environments verify the theoretical findings under the identifiability conditions and robustness to moderate violations, while visual benchmarks demonstrate improved state recovery and transfer to unseen transition mechanisms.

0.27