In the third lecture of our course on privacy and mechanism design, we go back to using differential privacy as a tool in mechanism design, and cover a remarkable result of Nissim, Smorodinsky, and Tennenholtz.
Traditionally in mechanism design, social welfare holds a special place in the pantheon of objective functions: this is because in any social choice setting, we can use the VCG mechanism to exactly optimize for social welfare while guaranteeing dominant strategy truthfulness. In general, it is not possible to truthfully optimize most other objective functions -- and even for social welfare, the VCG mechanism requires the ability to charge payments. It is the rare setting when we can achieve some objective truthfully without payments, and even rarer when that objective is not social welfare.
In todays lecture, we give a general mechanism that in any social choice setting (satisfying certain technical conditions) approximately optimizes any low-sensitivity objective function (social welfare satisfies this condition, but so do many others). Moreover, this mechanism is strictly dominant strategy truthful, and crucially does not require the use of payments. Of course, we can't get around classical impossibility results for free -- the tradeoff, as always, is that we are only optimizing our objective approximately up to some additive loss. However, in large economies, this loss will often become negligible as the size of the population grows.
After class, Rachel Cummings will give our theory seminar on her own work in privacy and mechanism design: The Empirical Implications of Privacy Aware Choice, which is joint work with Federico Echenique and Adam Wierman, both from Caltech. Be there or be square!
Thursday, January 30, 2014
Thursday, January 23, 2014
Lecture 2: Privacy as a Desideratum in Mechanism Design -- Making the Exponential Mechanism Truthful
For those of you following the privacy and mechanism design course at home, tomorrow's Lecture 2 is now online.
This lecture explores a different aspect of privacy and mechanism design. Last week, we considered the use of differential privacy purely as a tool, to design a prior free asymptotically truthful and revenue optimal mechanism for digital goods auctions. In this lecture, we motivate differential privacy as a desideratum for its own sake, and argue that it gives mechanisms (often at very little cost) a natural notion of robustness against the possibility of extra unmodeled parts of agents utility functions.
Finally, we derive a private version of the VCG mechanism, that for general social choice problems is simultaneously:
(And for those of you actually taking this class and looking for inspiration to do a course project, this paper started as Zhiyi Huang's course project in the 2011 privacy course I taught here at Penn)
This lecture explores a different aspect of privacy and mechanism design. Last week, we considered the use of differential privacy purely as a tool, to design a prior free asymptotically truthful and revenue optimal mechanism for digital goods auctions. In this lecture, we motivate differential privacy as a desideratum for its own sake, and argue that it gives mechanisms (often at very little cost) a natural notion of robustness against the possibility of extra unmodeled parts of agents utility functions.
Finally, we derive a private version of the VCG mechanism, that for general social choice problems is simultaneously:
- (Exactly) dominant strategy truthful
- Differentially private
- (Approximately) welfare optimal
(And for those of you actually taking this class and looking for inspiration to do a course project, this paper started as Zhiyi Huang's course project in the 2011 privacy course I taught here at Penn)
Friday, January 17, 2014
Privacy + Mechanism Design course begins today
Today several students will endure the first (3 hour!) lecture in an experimental course I am teaching on privacy and mechanism design. Its a very new area -- whether or not there is enough material to cover a whole semester may depend on how many new theorems are proven during the semester that the course is running. (I already know of the existence of several papers I will want to teach, but haven't read yet since they aren't yet available!)
A secondary goal that I have is to produce a nice set of lecture notes, that will be accessible to people curious about getting into the field. I encourage people to read along, starting with today's Lecture 1. We're starting from basics -- I don't want to assume that readers know anything about either privacy, or mechanism design. In the first lecture, we introduce differential privacy from the perspective of a game theorist, and use it to solve an interesting problem: prior-free revenue maximization in a digital goods auction. Along the way we learn about a useful tool, "The exponential mechanism", that we will encounter again.
The digital goods auction setting is not only a nice introduction to many of the ideas underlying the privacy/mechanism design connection, it is also historically faithful: all of the results in Lecture 1 are from the seminal paper of McSherry and Talwar which introduced the connection between differential privacy and game theory: Mechanism Design via Differential Privacy.
A secondary goal that I have is to produce a nice set of lecture notes, that will be accessible to people curious about getting into the field. I encourage people to read along, starting with today's Lecture 1. We're starting from basics -- I don't want to assume that readers know anything about either privacy, or mechanism design. In the first lecture, we introduce differential privacy from the perspective of a game theorist, and use it to solve an interesting problem: prior-free revenue maximization in a digital goods auction. Along the way we learn about a useful tool, "The exponential mechanism", that we will encounter again.
The digital goods auction setting is not only a nice introduction to many of the ideas underlying the privacy/mechanism design connection, it is also historically faithful: all of the results in Lecture 1 are from the seminal paper of McSherry and Talwar which introduced the connection between differential privacy and game theory: Mechanism Design via Differential Privacy.
Wednesday, January 08, 2014
COLT call for papers
Nina Balcan asked me to post the COLT 2014 call for papers. A couple of interesting things in the call: privacy is specifically mentioned as a constraint of interest on learning, and there is a call for papers on "Learning in other settings: e.g. social, economic, and game-theoretic".
The 27th Annual Conference on Learning Theory (COLT 2014) will take
place in Barcelona, Spain, on June 13-15, 2014
We invite submissions of papers addressing theoretical aspects of
machine learning and related topics. Submissions by authors who are
new to COLT are encouraged. We strongly support a broad definition of
learning theory, including, but not limited to:
• Design and analysis of learning algorithms and their generalization ability
• Computational complexity of learning
• Optimization procedures for learning
• Unsupervised, semi-supervised learning, and clustering
• Online learning
• Interactive learning
• Kernel Methods
• High dimensional and non-parametric empirical inference, including
sparsity methods
• Planning and control, including reinforcement learning
• Learning with additional constraints: E.g. privacy, time or memory
budget, communication
• Learning in other settings: E.g. social, economic, and game-theoretic
• Analysis of learning in related fields: natural language processing,
neuroscience, bioinformatics, privacy and security, machine vision,
data mining, information retrieval.
We are also interested in papers that include viewpoints that are new
to the COLT community. We welcome experimental and algorithmic papers
provided they are relevant to the focus of the conference by
elucidating theoretical results. Also, while the primary focus of the
conference is theoretical, papers can be strengthened by the inclusion
of relevant experimental results.
COLT will award both best paper and best student paper awards. Best
student papers must be authored or coauthored by a student. Authors
must indicate (using a footnote on the first page of the paper) at
submission time if they wish their paper to be eligible for a student
award. This does not preclude the paper to be eligible for the best
paper award. The program committee may decline to make these awards,
or may split them among several papers.
Papers that have previously appeared in journals or at other
conferences, or that are being submitted to other conferences, are not
appropriate for COLT. Papers that include work that has already been
submitted for journal publication may be submitted to COLT, as long as
the papers have not been accepted for publication by the COLT
submission deadline (conditionally or otherwise) and that the paper is
not expected to be published before the COLT conference (June 2014).
Accepted papers will be published electronically, in the JMLR Workshop
and Conference Proceedings series.
Rebuttal Phase
As in the previous years, we will have a rebuttal phase during the
review process. Initial reviews will be sent to authors before final
decisions have been made. Authors will have the opportunity to provide
a short response on the PC's initial evaluation. Final
acceptance/rejection decision will be made a week later.
Open Problems Session:
We also invite submission of open problems. A separate call for open
problems will be available at the conference website:
http://orfe.princeton.edu/
Submission Instructions:
Submissions are limited to 12 JMLR-formatted pages, plus additional
pages for references and appendices. All details, proofs and
derivations required to substantiate the results must be included in
the submission, possibly in the appendices. However, the contribution,
novelty and significance of submissions will be judged primarily based
on the main text (without appendices), and so enough details,
including proof details, must be provided in the main text to convince
the reviewers of the submissions' merits.
Important Dates:
• Paper submission deadline: February 7th, 2014, 11:00 PM EST
• Author response period: April 5-10, 2014
• Author notification: April 19, 2014
• Conference: June 13-15, 2014
On behalf of the COLT 2014 organizers,
Program Chairs
• Maria-Florina Balcan (Georgia Institute of Technology)
• Csaba Szepesvári (University of Alberta)
Local Arrangements Chairs
• Sébastien Bubeck (Princeton University)
• Gábor Lugosi (ICREA and Pompeu Fabra University)
Publication Chair
• Vitaly Feldman (IBM Almaden Research Center)
The 27th Annual Conference on Learning Theory (COLT 2014) will take
place in Barcelona, Spain, on June 13-15, 2014
We invite submissions of papers addressing theoretical aspects of
machine learning and related topics. Submissions by authors who are
new to COLT are encouraged. We strongly support a broad definition of
learning theory, including, but not limited to:
• Design and analysis of learning algorithms and their generalization ability
• Computational complexity of learning
• Optimization procedures for learning
• Unsupervised, semi-supervised learning, and clustering
• Online learning
• Interactive learning
• Kernel Methods
• High dimensional and non-parametric empirical inference, including
sparsity methods
• Planning and control, including reinforcement learning
• Learning with additional constraints: E.g. privacy, time or memory
budget, communication
• Learning in other settings: E.g. social, economic, and game-theoretic
• Analysis of learning in related fields: natural language processing,
neuroscience, bioinformatics, privacy and security, machine vision,
data mining, information retrieval.
We are also interested in papers that include viewpoints that are new
to the COLT community. We welcome experimental and algorithmic papers
provided they are relevant to the focus of the conference by
elucidating theoretical results. Also, while the primary focus of the
conference is theoretical, papers can be strengthened by the inclusion
of relevant experimental results.
COLT will award both best paper and best student paper awards. Best
student papers must be authored or coauthored by a student. Authors
must indicate (using a footnote on the first page of the paper) at
submission time if they wish their paper to be eligible for a student
award. This does not preclude the paper to be eligible for the best
paper award. The program committee may decline to make these awards,
or may split them among several papers.
Papers that have previously appeared in journals or at other
conferences, or that are being submitted to other conferences, are not
appropriate for COLT. Papers that include work that has already been
submitted for journal publication may be submitted to COLT, as long as
the papers have not been accepted for publication by the COLT
submission deadline (conditionally or otherwise) and that the paper is
not expected to be published before the COLT conference (June 2014).
Accepted papers will be published electronically, in the JMLR Workshop
and Conference Proceedings series.
Rebuttal Phase
As in the previous years, we will have a rebuttal phase during the
review process. Initial reviews will be sent to authors before final
decisions have been made. Authors will have the opportunity to provide
a short response on the PC's initial evaluation. Final
acceptance/rejection decision will be made a week later.
Open Problems Session:
We also invite submission of open problems. A separate call for open
problems will be available at the conference website:
http://orfe.princeton.edu/
Submission Instructions:
Submissions are limited to 12 JMLR-formatted pages, plus additional
pages for references and appendices. All details, proofs and
derivations required to substantiate the results must be included in
the submission, possibly in the appendices. However, the contribution,
novelty and significance of submissions will be judged primarily based
on the main text (without appendices), and so enough details,
including proof details, must be provided in the main text to convince
the reviewers of the submissions' merits.
Important Dates:
• Paper submission deadline: February 7th, 2014, 11:00 PM EST
• Author response period: April 5-10, 2014
• Author notification: April 19, 2014
• Conference: June 13-15, 2014
On behalf of the COLT 2014 organizers,
Program Chairs
• Maria-Florina Balcan (Georgia Institute of Technology)
• Csaba Szepesvári (University of Alberta)
Local Arrangements Chairs
• Sébastien Bubeck (Princeton University)
• Gábor Lugosi (ICREA and Pompeu Fabra University)
Publication Chair
• Vitaly Feldman (IBM Almaden Research Center)
Subscribe to:
Posts (Atom)