Differentially Private ERM

Right after Memorial Day, I submitted a paper with Kamalika Chaudhuri and Claire Monteleoni to the Journal of Machine Learning Research on differential privacy and empirical risk minimization. This work looks at how to learn a classifier from training data in such a way that an adversary with access to the classifier and full knowledge of all but one of the training data points would still have a difficult time inferring the values of the last data point.

Ben Rubenstein has a nice post on the differential privacy model, and Adam Smith has more to say on sample secrecy. Adam and his colleagues (Dan Kifer and Abhradeep Guha Thakurta) gave us useful feedback on an earlier draft, which prompted me to learn some new facts about matrix perturbations, symmetric functions, and eigenvalues. Perhaps I’ll blog about this a bit more in the future, but I seem to be going in fits and starts here, so I don’t want to promise anything.

On a related note, ArXiV has dramatically changed its interface for submissions, and it is soooooo much better than before.


CTW 2010

Playa Norte, Isla Mujeres

Playa Norte on Isla Mujeres

I was lucky enough to get invited to present at the Communications Theory Workshop (CTW) in Cancun last month. Since the conference started on a Monday I took the weekend before to do a little sightseeing, hang out on the beach (see above), and visit Chichen Itza, which was pretty amazing. CTW is a small conference — single track, 2.5 days, and plenty of time for panels, discussions, etc. I had a great time there, and it was really nice to meet new people who were working on interesting problems that I hadn’t even heard about.

The first day was focused on wireless data services, the explosion thereof, and the lack of capacity to support it all. Add more relays, femtocells, interference management and alignment, putting more antennas for MIMO gains. Reinaldo Valenzuela was pretty pessimistic — according to him we are pretty much at the point where service providers are losing money by providing data over wireless. He seemed to think the only way out now is to change pricing models or really try to exploit network MIMO.

The second day was on cognitive radio, where the picture also seemed a bit pessimistic. Michael Marcus kind of laid into academics for not participating in the FCC comment process. The criticism is valid — if we care about cognitive radio and its potentials and so on, we should try to persuade the regulators to do smart things and not piecemeal things. As things stand now, it’s unclear how much additional capacity is available in the TV bands, given the current requirements for operating there. The sensing requirements nigh unreasonable, and if you do detect a primary you have to stay silent for 30 minutes. That makes it kind of hard to run a commercial service.

Another thing I learned during that day was that wireless microphones in the US operate in the TV bands, and are grandfathered in to the existing rules for cognitive radio. This means you have to detect if you will interfere with a wireless mic, which seems quite tough. Steve Shellhammer talked about a contest Qualcomm ran to build a detector for this problem. In addition, a large fraction of wireless microphone users are not licensed and hence their use is illegal, but nobody’s enforcing that.

The second half of the day was on emerging topics, followed by a panel called “Is Communication Theory Dead?” I think the pessimism and despair of the first two days needed to be let out a little, and there was a pretty spirited discussion of whether communication theorists were answering the right questions or not. It was like group therapy or something. Luckily there was the banquet after the panel so people could forget their woes…

The last day of the workshop was the session I spoke in, which were 5 talks on wireless networks, but from vastly different perspectives. Tara Javidi talked about routing, Daniela Tuninetti about information theory and cognitive interference channels, Elza Erkip about game theory models for the interference channel, and Anna Scaglione about cooperative information flooding. For my part, I talked about (very) recent work I have done with Tara on distributed consensus with quantized messages. We have some nice first-order results but I’m still hammering away at better bounds on the convergence rate.