Consider the problem of learning the drift coefficient of a stochastic differential equation from a sample path. In this paper, we assume that the drift is parametrized by a high dimensional vector. We address the question of how long the system needs to be observed in order to learn this vector of parameters. We prove a general lower bound on this time complexity by using a characterization of mutual information as time integral of conditional variance, due to Kadota, Zakai, and Ziv. This general lower bound is applied to specific classes of linear and non-linear stochastic differential equations. In the linear case, the problem under consideration is the one of learning a matrix of interaction coefficients. We evaluate our lower bound for ensembles of sparse and dense random matrices. The resulting estimates match the qualitative behavior of upper bounds achieved by computationally efficient procedures.
An algorithm is presented for topology selection in graphical models of autoregressive Gaussian time series. The graph topology of the model represents the sparsity pattern of the inverse spectrum of the time series and characterizes conditional independence relations between the variables. The method proposed in the paper is based on an l1-type nonsmooth regularization of the conditional maximum likelihood estimation problem. We show that this reduces to a convex optimization problem and describe a large-scale algorithm that solves the dual problem via the gradient projection method. Results of experiments with randomly generated and real data sets are also included. 1. Automatic code generation for real-time convex optimization J. Mattingley and S. Boyd 2. Gradient-based algorithms with applications to signal recovery problems A. Beck and M. Teboulle 3. Graphical models of autoregressive processes J. Songsiri, J. Dahl and L. Vandenberghe 4. SDP relaxation of homogeneous quadratic optimization Z. Q. Luo and T. H. Chang 5. Probabilistic analysis of SDR detectors for MIMO systems A. Man-Cho So and Y. Ye 6. Semidefinite programming, matrix decomposition, and radar code design Y. Huang, A. De Maio and S. Zhang 7. Convex analysis for non-negative blind source separation with application in imaging W. K. Ma, T. H. Chan, C. Y. Chi and Y. Wang 8. Optimization techniques in modern sampling theory T. Michaeli and Y. C. Eldar 9. Robust broadband adaptive beamforming using convex optimization M. Rubsamen, A. El-Keyi, A. B. Gershman and T. Kirubarajan 10. Cooperative distributed multi-agent optimization A. Nenadic and A. Ozdaglar 11. Competitive optimization of cognitive radio MIMO systems via game theory G. Scutari, D. P. Palomar and S. Barbarossa 12. Nash equilibria: the variational approach F. Facchinei and J. S. Pang. We consider linear models for stochastic dynamics. To any such model can be associated a network (namely a directed graph) describing which degrees of freedom interact under the dynamics. We tackle the problem of learning such a network from observation of the system trajectory over a time interval @math . We analyze the @math -regularized least squares algorithm and, in the setting in which the underlying network is sparse, we prove performance guarantees that are as long as this is sufficiently high. This result substantiates the notion of a well defined time complexity' for the network inference problem.