# RAIN schedule for Autumn Quarter 2014-15

The RAIN seminar is held on Wednesdays from **12:00-1:00pm** in **Y2E2 101**. And yes, lunch is provided!

Date |
Speaker |
Topic |
---|---|---|

September 24 | Balasubramanian Sivan | Towards optimal algorithms for prediction with expert advice |

October 8 | Vivek Farias | Online A-B Testing |

October 29 | Fil Menczer | The spread of information in social media |

November 19 | Sergei Vassilvitskii | Inverting a Steady-State |

December 3 | Adam Wierman | Data Centers, Energy, and Online Optimization
(Joint seminar with OIT and OR) Note: Different location [Huang 305] and time [4pm-5pm] |

## Google Calendar for RAIN

# Previous year's talks

Archived talks can be accessed here.

# Talk Abstracts

**Towards optimal algorithms for prediction with expert advice**

Balasubramanian Sivan, Microsoft Research

We study the classic problem of prediction with expert advice. Focusing on settings with a constant number of experts, we develop optimal algorithms and obtain precisely optimal regret values for the case of 2 and 3 experts. Further, we develop regret lower bounds for the multiplicative weights algorithm that exactly match the known upper bounds for an arbitrary number of experts k. This establishes a constant factor separation between the regrets achieved by the optimal algorithm and the multiplicative weights algorithm for a constant number of experts.

The optimal algorithms have a crisp interpretation. For instance, in the case of 2 experts, the optimal algorithm follows the advice of a particular expert with exactly the probability that the expert will turn out to be the best expert.

Our main tool is the minimax principle which lets us analyze the optimal adversary to compute optimal regret values. While analyzing the optimal adversary, we establish deep connections with non-trivial aspects of random walk. We further use this connection to develop an improved regret bound for the case of 4 experts.

Joint work with Nick Gravin and Yuval Peres

**Bio:** Balasubramanian Sivan is a postdoctoral researcher at Microsoft Research, Redmond. He completed his PhD in Computer Science at the University of Wisconsin-Madison in 2013. His PhD thesis on “Prior Robust Optimization” was awarded the 2014 ACM SIGecom doctoral dissertation award and the University of Wisconsin-Madison Computer Science department’s outstanding graduate student researcher award. His research interests are in Algorithmic Game Theory, online and approximation algorithms, expert learning. More details can be found here: http://research.microsoft.com/en-us/um/people/bsivan/

**Online A-B Testing**

Vivek Farias, MIT

We consider the problem of A-B testing when the impact of a treatment is marred by a large number of covariates. This is the situation in a number of modern applications of A-B testing (such as in adTech and e-commerce) as well as in more traditional applications (such as clinical trials). Randomization can be highly inefficient in such settings, and thus we consider the problem of optimally allocating test subjects to either treatment with a view to maximizing the efficiency of our estimate of the treatment effect. Our main contribution is a tractable algorithm for this problem in the online setting where subjects arrive, and must be assigned, sequentially. We also characterize the value of optimization and show that it can be expected to grow large with the number of covariates. Finally, using a real-world impression dataset, we show that our algorithms can be expected to yield substantial improvements to efficiency in practice.

Joint work with Nikhil Bhat and Ciamac Moallemi (Columbia GSB)

**Bio:** Vivek Farias is interested in the development of new methodologies for large scale dynamic optimization and applications in revenue management, finance, marketing and healthcare. He received his Ph.D. in Electrical Engineering from Stanford University in 2007 and has been at MIT since, where he is the Robert N. Noyce Professor of Management. Outside academia, Vivek has contributed to ventures in finance and technology in the role of a researcher, consultant or founder. Vivek is a recipient of an IEEE Region 6 Undergraduate Student Paper Prize (2002), an INFORMS MSOM Student Paper Prize (2006), an MIT Solomon Buchsbaum Award (2008), an INFORMS JFIG paper prize twice (2009, 2011), the NSF CAREER award (2011), MIT Sloan’s Outstanding Teacher award (2013), and was a finalist for the 2011 INFORMS Pierskalla award in healthcare.

**The spread of information in social media**

Fil Menczer, Yahoo Labs/Indiana University

This talk overviews ongoing work on information diffusion in
social media, focusing in particular on mining, modeling, and
prediction tasks on data from the Twitter network. I present machine
learning efforts that leverage the structure of meme diffusion
networks and many other features to detect misinformation campaigns,
such as astroturf and social bots. We employ modeling techniques to
understand the formation of communities, the creation of social ties,
and the competition for attention. We investigate how different forms
of structural and topical diversity in the network can be leveraged to
predict which memes will go viral. Finally, it time permits, I will
review a few crowdsourcing projects exploring the computation of
unbiased scholarly impact metrics, the anonymous collection of
sensitive data, and social good.

Joint work with many members of the Center for Complex Networks and Systems Research at Indiana University. This
research is supported by the National Science Foundation, McDonnell
Foundation, and DARPA. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the authors
and do not necessarily reflect the views of these funding agencies.

**Bio:** Filippo Menczer is a visiting scientist at Yahoo Labs in Sunnyvale during 2014-15 while on sabbatical from Indiana University, where he is a professor of informatics and computer science, adjunct professor of physics, and a member of the cognitive science program. He holds a Laurea in Physics from the
University of Rome and a Ph.D. in Computer Science and Cognitive
Science from the University of California, San Diego. Dr. Menczer has
been the recipient of Fulbright, Rotary Foundation, and NATO fellowships, and a Career Award from the National Science Foundation. He serves as director of the Center for Complex Networks and Systems Research and is a Fellow of the Institute for Scientific Interchange Foundation in Torino, Italy, a Senior Research Fellow of The Kinsey Institute, and an ACM Distinguished Scientist. He previously served as division chair in the IUB School of Informatics and Computing, and was Fellow-at-large of the Santa Fe Institute. His research focuses on Web science, social networks, social media, social computation, Web
mining, distributed and intelligent Web applications, and modeling of
complex information networks. His work has been covered in The New
York Times, Wall Street Journal, NPR, CNN, The Economist, Nature,
Science, The Washington Post, Wired, The Atlantic, BBC, and many other
US and international news sources.

**Inverting a Steady-State**

Sergei Vassilvitskii, Google Research

We consider the problem of inferring choices made by users from data that only contains the relative popularity of each item. We propose a framework that models the problem as that of inferring a Markov chain given its stationary distribution. Formally, given a graph and a distribution on its nodes, the goal is to assign scores to nodes such that the stationary distribution of the following Markov chain will equal the given distribution on nodes: the transition probability from a node to its neighbor is proportional to the score of the neighbor. We prove sufficient conditions under which this problem is feasible, and, for the feasible instances, obtain a simple algorithm for a generic version of the problem. This iterative algorithm provably finds the unique solution to this problem and has a polynomial rate of convergence. In practice we find that the algorithm converges after fewer than 10 iterations. We then apply this framework to choice problems in online settings and show that our algorithm is able to explain the observed data and predict the user choice, much better than other competing baselines across a variety of diverse datasets.

Joint work with Ravi Kumar, Andrew Tomkins, and Erik Vee.

**Bio:** Sergei Vassilvitskii is a currently a Research Scientist at Google and a Fellow at the Applied Statistics Center at Columbia University. Previously, he was a Research Scientist at Yahoo! Research and an Adjunct Assistant Professor at Columbia University. He completed his PhD at Stanford University under the supervision of Rajeev Motwani.

**Data Centers, Energy, and Online Optimization**

Adam Wierman, California Institute of Technology

This talk will tell two parallel stories, one about designing sustainable data centers and one about the underlying algorithmic challenges, which fall into the context of online convex optimization.

Story 1: The typical story surrounding data centers and energy is an extremely negative one: Data centers are energy hogs. This message is pervasive in both the popular press and academia, and it certainly
rings true. However, the view of data centers as energy hogs is too simplistic. One goal of this talk is to highlight that, yes, data centers use a lot of energy, but data centers can also be a huge
benefit in terms of integrating renewable energy into the grid and thus play a crucial role in improving the sustainability of our energy landscape. In particular, I will highlight a powerful alternative
view: data centers as demand response opportunities.

Story 2: Typically in online convex optimization it is enough to exhibit an algorithm with low (sub-linear) regret, which implies that the algorithm can match the performance of the best static solution in
retrospect. However, what if one additionally wants to maintain performance that is nearly as good as the dynamic optimal, i.e., a good competitive ratio? In this talk, I'll highlight that it is impossible
for an online algorithm to simultaneously achieve these goals. Luckily though, in practical settings (like data centers), noisy predictions about the future are often available, and I will show that, under
a general model of prediction noise, even very limited predictions about the future are enough to overcome the impossibility result.

**Bio:**Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is a founding member of the Rigorous Systems Research Group (RSRG) and maintains a popular blog called Rigor + Relevance. His research interests center around resource allocation and scheduling decisions in computer systems and services. He received the 2011 ACM SIGMETRICS Rising Star award, the 2014 IEEE Communications Society William R. Bennett Prize, and has been coauthor on papers that received of best paper awards at ACM SIGMETRICS, IEEE INFOCOM, IFIP Performance (twice), IEEE Green Computing Conference, IEEE Power & Energy Society General Meeting, and ACM GREENMETRICS.