2011 Poster Sessions : Efficient Algorithms for Learning Stochastic Differential Equations

Student Name : José Bento, Morteza Ibrahimi
Advisor : Andrea Montanari
Research Areas: Information Systems
Abstract:
We consider the problem of learning the drift coefficient of a stochastic differential equation (SDE). To many such models can be associated a network describing which degrees of freedom interact under the dynamics. This is the case, for example, when the SDE is linear in the original variables or in an expanded basis (non-linear functions of the variables). We tackle the problem of learning such a network from observation of the system trajectory over a time interval $T$. We show that there exist a well defined `time complexity' for the network inference problem, and prove lower bounds on sample complexity under different regimes.

We analyze the $ell_1$-regularized least squares algorithm and, in the setting in which the underlying network is sparse and the system is linear, we derive performance guarantees that are emph{uniform in the sampling rate} as long as this is sufficiently high. Furthermore, the required sample complexity asymptotically matches the lower bound obtained. These results prove this algorithm as an efficient procedure, both in terms of sample complexity and computation complexity, for learning high dimensional SDEs.

Bios:
José Bento is a PhD candidate at Stanford University (department of Electrical Engineering) working with professor Andrea Montanari. His research focuses on statistical inference and structural learning of graphical models. He graduated from O'Porto University, Portugal, with a masters degree in Electrical Engineering in 2006 in the area of automation and control and in the same year was awarded a PhD fellowship from the Portuguese Foundation for Science and Technology.

Morteza Ibrahimi is a PhD candidate at Stanford University, Department of Electrical Engineering, working with professor Andrea Montanari. His research interests are in learning graphical models, optimization through message passing algorithms, and statistical inference with high dimensional data, specially through fast iterative algorithms. He received his BS from Sharif University of Technology in 2006, and from University of Toronto in 2007.