Over the past decade, new types of estimators have been developed in statistics, signal processing and system identification, which apply tools from supervised learning, such as deep neural networks or kernel regression on synthetic data. In spite of their competitive performance, a systematic finite-sample analysis of these so-called data-driven estimators is still missing. In this paper, we take first steps in this direction by deriving finite-sample bounds for a specific data-driven estimator, known as the Two-Stage method. The derived bounds hold under fairly general conditions, and highlight the effect of different user choices involved in the construction of this estimator.

First, a procedure is developed for providing a multicriteria model-agnostic Counterfactual Explanation (CE) for classifiers, which is formalized as a constrained multi-objective optimization problem. The proposed multicriteria framework takes into account the proximity between different input vector values by breaking down the influence of each actionable variable. This way, the resulting CE Pareto set allows for a flexible consideration of the relative relevance of such actionable variables. Next, the procedure is extended for the case in which the classifier is not accessible and only a set of labeled data is available. Several architectures are considered to approximate the classifier and a combined post-processing of the resulting approximations of the CE Pareto set is also proposed, that is aimed to two relevant objectives: to improve the approximation of such CE Pareto set and to comparatively assess the performance of the architectures. A simulation example illustrates the theoretical results and the applicability of the proposed schemes.

Knowing the features of a complex system that are highly relevant to a particular target variable is of fundamental interest in many areas of science. Existing approaches are often limited to linear settings, sometimes lack guarantees, and in most cases, do not scale to the problem at hand, in particular to images. We propose DRCFS, a doubly robust feature selection method for identifying the causal features even in nonlinear and high dimensional settings. We provide theoretical guarantees, illustrate necessary conditions for our assumptions, and perform extensive experiments across a wide range of simulated and semi-synthetic datasets. DRCFS significantly outperforms existing state-of-the-art methods, selecting robust features even in challenging highly non-linear and high-dimensional problems.

In this paper, we study finite-sample properties of the least squares estimator in first order autoregressive processes. By leveraging a result from decoupling theory, we derive upper bounds on the probability that the estimate deviates by at least a positive ε from its true value. Our results consider both stable and unstable processes. Afterwards, we obtain problem-dependent non-asymptotic bounds on the variance of this estimator, valid for sample sizes greater than or equal to seven. Via simulations we analyze the conservatism of our bounds, and show that they reliably capture the true behavior of the quantities of interest.

We consider fixed-interval smoothing problems for counter-adversarial autonomous systems. An adversary deploys an autonomous filtering and control system that i) measures our current state via a noisy sensor, ii) computes a posterior estimate (belief) and iii) takes an action that we can observe. Based on such observed actions and our knowledge of our state sequence, we aim to estimate the adversary's past and current beliefs - this forms a foundation for predicting, and counteracting against, future actions. We derive the optimal smoother for the adversary's beliefs (we treat the problem in a Bayesian framework). Moreover, we demonstrate how the smoother can be computed for discrete systems even though the corresponding backward variables do not admit a finite-dimensional characterization. Finally, we illustrate our results in numerical simulations.

Can the parameters of a hidden Markov model (HMM) be estimated from a single sweep through the observations – and additionally, without being trapped at a local optimum in the likelihood surface? That is the premise of recent method of moments algorithms devised for HMMs. In these, correlations between consecutive pair- or triplet-wise observations are empirically estimated and used to compute estimates of the HMM parameters. Albeit computationally very attractive, the main drawback is that by restricting to only low-order correlations in the data, information is being neglected which results in a loss of accuracy (compared to standard maximum likelihood schemes). In this paper, we propose extending these methods (both pair- and triplet-based) by also including non-consecutive correlations in a way which does not significantly increase the computational cost (which scales linearly with the number of additional lags included). We prove strong consistency of the new methods, and demonstrate an improved performance in numerical experiments on both synthetic and real-world financial time-series datasets.

We present the gain estimation problem for linear dynamical systems as a multi-armed bandit. This is particularly a very important engineering problem in control design, where performance guarantees are casted in terms of the largest gain of the frequency response of the system. The dynamical system is unknown and only noisy input-output data is available. In a more general setup, the noise perturbing the data is non-white and the variance at each frequency band is unknown, resulting in a two-dimensional Gaussian bandit model with unknown mean and scaled-identity covariance matrix. This model corresponds to a two-parameter exponential family. Within a bandit framework, the set of means is given by the frequency response of the system and, unlike traditional bandit problems, the goal here is to maximize the probability of choosing the arm drawing samples with the highest norm of its mean. A problem-dependent lower bound for the expected cumulative regret is derived and a matching upper bound is obtained for a Thompson-Sampling algorithm under a uniform prior over the variances and the two-dimensional means.

We address a generalization of change point detection with the purpose of detecting the change locations and the levels of clusters of a piecewise constant signal. Our approach is to model it as a nonparametric penalized least square model selection on a family of models indexed over the collection of partitions of the design points and propose a computationally efficient algorithm to approximately solve it. Statistically, minimizing such a penalized criterion yields an approximation to the maximum a-posteriori probability (MAP) estimator. The criterion is then analyzed and an oracle inequality is derived using a Gaussian concentration inequality. The oracle inequality is used to derive on one hand conditions for consistency and on the other hand an adaptive upper bound on the expected square risk of the estimator, which statistically motivates our approximation. Finally, we apply our algorithm to simulated data to experimentally validate the statistical guarantees and illustrate its behavior.

In the field of machine learning, the algorithm Adaptive Boosting has been successfully applied to a wide range of regression and classification problems. However, to the best of the authors' knowledge, the use of this algorithm to estimate dynamical systems has not been exploited. In this brief, we explore the connection between Adaptive Boosting and system identification, and give examples of an identification method that makes use of this connection. We prove that the resulting estimate converges to the true underlying system for an output-error model structure under reasonable assumptions in the large sample limit and derive a bound of the model mismatch for the noise-free case.

This paper considers a number of related inverse filtering problems for hidden Markov models (HMMs). In particular, given a sequence of state posteriors and the system dynamics; i) estimate the corresponding sequence of observations, ii) estimate the observation likelihoods, and iii) jointly estimate the observation likelihoods and the observation sequence. We show how to avoid a computationally expensive mixed integer linear program (MILP) by exploiting the algebraic structure of the HMM filter using simple linear algebra operations, and provide conditions for when the quantities can be uniquely reconstructed. We also propose a solution to the more general case where the posteriors are noisily observed. Finally, the proposed inverse filtering algorithms are evaluated on real-world polysomnographic data used for automatic sleep segmentation.

We consider estimating the transition probability matrix of a finite-state finite-observation alphabet hidden Markov model with known observation probabilities. We propose a two-step algorithm: a method of moments estimator (formulated as a convex optimization problem) followed by a single iteration of a Newton-Raphson maximum-likelihood estimator. The two-fold contribution of this letter is, first, to theoretically show that the proposed estimator is consistent and asymptotically efficient, and second, to numerically show that the method is computationally less demanding than conventional methods-in particular for large datasets.

In this paper, we consider the recovery of piecewise sparse signals from incomplete noisy measurements via a greedy algorithm. Here piecewise sparse means that the signal can be approximated in certain domain with known number of nonzero entries in each piece/segment. This paper makes a two-fold contribution to this problem: 1) formulating a piecewise sparse model in the framework of compressed sensing and providing the theoretical analysis of corresponding sensing matrices; 2) developing a greedy algorithm called piecewise orthogonal matching pursuit (POMP) for the recovery of piecewise sparse signals. Experimental simulations verify the effectiveness of the proposed algorithms.

It is often desirable to find the underlying trends in time series data. This is a well known signal processing problem that has many applications in areas such as financial data analysis, climatology, biological and medical sciences. Mean filtering finds a piece-wise constant trend in the data while trend filtering finds a piece-wise linear trend. When the signal is noisy, the main difficulty is finding the changing points in the data that mark the transition points when the mean or the trend changes. Previously proposed methods based on ℓ1filtering suffer from the occurrence of false changing points in the estimate. This is known as the stair-case effect. The main contribution in this paper is incorporating a technique to remove these false changing points to a fast mean filtering algorithm, referred to as the taut-string method, resulting in an efficient procedure with accurate change point detection and thus the removal of the stair-case effect.

In this paper we study the estimation of changing trends in time-series using ℓ1trend filtering. This method generalizes 1D Total Variation (TV) denoising for detection of step changes in means to detecting changes in trends, and it relies on a convex optimization problem for which there are very efficient numerical algorithms. It is known that TV denoising suffers from the so-called stair-case effect, which leads to detecting false change points. The objective of this paper is to show that ℓ1trend filtering also suffers from a certain stair-case problem. The analysis is based on an interpretation of the dual variables of the optimization problem in the method as integrated random walk. We discuss consistency conditions for ℓ1trend filtering, how to monitor their fulfillment, and how to modify the algorithm to avoid the stair-case false detection problem.

We consider a class of weighted nuclear norm optimization problems with important applications in signal processing, system identification, and model order reduction. The nuclear norm is commonly used as a convex heuristic for matrix rank constraints. Our objective is to minimize a quadratic cost subject to a nuclear norm constraint on a linear function of the decision variables, where the trade-off between the fit and the constraint is governed by a regularization parameter. The main contribution is an algorithm to determine the so-called approximate regularization path, which is the optimal solution up to a given error tolerance as a function of the regularization parameter. The advantage is that we only have to solve the optimization problem for a fixed number of values of the regularization parameter, with guaranteed error tolerance. The algorithm is exemplified on a weighted Hankel matrix model order reduction problem.

Designing the optimal experiment for the recovery of an unknown system with respect to the end performance metric of interest is a recently established practice in the system identification literature. This practice leads to superior end performance to designing the experiment with respect to some generic metric quantifying the distance of the estimated model from the true one. This is usually done by choosing and fixing the estimation method to either a standard maximum likelihood (ML) or a Bayesian estimator. In this paper, we pose the intuitive question: Can we design better estimators than the usual ones with respect to an end performance metric of interest? Based on a simple linear regression example we affirmatively answer this question.