Achieving $\widetilde{O}(1/ε)$ Sample Complexity for Bilinear Systems Identification under Bounded Noises

• URL: http://arxiv.org/abs/2603.20819v1
• Date: Sat, 21 Mar 2026 13:40:01 GMT
• Title: Achieving $\widetilde{O}(1/ε)$ Sample Complexity for Bilinear Systems Identification under Bounded Noises
• Abstract summary: This paper studies finite-sample set-membership identification for discrete-time bilinear systems under bounded symmetric log-cavecon disturbances.<n>Compared with existing finite-sample results for linear systems, we consider the more challenging bilinear setting with trajectory-dependent regressors and allow marginally stable dynamics with mean-square state growth.
• Score: 2.6857362061342998
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies finite-sample set-membership identification for discrete-time bilinear systems under bounded symmetric log-concave disturbances. Compared with existing finite-sample results for linear systems and related analyses under stronger noise assumptions, we consider the more challenging bilinear setting with trajectory-dependent regressors and allow marginally stable dynamics with polynomial mean-square state growth. Under these conditions, we prove that the diameter of the feasible parameter set shrinks with sample complexity $\widetilde{O}(1/ε)$. Simulation supports the theory and illustrates the advantage of the proposed estimator for uncertainty quantification.

Related papers

• Optimizing Parallel Schemes with Lyapunov Exponents and kNN-LLE Estimation [0.0]
  We present a unified analytical-data-driven methodology for identifying, measuring, and reducing such instabilities in inverse parallel solvers.<n>On the theoretical side, we derive stability and bifurcation characterizations of the underlying iterative maps.<n>On the computational side, we introduce a micro-series pipeline based on kNN-driven estimation of the local largest Lyapunov exponent.
  arXiv  Detail & Related papers  (2026-01-20T05:09:52Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• A Bayesian Framework for Symmetry Inference in Chaotic Attractors [0.0]
  We present a framework that formulates symmetry detection as probabilistic model selection over a lattice of candidate subgroups.<n>An application to human gait dynamics reveals symmetry changes induced by mechanical constraints.
  arXiv  Detail & Related papers  (2025-10-18T13:49:35Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• Sample Complexity Bounds for Linear System Identification from a Finite Set [0.0]
  We use the maximum likelihood estimator to identify the true system.<n>We leverage tools from information theory to provide a lower bound to the sample complexity.<n>The derived sample complexity bounds are analyzed analytically and numerically.
  arXiv  Detail & Related papers  (2024-09-17T12:52:16Z)
• Sample Complexity of the Sign-Perturbed Sums Method [0.0]
  The Sign-Perturbed Sums (SPS) method constructs exact, non-asymptotic confidence regions for the true system parameters. We study the sample complexity of SPS for general linear regression problems. The difference between the theoretical bounds and the empirical sizes of SPS confidence regions is investigated experimentally.
  arXiv  Detail & Related papers  (2024-09-02T13:18:53Z)
• Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case [0.0]
  Sign-Perturbed Sum (SPS) is a powerful finite-sample system identification algorithm. This paper studies the behaviour of SPS confidence intervals.
  arXiv  Detail & Related papers  (2024-01-28T22:44:41Z)
• Identifiability and Asymptotics in Learning Homogeneous Linear ODE Systems from Discrete Observations [114.17826109037048]
  Ordinary Differential Equations (ODEs) have recently gained a lot of attention in machine learning. theoretical aspects, e.g., identifiability and properties of statistical estimation are still obscure. This paper derives a sufficient condition for the identifiability of homogeneous linear ODE systems from a sequence of equally-spaced error-free observations sampled from a single trajectory.
  arXiv  Detail & Related papers  (2022-10-12T06:46:38Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  Independent component analysis (ICA) has been a popular dimension reduction tool in statistical machine learning and signal processing. In this paper, we present a by-product online tensorial algorithm that estimates for each independent component.
  arXiv  Detail & Related papers  (2020-12-28T18:52:37Z)
• Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator [79.3239137440876]
  We present a new finite-time analysis of the estimation error of the Ordinary Least Squares (OLS) estimator for stable linear time-invariant systems. We characterize the number of observed samples sufficient for the OLS estimator to be $(varepsilon,delta)$-PAC, i.e., to yield an estimation error less than $varepsilon$ with probability at least $1-delta$.
  arXiv  Detail & Related papers  (2020-03-17T20:59:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.