Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case

• URL: http://arxiv.org/abs/2401.15792v1
• Date: Sun, 28 Jan 2024 22:44:41 GMT
• Title: Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case
• Authors: Szabolcs Szentp\'eteri and Bal\'azs Csan\'ad Cs\'aji
• Abstract summary: Sign-Perturbed Sum (SPS) is a powerful finite-sample system identification algorithm. This paper studies the behaviour of SPS confidence intervals.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sign-Perturbed Sum (SPS) is a powerful finite-sample system identification algorithm which can construct confidence regions for the true data generating system with exact coverage probabilities, for any finite sample size. SPS was developed in a series of papers and it has a wide range of applications, from general linear systems, even in a closed-loop setup, to nonlinear and nonparametric approaches. Although several theoretical properties of SPS were proven in the literature, the sample complexity of the method was not analysed so far. This paper aims to fill this gap and provides the first results on the sample complexity of SPS. Here, we focus on scalar linear regression problems, that is we study the behaviour of SPS confidence intervals. We provide high probability upper bounds, under three different sets of assumptions, showing that the sizes of SPS confidence intervals shrink at a geometric rate around the true parameter, if the observation noises are subgaussian. We also show that similar bounds hold for the previously proposed outer approximation of the confidence region. Finally, we present simulation experiments comparing the theoretical and the empirical convergence rates.

Related papers

• Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation [23.89036529638614]
  We study time-uniform statistical inference for parameters in approximation (SA) We analyze the almost-sure convergence rates of the averaged iterates to a scaled sum of Gaussians in both linear and nonlinear SA problems.
  arXiv  Detail & Related papers  (2024-10-19T10:27:26Z)
• 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)
• Finite-Sample Identification of Linear Regression Models with Residual-Permuted Sums [0.0]
  Residual-Permuted Sums (RPS) is an alternative to the Sign-Perturbed Sums (SPS) algorithm, to construct confidence regions. RPS permutes the residuals instead of perturbing their signs. We provide the first proof that these permutation-based confidence regions are uniformly strongly consistent under general assumptions.
  arXiv  Detail & Related papers  (2024-06-08T11:09:30Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• 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)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• Generalized Sliced Distances for Probability Distributions [47.543990188697734]
  We introduce a broad family of probability metrics, coined as Generalized Sliced Probability Metrics (GSPMs) GSPMs are rooted in the generalized Radon transform and come with a unique geometric interpretation. We consider GSPM-based gradient flows for generative modeling applications and show that under mild assumptions, the gradient flow converges to the global optimum.
  arXiv  Detail & Related papers  (2020-02-28T04:18:00Z)

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.