Menu:

Tutorials


All tutorials will be held on Friday, June 19th, 2015. Details are given below.


Bandit Optimization: Theory and Applications

(Slides in PDF: Part 1, Part 2)

Time: 9:00am – 12:30pm

Speakers: Richard Combes (Supélec) and Alexandre Proutiere (KTH)

Abstract: Stochastic Multi-Armed Bandit (MAB) problems constitute the most fundamental sequential decision problems with an exploration vs. exploration trade-off. In such problems, the decision maker selects an arm or action in each round, and observes a realization of the corresponding reward whose distribution is unknown. The objective is to maximize the expected cumulative reward over some time horizon by balancing exploitation (actions with the highest observed rewards so far should be selected often) and exploration (all actions should be explored). MAB problems have found applications in many disciplines including medical treatment, communication systems, online services, economics, and physics. This tutorial provides a survey of recent advances in bandit optimization, and of the mathematical tools used to devise and analyze the performance of algorithms. We also present various relevant and contemporary applications, and highlight a few interesting open problems.

Bios: Richard Combes is currently an assistant professor in Supelec. He received the Engineering Degree from Telecom Paristech (2008), the Master Degree in Mathematics from university of Paris VII (2009) and the Ph.D. degree in Mathematics from university of Paris VI (2013). He was a visiting scientist at INRIA (2012) and a post-doc at KTH (2013). He received the best paper award at CNSM 2011. His current research interests are machine learning, networks and probability.

Alexandre Proutiere graduated in Mathematics from Ecole Normale Superieure (Paris), and got an engineering degree from Ecole Nationale Superieure des Telecoms (Paris). He is an engineer from Corps of Mines, and received his PhD in Applied Mathematics from Ecole Polytechnique, Palaiseau, France in 2003. From 1998 to 2000, he worked in the radio communication department at the Ministry of Foreign Affairs in Paris. He joined James Roberts' research group at France Telecom R&D in 2000. From 2007 to 2011, he held a position of researcher at Microsoft Research in Cambridge (UK). He is now Associate Professor at KTH, Sweden. Alexandre was the recipient in 2009 of the ACM Sigmetrics rising star award, and received twice the best paper awards at ACM Sigmetrics conference, and once at the ACM Mobihoc conference. He is an associate editor of IEEE Transactions on Networking, and of Queueing systems and applications. His research is supported by an ERC consolidator grant.


Social Search and Social Recommendations

Time: 1:45pm – 3:15pm

Speaker: Ashish Goel (Stanford)

Abstract: We will present efficient algorithms for many social search and recommendation problems. One particular emphasis will be algorithms that can be easily implemented on distributed platforms such as MapReduce/Hadoop, Spark, and Storm. The algorithms covered will include incremental and personalized Page Rank, Cosine Similarity, and searching for the closest instance of a word in a social network. We will motivate these problems with concrete examples of deployed systems.

Bio: Ashish Goel is a Professor of Management Science and Engineering and (by courtesy) Computer Science at Stanford University, and a member of Stanford's Institute for Computational and Mathematical Engineering. He received his PhD in Computer Science from Stanford in 1999, and was an Assistant Professor of Computer Science at the University of Southern California from 1999 to 2002. His research interests lie in the design, analysis, and applications of algorithms; current application areas of interest include social networks, participatory democracy, Internet commerce, and large scale data processing.

Professor Goel is a recipient of an Alfred P. Sloan faculty fellowship (2004-06), a Terman faculty fellowship from Stanford, an NSF Career Award (2002-07), and a Rajeev Motwani mentorship award (2010). He was a co-author on the paper that won the best paper award at WWW 2009, and an Edelman Laureate in 2014. Professor Goel was a research fellow and technical advisor at Twitter, Inc. from July 2009 to Aug 2014.


Learning with Strategic Agents: From Adversarial Learning to Game-Theoretic Statistics

Time: 3:45pm – 5:15pm

Speaker: Patrick Loiseau (EURECOM)

Abstract: Statistical learning methods developed in the last decades have proved very useful for many applications. However, most algorithms were developed under the assumption that the data is independent from the algorithm. This is no longer true in applications where data is generated or provided by (human) strategic agents. As more and more modern applications (in particular online applications) learn from data generated or provided by external parties who can act strategically, it becomes increasingly important to account for the data-provider's incentives in order to design well-performing learning algorithms in practice.

In this tutorial, we first present the methods called adversarial learning developed for security applications since the late 2000's. These methods aim at exposing the vulnerabilities of learning algorithms to data generated by an adversary and at developing algorithms that are robust to worst-case attacks (making various assumptions on the capability and information of the adversary). Then, we present more recent methods based on game theory that propose to model the utility of the adversary and of the learner in order to develop algorithms that are optimal at Nash equilibrium. These methods are more flexible and less pessimistic than worst-case analysis. They also reveal interesting insights into the learning problem.

If time permits, we will finally present recent works on learning from data provided by strategic agents. These works, originally motivated by applications where agents obfuscate their data before revealing it to protect their privacy, propose to develop general learning methods that incentivize agents to reveal high-quality data in order to improve the model learned.

Bio: Patrick Loiseau is an Assistant Professor at EURECOM (Sophia-Antipolis, France) since November 2011. He was recently a visiting researcher at UC Berkeley (summer 2012) and at MPI-SWS (summer 2014). He received a Ph.D. in Computer Science (2009) from ENS Lyon and a M.Sc. in Mathematics from UPMC (Paris 6) and Ecole Polytechnique (2010). Patrick Loiseau's research is in the areas of game theory and statistics and their application to network economics. His main interests are currently in game-theoretic statistical learning for security, economics of personal data, and resource allocation and pricing for cloud and security.