UW – MSR Machine Learning workshop 2015 – Session 3

13:00Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning – Brendan McMahan We analyze new online gradient descent algorithms for distributed systems with large delays between gradient computations and the corresponding updates. Using insights from adaptive gradient methods, we develop algorithms that adapt not only to the sequence of gradients, but also to the precise update delays that occur. We first give an impractical algorithm that achieves a regret bound that precisely quantifies the impact of the delays. We then analyze AdaptiveRevision, an algorithm that is efficiently implementable and achieves comparable guarantees. The key algorithmic technique is appropriately and efficiently revising the learning rate used for previous gradient steps. Experimental results show when the delays grow large (1000 updates or more), our new algorithms perform significantly better than standard adaptive gradient methods.

13:25 Offline Evaluation in Contextual Bandits – Lihong Li In contextual bandits, one observes the payoff for the chosen arm, but not the others. This counterfactual nature of the payoff leads to the difficulty of using historical data to evaluate a new arm-selection policy: when the new policy chooses an arm different from the one in the data, we simply do not have the payoff signal to do evaluation. It might appear that the only reliable way to estimate a new policy’s per-round payoff is to run it in the real bandit problem, a process that can be both expensive and slow. In this talk, through a case study at Bing, we show how historical data can be collected properly to enable *unbiased* offline evaluation, using statistical tools from causal inference. We will also discuss recent progress toward finding statistically optimal estimators for this offline evaluation problem.

13:50Spotlight: Finite population inference for causal parameters – Wen Wei Loh In a randomized experiment with non-compliance, testing whether treatment exposure X has an effect on the final response Y is often of scientific interest. We propose a finite-population significance test of the sharp null hypothesis that X has no effect on Y, within the principal stratum of compliers, using the likelihood ratio.

13:55Spotlight: A General Framework for Meta-Analysis of High-Dimensional Network Inference – Safiye Celik Inferring a high-dimensional graphical model is a key analysis tool in many fields including biology, computer vision and robotics. However, it is hampered by the need for very large sample sizes that are hard to be provided by a single dataset. A natural solution is to combine datasets available from similar studies to increase the sample size, but the discrepancy in variables makes it impossible to integrate these datasets into a single statistical model. For example, inferring a network of genes from expression data is a popular analysis method in the field of genomics. Combining expression data from multiple similar studies would increase the sample size of data for gene network inference. However, expression datasets from different studies are often generated by using different platforms or technologies that do not have exactly the same sets of variables. A naive approach is to impute the values on the variables that are missing in each dataset; however, most imputation methods perform poorly when the entire values are missing for a large number of variables. We present a novel network inference framework that can integrate datasets from different studies containing sets of variables with a partial overlap into a single statistical model. The proposed algorithm will significantly increase the applicability of network analysis by leveraging existing data, and will eliminate the cost of regenerating data from the same samples using different platforms.

Speaker Details

Lihong Li is a Researcher in the Machine Learning Group at Microsoft Research. Prior to joining MSR, he was a Research Scientist in the Machine Learning Group at Yahoo! Research. He obtained a PhD degree in Computer Science from Rutgers University. His main research interests are in machine learning with interaction, including reinforcement learning, multi-armed bandits, online learning, active learning, and their numerous applications on the Internet. More information can be found on his homepage: http://research.microsoft.com/en-us/people/lihongli .

Date:
Speakers:
Brendan McMahan, Lihong Li, Wen Wei Loh, and Safiye Celik
Affiliation:
Google, Microsoft Research, University of Washington
    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Lihong Li

      Lihong Li

      Principal Researcher