Several important problems in machine learning, such as maximum aposteriori (MAP) inference in graphical models, are inherently combinatorial. While extensive research has been devoted to designing approximation algorithms for such problems, existing algorithms do not scale well to large problems. This project focuses on leveraging ideas from online learning with expert advice to develop a novel family of online learning algorithms for combinatorial optimization problems.
Algorithms for combinatorial online learning are efficient and simple to analyze in order to establish guarantees. Unlike existing literature on approximation algorithms for combinatorial problems which rely on suitable real relaxations of the original problem, combinatorial online learning algorithms never use relaxations; they work directly with binary/integer solutions and have global approximation guarantees. The project investigates generalizations of the framework to solve online and batch binary quadratic programming problems, yielding approximation algorithms for a variety of combinatorial problems, including NP-complete problems, and MAP inference in directed and undirected graphical models. The project considers three important real life applications: portfolio selection for effectively investing in the stock market, automating surgical pathology by expediting disease detection in tissue images, and climate change detection for discovering abrupt climate changes from spatiotemporal climate data.
The project is expected to be transformative, especially in the context of surgical pathology and climate change detection, yielding significant long term societal benefits. The research results will be disseminated to the community through research papers, tutorials, open source software, and outreach activities using games based on mock stock markets.
