Efficient Algorithms for Learning Combinatorial Structures from Limited Data

Recovering combinatorial structures from noisy observations is a recurrent problem in many application domains, including, but not limited to, natural language processing, computer vision, genetics, health care, and automation. For instance, dependency parsing in natural language processing entails recovering parse trees from sentences which are inherently ambiguous. From a computational standpoint, such problems are typically intractable and call for designing efficient approximation or randomized algorithms with provable guarantees. From a statistical standpoint, algorithms that recover the desired structure using an optimal number of samples are of paramount importance.

This talk will introduce several such problems in the areas of causal inference, game theory and structured prediction, and present computationally and statistically efficient procedures for the same. Specifically,

(i) I will present polynomial-time algorithms for learning linear structural equation models — which are a widely used class of models for performing causal inference — that recover the correct directed acyclic graph structure under identifiability conditions that are weaker than existing conditions. I will also show that the sample complexity of our method is information-theoretically optimal.

(ii) I will present polynomial-time algorithms for learning the underlying graphical game from observations of the behavior of self-interested agents. The key combinatorial problem here is to recover the Nash equilibria set of the true game from behavioral data. I will present fundamental lower bounds on the number of samples required for learning games and show that our method is statistically optimal.

(iii) Lastly, departing from the generative model framework, the talk will delve into the problem of structured prediction where the goal is to learn predictors from data that predict complex structured objects directly from a given input. I will present an efficient learning algorithm for learning structured predictors by approximating the partition function and obtain generalization guarantees for our method. I will demonstrate that randomization can not only improve efficiency but also generalization to unseen data.