Back to Events

Seminar Series

February 28

Vasilis Syrgkanis: Oracle efficient Learning and Auction Design

Vasilis Syrgkanis, Microsoft Research, New England

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-02-28 16:00:00 2017-02-28 17:00:00 America/New_York Vasilis Syrgkanis: Oracle efficient Learning and Auction Design > Abstract. We consider the design of online no-regret algorithms that are computationally efficient, given access to an offline optimization oracle. We present an algorithm we call Generalized Follow-the-Perturbed-Leader and provide conditions under which it achieves vanishing regret and is oracle-efficient. Our second main contribution is introducing a new adversarial auction-design framework for revenue maximization and applying our oracle-efficient learning results to the adaptive optimization of auctions. Our work extends to oracle-efficient algorithms with contextual information, learning with Maximal-in-Range approximation algorithms, and no-regret bidding in simultaneous auctions.>> Joint with: Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E. > Schapire and Jennifer Wortman Vaughan Patil/Kiva G449

February 22

Aaron Roth: Quantifying Tradeoffs Between Fairness and Accuracy in Online Learning

Aaron Roth, University of Pennsylvania

Part Of

4:00P
- 5:00P

Location

G575
Add to Calendar 2017-02-22 16:00:00 2017-02-22 17:00:00 America/New_York Aaron Roth: Quantifying Tradeoffs Between Fairness and Accuracy in Online Learning Abstract:In this talk, I will discuss our recent efforts to formalize a particular notion of “fairness” in online decision making problems, and study its costs on the achievable learning rate of the algorithm. Our focus for most of the talk will be on the “contextual bandit” problem, which models the following scenario. Every day, applicants from different populations submit loan applications to a lender, who must select a subset of them to give loans to. Each population has a (potentially different) mapping from applications to credit-worthiness that is initially unknown to the lender. The fairness constraint we impose roughly translates to: “Less credit worthy individuals should never be preferentially favored over more credit worthy individuals, regardless of group membership”. Despite the fact that this constraint seems consistent with the profit motivation of the bank, we show that imposing a fairness constraint provably slows down learning --- sometimes only mildly, but sometimes substantially, depending on the structure of the problem. Time permitting, we will mention recent extensions to the reinforcement learning setting in which the actions of the learner can affect its environment, and to economic settings in which the learner must be incentivized by a principal to act fairly. Joint Work with Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Seth Neel G575

February 14

Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity

Vitaly Feldman, IBM Research, Almaden Research Center

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-02-14 16:00:00 2017-02-14 17:00:00 America/New_York Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity Abstract: In this talk I'll show how algorithms for convex optimization can beused to derive lower bounds against general convex relaxations forconstraint satisfaction problems. This technique relies on severalrecent advances in understanding of statistical query* (SQ)complexity:1. A notion of SQ dimension of a problem that lower bounds the SQ complexity2. Lower bounds on the SQ dimension of constraint satisfaction problems3. SQ algorithms for stochastic convex optimization.I'll overview these results and give some of their additional applications.* Statistical query algorithms (Kearns, 1993) are algorithms thatinstead of random samples from an input distribution D over a domainX, have access to a SQ oracle for D. Given a real-valued queryfunction g over X, the oracle returns an estimate of the expectationof g on a sample chosen randomly from D.Based on joint works with C. Guzman, W. Perkins and S. Vempala. Patil/Kiva G449

February 07

Silvio Micali: ALGORAND: The True Public Ledger

Silvio Micali, MIT

Part Of

4:00P
- 5:00P

Location

Patil/Kiva G449
Add to Calendar 2017-02-07 16:00:00 2017-02-07 17:00:00 America/New_York Silvio Micali: ALGORAND: The True Public Ledger ABSTRACTA public ledger is a tamperproof sequence of data that can be read and augmented by everyone. Shared public ledgers stand to revolutionize the way a democratic society operates. They secure all kinds of traditional transactions –such as payments, asset transfers, titling– in the exact order in which they occur; and enable totally new transactions ---such as cryptocurrencies and smart contracts. They can remove intermediaries and usher in a new paradigm for trust. As currently implemented, however, public ledgers cannot achieve their enormous potential.Algorand is a quite alternative, truly democratic, and very efficient way to implement a public ledger. Unlike prior implementations based on proof of work, it requires a negligible amount of computation, and generates a transaction history that will not “fork” with overwhelmingly high probability. Patil/Kiva G449