Author Archives: Anand Sarwate

IPAM Workshop on Algorithmic Challenges in Protecting Privacy for Biomedical Data

Posted on by

IPAM is hosting a workshop on “Algorithmic Challenges in Protecting Privacy for Biomedical Data” which will be held at IPAM from January 10-12, 2018.

The workshop will be attended by many junior as well as senior researchers with diverse backgrounds. We want to to encourage students or postdoctoral scholars who might be interested, to apply and/or register for this workshop.

I think it will be quite interesting and has the potential to spark a lot of interesting conversations around what we can and cannot do about privacy for medical data in general and genomic data in specific.

Advertisement

The Ideological Echo Chamber of the Beach

Posted on by

Disclaimer: I think that the beach should be open to all. Clearly there are some who unfairly malign some beach-goers. However, we need to have an honest discussion about the differences between different types of beach denizens. Thankfully, because I am a Star-Bellied and not Star-Eyed Sneech, I believe that we we can have an open and frank discussion about why Sneeches who originally did not have stars on their bellies have been disrupting the natural hierarchy of the beach. This bias towards equal-starness in Sneechdom threatens the viability of the beach and makes pariahs of those Sneeches whose came by their stars honestly [1]. It is imperative that we have this conversation now before the beach is destroyed forever.

There are obvious innate biological differences between Star-Bellied Sneeches and Common Sneeches. Star-bellied Sneeches have stars: this makes them more adept at skills that require people who have stars on their bellies [2]. Star-Belliedness is heritable: evolutionary sneechology shows that the reason Star-Bellied Sneeches are the “best kind of Sneetch on the beaches” because of the benefits conferred by their stars. What could be more simple? Of course, there are occasional bad Star-Bellied Sneeches and occasional good Common Sneeches, but the fact is on average, the Common Sneech is simply not as good on the beach as the Star-Bellied Sneech. Since the only difference between them is the star, it is only logical to assume that having a star makes a Sneech better at being on the beach.

Star-Bellied Sneeches are better at beach-related activities such as hiking and playing ball [3]. They are natural denizens of the warm beaches. By contrast, the Sneeches without stars are less adapted, preferring the “cold in the dark of the beaches” and “moping alone on the beaches.” This explains why the two types have different roles: Common Sneeches prefer the cold and moping alone because that is what they are good at. Unfortunately, because of our new culture of suppressing traditional viewpoints, we cannot have an honest discussion about this beach-appropriateness gap; the dire consequences of attempting to make all Sneeches have equivalent stars discriminates against the true Star-Bellied Sneeches. The time has come where a Star-Bellied Sneech can no longer speak of “frankfurter roasts, or picnics or parties or marshmallow toasts,” without requiring that Common Sneeches be invited too (despite the superficial appearance of their stars).

As an employee of Sylvester McMonkey McBean Corp. (SMMC), I feel it is my duty to speak out against unfair discrimination against Star-bellied Sneeches. The company offers special “fix-it-up” training and that puts stars on the bellies of Common Sneeches. What’s more, this star service is only available to Sneeches without stars! This is highly discriminatory: how can will we ever know whose stars are original and whose stars are the result of special training? This violates the natural order of things. Because Common Sneeches have a tendency to mope alone, we run the risk of having Sneeches without innate hiking- and ball-playing-skill gaining prominence on the beech. Again, this is not bad for specific Sneeches, but on average will make SMMC less competitive and the beach sub-optimal.

My recommendation is that we should treat each Sneech individually. Those Common Sneeches who are demonstrably non-mopey and can, in controlled environments, enjoy a marshmallow toast, could be possibly considered for further admission into frankfurter roasts and picnics. However, we cannot simply erase differences between Sneeches by allowing non-Star-Bellied Sneeches to obtain stars. It may be politically incorrect to say this, but we must have a way of distinguishing those Common Sneeches who are deserving of stars from those who are not [4].

Sylvester McMonkey McBean Corp. is treading down a dangerous path and is alienating a great number of Star-Bellied Sneeches. I have received very positive feedback regarding these opinions, so there is clearly a “silent minority” of Star-Bellied Sneeches who are yearning for an open conversation [5] about these topics. However, the beach has become an inhospitable plate for the rational-minded Sneech.

In closing, I wish to state here that I do not intend to offend Common Sneeches: therefore I cannot possibly have offended any of them, because I said so. That is logic that any Star-Bellied Sneech can understand: Sneeches who cannot are clearly Common mopes.

[1] That is, they were born with them.

[2] For example, fooling starfish while snorkeling is something only Star-bellied Sneeches can do.

[3] While it’s true that in previous years “you could only play ball if your bellies had stars,” I would like to strenuously emphasize that that is #NotAllStarBellies. Not mentioning this disclaimer is evidence of the ideological commitment to the notion that all Sneeches are similarly capable of playing ball. Common Sneeches should perhaps play in a league of their own.

[4] Although there may be Star-Bellied Sneeches who fail to meet the bar, this can be addressed by introducing better role models and mentors. Unfortunately, such programs are only available to Common Sneeches.

[5] Preferably one only involving non-mopey Sneeches.

100 signatures needed by 5/12 to nominate José Moura for IEEE President

Posted on by

As I wrote earlier, José Moura is trying to get on the ballot for IEEE President. The deadline is May 12 and he needs only 100 more signatures to get onto the ballot. If you are an IEEE member please take the 1 minute to sign the petition to get him on the ballot.

IEEE has an undemocratic nominations process in which the IEEE Board of Directors (BoD) gets to decide who the candidates will be. Because Prof. Moura opposed the BoD proposed amendment to consolidate power into the BoD and reduce regional representation, it is not hard to imagine that the BoD would not want to allow dissenting voices in the Presidential race. There is a petition at the IEEE website to put him on the ballot. It needs around 4,000 signatures and students members are also welcome to sign. You sign in with your IEEE account and then go to “Annual Election Petitions.”

Put José Moura on the ballot!

Retraction for Symmetric Matrix Perturbation for Differentially-Private Principal Component Analysis, ICASSP 2016

Posted on by

This is somewhat difficult to write, so I’ll cut to the chase. The proposed differentially private PCA method from the ICASSP 2016 paper by my student Hafiz Imtiaz and myself is incorrect and so should be retracted:

H. Imtiaz, A.D. Sarwate, Symmetric Matrix Perturbation for Differentially-Private Principal Component Analysis, Proceedings of the 2016 International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2339–2343, March 2016.

As a side-result, the paper of Jiang et al. from AAAI 2016 has as similar incorrect result. I’d like to thank my collaborator Kamalika Chaudhuri, who brought this up to me after a conversation with Kunal Talwar. The fact that I have taken so long to make this public announcement was due to a misguided effort to adapt the algorithm and run new experiments. Unfortunately, this was not to be.

What is the algorithm? Well, the basic idea in all of these papers is to add Wishart noise to produce a noisy estimate of the second-moment matrix of a data set. We start with some data vectors \mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n \in \mathbb{R}^d and compute the second moment matrix A = \sum_{i} \mathbf{x}_i \mathbf{x}_i^{\top}. If we want to compute the SVD in a differentially private way, one approach is to add noise E to the second moment matrix to form \hat{A} = A + E such that \hat{A} is a differentially private version of A. Then by postprocessing invariance, the SVD of \hat{A} is also differentially private.

The motivation for our work was twofold: 1) we wanted to see how theoretically “optimal” algorithms performed on real data sets, especially for suggested settings of the parameters, and 2) we wanted to propose a good (\epsilon,0)-differentially private algorithm? What is wrong with \delta > 0? In some application domains, I have found that the notion of a “failure probability” is not compatible with practitioners’t (often lawyer-driven) policy requirements. Concentrated DP and newer concepts still keep the \delta > 0, so they might not fly either. Plus, it’s a slightly more challenging and interesting mathematical problem.

A very good (\epsilon,\delta) choice for E is to choose the entries to be i.i.d. Gaussian on the diagonal and above and copy entries below the diagonal such that E is symmetric. This is the Analyze Gauss (AG) algorithm of Dwork et al. Although \hat{A} is symmetric, it’s no longer positive semidefinite (PSD). However, this gives order-optimal guarantees on utility. Taking that as a cue, we wanted to preserve the PSD property in \hat{A}, so we proposed adding noise with a Wishart distribution, which corresponds to generating an i.i.d. rectangular d \times p Gaussian matrix $\latex Z$ and settting E = Z Z^{\top}. This generates a PSD perturbation fo \hat{A} and has pretty good utility guarantees as well.

Unfortunately, the Wishart perturbation is blatantly non-private because the image under the perturbation is a PSD cone starting from A, and for A and A' coming from neighboring databases, the cones are not the same. As a trivial example, suppose A = \mathbf{x} \mathbf{x}^{\top} and A' = \mathbf{0}. Hafiz has written up a more formal description. Because differential privacy requires the support of the output distribution under different inputs to coincide, it is difficult to create a (data-independent) additive perturbation that preserves the PSD property. The exponential mechanism works, but is not additive.

In the end, I was rather excited about the empirical performance (c.f. goal 1) above) and we were close to the deadline so I did not do a proper job checking the technical results in our rush to submit. I’m making this a teachable moment for myself but wanted to make sure there was a public, findable version of this retraction so that people don’t continue to build on our results. What we learned from 1) is that designing practical PCA methods for reasonable values of (\epsilon,\delta) is still challenging — many data sets do not have the sample sizes needed to make differential privacy practical. The solution may be to design more complex multi-stage pipeline, revisit what we can assume about the data space and neighborhood relations, or come up with better (\epsilon,0) algorithms that pass muster for the applications when nonzero \delta is unacceptable.

Readings

Posted on by

Last semester was full of travel but short on time. Despite having more time to read, I end up reading less. Maybe I can just blame the election. This semester is not going that great either, reading-wise.

Measuring the World (Daniel Kehlmann). This was apparently a bestseller in German-speaking countries. It’s about Gauss meeting von Humboldt, but mostly about von Humboldt. Gauss comes off as pretty cranky, but von Humboldt’s adventures have an air of the fantastical about them. I’m not sure why it was so popular in Germany, but I think those who like science and history would enjoy it.

The Fifth Season (N.K. Jemisin). Won the Hugo award, wide-ranging, multiple perspectives. A world in which seismic activity crushes civilizations regularly. Engenders a kind of cruelty and fend-for-oneselfness that seems raw but desperate. Really a great book, can’t wait to read the next.

The Social Construction of What? (Ian Hacking). A book that is not really about the “science wars” but is couched in there nonetheless. Hacking tries to taxonomize and break down what “social construction” means. I like the approach but as a “book” it kind of meanders to the end, with a chapter on child abuse more or less stapled in. He sets up the first half with a bunch of scalpels with which to dissect cases, but then doesn’t use them as clearly. I think I’m biased because I like reading math books where you get a general theorem and then a bunch of nice corollaries that recover known results or shed new light on something etc.

Too Like The Lightning (Ada Palmer) One of the best sci-fi books I’ve read in terms of Big Ideas and Lots of History. The second book in the series came out and I am going to read it soon. There’s a Crooked Timber seminar on it that I’ll read afterwards because spoilers. It’s a very difficult book to describe to others, but it’s in a very futuristic Earth with a very complex governmental system and perhaps extreme stratification into affinity groups. The latter seems “for the purposes of argument” in terms of the philosophizing. The narrator is remarkably unreliable, and the novel is written in a historical style, addressing the Reader, who sometimes themselves interjects. Read it if you like heady speculative fiction and complex worlds.

My Brilliant Friend (Elena Ferrante) This is the first of the Neapolitan Quartet novels and I found it utterly engaging. I think it’s one of those books which many of my friends who are women have read and almost none of my male friends have read, but that’s just some stupid sexism-in-publishing BS. I’m looking forward to the next three books, although I’ve heard this is the best of them. The thing to me about it is how vividly I could picture the events without Ferrante actually going through and describing the details. It somehow captures the feeling of revisiting a memory. Maybe I’m getting older. Time to start reading Proust?

 

Postdoc at ASU/Harvard on ML and Privacy

Posted on by

A joint postdoc position at Arizona State University and Harvard University in the area of machine learning and privacy is available immediately. The successful candidate will be working with the research groups of Prof. Lalitha Sankar and Prof. Flavio du Pin Calmon.

Specific topics of focus are the interplay of machine learning and privacy with focus on both rigorous information-theoretical results as well as practical design aspects.

The appointment will be for a period of 12 months initially, with a possibility for renewal. We are looking for strong applicants with an excellent theoretical background and a proven capacity for high-quality research in form of a strong publication record. Knowledge of privacy literature is desirable.

Interested applicants should submit a current CV, a 1-page research statement and a list of three references. Candidates should contact us via email at lsankar@asu.edu and/or flavio@seas.harvard.edu.

DIMACS Workshop on Distributed Optimization, Information Processing, and Learning

Posted on by

My colleague Waheed Bajwa, Alejandro Ribeiro, and Alekh Agarwal are organizing a Workshop on Distributed Optimization, Information Processing, and Learning from August 21 to August 23, 2017 at Rutgers DIMACS. The purpose of this workshop is to bring together researchers from the fields of machine learning, signal processing, and optimization for cross-pollination of ideas related to the problems of distributed optimization, information processing, and learning. All in all, we are expecting to have 20 to 26 invited talks from leading researchers working in these areas as well as around 20 contributed posters in the workshop.

Registration is open from now until August 14 — hope to see some of you there!

Register soon for the 2017 North American School of Information Theory

Posted on by

The site for the 2017 North American School of Information Theory is now live and registration will begin next week. The IT Schools have been going strong for the last few years and are a great resource for students, especially new students, to get some exposure to information theory research beyond their own work and what they learned in class. Most schools do not have several people working on information theory. For students at such institutions the school provides a great way to meet other new researchers in the field.

Why I will no longer do research sponsored by the Department of Homeland Security

Posted on by

Shortly after the inauguration, the new administration announced a blanket ban on  refugees and any entry into the US from 7 proscribed countries. The announcement was met with outrage, ridicule, and legal opposition. Despite its obvious unconstitutionality and complete lack of guidance on implementation, the Department of Homeland Security (DHS) engaged in a weekend of harassment and intimidation at our border. They were big cheerleaders of the effort but also incompetent and unprofessional. At the same time, a pilot project I had worked on, funded by DHS, was about to be submitted for a “phase 2” extension. In light of those events, I asked to be taken off the project entirely and will no longer seek funding from DHS.

Now the administration has revealed an harsh and chilling new plan to terrorize immigrants and their families through a campaign of demonization and deportation. The biggest cheerleader of this plan is the new DHS secretary, John F. Kelly. This only validates my decision: I cannot conduct research under the aegis of an agency whose planned actions run counter to nearly everything I believe. It would be unethical for me to continue to do so. If that were not enough, DHS has also ceded its technical authority on security/privacy issues. I have little confidence that real security/privacy is a priority.

Supporting graduate students in engineering often requires getting funds from multiple sources; it is difficult to sustain a research group (and in some places, get tenure) on NSF (or NIH, in my field at least) funding alone. The usual suspects are industry, foundations, the various defense research programs (ARO, ONR, AFOSR, DARPA), or other government departments (DOE comes to mind). If you work in security/privacy, DHS has also been a (relatively) new source of research funding. Many of the other government agencies do fund basic research but some are focused more on applied research or transitioning research to practice.

There are many considerations to balance. As a theory and algorithms person, the overhead of making “deliverables” can take time away from basic research. Some programs have a lot of check-ins and progress updates which don’t necessarily work with the academic calendar. Finally, trying to describe your theory question about graph topology and its impact on convergence rates of some estimator as crucial to improving “warfighter capabilities” can sometimes feel awkward. My approach thus far has been to try things out. If the proposal is on research I would want to do anyway and everything is public domain and open, then OK. If the experience is not so good/fun, maybe I will consider alternatives. Basic research has lots of applications; improving a control algorithm could yield better drone targeting or more accurate laser-aided surgery.

It was with this in mind that I proceeded with a DHS-funded project on privacy-sensitive anomaly detection. It was a short project but raised a number of interesting new problems and models that I would like to explore, if possible, in the future. It also funded a student whose studies are now threatened by this very administration. Indeed, the entire academic research enterprise in the US is under threat. As academics we can sign petitions, but it is not enough. Scott Aaronson wrote very eloquently about this issue after the initial ban was announced (see also Terry Tao). My department has seen a dramatic decrease in the number of applicants in general and not just from Iran. We were just informed that we can no longer make TA offers for students who are unlikely to get a visa to come here.

The Department of Homeland Security has demonstrated its blatant disregard for moral norms. Why should we trust its scientific norms? What confidence do we have that funding will not be used in some coercive way? What does it say to our students when we ask them to work for DHS? Yes, the government is big, but at some point the argument that it’s mostly the guy at the top who is bad but the rest of the agency is still committed to good science becomes just too hard to swallow. I decided that I can’t square that circle. Each one of us should think hard about whether we want to.

Put José M.F. Moura on the IEEE President Ballot!

Posted on by

José Moura was nominated to be considered as a candidate for IEEE President. The IEEE Board of Directors (BoD) is the body that decides who the candidates will be. They were also behind the proposed IEEE constitutional amendment that was opposed by more than 25 IEEE Societies because it was a rather naked power grab that would have moved much of the constitution to bylaws that could be amended by a small group of individuals, reducing regional representation, and reducing technical activities representation. You can think of it as an attempt by the BoD to Make IEEE Great Again. Prof. Moura spoke up against the amendment (including at an ITSOC BoG meeting) and in the end the amendment did not pass.

It is likely that the BoD’s decision to not nominate him is retaliation for his actions in defense of what he (and many others) felt are the best interests of the IEEE. While this Trump-esque approach to handling dissent may be popular in Washington, it seems quite inappropriate for an international organization such as IEEE. There is a petition at the IEEE website to put him on the ballot. It needs around 4,000 signatures and students members are also welcome to sign. You sign in with your IEEE account and then go to “Annual Election Petitions.” Note this is not a vote for him, but rather allowing him to be on the ballot. Please consider signing!