Tuhin Sarkar

Tuhin Sarkar, Alexander Rakhlin

We derive finite time error bounds for estimating general linear time-invariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a self--normalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signal-to-noise ratio is high.

Tuhin Sarkar, Alexander Rakhlin, Munther A. Dahleh

We address the problem of learning the parameters of a stable linear time invariant (LTI) system or linear dynamical system (LDS) with unknown latent space dimension, or order, from a single time--series of noisy input-output data. We focus on learning the best lower order approximation allowed by finite data. Motivated by subspace algorithms in systems theory, where the doubly infinite system Hankel matrix captures both order and good lower order approximations, we construct a Hankel-like matrix from noisy finite data using ordinary least squares. This circumvents the non-convexities that arise in system identification, and allows accurate estimation of the underlying LTI system. Our results rely on careful analysis of self-normalized martingale difference terms that helps bound identification error up to logarithmic factors of the lower bound. We provide a data-dependent scheme for order selection and find an accurate realization of system parameters, corresponding to that order, by an approach that is closely related to the Ho-Kalman subspace algorithm. We demonstrate that the proposed model order selection procedure is not overly conservative, i.e., for the given data length it is not possible to estimate higher order models or find higher order approximations with reasonable accuracy.

Tuhin Sarkar, Mardavij Roozbehani, Munther A. Dahleh

We consider the problem of robustness in large consensus networks that occur in many areas such as distributed optimization. Robustness, in this context, is the scaling of performance measures, e.g. H2-norm, as a function of network dimension. We provide a formal framework to quantify the relation between such performance scaling and the convergence speed of the network. Specifically, we provide upper and lower bounds for the convergence speed in terms of robustness and discuss how these bounds scale with the network topology. The main contribution of this work is that we obtain tight bounds, that hold regardless of network topology. The work here also encompasses some results in convergence time analysis in previous literature.

Tuhin Sarkar, Mardavij Roozbehani, Munther A. Dahleh

This paper addresses two fundamental problems in the context of jump linear systems (JLS). The first problem is concerned with characterizing the minimal state space dimension solely from input-output pairs and without any knowledge of the number of mode switches. The second problem is concerned with characterizing the number of discrete modes of the JLS. For the first problem, we develop a linear system theory based approach and construct an appropriate Hankel-like matrix. The rank of this matrix gives us the state space dimension. For the second problem we show that minimal number of modes corresponds to the minimal rank of a positive semi-definite matrix obtained via a non--convex formulation.

X. Flora Meng, Tuhin Sarkar, Munther A. Dahleh

We study the problem of nonstochastic bandits with expert advice, extending the setting from finitely many experts to any countably infinite set: A learner aims to maximize the total reward by taking actions sequentially based on bandit feedback while benchmarking against a set of experts. We propose a variant of Exp4.P that, for finitely many experts, enables inference of correct expert rankings while preserving the order of the regret upper bound. We then incorporate the variant into a meta-algorithm that works on infinitely many experts. We prove a high-probability upper bound of $\tilde{\mathcal{O}} \big( i^*K + \sqrt{KT} \big)$ on the regret, up to polylog factors, where $i^*$ is the unknown position of the best expert, $K$ is the number of actions, and $T$ is the time horizon. We also provide an example of structured experts and discuss how to expedite learning in such case. Our meta-learning algorithm achieves optimal regret up to polylog factors when $i^* = \tilde{\mathcal{O}} \big( \sqrt{T/K} \big)$. If a prior distribution is assumed to exist for $i^*$, the probability of optimality increases with $T$, the rate of which can be fast.

Dylan J. Foster, Alexander Rakhlin, Tuhin Sarkar

We introduce algorithms for learning nonlinear dynamical systems of the form $x_{t+1}=σ(Θ^{\star}x_t)+\varepsilon_t$, where $Θ^{\star}$ is a weight matrix, $σ$ is a nonlinear link function, and $\varepsilon_t$ is a mean-zero noise process. We give an algorithm that recovers the weight matrix $Θ^{\star}$ from a single trajectory with optimal sample complexity and linear running time. The algorithm succeeds under weaker statistical assumptions than in previous work, and in particular i) does not require a bound on the spectral norm of the weight matrix $Θ^{\star}$ (rather, it depends on a generalization of the spectral radius) and ii) enjoys guarantees for non-strictly-increasing link functions such as the ReLU. Our analysis has two key components: i) we give a general recipe whereby global stability for nonlinear dynamical systems can be used to certify that the state-vector covariance is well-conditioned, and ii) using these tools, we extend well-known algorithms for efficiently learning generalized linear models to the dependent setting.

Tuhin Sarkar, Mardavij Roozbehani, Munther A. Dahleh

This paper examines the dependence of network performance measures on network size and considers scaling results for large networks. We connect two performance measures that are well studied, but appear to be unrelated. The first measure is concerned with energy metrics, namely the $\Hcal_2$--norm of a network, which arises in control theory applications. The second measure is concerned with the notion of "tail risk" which arises in economic and financial networks. We study the question of why such performance measures may deteriorate at a faster rate than the growth rate of the network. We first focus on the energy metric and its well known connection to controllability Gramian of the underlying dynamical system. We show that undirected networks exhibit the most graceful energy growth rates as network size grows. This rate is quantified completely by the proximity of spectral radius to unity or distance to instability. In contrast, we show that the simple characterization of energy in terms of network spectrum does not exist for directed networks. We demonstrate that, for any fixed distance to instability, energy of a directed network can grow at an exponentially faster rate. We provide general methods for manipulating networks to reduce energy. In particular, we prove that certain operations that increase the symmetry in a network cannot increase energy (in an order sense). Secondly, we focus on tail risk in economic and financial networks. In contrast to $\Hcal_2$--norm which arises from computing the expectation of energy in the network, tail risk focuses on tail probability behavior of network variables. Although the two measures differ substantially we show that they are precisely connected through the system Gramian. This surprising result explains why topology considerations rather than specific performance measures dictate the large scale behavior of networks.