PhD Proposal: Randomized Methods in Discrete Machine Learning.

Karthik Sankararaman
03.12.2018 10:00 to 12:00
AVW 3258

Discrete machine learning (DiscML) broadly encompasses the class of problems where the central object of interest is a discrete structure and the learning problem is concerned with this structure. In this proposal, we consider three broad classes of problems in DiscML, namely, online matching, multi-armed bandits and causal inference. In the first class the object of interest is matching in bipartite graphs. In the second, we deal with matroids and in the third we consider a structure which is a super-position of a directed acyclic graph (DAG) and an undirected graph. In each of these classes, we consider a specific problem and use randomized methods to solve it. These randomized methods are divided into two categories: first is randomized algorithms with provable guarantees and second is (randomized) stability arguments.
Online stochastic matching: The basic version of this problem and many of its variants model many applications such as display ad recommendation, crowdsourcing markets, etc. They deal with bipartite graphs where one side is available offline while the other side comes online as samples from a dis- tribution. The algorithm has to make an immediate and irrevocable decision, when a vertex comes online. The goal is to devise randomized algorithms to maximize the total weight of matching. In this proposal, we study many variants with a variety of additional constraints and restrictions.
Bandits with resource consumption: In this problem, we consider the variant of the multi-armed bandit problem, introduced by Badanidiyuru et al., where every arm pull is associated with consumption of some finite resources with limited budget. The goal is to minimize regret without violating the budget constraint. We consider the semi-bandit version of the problem where the action set lies within a matroid and provide randomized algorithms for minimizing regret. This abstraction has many applications in auction design, dynamic pricing, etc.
Linear structural equation model for causal inference: In the linear structural equation model of causal inference, we are given two graphs on the same set of vertices, one directed and one undirected both on the same set of vertices. The directed graph represents the causal effects which are observable and the undirected edges represents the unobservable confounding effects. Here we consider a statistical model for the prior of input graphs and analyze the (expected) numerical stability on this family through the notion of condition number.

Examining Committee:

Chair: Dr. Aravind Srinivasan Dept. rep: Dr. John Dickerson Members: Dr. Alex Slivkins