Inauguration: 1:55 PM
The Alan Turing lecture series is a new initiative of ICTS. In this series, eminent Biologists, Computer Scientists, and Engineers would be invited to deliver lectures on significant developments in their areas. Details about this inaugural Turing lecture series and the lecturers are given below.
Prof. Sanjeev Arora
Time: 2:00 - 2:45 PM
Overcoming Computational Intractability in Unsupervised Learning
Given today’s data deluge, unsupervised learning i.e. learning with unlabeled data is becoming increasingly important. Most natural problems in this domain e.g. for models such as mixture models, HMMs, graphical models, topic models and sparse coding/dictionary learning, deep learning are NP-hard. Therefore researchers in practice use either heuristics or convex relaxations with no concrete approximation bounds. Several nonconvex heuristics work well in practice, which is also a mystery. The talk will describe a sequence of recent results whereby rigorous approaches leading to polynomial running time are possible for several problems in unsupervised learning. The proof of polynomial running time usually relies upon nondegeneracy assumptions on the data and the model parameters, and often also on stochastic properties of the data (average-case analysis). Some of these new algorithms are very efficient and practical. e.g. for topic modeling.
Prof. Robert Schapire
Time: 2:45 - 3:30 PM
The Contextual Bandits Problem: A New, Fast, and Simple Algorithm
In the contextual bandits learning problem, the learner must repeatedly decide which action to take in response to an observed context, and is then permitted to observe the received reward, but only for the chosen action. The goal is to learn through experience to behave nearly as well as the best policy (or decision rule) in some possibly very large space of candidate policies. We assume that the learner can only access this policy space using an oracle for solving empirical cost-sensitive classification problems; in practice, most off-the-shelf classification algorithms could be used for this purpose. In this very general setting, we present a new, fast, and simple algorithm that achieves a regret guarantee that is statistically optimal. Moreover, this algorithm makes very modest use of the oracle, which it calls far less than once per round, on average. These properties suggest this may be the most practical contextual bandits algorithm among all existing approaches that are provably effective for general policy classes.
This is joint work with Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford and Lihong Li.
Prof. Ravi Kannan
Time: 4:00 - 4: 45 PM
Versatility of Singular Value Decomposition
Singular Value Decomposition (SVD) is a basic tool to deal with matrix data and has traditionally been applied in a variety of fields. In the modern setting, matrix sizes have increased, but improved sampling based algorithms are still effective. Besides, many new applications of SVD to Gaussian Mixtures, Nearest Neighbors, Topic Modeling etc. have been developed. Combined with a simple device of thresholding, SVD is useful on a new bunch of problems. The talk will discuss from first principles some recent developments.
These lectures jointly organized by ICTS and the Department of Computer Science and Automation, IISc are a part of the Symposium on Learning, Algorithms and Complexity
