Online Optimization Post 0: Definitions

Online convex optimization deals with the following setup: we want to design an algorithm that, at each discrete time step {t=1,2,\ldots}, comes up with a solution {x_t \in K}, where {K} is a certain convex set of feasible solution. After the algorithm has selected its solution {x_t}, a convex cost function {f_t : K \rightarrow {\mathbb R}}, coming from a known restricted set of admissible cost functions {{\cal F}}, is revealed, and the algorithm pays the loss {f_t (x_t)}.

Again, the algorithm has to come up with a solution without knowing what cost functions it is supposed to be optimizing. Furthermore, we will think of the sequence of cost functions {f_1,f_2, \ldots,f_t,\ldots} not as being fixed in advanced and unknown to the algorithm, but as being dynamically generated by an adversary, after seeing the solutions provided by the algorithm. (This resilience to adaptive adversaries will be important in most of the applications.)

The offline optimum after {T} steps is the total cost that the best possible fixed solution would have incurred when evaluated against the cost functions seen by the algorithm, that is, it is a solution to

\displaystyle  \min_{x\in K} \ \ \sum_{t=1}^T f_t (x)

The regret after {T} steps is the difference between the loss suffered by the algorithm and the offline optimum, that is,

\displaystyle  {\rm Regret}_T = \sum_{t=1}^T f_t (x_t) - \min_{x\in K} \ \ \sum_{t=1}^T f_t (x)

The remarkable results that we will review give algorithms that achieve regret

\displaystyle  {\rm Regret}_T \leq O_{K, {\cal F}} (\sqrt T)

that is, for fixed {K} and {{\cal F}}, the regret-per-time-step goes to zero with the number of steps, as {O\left( \frac 1 {\sqrt T} \right)}. It is intuitive that our bounds will have to depend on how big is the “diameter” of {K} and how large is the “magnitude” and “smoothness” of the functions {f\in {\cal F}}, but depending on how we choose to formalize these quantities we will be led to define different algorithms.

Advertisements

Online Optimization for Complexity Theorists

Last year I took some time off to study online convex optimization in some detail. The reason for doing that was similar to the reason why at some point I took time off to study spectral graph theory: it was coming up in several papers that I wanted to understand, and I felt that I was missing out by not mastering an important tool. In particular, I wanted to understand:

  1. The Barak-Hardt-Kale proof of the Impagliazzo hard-core lemma.
  2. The online convex optimization viewpoint on the Frieze-Kannan weak regularity lemma, on the dense model theorem of (RTTV), and on the abstract weak regularity lemma of (TTV) that were described to me by Madhur Tulsiani a few years ago. Furthermore, I wanted to see if Russel Impagliazzo’s subsequent improvements to the dense model theorem and to the abstract weak regularity lemma could be recovered from this point of view.
  3. The Arora-Kale algorithms for semidefinite programming, including their nearly linear-time algorithm for approximating the Goemans-Williamson relaxation of Max Cut.
  4. The meaning of the sentence “multiplicative weights and gradient descent are both special cases of follow-the-regularized-leader, using negative entropy and {\ell_2^2} as regularizer, respectively.”
  5. The AllenZhu-Liao-Orecchia online optimization proof of the Batson-Spielman-Srivastava sparsification result.

I am happy to say that, except for the “furthermore” part of (2), I achieved my goals. To digest this material a bit better, I came up with the rather ambitious plan of writing a series of posts, in which I would alternate between (i) explaining a notion or theorem from online convex optimization (at a level that someone learning about optimization or machine learning might find useful) and (ii) explaining a complexity-theoretic application. Now that a very intense Spring semester is almost over, I plan to get started on this plan, although it is not clear that I will see it through the end. So stay tuned for the forthcoming first episode, which will be about the good old multiplicative weights algorithm.

The Early Years of Computing in Italy

Here are in theory‘s first ever book reviews! The books are

Giorgio Garuzzo
Quando in Italia si facevano i computer
Available for free at Amazon.com and Amazon.it.

Giorgio Ausiello
The Making of a New Science
Available from Springer, as a DRM-free PDF through your academic library.

Both books talk about the early years of computing in Italy, on the industrial and academic side, respectively. They briefly intersect with the story of Olivetti’s Elea computer.

Continue reading

Knuth Prize to Avi Wigderson

avi

Congratulations to the Knuth prize committee chaired by Avrim Blum for the excellent choice of awarding the 2019 Knuth prize to Avi Wigderson.

Avi has worked on all aspects of computational complexity theory, and he has had a transformative influence on the way theoretical computer science relates to pure mathematics. I will not repeat what I wrote about his work on the occasion of his 60th birthday here and here. Long-term readers of in theory will remember that I consider him as one of the saints of computational complexity.

The organizers of the coming FOCS would like me to remind you that the deadline is this Friday, and that someone, for some reason, has set up a fake submission site (on the domain aconf dot org) but the true submission site (that, to be honest, looks less legit than the fake one) is at focs19.cs.utexas.edu.

Also, the deadline to submit nominations for the inaugural FOCS test of time award is in three weeks. There will be three awards, one for papers appeared in FOCS 1985-89, one for FOCS 1995-99 and one for FOCS 2005-09.

On an unrelated note, GMW appeared in FOCS 1986 and the Nisan-Wigderson “Hardness versus randomness” paper appeared in FOCS 1988.

And now for something completely different

After 22 years in the United States, 19 of which spent in the San Francisco Bay Area, this Summer I will move to Milan to take a job at Bocconi University.

Like a certain well-known Bay Area institution, Bocconi is a private university that was endowed by a rich merchant in memory of his dead son. Initially characterized by an exclusive focus on law, economics and business, it has had for a while a high domestic recognition for the quality of teaching and, more recently, a good international profile both in teaching and research. Despite its small size, compared to Italy’s giant public universities, in 2017 Bocconi was the Italian university which had received the most ERC grants during the first ten years of existence of the European Research Council (in second place was my Alma Mater, the Sapienza University of Rome, which has about nine times more professors) (source).

About three years ago, Bocconi started planning for a move in the space of computing, in the context of their existing efforts in data science. As a first step, they recruited Riccardo Zecchina. You may remember Riccardo from his work providing a non-rigorous calculation of the threshold of random 3-SAT, his work on the “survey propagation” algorithm for SAT and other constraint satisfaction problems, as well as other work that brought statistical physics techniques to computer science. Currently, Riccardo and his group are doing very exciting work on the theory of deep learning.

Though I knew of his work, I had never met Riccardo until I attended a 2017 workshop at the Santa Fe Institute on “Thermodynamics and computation,” an invitation that I had accepted on whim, mostly based on the fact that I had never been to New Mexico and I had really liked Breaking Bad. Riccardo had just moved to Bocconi, he told me about their future plans, and he asked me if I was interested. I initially politely declined, but one thing led to another, and now here I am putting up my San Francisco house for sale.

Last August, as I was considering this move, I applied for an ERC grant from the European Union, and I just learned that the grant has been approved. This grant is approximately the same amount as the total of all the grants that I have received from the NSF over the past twenty years, and it will support several postdoc positions, as well as visitors ranging from people coming for a week to give a talk and meet with my group to a full-year sabbatical visit.

Although it’s a bit late for that, I am looking for postdocs starting as early as this September: if you are interested please contact me. The postdoc positions will pay a highly competitive salary, which will be free of Italian income tax (although American citizens will owe federal income tax to the IRS correction: American citizens would not owe anything to IRS either). As a person from Rome, I am not allowed to say good things about Milan or else I will have to return my Roman card (it’s kind of a NY versus LA thing), but I think that the allure of the city speaks for itself.

Likewise, if you are a senior researcher, and you have always wanted to visit me and work together on spectral methods, approximation algorithms, graph theory or graph algorithms, but you felt that Berkeley had insufficiently many Leonardo mural paintings and opera houses, and that it was too far from the Alps, then now you are in luck!

Tested by time

I was delighted (and not at all surprised) to hear that this year’s Turing Award will go to LeCun, Hinton, and Y. Bengio for their work on deep learning.

Like public-key cryptography, deep learning was ahead of its time when first studied, but, thanks to the pioneering efforts of its founders, it was ready to be used when the technology caught up.

Mathematical developments take a long time to mature, so it is essential that applied mathematical research be done ahead of the time of its application, that is, at a time when it is basic research. Maybe quantum computing will be the next example to teach this lesson.

By the way, this summer the Simons Institute will host a program on the foundations of deep learning, co-organized by Samy Bengio, Aleks Madry, Elchanan Mossel and Matus Telgarsky.

Sometimes, it is not just the practical applications of a mathematical advance that take time to develop: the same can be true even for its theoretical applications! Which brings me to the next announcement of this post, namely that the call for nominations for the FOCS test of time award is out. Nominations are due in about four weeks.

Average Case Complexity News

Greetings from Taiwan, a tropical country with democracy, free press, and rule of law, in which the trains run on time, and the food is awesome. Also people are friendly, drivers don’t honk, and the “close doors” buttons in elevators actually work. Talk about exceptionalism! On November 24, In Theory endorses voting No on 10, No on 11, No on 12, Yes on 13, Yes on 14 and Yes on 15.

More on Taiwan in a later post. Today I would like to give a couple of updates on the survey paper on average-case complexity theory that Andrej Bogdanov and I wrote in 2006: apologies to the readers for a number of missing references, and news on the front of worst-case to average-case reductions.

Continue reading

ERC vs NSF

The EU is often criticized for being a big, unwieldy bureaucracy. Here, however, are the review criteria for European Research Council proposals (from page 10 of this document):

Excellence is the sole criterion of evaluation

Here are the review criteria for the US National Science Foundation:

Reviewers evaluate all NSF proposals through the use of two National Science Board approved merit review criteria: Intellectual Merit and Broader Impacts, which are based upon Merit Review Principles. Reviewers are asked to consider five elements in the review for both criteria. For more information on merit review principles and criteria, see PAPPG Chapter III.A.

(If you are keeping track, that’s two criteria and ten principles)

Guest post by Chris Brzuska: LGBTQIA Meeting at Eurocrypt

[I was delighted to receive the following guest post by Chris Brzuska about a meeting that took place last week during Eurocrypt in Tel Aviv. This piece will also appear in Omer Reingold’s blog. Let me take this opportunity for a couple of shoutouts. Next week it’s going to be two years since Italy, last among Western European countries, has instituted same-sex civil unions (yay!) and the parties that opposed it now have an absolute majority after the last elections (boo!). The Berkeley EECS department has an LGBT+ graduate student organization called QiCSE that organizes a very visible breakfast meeting during the visit days for prospective grad students and regular meetings during the school year – as much as I value Berkeley exceptionalism, think about creating something like this in your own school. It would be great if there was a LGBT+ meeting at STOC this year; I am not going to STOC this year, but maybe someone else can take the lead. And now, on to Chris’s beautiful essay. Congratulations, Chris!. — Luca]

I gender-transitioned two years ago, and Eurocrypt 2018 in Tel-Aviv is the first major conference I attend since then. I am a bit nervous. How much time does it take for 400 people to update my name and pronouns to use “Chris” and he/him? Two years feels like an eternity to me, but surely, some people will not have heard about my gender-transition. I will need to come out to some people.

Coming-out is very empowering, but after two years and uncountable coming-outs, I really wish that everyone knows that I am trans and gay.

A gay friend of mine remarks that when being bisexual/lesbian/gay, coming out is really never over, and one needs to come out again and again, to each new person. And really, he says, there is rarely a good time to bring it up.

“How come you didn’t know I am lesbian/gay?”, I heard from several friends, in shock, worried I might have wrongly assumed they are heterosexual.

How many LGBTQIA people are in our communities? I know some LGBTQIA people in the community, but how many more are there, and how can I find them?

This simple question leads to something which would become more important to me than I expected initially.

In the rump session, I give a coming-out talk, combined with an announcement for an LGBTQIA cryptographers meeting during the rump session break ( https://eurocrypt.2018.rump.cr.yp.to/4f756d069387ee90de62454a828a3b9b.pdf).

Giving this talk in itself was very nice. I enjoyed sharing my happiness with the community, see my happiness reflected in other people’s eyes. I enjoyed the many positive comments I received during the hours and days that followed, and the recognition of daring to be visible.

During the break, I am excited and nervous. How many people will come to the meeting? And who? More than 10 people come, most of which I knew without knowing they are LGBTQIA. We walk into the room, one by one, each with light in our eyes. We came out to each other, all of us, in that moment. It’s intimate, moving, exciting. Coming out remains deeply personal. It can be daunting, even in a warm, progressive environment such as our research community and even to an LGBTQIA subgroup.

After the rump session, we go to the gay-lesbian bar Shpagat in Tel-Aviv, in happy excitement. We are the last customers that night. The next day, during the breaks, we often find ourselves with a majority of LGBTQIA people in a conversation, we sit next to each other during talks. Something important happened.

In light of our increased visibility (to each other and to the community at large), there were more opportunities for coming outs the next days (or so was my impression, although I am only conscious of 2 explicit cases…). It was very liberating for me to share many of the following conference moments with LGBTQIA cryptographers who would add additional views to a heterosexual, cissexual perspective, and who would help me explain the sensitive issue of coming out to other caring members of our research community.

The research community is my permanent country of residence, my frame of reference, the source of almost all my long-term friendships – and enfin, in this country, there live quite a few LGBTQIA people, and the research community encourages us and shares our happiness.

We are going to organize more LGBTQIA meetings alongside cryptography-related conferences. I hope, there will be more such meetings inside and outside of CS. And we look forward to see the number of LGBTQIA researchers (that we are aware of) grow.

If you are an LGBTQIA researcher who wants to get in touch with us more discretely than at a public meeting (to talk to one of us, e.g., in the beginning of your PhD etc.), you can send an eMail to queercrypt@gmail.com. You can also use that eMail address to join our mailing list (for event announcements) and/or our WhatsApp group (include your phone number if you want to join the WhatsApp group). While the group centers around cryptography-related events, the group is not limited to researchers in cryptography.