I have been practicing for this my whole life

As the coronavirus epidemic advances in Italy with a 25-30% growth rate (meaning that the numbers are doubling every 3-4 days), and after two weeks of “lockdown-lite” in Northern Italy seems to have made no difference, the Italian government imposed on Sunday morning a stricter lockdown on the region of Lombardy and some cities outside the region including Venice. Several people have reached out to ask how things are going, so here is a brief recap.

Continue reading

Lies, damn lies, and covid-19

In the past two weeks, in Italy, we have been drowning in information about the novel coronavirus infection, but the statistics that have been circulating were lacking proper context and interpretation. Is covid-19 just a stronger form of the flu or is it a threat to the world economy? Yes.

Now that the first community transmissions are happening in my adopted home in the San Francisco Bay Area, I would like to relay to my American readers what I learned from the Italian experience.

Continue reading

This year, for Lent, Milan gave up nightlife

Greetings from Milan, in Italy’s “yellow zone” of areas bordering clusters of coronavirus infections. This week, all schools, universities, museums, theaters are closed, bars have to close by 6pm, and fairs and conferences are being postponed. The “red zone” of small towns with the clusters of infections is on lockdown.

Milan has been unseasonably warm and sunny in the past few days, and walking through the city, with very light car and pedestrian traffic, has been lovely. This is apparently what the city usually looks like in August, but without the heat and humidity.
Continue reading

Postdoc Position at Bocconi

I am recruiting for two postdoctoral positions, each for one year renewable to a second, to work with me at Bocconi University on topics related to average-case analysis of algorithms, approximation algorithms, and combinatorial constructions.

The positions have a very competitive salary and relocation benefits. Funding for travel is available.

Application information is at this link. The deadline is December 15. If you apply, please also send me an email (L.Trevisan at unibocconi.it) to let me know.

So you want to move to Milan

Ten weeks into my move to Italy I am feeling more and more settled. I even eventually got a Milan bus card, which proves that if you really believe in yourself you can achieve anything. I held a midterm for my theoretical computer science undergraduate class, and there were zero students asking for special accommodations and zero students complaining to me about their grade.

According to our national tradition, I like to complain, but Bocconi is really not giving me much to work with.

But enough about me, let’s talk about you. I am going to assume that you want to come to Milan, because, really, why not? Here are some ways in which this can happen:

  • You are a high school senior and you would like to study computer science in college, but you like math as well: next academic year, Bocconi is starting a new undergraduate program on math and CS
  • You are an undergraduate or masters student applying to PhD programs and you would like to work with me: next academic year, Bocconi is starting a new PhD program on statistics and computer science
  • You are a theory PhD student and you are looking for what to do next summer: I would be interested in hosting graduate students for part of next summer, especially during the month of July. Ask your advisor to contact me if this is something that you would be interested in
  • You are a graduating theory PhD student and you are looking for a postdoc next year: I will have one or two openings for postdocs next year. The call for applications will be up soon. The tax-free salary will be very competitive and Bocconi has exceptionally well-functioning processes to get non-Italian-speakers settled in, help them do the immigration paperwork, look for housing, finding English-speaking primary care physicians, etc.
  • You are (or might be tempted to be) on the job market for a faculty position: in light of all the new initiatives on computing, and the current staff of one computer science professor, Bocconi would like to hire at all levels, preferably at the levels of Associate Professor or Full Professor, in computer science, especially in theory and in AI. Salaries are very competitive, they are essentially tax-free for six years for people who have not lived in Italy in the past two years, all teaching is in English, and the university makes it very easy for foreigners to settle in.
  • You are a professor and your sabbatical is coming up, or you arranged your teaching to have a semester without teaching to do some traveling: contact me if you are interested in visiting for any length of time.

I am in Baltimore for FOCS through Tuesday morning if you want to talk to me in person.

What’s New

It has been six weeks since I moved to Milan, and I am not yet completely settled in yet.

For example, although, as of yesterday, I finally have working wired internet access in my place, I still do not have a bus card (obtaining the latter has been one of the most stubbornly intractable problems I have encountered) and all the stuff that I did not carry in two bags is still in transit in a container.

Meanwhile, the busyness of handling the move, getting settled, trying to get a bus card, and teaching two courses, has meant that I did not really have time to sit down with my thoughts and process my feelings about such a major life change. If people ask me what I miss about San Francisco I will, truthfully, say something like UberX, or Thai food, or getting a bus card from a vending machine, because I still have not had a chance to miss the bigger stuff. Similarly, this post will be about random small stuff.

Continue reading

A New Conference on Information-Theoretic Cryptography

A new conference on Information-Theoretic Cryptography is starting next year. It is about topics that I have always been fond of, a former student of mine is in the steering committee, and an academic grandchild of mine is in the program committee of the inaugural conference, so I am very happy to pass along the following announcement from Benny Applebaum.

Dear friends,
We are happy to announce the birth of a new conference on Information-Theoretic Cryptography (ITC). Information-theoretic cryptography studies security in the presence of computationally unbounded adversaries and covers a wide array of topics at the intersection of cryptography, coding theory, information-theory and theory of computation. Notable examples include randomness extraction and privacy amplification, secret sharing, secure multiparty computation and proof systems, private-information retrieval and locally decodable codes, authentication codes and non-malleable codes, differential privacy, quantum information processing, and information-theoretic foundations of physical-layer security. See https://itcrypto.github.io for more information.

ITC replaces the International Conference on Information Theoretic Security (ICITS), which was dedicated to the same topic and ran 2005-2017. ITC can be seen as a reboot of ICITS with a new name, a new steering committee and a renewed excitement.  (beware: there is  a fake website for ICITS 2019 created by a known fraudulent organization)

The conference will have two tracks: a conference track and  a “greatest hits” track. The conference track will operate like a traditional conference with the usual review process and published proceedings. The “greatest hits” track consists of invited talks (not included in the proceedings) that highlight the most exciting recent advances in the area. We solicit nominations for “greatest hits” talks from the community.

The first ITC conference will take place in Boston, MA on June 17-19, 2020 (just before STOC).  The submission deadline for ITC 2020 is Dec 16, 2019 and the call for papers (including a nomination procedure for the greatest hits track) is available here:  https://itcrypto.github.io/2020.html

Please submit your best work to ITC 2020! We hope to see many of you there!

best regards,
The Steering Committee:  Benny Applebaum (Chair), Ivan Damgård , Yevgeniy Dodis,  Yuval Ishai, Ueli Maurer,  Kobbi Nissim, Krzysztof Pietrzak, Manoj Prabhakaran, Adam Smith, Yael Tauman Kalai, Stefano Tessaro, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs, Mary Wootters,  Chaoping Xing, Moti Yung

Three stories about U.C. administration

A few months ago, I was delighted to see the University of California holding on to its demands in its negotiations with Elsevier. The U.C. wanted to renegotiate its contract so that, in addition to having access to the subscribed journals, U.C. scholars could publish in them with open access (that is, so that anybody in the world would have free access to the articles written by U.C. scholars).

This seemed like a reasonable model to balance profitability for publishers and open access, but there was no way to agree on it with Elsevier. Meanwhile, U.C. has not renewed its Elsevier subscriptions and Elsevier has cut off access to U.C. libraries.

I was very impressed to see the University of California central administration do something right, so I wondered if this was the kind of portent that is a harbinger of the apocalypse, or just a fluke. Subsequent events suggest the latter.

The University of California has spent a lot of time and money to build a centralized system for job applications and for job applicant review. I was first made aware of this when I chaired the recruiting committee for the Simons Director position. At first we were told that we could solicit applications through the (vastly superior) EECS-built system for job applications and reviews. After the application deadline passed, we were told that, in fact, we could not use the EECS system, and so the already overworked EECS faculty HR person had to manually copy all the data in the central campus system.

The American Mathematical Society has created a wonderfully functional system, called Mathjobs where applicants for academic mathematics jobs (ranging from postdocs to professorship) can upload their application material once, and their recommenders can upload their letters once, and then all the universities that the candidate applies to have access to this material. Furthermore, if needed, both applicants and recommenders can tailor-make their material for a particular university or universities, if they want to.

Everybody was living happily, but not ever after, because the U.C. central campus administration decided that everybody in the University of California had to use the centralized system for all jobs. Both the AMS and U.C. mathematicians tried to find a reasonable accommodation, such as allowing the U.C. system to access the letters posted on mathjobs. The campus administration reasoned response was roughly “sucks to be you.” There is more of the story in an AMS notices article by the chair of math at U.C. Davis.

Finally, this year U.C. Berkeley will not be listed in the US News and World Report rankings because it has submitted wrong data in the past.

Online Optimization Post 5: Bregman Projections and Mirror Descent

In this post we return to the generic form of the FTRL online optimization algorithm. If the cost functions are linear, as they will be in all the applications that I plan to talk about, the algorithm is:

\displaystyle   x_t := \arg\min_{x\in K} \ R(x) + \sum_{k=1}^{t-1} \langle \ell_k, x \rangle \ \ \ \ \ (1)

where {K\subseteq {\mathbb R}^n} is the convex set of feasible solutions that the algorithm is allowed to produce, {x \rightarrow \langle \ell_k , x \rangle} is the linear loss function at time {k}, and {R: K \rightarrow {\mathbb R}} is the strictly convex regularizer.

If we have an unconstrained problem, that is, if {K= {\mathbb R}^n}, then the optimization problem (1) has a unique solution: the {x_t} such that

\displaystyle  \nabla R(x_t) = - \sum_{k=1}^{t-1} \ell_k

and we can usually both compute {x_t} efficiently in an algorithm and reason about {x_t} effectively in an analysis.

Unfortunately, we are almost always interested in constrained settings, and then it becomes difficult both to compute {x_t} and to reason about it.

A very nice special case happens when the regularizer {R} acts as a barrier function for {K}, that is, the (norm of the) gradient of {R} goes to infinity when one approaches the boundary of {K}. In such a case, it is impossible for the minimum of (1) to occur at the boundary and the solution will be again the unique {x_t} in {K} such that

\displaystyle  \nabla R(x_t) = - \sum_{k=1}^{t-1} \ell_k

We swept this point under the rug when we studied FTRL with negative-entropy regularizer in the settings of experts, in which {K = \Delta} is the set of probability distributions. When we proceeded to solve (1) using Lagrange multipliers, we ignored the non-negativity constraints. The reason why it was ok to do so was that the negative-entropy is a barrier function for the non-negative orthant {({\mathbb R}_{\geq 0})^n}.

Another important special case occurs when the regularizer {R(x) = c || x||^2} is a multiple of length-squared. In this case, we saw that we could “decouple” the optimization problem by first solving the unconstrained optimization problem, and then projecting the solution of the unconstrained problem to {K}:

\displaystyle y_{t} = \arg\min_{y\in {\mathbb R}^n} \ c || y||^2 + \sum_{k=1}^{t-1} \langle \ell_k, y \rangle

\displaystyle  x_t = \Pi_K (y_t) = \arg\min _{x\in K} || x - y_t ||

Then we have the closed-form solution {y_t = - \frac 1{2c} \sum_{k=1}^{t-1} \ell _k} and, depending on the set {K}, the projection might also have a nice closed-form, as in the case {K= [0,1]^n} that comes up in results related to regularity lemmas.

As we will see today, this approach of solving the unconstrained problem and then projecting on {K} works for every regularizer, for an appropriate notion of projection called the Bregman projection (the projection will depend on the regularizer).

To define the Bregman projection, we will first define the Bregman divergence with respect to the regularizer {R}, which is a non-negative “distance” {D(x,y)} defined on {{\mathbb R}^n} (or possibly a subset of {{\mathbb R}^n} for which the regularizer {R} is a barrier function). Then, the Bregman projection of {y} on {K} is defined as {\arg\min_{x\in K} \ D(x,y)}.

Unfortunately, it is not so easy to reason about Bregman projections either, but the notion of Bregman divergence offers a way to reinterpret the FTRL algorithm from another point of view, called mirror descent. Via this reinterpretation, we will prove the regret bound

\displaystyle  {\rm Regret}_T(x) \leq D(x,x_1) + \sum_{t=1}^T D(x_t,y_{t+1})

which carries the intuition that the regret comes from a combination of the “distance” of our initial solution from the offline optimum and of the “stability” of the algorithm, that is, the “distance” between consecutive soltuions. Nicely, the above bound measures both quantities using the same “distance” function.

Continue reading