IDSS Special Seminar

The strategic interaction of multiple parties with different objectives is at the heart of modern large scale computer systems and electronic markets. Participants face such complex decisions in these settings that the classic economic equilibrium is not a good predictor of their behavior. The analysis and design of these systems has to go beyond equilibrium assumptions. Evidence from online auction marketplaces suggests that participants rather use algorithmic learning. In the first part of the talk, I will describe a theoretical framework for the analysis and design of efficient market mechanisms, with robust guarantees that hold under learning behavior, incomplete information and in complex environments with many mechanisms running at the same time. In the second part of the talk, I will describe a method for analyzing datasets from such marketplaces and inferring private parameters of participants under the assumption that their observed behavior is the outcome of a learning algorithm. I will give an example application on datasets from Microsoft’s sponsored search auction system.

Most applications of machine learning across science and industry rely on the holdout method for model selection and validation. Unfortunately, the holdout method often fails in the now common scenario where the analyst works interactively with the data, iteratively choosing which methods to use by probing the same holdout data many times. In this talk, we apply the principle of algorithmic stability to design reusable holdout methods, which can be used many times without losing the guarantees of fresh data. Applications include a model benchmarking tool that detects and prevents overfitting at scale. We conclude with a bird’s eye view of what algorithmic stability says about machine learning at large, including new insights into stochastic gradient descent, the most popular optimization method in contemporary machine learning.