On the Convergence Rates of Set Membership Estimation of Linear Systems with Disturbances Bounded by General Convex Sets

• URL: http://arxiv.org/abs/2406.00574v1
• Date: Sat, 1 Jun 2024 23:41:29 GMT
• Title: On the Convergence Rates of Set Membership Estimation of Linear Systems with Disturbances Bounded by General Convex Sets
• Abstract summary: This paper focuses on a method commonly used in (robust constrained) control literature: set membership estimation (SME) SME tends to enjoy better empirical performance than LSE's confidence bounds when the system disturbances are bounded. The main contribution of this paper is relaxing the assumption on the disturbance support and establishing the convergence rates of SME for general convex supports.
• Score: 10.543371327361074
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the uncertainty set estimation of system parameters of linear dynamical systems with bounded disturbances, which is motivated by robust (adaptive) constrained control. Departing from the confidence bounds of least square estimation from the machine-learning literature, this paper focuses on a method commonly used in (robust constrained) control literature: set membership estimation (SME). SME tends to enjoy better empirical performance than LSE's confidence bounds when the system disturbances are bounded. However, the theoretical guarantees of SME are not fully addressed even for i.i.d. bounded disturbances. In the literature, SME's convergence has been proved for general convex supports of the disturbances, but SME's convergence rate assumes a special type of disturbance support: $l_\infty$ ball. The main contribution of this paper is relaxing the assumption on the disturbance support and establishing the convergence rates of SME for general convex supports, which closes the gap on the applicability of the convergence and convergence rates results. Numerical experiments on SME and LSE's confidence bounds are also provided for different disturbance supports.

Related papers

• Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability [54.40598524756038]
  emphKullback-Leibler (KL) regularization is ubiquitous in reinforcement learning algorithms.<n>Recent studies have demonstrated $-1$-type fast rates for decision making under reverse KL regularization.<n>We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs.
  arXiv  Detail & Related papers  (2026-05-09T23:17:46Z)
• Periodic Event-Triggered Explicit Reference Governor for Constrained Attitude Control on SO(3) [0.7346058953290145]
  We propose a novel Periodic Event-Triggered Explicit Reference Governor (PET-ERG)<n>PET-ERG enforces input saturation and geometric pointing constraints without relying on online optimization.<n>We rigorously establish the stability and exponential convergence of the closed-loop system for almost all initial configurations.
  arXiv  Detail & Related papers  (2026-04-05T09:47:32Z)
• Achieving $\widetilde{O}(1/ε)$ Sample Complexity for Bilinear Systems Identification under Bounded Noises [2.6857362061342998]
  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.
  arXiv  Detail & Related papers  (2026-03-21T13:40:01Z)
• Bridging Conformal Prediction and Scenario Optimization: Discarded Constraints and Modular Risk Allocation [0.0]
  This paper revisits that connection directly from a systems-and-control viewpoint.<n>We introduce a simple modular composition rule that combines several blockwise calibration certificates into a single joint guarantee.
  arXiv  Detail & Related papers  (2026-03-19T18:37:58Z)
• Verifying Closed-Loop Contractivity of Learning-Based Controllers via Partitioning [52.23804865017831]
  We address the problem of verifying closed-loop contraction in nonlinear control systems whose controller and contraction metric are both parameterized by neural networks.<n>We derive a tractable and scalable sufficient condition for closed-loop contractivity that reduces to checking that the dominant eigenvalue of a symmetric Metzler matrix is nonpositive.
  arXiv  Detail & Related papers  (2025-12-01T23:06:56Z)
• Statistical Inference under Adaptive Sampling with LinUCB [15.167069362020426]
  We show that the linear upper confidence bound (LinUCB) algorithm for linear bandits satisfies a property called stability.<n>We establish a central limit theorem for the LinUCB algorithm, establishing normality for the limiting distribution of the estimation error.
  arXiv  Detail & Related papers  (2025-11-28T21:48:18Z)
• Schrödinger bridge for generative AI: Soft-constrained formulation and convergence analysis [6.584866740785309]
  We study the so-called soft-constrained Schr"odinger bridge problem (SCSBP)<n>We prove that as the penalty grows, both the controls and value functions converge to those of the classical SBP at a linear rate.<n>These results provide the first quantitative convergence guarantees for soft-constrained bridges.
  arXiv  Detail & Related papers  (2025-10-13T18:29:15Z)
• NDCG-Consistent Softmax Approximation with Accelerated Convergence [67.10365329542365]
  We propose novel loss formulations that align directly with ranking metrics.<n>We integrate the proposed RG losses with the highly efficient Alternating Least Squares (ALS) optimization method.<n> Empirical evaluations on real-world datasets demonstrate that our approach achieves comparable or superior ranking performance.
  arXiv  Detail & Related papers  (2025-06-11T06:59:17Z)
• CLUE: Neural Networks Calibration via Learning Uncertainty-Error alignment [7.702016079410588]
  We introduce CLUE (Calibration via Learning Uncertainty-Error Alignment), a novel approach that aligns predicted uncertainty with observed error during training.<n>We show that CLUE achieves superior calibration quality and competitive predictive performance with respect to state-of-the-art approaches.
  arXiv  Detail & Related papers  (2025-05-28T19:23:47Z)
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
  This paper focuses on applying entropic mirror descent to solve linear systems.<n>The main challenge for the convergence analysis stems from the unboundedness of the domain.<n>To overcome this without imposing restrictive assumptions, we introduce a variant of Polyak-type stepsizes.
  arXiv  Detail & Related papers  (2025-05-05T12:33:18Z)
• Data-Driven Calibration of Prediction Sets in Large Vision-Language Models Based on Inductive Conformal Prediction [0.0]
  We propose a model-agnostic uncertainty quantification method that integrates dynamic threshold calibration and cross-modal consistency verification. We show that the framework achieves stable performance across varying calibration-to-test split ratios, underscoring its robustness for real-world deployment in healthcare, autonomous systems, and other safety-sensitive domains. This work bridges the gap between theoretical reliability and practical applicability in multi-modal AI systems, offering a scalable solution for hallucination detection and uncertainty-aware decision-making.
  arXiv  Detail & Related papers  (2025-04-24T15:39:46Z)
• Supervised Optimism Correction: Be Confident When LLMs Are Sure [91.7459076316849]
  We establish a novel theoretical connection between supervised fine-tuning and offline reinforcement learning. We show that the widely used beam search method suffers from unacceptable over-optimism. We propose Supervised Optimism Correction, which introduces a simple yet effective auxiliary loss for token-level $Q$-value estimations.
  arXiv  Detail & Related papers  (2025-04-10T07:50:03Z)
• Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming [18.371947752008744]
  We show that Certainty Equivalent achieves uniformly near-optimal regret under mild assumptions on the underlying distribution. Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances. These techniques may find potential applications in broader online decision-making contexts.
  arXiv  Detail & Related papers  (2025-01-03T09:21:27Z)
• Randomized Midpoint Method for Log-Concave Sampling under Constraints [5.548787731232499]
  We study the problem of sampling from log-concave distributions supported on convex, compact sets.<n>We propose a unified proximal framework for handling constraints via a broad class of projection operators.
  arXiv  Detail & Related papers  (2024-05-24T09:24:21Z)
• Distributionally Robust Policy and Lyapunov-Certificate Learning [13.38077406934971]
  Key challenge in designing controllers with stability guarantees for uncertain systems is the accurate determination of and adaptation to shifts in model parametric uncertainty during online deployment. We tackle this with a novel distributionally robust formulation of the Lyapunov derivative chance constraint ensuring a monotonic decrease of the Lyapunov certificate. We show that, for the resulting closed-loop system, the global stability of its equilibrium can be certified with high confidence, even with Out-of-Distribution uncertainties.
  arXiv  Detail & Related papers  (2024-04-03T18:57:54Z)
• f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization [9.591164070876689]
  This paper presents a unified optimization framework for fair empirical risk based on f-divergence measures (f-FERM) In addition, our experiments demonstrate the superiority of fairness-accuracy tradeoffs offered by f-FERM for almost all batch sizes. Our extension is based on a distributionally robust optimization reformulation of f-FERM objective under $L_p$ norms as uncertainty sets.
  arXiv  Detail & Related papers  (2023-12-06T03:14:16Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Learning the Uncertainty Sets for Control Dynamics via Set Membership: A Non-Asymptotic Analysis [18.110158316883403]
  This paper focuses on set membership estimation (SME) for unknown linear systems. We provide the first convergence rate bounds for SME and discuss variations of SME under relaxed assumptions. We also provide numerical results demonstrating SME's practical promise.
  arXiv  Detail & Related papers  (2023-09-26T03:58:06Z)
• A Robustness Analysis of Blind Source Separation [91.3755431537592]
  Blind source separation (BSS) aims to recover an unobserved signal from its mixture $X=f(S)$ under the condition that the transformation $f$ is invertible but unknown. We present a general framework for analysing such violations and quantifying their impact on the blind recovery of $S$ from $X$. We show that a generic BSS-solution in response to general deviations from its defining structural assumptions can be profitably analysed in the form of explicit continuity guarantees.
  arXiv  Detail & Related papers  (2023-03-17T16:30:51Z)
• On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
  We propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. We empirically analyze the effect of this new loss-gradient norm term on different neural architectures.
  arXiv  Detail & Related papers  (2022-10-12T12:49:20Z)
• Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO [66.5384483339413]
  We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforcement Learning (MARL) We show that a trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training.
  arXiv  Detail & Related papers  (2022-01-31T20:39:48Z)
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective [49.17352150219212]
  Federated AveragingFedAvg, also known as Local SGD, is one of the most popular algorithms in Federated Learning (FL) We show how to analyze this quantity from the Differential Equation (SDE) perspective.
  arXiv  Detail & Related papers  (2021-11-05T22:16:11Z)
• Keep it Tighter -- A Story on Analytical Mean Embeddings [0.6445605125467574]
  Kernel techniques are among the most popular and flexible approaches in data science. Mean embedding gives rise to a divergence measure referred to as maximum mean discrepancy (MMD) In this paper we focus on the problem of MMD estimation when the mean embedding of one of the underlying distributions is available analytically.
  arXiv  Detail & Related papers  (2021-10-15T21:29:27Z)
• Tight Mutual Information Estimation With Contrastive Fenchel-Legendre Optimization [69.07420650261649]
  We introduce a novel, simple, and powerful contrastive MI estimator named as FLO. Empirically, our FLO estimator overcomes the limitations of its predecessors and learns more efficiently. The utility of FLO is verified using an extensive set of benchmarks, which also reveals the trade-offs in practical MI estimation.
  arXiv  Detail & Related papers  (2021-07-02T15:20:41Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Sequential Estimation of Convex Divergences using Reverse Submartingales and Exchangeable Filtrations [31.088836418378534]
  We present a unified technique for sequential estimation of convex divergences between distributions. The technical underpinnings of our approach lie in the observation that empirical convex divergences are (partially ordered) reverse submartingales. These techniques appear to be powerful additions to the existing literature on both confidence sequences and convex divergences.
  arXiv  Detail & Related papers  (2021-03-16T18:22:14Z)
• Estimating means of bounded random variables by betting [39.98103047898974]
  This paper derives confidence intervals (CI) and time-uniform confidence sequences (CS) for the classical problem of estimating an unknown mean from bounded observations. We present a general approach for deriving concentration bounds, that can be seen as a generalization and improvement of the celebrated Chernoff method. We show how to extend these ideas to sampling without replacement, another heavily studied problem.
  arXiv  Detail & Related papers  (2020-10-19T17:22:03Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
  arXiv  Detail & Related papers  (2020-06-26T12:37:17Z)
• GenDICE: Generalized Offline Estimation of Stationary Values [108.17309783125398]
  We show that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions. The resulting algorithm, GenDICE, is straightforward and effective.
  arXiv  Detail & Related papers  (2020-02-21T00:27:52Z)

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.