# Online Optimization Post 7: Matrix Multiplicative Weights Update

This is the seventh in a series of posts on online optimization, where we alternate one post explaining a result from the theory of online convex optimization and one post explaining an “application” in computational complexity or combinatorics. The first two posts were about the technique of Multiplicative Weights Updates and its application to “derandomizing” probabilistic arguments based on combining a Chernoff bound and a union bound. The third and fourth post were about the Follow-the-Regularized-Leader framework, which unifies multiplicative weights and gradient descent, and a “gradient descent view” of the Frieze-Kannan Weak Regularity Lemma. The fifth and sixth post were about the constrained version of the Follow-the-Regularized-Leader framework, and the Impagliazzo Hard-Core Set Lemma. Today we shall see the technique of Matrix Multiplicative Weights Updates.

1. Matrix Multiplicative Weights Update

In this post we consider the following generalization, introduced and studied by Arora and Kale, of the “learning from expert advice” setting and the multiplicative weights update method. In the “experts” model, we have a repeated game in which, at each time step ${t}$, we have the option of following the advice of one of ${n}$ experts; if we follow the advice of expert ${i}$ at time ${t}$, we incur a loss of ${\ell_t (i)}$, which is unknown to us (although, at time ${t}$ we know the loss functions ${\ell_1(\cdot),\ldots,\ell_{t-1}(\cdot)}$). We are allowed to choose a probabilistic strategy, whereby we follow the advice of expert ${i}$ with probability ${x_t(i)}$, so that our expected loss at time ${t}$ is ${\sum_{i=1}^n x_t(i) \ell_t(i)}$.

In the matrix version, instead of choosing an expert ${i}$ we are allowed to choose a unit ${n}$-dimensional vector ${v_t}$, and the loss incurred in choosing the vector ${v_t}$ is ${v_t ^T L_t v_t}$, where ${L_t}$ is an unknown symmetric ${n\times n}$ matrix. We are also allowed to choose a probabilistic strategy, so that with probability ${x_t(j)}$ we choose the unit vector ${v_t^{(j)}}$, and we incur the expected loss

$\displaystyle \sum_j x_t (j) \cdot (v_t^{(j)})^T L_t v_t^{(j)}$

# Postdoc Positions

The call is out for two postdoctoral positions at Bocconi to work in my group (see below for how to apply). If you are interested and you have any questions, feel free to email me (L.Trevisan at Unibocconi dot it)

The negotiable start date is September 1st, 2022. Each position is for one year, renewable for a second. The positions offer an internationally competitive salary (up to 65,000 Euro per year, tax-free, plus relocation assistance and travel allowance), in a wonderful location that, at long last, is back to more or less normal life. The application deadline is December 17, 2021.

Among the topics that I am interested in are spectral graph theory, average-case complexity, “applications” of semidefinite programming, random processes on networks, approximation algorithms, pseudorandomness and combinatorial constructions.

Bocconi Computer Science is building up a theory group: besides me, we have Alon Rosen, Marek Elias, a tenured person that will join next Fall, and more hires are on the horizon. Now that traveling is ok again, and considering that Alon and I both have ERC grants, we should expect a big stream of theory visitors coming and going through Bocconi from week-long visits to semester or year long sabbaticals.

To apply, go to https://www.unibocconi.eu/faculty-postdoc and look for the position advertised as “BIDSA Informatics”, which looks like this:

and click on “apply online”. Currently it is the second position from the top in the list

# Online Optimization Post 6: The Impagliazzo Hard-Core Set Lemma

(This is the sixth in a series of posts on online optimization techniques and their “applications” to complexity theory, combinatorics and pseudorandomness. The plan for this series of posts is to alternate one post explaining a result from the theory of online convex optimization and one post explaining an “application.” The first two posts were about the technique of multiplicative weight updates and its application to “derandomizing” probabilistic arguments based on combining a Chernoff bound and a union bound. The third and fourth post were about the Follow-the-Regularized-Leader framework, and how it unifies multiplicative weights and gradient descent, and a “gradient descent view” of the Frieze-Kannan Weak Regularity Lemma. The fifth post was about the constrained version of the Follow-the-Regularized-Leader framework, and today we shall see how to apply that to a proof of the Impagliazzo Hard-Core Lemma.)

# The Khot-Naor Approximation Algorithm for 3-XOR

Today I would like to discuss the Khot-Naor approximation algorithm for the 3-XOR problem, and an open question related to it.

# ARV on Abelian Cayley Graphs

Continuing from the previous post, we are going to prove the following result: let ${G}$ be a ${d}$-regular Cayley graph of an Abelian group, ${\phi(G)}$ be the normalized edge expansion of ${G}$, ${ARV(G)}$ be the value of the ARV semidefinite programming relaxation of sparsest cut on ${G}$ (we will define it below), and ${\lambda_2(G)}$ be the second smallest normalized Laplacian eigenvalue of ${G}$. Then we have

$\displaystyle \lambda_2 (G) \leq O(d) \cdot (ARV (G))^2 \ \ \ \ \ (1)$

which, together with the fact that ${ARV(G) \leq 2 \phi(G)}$ and ${\phi(G) \leq \sqrt{2 \lambda_2}}$, implies the Buser inequality

$\displaystyle \lambda_2 (G) \leq O(d) \cdot \phi^2 (G) \ \ \ \ \ (2)$

and the approximation bound

$\displaystyle \phi(G) \leq O(\sqrt d) \cdot ARV(G) \ \ \ \ \ (3)$

The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).

# Buser Inequalities in Graphs

As life is tentatively returning to normal, I would like to once again post technical material here. Before returning to online optimization, I would like to start with something from 2015 that we never wrote up properly, that has to do with graph curvature and with Buser inequalities in graphs.

# A Couple of Announcements

In the second week of July, 2022, there will be a summer school on algorithmic fairness at IPAM, on the UCLA campus, with Cynthia Dwork and Guy Rothblum among the lecturers. Applications (see the above link) are due by March 11, 2022.

We will soon put up a call for nominations for the test of time award to be given at FOCS 2021 (which will take place in Boulder, Colorado, in early 2022). There are three award categories, recognizing, respectively, papers from FOCS 2011, FOCS 2001, and FOCS 1991. In each category, it is also possible to nominate older papers, up to four years before the target conference. For example, for the thirty-year category, it is possible to nominate papers from FOCS 1987, FOCS 1988, FOCS 1989, FOCS 1990, in addition to the target conference FOCS 1991.

Nominations should be sent by October 31, 2021 to focs.tot.2021@gmail.com with a subject line of “FOCS Test of Time Award”. Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.

In the second week of November, 2021, the Simons Institute will host a workshop on using cryptographic assumptions to prove average-case hardness of problems in high-dimensional statistics. This is such a new topic that the goal of the workshop will be more to explore new directions than to review known results, and we (think that we have) already invited all the authors of recent published work of this type. If you have proved results of this type, and you have not been invited (perhaps because your results are still unpublished?) and you would like to participate in the workshop, there is still space in the schedule so feel free to contact me or one of the other organizers. For both speakers and attendees, physical participation is preferred, but remote participation will be possible.

# The Third Annual “Why am I in Italy and you are not?” post

I moved back to Italy exactly two years ago. I was looking for some change and for new challenges and, man, talk about being careful what you wish for!

Last year was characterized by a sudden acceleration of Bocconi’s plans to develop a computer science group. From planning for a slow growth of a couple of people a year until, in 5-7 years, we could have the basis to create a new department, it was decided that a new computer science department would start operating next year — perhaps as soon as February 2022, but definitely, or at least to the extent that one can make definite plans in these crazy times, by September 2022.

Consequently, we went on a hiring spree that was surprisingly successful. Five computer scientists and four statistical physicists have accepted our offers and are coming between now and next summer. In computer science, Andrea Celli (who won the NeurIPS best paper award last year) and Marek Elias started today. Andrea, who is coming from Facebook London, works in algorithmic game theory, and Marek, who is coming TU Eindhoven, works in optimization. Within the next couple of weeks, or as soon as his visa issues are sorted out, Alon Rosen will join us from IDC Herzliya as a full professor. Readers of in theory may know Alon from his work on lattice-based cryptography, or his work on zero-knowledge, or perhaps his work on the cryptographic hardness of finding Nash equilibria. Two other computer science tenured faculty members are going to come, respectively, in February and September 2022, but I am not sure if their moves are public yet.

Meanwhile, I have been under-spending my ERC grant, but perhaps this is going to change and some of my readers will help me out.

If you are interested in coming to Milan for a post-doc, do get in touch with me. A call will be out in a month or so.

After twenty years in Northern California, I am still readjusting to seasonal weather. September is among Milan’s best months: the oppressive heat of the summer gives way to comfortable days and cool nights, but the days are still bright and sunny. Currently, there is no quarantine requirement or other travel restrictions for fully vaccinated international travellers. If you want to visit, this might be your best chance until Spring Break (last year we had a semi-lockdown from late October until after New Year, which might very well happen again; January and February are not Milan’s best months; March features spectacular cherry blossoms, and it is again an ok time to visit).

# Benny Chor

I just heard that Benny Chor died this morning. Chor did very important work on computational biology and distributed algorithms, but I (and probably many of my readers) know him primarily for his work on cryptography, for his work on randomness extraction and for introducing the notion of private information retrieval.

I only met him once, at the event for Oded Goldreich’s 60th birthday. On the occasion, he gave a talk on the Chor-Goldreich paper, which introduced the problem of randomness extraction from independent sources, and which introduced min-entropy as the right parameter by which to quantify the randomness content of random sources. He did so using the original slides used for the FOCS 1985 talk.

I took a picture during the talk, which I posted online, and later he sent me an email asking for the original. Sadly, this was the totality of our correspondence. I heard that besides being a brilliant and generous researchers, he was a very playful, likeable and nice person. My thoughts are with his family and his friends.