Learning Theory Alliance

Spotlight Talk Abstracts.

1. Bridging Learning and Decision Making: Recent Progress in Contextual Bandits. Dylan Foster. Machine learning is becoming widely used in decision making, in domains ranging from personalized medicine and mobile health to online education and recommendation systems. While (supervised) machine learning traditionally excels at prediction problems, decision making requires answering questions that are counterfactual in nature, and ignoring this mismatch leads to unreliable decisions. As a consequence, our understanding of the algorithmic foundations for data-driven decision making is limited, and efficient algorithms are typically developed on an ad hoc basis. Can we bridge this gap and make decision making as easy as machine learning? Focusing on the contextual bandit, a core problem in data-driven decision making, we bridge the gap by providing the first optimal and efficient reduction to supervised machine learning. The algorithm allows users to seamlessly apply off-the-shelf supervised learning models and methods to make decisions on the fly, and has been implemented in widely-used, industry-standard tools for decision making.
2. Non-parametric exploration in multi-armed bandits. Emilie Kaufmann. Multi-Armed Bandit models are powerful to describe several sequential resource allocation tasks in a stochastic environments, e.g., the design of a recommendation algorithm or an adaptive clinical trial. This simple model also captures the exploration/exploitation dilemma that is central in more structured reinforcement learning problems. The two most famous approaches to MABs, namely Upper Confidence Bounds and Thompson Sampling, share the need for some prior information about the arms’ distributions in order to attain optimal performance. We will discuss other families of algorithms based on sub-sampling that perform well in practice and can be proved to be optimal for different families of distributions.
3. Boosting Simple Learners. Shay Moran Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting under the assumption that the weak hypotheses belong to a class of bounded capacity. This assumption is inspired by the common convention that weak hypotheses are “rules-of-thumbs” from an “easy-to-learn class”. (Schapire and Freund ’12, Shalev-Shwartz and Ben-David ’14.) Formally, we assume the class of weak hypotheses has a bounded VC dimension. We focus on two main questions:
   • Oracle Complexity: How many weak hypotheses are needed in order to produce an accurate hypothesis? We design a novel boosting algorithm and demonstrate that it circumvents a classical lower bound by Freund and Schapire (’95, ’12). Unlike previous boosting algorithms which aggregate the weak hypotheses by majority votes, the new boosting algorithm uses more complex (“deeper”) aggregation rules. We complement this result by showing that complex aggregation rules are in fact necessary to circumvent the aforementioned lower bound.
   • Expressivity: Which tasks can be learned by boosting weak hypotheses from a bounded VC class? Can complex concepts that are “far away” from the class be learned? Towards answering the first question we identify a combinatorial-geometric parameter which captures the expressivity of base-classes in boosting. Along the way, we establish and exploit connections with Discrepancy Theory.
   Joint work with Noga Alon, Alon Gonen, and Elad Hazan.