🧩 📊 Alice and Bob are in trouble. They've been accused (wrongly, of course!) of stealing classified data, and as theorists they now have to prove they innocence and defend their honour: they've never used any data!

Help them! #WeaklyQuiz #TCSSky

1/

One hidden (?) gem: the XOR lemma for probability distributions, which gives a computationally efficient and cute way to "tensorize" total variation (TV) distances, the way just taking products doesn't.

Below, the "baby version" (for k=2 pairs) which implies the general case (k pairs) by induction.

It's the end of the semester! To celebrate that, one last* puzzle 🧩 for 2024: pick a permutation π of {1,2,...,n} uniformly at random, and let L(π) be the length of its longest increasing subsequence.

What is the expectation of L(π)? Is it O(1), Θ(log n), Θ(√n), Θ(n)—something else?

*maybe

There exists f:[0,1]→[0,1] strictly increasing, continuous function such that its derivative is 0 almost everywhere. https://www.jstor.org/stable/2978047?seq=1

We are on Bluesky as well! We will keep posting on both X and here.

Ge et al. show that they violate some basic axioms from social choice theory: Pareto optimality and pairwise majority consistency (true for any nondecreasing and convex loss function, not just Bradley-Terry-Luce). arxiv.org/abs/2405.14758 3/3.

This first is PRO, which post-trains an LLM directly via preference data. It uses general ranked lists rather than just pairwise, similar to the Plackett-Luce approach in the appendix of the DPO paper: arxiv.org/abs/2306.17492 2/3.

I've become quite interested in RLHF, DPO, and AI alignment: specifically on the foundations of the reward modelling they are based on.

What assumptions are we making and what are the consequences of making them?

Today's two papers identify some potential issues.

🧵 1/3.

I've created an initial Grumpy Machine Learners starter park. If you think you're grumpy and you "do machine learning", nominate yourself. If you're on the list, but don't think you are grumpy, then take a look in the mirror.

go.bsky.app/6ddpivr

This one is my favorite of the ones we found after VasE.

It's position paper arguing that social choice should be used to guide AI alignment by @conitzer.bsky.social @natolambert.bsky.social and others.

I agree! 👍

I'll share more papers on this topic next week.

arxiv.org/abs/2404.10271

Ok, time to start posting some actual AI things. 😅

This week I will tell you about several papers in the theme of social choice theory (and agent/model evals), starting with an old paper of ours that I am still excited about:

"Evaluating Agents using Social Choice Theory"

🧵 1/N