Fairness and The Problem with Exploration: A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem

Bandit Problems

"Bandit problems" are a common abstraction in machine learning. The name is supposed to evoke the image of slot machines, which are also known as "One-armed bandits" (or so I am told... Somehow nobody speaks like this in the circles I run in.) In the classic formulation, you imagine yourself standing in front of a bank of slot machines, each of which is different and might have a different distribution on payoffs. You can sequentially decide which machine's arm to pull: when you pull the arm, you get a sample from that machine's reward distribution. Your goal is to pull the arms in such a way so that your average reward approaches what it would have been had you played the optimal strategy in hindsight: i.e. always pulled the arm of the machine that had the highest mean reward. The problem is tricky because you don't know the reward distributions to start. The key feature of the problem is that in order to observe a sample from the reward distribution of a particular machine, you actually have to pull that arm and spend a turn to do it.

There are more complicated variants of this kind of problem, in which your choices may vary from round to round, but have differentiating features. For example, in the linear contextual bandit problem, in every round, you are presented with a number of choices, each of which is represented by some real valued vector, which may be different from round to round. You then get to choose one of them. The reward you get, corresponding to the action you choose, is random --- but its expectation is equal to some unknown linear function of the action's features. The key property of the problem is that you only get to observe the reward of the action you choose. You do not get to observe the reward you would have obtained had you chosen one of the other actions --- this is what makes it a bandit problem. The goal again is to choose actions such that your average reward approaches what it would have been had you played the optimal strategy in hindsight. In this case, with full knowledge of the underlying linear functions, the optimal strategy would simply compute the expected reward of each action, and play the action with highest expected reward (this may now be a different action at  each round, since the features change). Again, the problem is tricky because you don't know the linear functions which map features to expected reward. 

Bandit problems are characterized by the tension between exploration and exploitation. At any given moment, the algorithm has some guess as to what the best action is. (In a linear contextual bandit problem, for example, the algorithm might just run least-squares regression on the examples it has observed rewards for: the point predictions of the regression estimate on the new actions are these best guesses). In order to be able to compete with the optimal policy, the algorithm definitely needs to (eventually) play the action it thinks is the best one, a lot of the time. This is called exploitation: the algorithm is exploiting its knowledge in order to do well. However, since the algorithm does not observe the rewards for actions it does not play, it also will generally need to explore. Consider someone in front of those slot machines: if he has played each machine once, he has some weak beliefs about the payoff distribution for each machine. But those beliefs have resulted from just a single sample, so they may well be very wrong. If he just forever continues to play the machine that has the highest empirical reward, he might play the same machine every day, and he will never learn more about the other machines  --- even though one of them might have turned out to really have higher average reward. He has fooled himself, and because he never explores, he continues to be wrong forever. So optimal algorithms have to carefully balance exploration and exploitation in order to do well. 

There are various clever schemes for trading off exploration and exploitation, but the simplest one is called epsilon-Greedy. At every round, the algorithm flips a coin with bias epsilon. If the coin comes up heads (with probability 1-epsilon), the algorithm exploits: it just greedily chooses the action that it estimates to be best. If the coin comes up tails (with probability epsilon), the algorithm explores: it chooses an action uniformly at random. If you set epsilon appropriately, in many settings, you have the guarantee that the average reward of the algorithm will approach the average reward of the optimal policy, as time goes on. Fancier algorithms for bandit problems more smoothly interpolate between exploration and exploitation: but all of them inevitably have to manage this tradeoff. 

Fairness Concerns

(Contextual) bandit problems are not just an interesting mathematical curiosity, but actually arise all the time in important applications. Here are just a few:

• Lending: Banks (and increasingly algorithms) consider applicants for loans. They can look at applicant features, and observe the repayment history of applicants they grant loans to, but they cannot observe counterfactuals: would an applicant not given a loan have defaulted if he had been given the loan? 
• Parole Decisions: Judges (and increasingly algorithms) consider inmates for parole. In part, they want to predict which inmates will go on to re-offend if released, and not release those inmates. But it is not possible to observe the counterfactual: would an inmate who was not released have gone on to commit a crime if he had been released? 
• Predictive Policing: Police chiefs (and increasingly algorithms) consider where in their city they want to deploy their police. In part, they want to predict where crimes will occur, so they can deploy a heavier police presence in those areas. But they also disproportionately observe crimes in the areas in which police are deployed.
• Sequential Clinical Trials: Certain kinds of drugs affect patients differently, depending on their genetic markers. But for a new drug, the relationship might be unknown. As patients show up, they can be assigned to different clinical trials, corresponding to different drugs --- but we cannot observe the counterfactual: how would a patient have reacted to a drug she was not given? 

I picked these four examples (rather than the more commonly used example of ad targeting) because in each of the above examples, the decision made by the algorithm has an important effect on someone's life. This raises issues of fairness, and as we will see, these fairness questions relate to exploration in at least two different ways. 

First, there is an issue that was recently raised by Bird, Barocas, Crawford, Diaz, and Wallach: that exploring can be unfair to the individuals who have the misfortune of being present during the exploration rounds. Consider the example of sequential clinical trials: if a patient shows up on an "exploitation" round, then she is given the treatment that is believed to be the best for her, using a best effort estimate given the information available. But if she shows up during an "exploration" round, she will be given a random treatment --- generally, one that current evidence suggests is not the best for her. Is this fair to her? What if her life depends on the treatment? Exploration is explicitly sacrificing her well-being, for the possible good of future individuals, who might be able to benefit from what we learned from the exploration. It can be that when we are dealing with important decisions about peoples lives, we don't want to sacrifice the welfare of an individual for the good of others. Certainly, our notional patient would prefer not to show up on an exploration round. In various other settings, we can also imagine exploration being repugnant, even though it is in principle necessary for learning. Can we (for example) randomly release inmates on parole, even if we believe them to be high risks for committing more violent crimes? 

There is another, conflicting concern: if we do not explore, we might not correctly learn about the decisions we have to make. And there are a number of reasons we might expect to see insufficient exploration. Exploration is necessary to maximize long-term reward, but decision makers might be myopic. For example, the loan officers actually making lending decisions might be more interested in maximizing their annual bonuses than maximizing the long-term profits of the bank. Even the CEO might be more interested in quarterly share prices. But myopic decision makers won't explore (tangent: We had a paper at EC thinking about how one might incentivize myopic decision makers to nevertheless be meritocratically fair). The algorithms in use in many settings might also not have been designed properly --- if our learning algorithms don't explicitly take into account the bandit nature of the problem, and just treat it as a supervised classification problem, then they won't explore --- and this kind of mistake is probably extremely common. And finally, as we argued above, we might believe that it is simply not "fair" to explore, and so we intentionally avoid it. But a lack of exploration (and the resulting failure to properly learn) can itself be a source of unfairness. The "feedback loops" that result from a lack of exploration have been blamed by Lum and Isaac and by Ensign, Friedler, Neville, Scheidegger, and Venkatasubramanian as a primary source of unfairness in predictive policing. (See Suresh's recent blog post). Such algorithms can over-estimate crime in the poor neighborhoods in which police are deployed, and underestimate crime in the rich neighborhoods. If they don't explore to correct these mis-estimates, they will deploy more police to the poor neighborhoods, and fewer to the rich neighborhoods, which only exacerbates the data collection problem.  

Our New Paper

These two concerns both lead us to wonder how bad things need be if a decision maker doesn't explore, and instead simply runs a greedy algorithm, that exploits at every round. Maybe this is because we believe that greedy algorithms are already being run in many cases, and we want to know how much of a risk we are at for developing pernicious feedback loops. Or maybe we want to run a greedy algorithm by design, because we are in a medical or legal setting in which exploration is unacceptable. This is the question we consider in a new paper, joint with Sampath Kannan, Jamie Morgenstern, Bo Waggoner, and Steven Wu. (P.S. Bo is on the job market right now!)

Specifically, we consider the linear contextual bandit problem, described at the beginning of this post. A decision maker must choose amongst a set of actions every day, each of which is endowed with a vector of features. The reward distribution for each action is governed by an unknown linear function of the features. In this case, the greedy algorithm is simply the algorithm that maintains ordinary least squares regression estimates for each action, and always plays the action that maximizes its current point prediction of the reward, using its current regression estimate. 

Motivated in part by the problem with exploration in sequential drug trials, Bastani, Bayati, and Khosravi previously studied a two-action variant of this problem, and showed that when the features are drawn stochastically from a distribution satisfying certain strong assumptions, then the greedy algorithm works well: its reward approaches that of the optimal policy, without needing exploration! We take their result as inspiration, and prove a theorem of this flavor under substantially weaker conditions (although our model is slightly different, so the results are technically incomparable). 

We consider a model in which the number of actions can be arbitrary, and give a smoothed analysis. What that means is we don't require that the actions or their features are drawn from any particular distribution. Instead, we let them be chosen by an adversary, who knows exactly how our algorithm works, and can be arbitrarily sneaky in his attempt to cause our algorithm to fail to learn. Of course, if we stopped there, then the result would be that the greedy algorithm can be made to catastrophically fail to learn with constant probability: it has long been known that exploration is necessary in the worst case. But our adversary has a slightly shaky hand. After he chooses the actions for a given round, the features of those actions are perturbed by a small amount of Gaussian noise, independently in each coordinate. What we show is that this tiny amount of noise is sufficient to cause the greedy algorithm to succeed at learning: it recovers regret bounds (regret is the difference between the cumulative reward of the greedy algorithm, and what the optimal policy would have done) that are close to optimal, up to an inverse polynomial factor of the standard deviation of the Gaussian noise. (The regret bound must grow with the inverse of the standard deviation of the noise in any smoothed analysis, since we know that if there is no noise, the greedy algorithm doesn't work...) 

The story is actually more nuanced: we consider two different models, derive qualitatively different bounds in each model, and prove a separation: see the paper for details. But the punchline is that, at least in linear settings, what we can show is that "generically" (i.e. in the presence of small perturbations), fast learning is possible in bandit settings, even without exploration. This can be taken to mean that in settings in which exploration is repugnant, we don't have to do it --- and that perhaps pernicious feedback loops that can arise when we fail to explore shouldn't be expected to persist for a long time, if the features we observe are a little noisy. Of course, everything we prove is in a linear setting. We still don't know the extent to which these kinds of smoothed analyses carry over into non-linear settings. Understanding the necessity of exploration in more complex settings seems like an important problem with real policy implications.  

Adaptive Data Analysis Class Notes

Adam Smith and I both taught a PhD seminar this semester (at BU and Penn respectively) on adaptive data analysis. We collaborated on the course notes, which can be found here: https://adaptivedataanalysis.com/lecture-schedule-and-notes/

As part of their final project, students will be writing lecture notes for papers that we didn't have time to cover (listed here: https://adaptivedataanalysis.com/more-reading/ ). I'll post those as they are turned in. 

Between "statistical" and "individual" notions of fairness in Machine Learning

If you follow the fairness in machine learning literature, you might notice after awhile that there are two distinct families of fairness definitions:

1. Statistical definitions of fairness (sometimes also called group fairness), and
2. Individual notions of fairness. 

The statistical definitions are far-and-away the most popular, but the individual notions of fairness offer substantially stronger semantic guarantees. In this post, I want to dive into this distinction a little bit. Along the way I'll link to some of my favorite recent fairness papers, and end with a description of a recent paper from our group which tries to get some of the best properties of both worlds.

Statistical Definitions of Fairness

At a high level, statistical definitions of fairness partition the world into some set of "protected groups", and then ask that some statistical property be approximately equalized across these groups. Typically, the groups are defined via some high level sensitive attribute, like race or gender. Then, statistical definitions of fairness ask that some relevant statistic about a classifier be equalized across those groups. For example, we could ask that the rate of positive classification be equal across the groups (this is sometimes called statistical parity). Or, we could ask that the false positive and false negative rates be equal across the groups (This is what Hardt, Price, and Srebro call "Equalized Odds"). Or, we could ask that the positive predictive value (also sometimes called calibration) be equalized across the groups.  These are all interesting definitions, and there are very interesting impossibility results that emerge if you think you might want to try and satisfy all of them simultaneously.

These definitions are attractive: first of all, you can easily check whether a classifier satisfies them, since verifying that these fairness constraints hold on a particular distribution simply involves estimating some expectations, one for each protected group. It can be computationally hard to find a classifier that satisfies them, while minimizing the usual convex surrogate losses --- but computational hardness pervades all of learning theory, and hasn't stopped the practice of machine learning. Already there are a number of practical algorithms for learning classifiers subject to these statistical fairness constraints --- this recent paper by Agarwal et al. is one of my favorites. 

Semantics 

But what are the semantics of these constraints, and why do they correspond to "fairness"? You can make a different argument for each one, but here is the case for equalizing false positive and negative rates across groups (equalized odds), which is one of my favorites: 

You can argue (making the big assumption that the data is not itself already corrupted with bias --- see this paper by Friedler et al. for a deep dive into these assumptions...) that a classifier potentially does harm to an individual when it misclassifies them. If the (say) false positive rate is higher amongst black people than white people, then this means that if you perform the thought experiment of imagining yourself as a uniformly random black person with a negative label, the classifier is more likely to harm you than if you imagine yourself as a uniformly random white person with a negative label. On the other hand, if the classifier equalizes false positive and negative rates across populations, then behind the "veil of ignorance", choosing whether you want to be born as a uniformly random black or white person (conditioned on having a negative label), all else being equal, you should be indifferent!

Concerns

However, in this thought experiment, it is crucial that you are a uniformly random individual from the population. If you know some fact about yourself that makes you think you are not a uniformly random white person, the guarantee can lack bite. Here is a simple example:

Suppose we have a population of individuals, with two features and a label. Each individual has a race (either black or white) and a gender (either male or female). The features are uniformly random and independent. Each person also has a label (positive or negative) that is also uniformly random, and independent of the features. We can define four natural protected groups: "Black people', "White people", "Men", and "Women". 

Now suppose we have a classifier that labels an individual as positive if and only if they are either a black man or a white woman. Across these four protected groups, this classifier appears to be fair: the false positive rate and false negative rate are all exactly 50% on all four of the protected groups, so it satisfies equalized odds. But this hides a serious problem: on two subgroups (black men and white women), the false positive rate is 100%! If being labelled positive is a bad thing, you would not want to be a random (negative) member of those sub-populations.

Of course, we could remedy this problem by simply adding more explicitly protected subgroups. But this doesn't scale well: If we have d protected binary features, there are 2^(2^d) such subgroups that we can define. If the features are real valued, things are even worse, and we quickly get into issues of overfitting (see the next section).   

Individual Definitions of Fairness

At a high level, the problem with statistical definitions of fairness is that they are defined with respect to group averages, so if you are not an "average" member of your group, they don't promise you anything. Individual definitions of fairness attempt to remedy this problem by asking for a constraint that binds at the individual level. The first attempt at this was in the seminal paper "Fairness Through Awareness", which suggested that fairness should mean that "similar individuals should be treated similarly". Specifically, if the algorithm designer knows the correct metric by which individual similarity should be judged, the constraint requires that individuals who are close in that metric should have similar probabilities of any classification outcome. This is a semantically very strong definition. It hasn't gained much traction in the literature yet, because of the hard problem of specifying the similarity metric. But I expect that it will be an important definition going forward --- there are just some obstacles that have to be overcome. I've been thinking about it a lot myself. 

Another definition of individual fairness is one that my colleagues and I at Penn introduced in this paper, which we have taken to calling "Weakly Meritocratic Fairness". I have previously blogged about it here. We define it in a more general context, and in an online setting, but it makes sense to think about what it means in the special case of batch binary classification as well. In that case, it reduces to three constraints:

1. For any two individuals with a negative label, the false positive rate on those individuals must be equal
2. For any two individuals with a positive label, the false negative rate on those individuals must be equal
3. For any pair of individuals A and B such that A has a negative label, and B has a positive label, the true positive rate on B can't be lower than the false positive rate on A. (Assuming that positive is the more desirable label --- otherwise this is reversed). 

Again, we are talking about false positive rates --- but now there is no distribution --- i.e. nothing to take an average over. Instead, the constraints bind on every pair of individuals. As a result, the "rate" we are talking about is calculated only over the randomness of the classifier itself. 

This constraint in particular implies that false positive rates are equal across any sub-population that you might define, even ex-post! Problem solved! Why don't we all just use this definition of fairness? Here is why:

Concerns:

Weakly meritocratic fairness is extremely similar (identical, except for the added condition 3) to asking for equalized odds fairness on the (potentially infinitely large) set of "protected groups" corresponding to singletons --- everyone forms their own protected group! As a result, you shouldn't hope to be able to satisfy a fairness definition like this without making some assumption on the data generating process. Even if on your sample of data, it looks like you are satisfying this definition of fairness, you are overfitting --- the complexity of this class of groups is too large, and your in-sample "fairness" won't generalize out of sample. If you are willing to make assumptions on the data generating process, then you can do it! In our original paper, we show how to do it if you assume the labels obey a linear relationship to the features. But assumptions of this sort generally won't hold exactly in practice, which makes this kind of approach difficult to implement in practical settings. 

The "Fairness Through Awareness" definition at a high level suffers from the same kind of problem: you can only use it if you make a very strong assumption (namely that you have what everyone agrees is the "right" fairness metric). And this is the crux of the problem with definitions of individual fairness: they seem to require such strong assumptions, that we cannot actually realize them in practice. 

A Middle Ground

Asking for statistical fairness across a small number of coarsely defined groups leaves us open to unfairness on structured subgroups we didn't explicitly designate as protected (what you might call "Fairness Gerrymandering").  On the other hand, asking for statistical fairness across every possible division of the data that can be defined ex-post leaves us with an impossible statistical problem. (Consider, that every imperfect classifier could be accused of being "unfair" to the subgroup that we define, ex-post, to be the set of individuals that the classifier misclassifies! But this is just overfitting...)

What if we instead ask for statistical fairness across exponentially many (or infinitely many) subgroups, defined over a set of features we think should be protected, but ask that this family of subgroups itself has bounded VC-dimension? This mitigates the statistical problem --- we can now in principle train "fair" classifiers according to this definition without worrying about overfitting, assuming we we have enough data (proportional to the VC-dimension of the set of groups we want to protect, and the set of classifiers we want to learn). And we can do this without making any assumptions about the data. It also mitigates the "Fairness Gerrymandering" problem --- at least now, we can explicitly protect an enormous number of detailed subgroups, not just coarsely defined ones. 

This is what we (Michael Kearns, Seth Neel, Steven Wu, and I) propose in our new paper. In most of the paper, we investigate the computational challenges surrounding this kind of fairness constraint, when the statistical fairness notion we want is equality of false positive rates, false negative rates, or classification rates (statistical parity):

• First, it is no longer clear how to even check whether a fixed classifier satisfies a fairness constraint of this sort, without explicitly enumerating all of the protected groups (and recall, there might now be exponentially or even uncountably infinitely many such subgroups). We call this the Auditing problem. And indeed, in the worst case, this is a hard problem: we show that it is equivalent to weak agnostic learning, which brings with it a long list of computational hardness results from learning theory. It is hard to audit even for simple subgroup structures, definable by boolean conjunctions over features, or linear threshold functions. However, this connection also suggests an algorithmic approach to auditing. The fact that learning linear separators is NP hard in the worst case hasn't stopped us from doing this all the time, with simple heuristics like logistic regression and SVMs, as well as more sophisticated techniques. These same heuristics can be used to solve the auditing problem. 
• Going further, lets suppose those heuristics work --- i.e. we have oracles which can optimally solve agnostic learning problems over some collection of classifiers C, and can optimally solve the auditing problem over some class of subgroups G. Then we give an algorithm that only has to maintain small state, and provably converges to the optimal distribution over classifiers in C  that equalizes false positive rates (or false negative rates, or classification rates...) over the groups G. Our algorithm draws inspiration from the Agarwal et al. paper: "A Reductions Approach to Fair Classification". 
• And we can run these algorithms! We use a simple linear regression heuristic to implement both the agnostic learning and auditing "oracles", and run the algorithm to learn a distribution over linear threshold functions (defined over 122 attributes) that approximately equalizes false positive rates across every group definable by a linear threshold function over 18 real valued racially associated attributes, in the "Communities and Crime" dataset. It seems to work and do well! 

In Conclusion...

I've long been bothered by the seemingly irreconcilable gap between individual and group notions of fairness. The individual notions of fairness have the right semantics, but they are unimplementable. The group notions of fairness promise something too weak. Going forward, I think these two schools of thought on fairness have to be reconciled. I think of our work as a small step in that direction.

Michael recorded a short talk about this work, which you can watch on YouTube: https://www.youtube.com/watch?v=AjGQHJ0FKMg

Call for Nominations for the SIGecom Doctoral Dissertation Award

The SIGecom Doctoral Dissertation Award recognizes an outstanding dissertation in the field of economics and computer science. The award is conferred annually at the ACM Conference on Economics and Computation and includes a plaque, complimentary conference registration, and an honorarium of $1,500. A plaque may further be given to up to two runners-up. No award may be conferred if the nominations are judged not to meet the standards for the award.

To be eligible, a dissertation must be on a topic related to the field of economics and computer science and must have been defended successfully during the calendar year preceding the year of the award presentation.

The next SIGecom Doctoral Dissertation Award will be given for dissertations defended in 2017. Nominations are due by the March 31, 2018, and must be submitted by email with the subject "SIGecom Doctoral Dissertation Award" to the awards committee at sigecom-awards-diss@acm.org. A dissertation may be nominated simultaneously for both the SIGecom Doctoral Dissertation Award and the ACM Doctoral Dissertation Award.

Nominations may be made by any member of SIGecom, and will typically come from the dissertation supervisor. Self-nomination is not allowed. Nominations for the award must include the following, preferably in a single PDF file:

1. A two-page summary of the dissertation, written by the nominee, including bibliographic data and links to publicly accessible versions of published papers based primarily on the dissertation.
2. An English-language version of the dissertation.
3. An endorsement letter of no more than two pages by the nominator, arguing the merit of the dissertation, potential impact, and justification of the nomination. This document should also certify the dissertation defense date.
4. The names, email addresses, and affiliations of at least two additional endorsers.

The additional endorsement letters themselves should be emailed directly to sigecom-awards-diss@acm.org, by the same deadline. These endorsements should be no longer than 500 words, and should specify the relationship of the endorser to the nominee, contributions of the dissertation, and its potential impact on the field.

It is expected that a nominated candidate, if selected for the award, will attend the next ACM Conference on Economics and Computation to accept the award and give a presentation on the dissertation work. The cost of attending the conference is not covered by the award, but complimentary registration is provided.

Submit your papers to WWW 2018

Jennifer Wortman Vaughan and I are the track chairs for the the "Web Economics, Monetization, and Online Markets" track of WWW 2018. The track name is a little unwieldy -- we tried to change it to "Economics and Markets" -- but the focus should be of interest to many in the AGT, theory, and machine learning communities. See the call for papers here: https://www2018.thewebconf.org/call-for-papers/research-tracks-cfp/web-economics/ We have a great PC, and the topics of interests include (amongst many other things), "Economics of Privacy" and "Fairness in Economic Environments".

January Fairness Workshop at Penn

At the beginning of the semester, I mentioned that after the law school's semester of events (click for videos) on fairness, machine learning, and the law, we would host a technical workshop on recent work on fairness in machine learning.

We have now finished putting together the program, which will be terrific. The workshop will take place here at Penn from January 19-20th. Take a look at our great line-up of speakers here: https://sites.google.com/view/fairnessconfererencepenn

The event is open to the public, but registration is required.

Designing the Digital Economy

I'm on a train to New Haven, where I'll be giving a guest lecture (together with Solon Barocas) in Glen Weyl's class, "Designing the Digital Economy" (n.b. I need to get advice from Glen about how to get as good publicity for my classes...)

Solon and I will be sharing the 3 hour class, talking about fairness in machine learning, starting at 2:30. Pop by if you are around -- otherwise, here are my slides.

Semester on Fairness and Algorithms at Penn

This year, the "Fels Policy Research Initiative" is funding two exciting events, both related to fairness and machine learning. The first, joint between the law school and statistics, is called "Optimizing Government", and will host a series of 4 seminars over the course of this semester touching on technical and legal aspects of fairness.

I will be speaking at the first one, introducing the basics of Machine Learning and scenarios in which its use can lead to inadvertent discrimination. My inimitable colleague Richard Berk (who actually builds models used to predict criminal recidivism used by the state of Pennsylvania) will be offering his comments following my talk.

The second seminar will provide a panel discussion on what the law demands in terms of "fair and equal treatment", and how it relates to the use of machine learning. The panelists will come from Philosophy, Political Science, and Law.

The third seminar will be given by our excellent Warren Center postdoc Jamie Morgenstern, and will focus on technical solutions to the problem of unfairness in machine learning, and how it can be squared with learning the optimal policy in online decision making settings.

Finally, the fourth seminar will be an exciting keynote delivered by the current Deputy U.S. CTO Ed Felten on uses of machine learning in government.

I believe the talks will be recorded.


We will begin next semester with the second Fels sponsored workshop, organized between computer science and economics -- a 2 day intensive workshop exploring current research on technical and economic solutions to addressing unfairness in decision making. More details to come.

Below is the schedule for this semester:

The “Optimizing Government” interdisciplinary research collaboration, supported by the Fels Policy Research Initiative, will hold the following workshops this fall:

Thursday, 9/22/16: What is Machine Learning (and Why Might it be Unfair)?Fundamentals of machine learning with a focus on what makes it different from traditional statistical analysis and why it might lead to unfair outcomes.Speakers: Aaron Roth (Penn Computer Science), with comments from Richard Berk (Wharton Statistics; Chair of SAS Criminology)

Thursday, 10/6/16: What Does Fair and Equal Treatment Demand?

Current legal and moral norms about fairness and equal protection as they relate to the use of machine learning in government.

Speakers: Panel featuring Samuel Freeman (Penn Philosophy), Nancy Hirschmann (Penn Political Science), and Seth Kreimer (Penn Law)

Thursday, 11/3/16: Fairness and Performance Trade-Offs in Machine Learning

Technical solutions to fairness challenges raised by machine learning and their impacts on algorithm effectiveness.

Speaker: Jamie Morgenstern (Penn Computer Science)

Thursday, 11/17/16: Keynote on Machine Learning and Government

How to use machine learning for a variety of administrative and policy functions, and findings from a White House initiative on artificial intelligence in government.

Speaker: Ed Felten, Deputy U.S. CTO (Invited)

Each workshop will take place from 4:30-6:00 pm in Gittis 213 (Penn Law). You can enter the Law School through its main entrance at 3501 Sansom Street.

EDIT: The Optimizing Government Project now has a website: https://www.law.upenn.edu/institutes/ppr/optimizing-government-project/ and the talks will be livestreamed here: https://www.law.upenn.edu/institutes/ppr/optimizing-government-project/media.php

Call for Papers: Second Workshop on Adaptive Data Analysis

As part of NIPS 2016, we will be running the second annual workshop on adaptive data analysis. Last year's workshop was a big hit. As a new addition this year, we are soliciting submitted contributions in addition to invited speakers. The call for papers is below. If you are working on relevant work, definitely submit it to our workshop! More information at: http://wadapt.org/

Call for Papers


The overall goal of WADAPT is to stimulate the discussion on theoretical analysis and practical aspects of adaptive data analysis. We seek contributions from different research areas of machine learning, statistics and computer science. Submissions focused on a particular area of application are also welcome.

Submissions will undergo a lightweight review process and will be judged on originality, relevance, clarity, and the extent to which their presentation can stimulate the discussion between different communities at the workshop. Submissions may describe either novel work (completed or in progress), or work already published or submitted elsewhere provided that it first appeared after September 1, 2015.

Authors are invited to submit either a short abstract (2-4 pages) or a complete paper by Oct 15, 2016. Information about previous publication, if applicable, should appear prominently on the first page of the submission. Abstracts must be written in English and be submitted as a single PDF file at EasyChair.

All accepted abstracts will be presented at the workshop as posters and some will be selected for an oral presentation. The workshop will not have formal proceedings, and presentation at the workshop is not intended to preclude later publication at another venue.

Those who need to receive a notification before the NIPS early registration deadline (Oct 6, 2016) should submit their work by the early submission deadline of Sept 23, 2016.

Important Dates:


Submission deadlines. Early: Sep 23, 2016; Regular: Oct 25, 2016. Submit at EasyChair.
Notification of acceptance. Early: Oct 3, 2016, Regular: Nov 7, 2016.
Workshop: December 9, 2016



Specific topics of interest for the workshop include (but are not limited to):


Selective/post-selection inference
Sequential/online false discovery rate control
Algorithms for answering adaptively chosen data queries
Computational and statistical barriers to adaptive data analysis
Stability measures and their applications to generalization
Information-theoretic approaches to generalization

Machine Learning Postdoc

My brand new colleague Shivani Agarwal is in the market for a postdoc; the announcement is below. One of the targeted areas is machine learning and economics. Whoever takes this position will join a growing group of exceptional postdocs in this area at Penn, including Jamie Morgenstern and Bo Waggoner.

Postdoctoral Position in Machine Learning at UPenn

Applications are invited for a postdoctoral position in machine learning  in the Department of Computer and Information Science at the University  of Pennsylvania. The position is expected to begin in Fall 2016, and is  for a period of up to two years (with renewal in the second year  contingent on performance in the first year). Applications in all areas  of machine learning will be considered, with special emphasis on the  following areas: ranking and choice modeling; connections between machine learning and economics; and learning of complex structures.

The ideal candidate will demonstrate both ability for independent  thinking and interest in co-mentoring of graduate students. The candidate will work primarily with Shivani Agarwal (joining UPenn faculty in July 2016), but will also have opportunities to collaborate with other faculty in machine learning and related areas at UPenn, including Michael Kearns, Daniel Lee, Sasha Rakhlin, Aaron Roth, Lyle Ungar, and other faculty.

UPenn is located in the vibrant city of Philadelphia, which is known for its rich culture, history, museums, parks, and restaurants. It is less than 1.5 hrs by train to NYC, 1.5 hrs by flight to Boston, 2 hrs by train to Washington DC, and 40 mins by train to Princeton. For more details about the CIS department at UPenn, see:

http://www.cis.upenn.edu/

To apply, send the following materials in an email titled “Application for Postdoctoral Position” to  by June 17, 2016:

- curriculum vitae
- 2-page statement of research interests and goals
- 3 representative publications or working papers
- 3 letters of recommendation (to be sent separately by the same date)

Shortlisted candidates will be invited for a short meeting/interview at ICML/COLT in NYC during June 23-26 (in your email, please indicate your availability for this).

Fairness in Learning

The very real problem of (un)fairness in algorithmic decision making in general, and machine learning in particular seems to have finally reached the forefront of public attention. Every day there is a new popular article about the topic. Just in the last few weeks, we have seen articles in the Times about built in bias in facebook, and an in-depth ProPublica study about racial bias in statistical models for predicting criminal recidivism. Earlier this month, the White House released a report on the challenges in promoting fairness in Big Data.

The tricky thing is saying something concrete and technical about this problem -- even defining what "fairness" is is delicate. There has been some good technical work in this area that I have long admired from afar -- see e.g. the "FATML" (Fairness and Transparency in Machine Learning) Workshop to get an idea of the range of work being done, and the folks doing it. People like Cynthia Dwork, Moritz Hardt, Solon Barocas, Suresh Venkatasubramanian, Sorelle Friedler, Cathy O'Neil, and others have been doing important work thinking about these problems for quite some time. A particularly nice early paper that I recommend everyone interested in the area read is Fairness Through Awareness, by Dwork, Hardt, Pitassi, Reingold, and Zemel. It was first posted online in 2011(!), and in retrospect is quite prescient in its discussion of algorithmic fairness.

So I'm happy to finally have something interesting to say about the topic! My student Matthew Joseph, Michael Kearns, Jamie Morgenstern, and I just posted a new paper online that I'm excited about: Fairness in Learning: Classic and Contextual Bandits. I'll mostly let the paper speak for itself, but briefly, we write down a simple but (I think) compelling definition of fairness in a stylized general model of sequential decision making called the "contextual bandit setting". To keep a canonical problem in your mind, imagine the following: There are a bunch of different populations (say racial or socioeconomic groups), and you are a loan officer. Every day, an individual from each population applies for a loan. You get to see the loan application for each person (this is the "context"), and have to decide who to give the loan to. When you give out the loan, you observe some reward (e.g. you see if they paid back the loan), but you don't see what reward you -would- have gotten had you given the loan to someone else. Our fairness condition says roughly that an algorithm is "fair" if it never preferentially gives a loan to a less qualified applicant over a more qualified applicant -- where the quality of an applicant in our setting is precisely the probability that they pay back the loan. (It prohibits discriminating against qualified applicants on an individual basis -- even if  they happen to come from a population that is less credit-worthy on average, or from a population that the bank doesn't understand as well).

It might seem like this definition of fairness is entirely consistent with the profit motivation of a bank -- why would a bank ever want to give a loan to an applicant less likely to pay it back? Indeed, this would be true if the bank had nothing to learn -- i.e. if it already knew the optimal rule mapping loan applications to credit-worthiness. Said another way, implementing the optimal policy is entirely consistent with our fairness definition. Our main conceptual message is that fairness can nevertheless be an obstruction to learning the optimal policy.

What our results say is that "fairness" always has a cost in terms of the optimal learning rate achievable by algorithms in this setting. For some kinds of problems, the cost is mild in that the cost of fairness on the learning rate is only polynomial (e.g. when credit-worthiness is determined by a simple linear regression model on the features of a loan application). On the other hand, for other kinds of problems, the cost of fairness on the learning rate is severe, in that it can slow learning by an exponential factor (e.g. when credit-worthiness is determined by an AND of features in the loan application). Put another way, for the problems in which the cost of fairness is severe, if the bank were to use a fast learning algorithm (absent a fairness constraint), the algorithm might be "unfair" for a very long time, even if in the limit, once it learned the truly optimal policy, it would eventually be fair. One friction to fairness is that we don't live in the limit -- we are always in a state of learning.

Penn is Hiring in Computer Science

Penn Engineering is embarking on a period of substantial growth, and the computer science department plans to hire lots of people over the next several years. (You can see a draft of the Penn Engineering plan for growth here. "Data Science and Computation" and Security are both priority areas).

This year, we are planning to hire for multiple positions, both junior and senior, with a focus on (among other things), machine learning. 

So if you are on the market (or thinking about it), send us your application -- apply here: https://facultysearches.provost.upenn.edu/postings/663 

(Unless you want to apply for an endowed chair in computer graphics -- then apply here: https://facultysearches.provost.upenn.edu/postings/664 )

Edit: I forgot to mention! Interest in machine learning is university wide -- both statistics and ESE also plan to hire in machine learning.
Here is the link for applying to the statistics position: https://statistics.wharton.upenn.edu/recruiting/facultypositions/
And here is the link for ESE: http://www.ese.upenn.edu/faculty-staff/index.php

An action packed Monday at FCRC

FCRC begins next week, and due to the wonders of co-location will be action packed. (Monday will have among other things EC workshops, as well as the first full day of STOC talks). I've found myself on the organizing committee of two of the three EC workshops, and Monday is also when our STOC paper is scheduled.

So here are three (partially) conflicting events you might be interested in:

NetEcon 2015: Highlights include excellent keynote speakers: Rakesh Vohra at  9:00 am, Eva Tardos at 2:00 pm, and R. Srikant at 4:00 pm

The Workshop on Algorithmic Game Theory and Data Science: This workshop is highlighting work in a very exciting area -- the intersection between "data science" and mechanism design -- which is at its very beginning, and I think ripe for lots of important work to be done. Its also attracted a great lineup of speakers (my student Steven will be giving the talk on our paper).

The STOC presentation of our paper, Preserving Statistical Validity in Adaptive Data Analysis: This is at 1:55pm, unfortunately conflicting with NetEcon -- but the attendees of the AGT + Data Science workshop will get a break in order to attend. Vitaly will be giving the talk, which I expect will be very good.

If you want to hear a longer (but probably less good) version of the talk, you can tune in tomorrow at 1pm eastern when I talk about this paper for TCS+

EDIT: The video of the talk is here. It went off with only one technical hitch.

Algorithmic Game Theory and Data Science

With FOCS submissions sent off and EC rejections in hand, its time to think about presenting your work at a workshop, and chat with your colleagues doing similar things. 

If you are working on something at the intersection of algorithmic game theory and machine learning (this includes e.g. the sample complexity of auction design, or learning from revealed preferences, or learning from censored feedback), then you should consider the "Algorithmic Game Theory and Data Science" workshop that we'll be running during EC 2015. Conveniently, this is at FCRC, so if you were planning on attending EC or STOC (or SIGmetrics, or CCC, or...) you'll already be there in Portland. 

Deadline is in 10 days!

https://sites.google.com/site/agtanddatascienceworkshop2015/

---------------------------

Call for Papers

In conjunction with the Sixteenth ACM Conference on Economics and Computation (EC'15), we solicit submissions for the First Workshop on Algorithmic Game Theory and Data Science, to be held on June 15, 2015 in Portland, Oregon, USA. Computer systems have become the primary mediator of social and economic interactions, enabling transactions at ever-increasing scale.  Mechanism design when done on a large scale needs to be a data-driven enterprise.  It seeks to optimize some objective with respect to a huge underlying population that the mechanism designer does not have direct access to.  Instead, the mechanism designer typically will have access to sampled behavior from that population (e.g. bid histories, or purchase decisions).  This means that, on the one hand, mechanism designers will need to bring to bear data-driven methodology from statistical learning theory, econometrics, and revealed preference theory.  On the other hand, strategic settings pose new challenges in data science, and approaches for learning and inference need to be adapted to account for strategization.   The goal of this workshop is to frame the agenda for research at the interface of algorithms, game theory, and data science.  Papers from a rich set of experimental, empirical, and theoretical perspectives are invited.  Topics of interest include but are not limited to: Can good mechanisms be learned by observing agent behavior in response to other mechanisms?  How hard is it to "learn'' a revenue maximizing auction given a sampled bid history?  How hard is it to learn a predictive model of customer purchase decisions, or better yet, a set of prices that will accurately maximize profit under these behavioral decisions?  What is the sample complexity of mechanism design?  How much data is necessary to enable good mechanism design? How does mechanism design affect inference?  Are outcomes of some mechanisms more informative than those of others from the viewpoint of inference? How does inference affect mechanism design?  If participants know that their data is to be used for inference, how does this knowledge affect their behavior in a mechanism? Can tools from computer science and game theory be used to contribute rigorous guarantees to interactive data analysis?  Strategic interactions between a mechanism and a user base are often interactive (e.g. in the case of an ascending price auction, or repeated interaction with a customer and an online retailer), which is a setting in which traditional methods for preventing data over-fitting are weak. Is data an economic model? Can data be used to evaluate or replace existing economic models?  What is the consequence for game theory and economics for replacing the model with data. Submission Instructions Any submission format between abstracts and full papers will be considered.  Abstracts may be rejected if we cannot sufficiently evaluate their contribution.  Full papers will be evaluated after page 10 only at the discretion of the committee. We solicit both new work and work recently published or soon to be published in another venue.  For submissions of the latter kind, authors must clearly state the venue of publication.  This workshop will have no published proceedings.  Papers appearing in published conference proceedings or journals subsequent to EC 2014 will be considered, though preference may be given to papers that have not yet appeared.  Papers that have appeared or are to appear at EC or affiliated workshops will not be considered. Authors are encouraged to provide a link to an online version of the paper (such as on arXiv).  If accepted, such papers will be linked via an index to give an informal record of the workshop. All submissions should be sent electronically to AGTDataScienceWorkshop15@gmail.com on or before April 26th, 2015.  Notification of acceptance will be on May 11, 2015. Organizing Committee Shuchi Chawla, U. of Wisconsin  Hu Fu, Microsoft Research Jason Hartline, Northwestern U. Denis Nekipelov, U. of Virginia Aaron Roth, U. of Pennsylvania Kane Sweeney, eBay and Stubhub

Netecon deadline in two weeks

A reminder that the NetEcon workshop deadline is coming up in two weeks. If you plan to be at FCRC (for e.g. STOC, or EC, or Sigmetrics), this will be a great place to present your work and get it seen by both the EC and the SIGmetrics community. There's also a great lineup of invited talks (abstracts here: http://netecon.eurecom.fr/NetEcon2015/keynotes.html ) by R. Srikant, Rakesh Vohra, and Eva Tardos.

Here is the call: http://netecon.eurecom.fr/NetEcon2015/index.html

The submission deadline is April 22.

STOC 2015 Call for Workshops and Tutorials

Sanjeev Khanna and Chandra Chekuri are co-chairing the STOC 2015 workshops and tutorials, and are looking for submissions. The call is below:

Call for STOC 2015 Workshop and Tutorial Proposals

• Workshop and Tutorial Day: Sunday, June 14, 2015
• Workshop and Tutorial Co-Chairs: Chandra Chekuri and Sanjeev Khanna
• Submission deadline: March 20, 2015
• Notification: March 30, 2015

On Sunday, June 14, immediately preceding the main conference, STOC 2015 will hold a workshop-and-tutorials day. We invite groups of interested researchers to submit workshop or tutorial proposals. The goal of a workshop is to provide an informal forum for researchers to discuss important research questions, directions, and challenges. Connections between theoretical computer science and other areas, topics that are not well represented at STOC, and open problems are encouraged as workshop topics. Organizers are completely free to choose their workshop formats (invited speakers, panel discussions, etc.). The program for June 14th may also involve tutorials, each consisting of 1-2 survey talks on a particular area, and we welcome tutorial proposals as well.
STOC does not have funds to pay travel expenses or honoraria to invited workshop and tutorial speakers. Workshop and tutorials attendance will be free, and there is no separate registration for attending them. STOC will support coffee breaks for the workshops/tutorials attendees but no lunch will be provided. Note that STOC registration neither includes FCRC registration for Sunday, June 14 nor covers lunch for Sunday, June 14. Workshop/tutorial attendees who wish to attend another FCRC conference on June 14, would need to register for that conference.

Proposal submission

Workshop and tutorial proposals should be no longer than 2 pages. Please include a list of names and email addresses of the organizers, a description of the topic and the goals of the workshop or tutorial, the proposed workshop format (invited talks, contributed talks, panel, etc.), and proposed or tentatively confirmed speakers if known. Please also indicate the preferred length of time for your workshop or tutorial, along with the minimum acceptable time. We anticipate a 4-5 hour block for each workshop and a 2-4 hour block for each tutorial. Please feel free to contact the Workshop and Tutorial Co-Chairs at the email addresses below if you have questions about workshop or tutorial proposals.

Submission deadline

Proposals should be submitted by March 20, 2015, via email to chekuri@illinois.edu and sanjeev@cis.upenn.edu. Proposers will be notified by March 30, 2015, about whether their proposals have been accepted.

http://acm-stoc.org/stoc2015/callforworkshops.html

Bringing Differential Privacy to the Masses <3

This Valentines Day, we'll be bringing differential privacy to the (scientific) masses, with a session at the AAAS annual meeting in San Jose.

If you happen to be attending, you should stop by: https://aaas.confex.com/aaas/2015/webprogram/Session9556.html

NetEcon 2015

Patrick Loiseau, Adam Wierman, and I are co-chairing the 2015 NetEcon workshop, to be held in conjunction with EC and Sigmetrics at this year's FCRC in Portland. You should stop by if you are attending any of the FCRC conferences, (and submit a paper). If you haven't been to a previous iteration, this workshop brings together people interested in game theory from both the networking and theory/AI communities, so is a great place to present work that might be of interest to both communities, or to pick up problems that are interesting from a different community than yours.

We've got a great set of invited speakers: R. Srikant, Ricky Vohra, and Eva Tardos.

So start thinking about what you want to submit -- you've only got about 3 months.

*******************************************************************
Call For Papers:

         NetEcon 2015: The 10th Workshop on the Economics of Networks, 
Systems and Computation
         At FCRC 2015, in conjunction with ACM EC and ACM SIGMETRICS
         Monday, June 15, 2015 (Portland, Oregon, USA)

http://netecon.eurecom.fr/NetEcon2015/


*******************************************************************
INVITED SPEAKERS

     * *R. Srikant*, University of Illinois at Urbana-Champaign
     * *Rakesh V. Vohra*, University of Pennsylvania
     * *Eva Tardos*, Cornell University


*******************************************************************
CALL FOR PAPERS

Today's communication networks and networked systems are highly complex 
and heterogeneous, and are often owned by multiple profit-making 
entities. For new technologies or infrastructure designs to be adopted, 
they must not be only based on sound engineering performance 
considerations but also present the right economic incentives. Recent 
changes in regulations of the telecommunication industry make such 
economic considerations even more urgent. For instance, concerns such as 
network neutrality have a significant impact on the evolution of 
communication networks.

At the same time, communication networks and networked systems support 
increasing economic activity based on applications and services such as 
cloud computing, social networks, and peer-to-peer networks. These 
applications pose new challenges such as the development of good pricing 
and incentive mechanisms to promote effective system-wide behavior. In 
relation to these applications, security and privacy also require 
consideration of economic aspects to be fully understood.

The aim of NetEcon is to foster discussions on the application of 
economic and game-theoretic models and principles to address challenges 
in the development of networks and network-based applications and 
services. NetEcon was established in 2006 (succeeding to the P2PECON, 
IBC and PINS workshops) and merged with the W-PIN workshop in 2013. We 
invite submission of extended abstracts describing original research on 
theoretical/methodological contributions or on applications to cases of 
interest. It is our hope that NetEcon will serve as a feeder workshop, 
i.e., that expanded, polished versions of extended abstracts will appear 
later in major conference proceedings and refereed journals of relevant 
research communities.

Topics of interest include (but are not limited to):

     * Pricing of resources in communication networks, grids, and cloud 
computing
     * Pricing of information goods and services; copyright issues, 
effect of network externalities (e.g., in social network)
     * Economic issues in universal broadband access; economics of 
interconnection and peering
     * Effects of market structure and regulations (e.g., network 
neutrality)
     * Economics of network security and privacy; valuation of personal data
     * Auctions with applications to networks: spectrum auctions, 
auction-based marketplaces for network and cloud resources
     * Incentive mechanisms for networks: peer-to-peer systems, clouds, 
wireless networks, spam prevention, security
     * Methods for engineering incentives and disincentives (e.g., 
reputation, trust, control, accountability, anonymity)
     * Empirical studies of strategic behavior (or the lack thereof) in 
existing, deployed systems
     * Design of incentive-aware network architectures and protocols
     * Game-theoretic models and techniques for network economics: large 
games, learning, mechanism design, interaction of game theory and 
information theory or queuing theory, information exchange, diffusion, 
dynamics of cooperation and network formation, trades in social and 
economic networks
     * Algorithmic mechanism design for network systems
     * Critiques of existing models and solution concepts, as well as 
proposals of better models and solution concepts
     * Studies of open collaboration, peer production, crowdsourcing, 
and human computation.


*******************************************************************
SUBMISSION FORMATTING GUIDELINES AND PROCEEDINGS

Submissions must be in the form of extended abstracts of 3-4 pages, 
including all figures, tables, references, appendices, etc. They must be 
formatted according to the standard alternate ACM PER double column 
format using letter paper. You are encouraged to use the ACM 
sig-alternate-per latex template 
(http://www.sigmetrics.org/sig-alternate-per.cls).

Accepted extended abstracts will be published in a special issue of ACM 
Performance Evaluation Review (PER) and will be available online through 
ACM portal digital library. Authors of accepted abstracts grant ACM 
permission to publish them in print and digital formats.

Note that authors retain the copyright of their work published in ACM 
PER, with freedom to submit it elsewhere. Yet, authors for whom 
publication of a 3-4 pages extended abstract in the NetEcon 2015 
proceedings would preclude later publication of an expanded version in 
the relevant venue may elect to contribute only a one-page abstract of 
their submitted extended abstract to the NetEcon 2015 proceedings. Such 
an abstract should include the URL of a working paper or preprint that 
contains the main results presented at the NetEcon workshop. Authors 
will make this decision after receiving a notice of acceptance.

If the number of excellent submissions is larger than we have space to 
allot presentations for, some authors will be offered the opportunity to 
present their work during a poster session.


*******************************************************************
COMMITTES

PC CHAIRS
     Patrick Loiseau (EURECOM, France)
     Aaron Roth (UPenn, USA)
     Adam Wierman (Caltech, USA)

WEBMASTER
     Michela Chessa (EURECOM, France)

TECHNICAL PROGRAM COMMITTEE
     Matthew Andrews (Alcatel-Lucent Bell Labs, USA)
     Itai Ashlagi (MIT, USA)
     Moshe Babaioff (Microsoft Research, Israel)
     Tamer BaÅŸar (University of Illinois, Urbana-Champaign, USA)
     Bobby Bhattarcharjee (University of Maryland, USA)
     Rainer Böhme (WWU Münster, Germany)
     Kostas Bimpikis (Stanford University, USA)
     Eilyan Bitar (Cornell University, USA)
     Augustin Chaintreau (Columbia University, USA)
     Michela Chessa (EURECOM, France)
     kc claffy (CAIDA / UC San Diego, USA)
     Costas Courcoubetis (SUTD, Singapore and AUEB, Greece)
     Amogh Dhamdhere (CAIDA / UC San Diego, USA)
     Constantine Dovrolis (GeorgiaTech, USA)
     Rachid Elazouzi (University of Avignon, France)
     Sergey Gorinsky (Institute IMDEA Networks, Spain)
     Jens Grossklags (The Pennsylvania State University, USA)
     Roch Guerin (Washington University in St. Louis, USA)
     Nidhi Hegde (Alcatel-Lucent Bell Labs, France)
     Ekram Hossain (University of Manitoba, Canada)
     Stratis Ioannidis (Yahoo! labs, USA)
     Krisnamurthy Iyer (Cornell University, USA)
     Rahul Jain (USC, USA)
     Ian Kash (Microsoft Research, UK)
     David Kempe (USC, USA)
     Peter Key (Microsoft Research, UK)
     Nikolaos Laoutaris (Telefonica Research, Spain)
     Dave Levin (University of Maryland, USA)
     Patrick Loiseau (EURECOM, France) -- co-chair
     Brendan Lucier (Microsoft Research, USA)
     John C. S. Lui (The Chinese University of Hong Kong, Hong Kong)
     Patrick Maillé (Institut Mines-Telecom / Telecom Bretagne, France)
     Jason Marden (University of Colorado, Boulder, USA)
     Ravi Mazumdar (University of Waterloo, Canada)
     Jeonghoon Mo (Yonsei University, South Korea)
     John Musacchio (UC Santa Cruz, USA)
     Andrew Odlyzko (University of Minnesota, Minneapolis, USA)
     Aaron Roth (UPenn, USA) -- co-chair
     Galina Schwartz (UC Berkeley, USA)
     Paul G. Spirakis (University of Liverpool, UK and CTI, Greece)
     Nicolás Stier Moses (Facebook Data Science, USA)
     Vijay Subramanian (University of Michigan, Ann Arbor, USA)
     John N. Tsitsiklis (MIT, USA)
     Bruno Tuffin (Inria, France)
     Adrian Vetta (McGill University, Canada)
     Steven Weber (Drexel University, USA)
     Adam Wierman (Caltech, USA) -- co-chair


*******************************************************************
IMPORTANT DATES

     * Wednesday April 22, 2015, 11:59pm PST: Submission deadline (firm)
     * Wednesday May 13, 2015: Notification to authors
     * Monday June 8, 2015: Final version for the workshop's website due
     * Monday June 15, 2015: Workshop in Portland
     * Monday July 13, 2015: Final version for the ACM PER proceedings due


*******************************************************************
ADDITIONAL INFORMATION

For more information, please contact the organizers or visit the 
workshop website: http://netecon.eurecom.fr/NetEcon2015/.

Differential Privacy Workshop in London

There will be a differential privacy workshop in London in April, accepting submissions soon. If you have something you are working on, consider submitting here. Some highlights:

-- Although the workshop will not have proceedings (so you can as usual submit a talk and still submit it to a conference of your choosing), exceptional submissions will be invited to a special issue of the Journal of Privacy and Confidentiality.

-- The PC is pretty inter-disciplinary. This is certainly not just a Theory-A workshop. Work on privacy in all areas is on topic.

-- You get to hear Jon Ullman give a (presumably excellent) talk. 

CALL FOR PAPERS
TPDP 2015
First workshop on the Theory and Practice of Differential Privacy
18th April 2015, London, UK
Affiliated to ETAPS
http://tpdp.computing.dundee.ac.uk

Differential privacy is a promising approach to the privacy-preserving
release of data: it offers a strong guaranteed bound on the increase
in harm that a user incurs as a result of participating in a
differentially private data analysis.

Researchers in differential privacy come from several area of computer
science as algorithms, programming languages, security, databases,
machine learning, as well as from several areas of statistics and data
analysis. The workshop is intended to be an occasion for researchers
from these different research areas to discuss the recent developments
in the theory and practice of differential privacy.

**Submissions**

The overall goal of TPDP is to stimulate the discussion on the
relevance of differentially private data analyses in practice. For
this reason, we seek contributions from different research areas of
computer science and statistics.

Authors are invited to submit a short abstract (4-5 pages maximum) of
their work by January 23, 2015. Abstracts must be written in English
and be submitted as a single PDF file at the EasyChair page for TPDP:
https://easychair.org/conferences/?conf=3Dtpdp2015

Submissions will be judged on originality, relevance, interest and
clarity. Submission should describe novel works or works that have
already appeared elsewhere but that can stimulate the discussion
between the different communities. Accepted abstracts will
be presented at the workshop.

The workshop will not have formal proceedings, but we plan to have a
special issue of the Journal of Privacy and Confidentiality devoted to
TPDP. Authors presenting valuable contributions at the workshop will
be invited to submit a journal version of their work right after the
workshop.


**Important Dates**

-January 23, 2015 - Abstract Submission
-February 10, 2015 - Notification
-February 14, 2015 - Deadline early registration ETAPS
-April 18, 2015 - Workshop

-May 15, 2015 Deadline for journal special issue


**Topics**

Specific topics of interest for the workshop include (but are not limited t=
o):
theory of differential privacy,
verification techniques for differential privacy,
programming languages for differential privacy,
models for differential privacy,
trade-offs between privacy protection and analytic utility,
differential privacy and surveys,
relaxations of the differential privacy definition,
differential privacy vs other privacy notions and methods,
differential privacy and accuracy,
practical differential privacy,
implementations for differential privacy,
differential privacy and security,
applications of differential privacy.


**Invited Speakers**

Jonathan Ullman - Simons Fellow at Columbia University,

Another invited speaker joint with HotSpot'15 to be confirmed.


**Program Committee**

Gilles Barthe - IMDEA Software
Konstantinos Chatzikokolakis - CNRS and LIX, Ecole Polytechnique
Kamalika Chaudhuri - UC San Diego
Graham Cormode - University of Warwick
George Danezis - University College London
Marco Gaboardi - University of Dundee
Matteo Maffei - CISPA, Saarland University
Catuscia Palamidessi - INRIA and LIX, Ecole Polytechnique
Benjamin C. Pierce - University of Pennsylvania
Aaron Roth - University of Pennsylvania
David Sands - Chalmers University of Technology
Chris Skinner - London School of Economics
Adam Smith - Pennsylvania State University
Carmela Troncoso - Gradiant
Salil Vadhan - Harvard University

Differential Privacy Book is Here

After a much longer time than either of us thought it would take, my book with Cynthia Dwork, "The Algorithmic Foundations of Differential Privacy" is finally available.

You have 3 options for obtaining a copy! (I must admit to not quite understanding the pricing model of our publisher).

1. Hard Copy: You can buy a hard copy directly from NOW for $99 (http://www.nowpublishers.com/articles/foundations-and-trends-in-theoretical-computer-science/TCS-042/book-details) or from Amazon for $101 and free shipping (http://www.amazon.com/Algorithmic-Foundations-Differential-Privacy/dp/1601988184/ )
2. "ebook" format (which I believe is just a downloadable pdf): If you don't have room on your book shelf, and are happy with a PDF, the book can be yours from NOW for only $240. This is a bargain -- coming in at 281 pages, this is less than 86 cents per digital "page".   (http://www.nowpublishers.com/articles/foundations-and-trends-in-theoretical-computer-science/TCS-042/book-details)
3. Free download: The PDF is also available for free on my web page: http://www.cis.upenn.edu/~aaroth/privacybook.html