Recent advances in Regularity Lemmas(with and without calibration)

About

Regularity lemmas show that complex objects can be approximated by simple ones that are indistinguishable from them by a given class of tests. Originating in graph theory with the work of Szemerédi (1975) and of Frieze and Kannan (1999), they were brought to complexity theory by Trevisan, Tulsiani, and Vadhan (2009), and have since found many applications in various fields of theoretical computer science.

In recent years, a connection to algorithmic fairness, where this indistinguishability condition is known as multiaccuracy and its strengthening as multicalibration, has led to a surge of work on regularity lemmas. These results have clarified what can be achieved through multiaccuracy alone and what additional guarantees arise from different forms of calibration. They have also led to new connections and applications in complexity theory, cryptography, learning theory, information theory, and communication complexity, among other areas. This workshop brings together researchers working on these developments to discuss recent progress and open problems.

Program

1. 9:00 – 9:45am

   Princewill Okoroafor (Harvard University)

   The Sample Complexity of Multicalibration with an ERM Oracle

2. 9:45 – 10:30am

   Georgy Noarov (Institute for Advanced Study)

   Defensive Boosting for Online Probabilistic Forecasting

3. 10:30 – 11:00am
   Break
4. 11:00 – 11:45am

   Pranay Tankala (Harvard University)

   Agnostic Learning by Imitating

5. 11:45am – 12:30pm

   Konstantinos Stavropoulos (Institute for Advanced Study)

   Learning under Contamination and Distribution Shift: Sharper Bounds via Multiaccuracy

   Abstract

   Standard learning objectives can lead to suboptimal error guarantees when training data are adversarially corrupted or the test distribution differs from the training distribution. In this talk, I will discuss how multiaccuracy and related notions of regularity can be used to obtain sharper error guarantees in both settings.

   First, in the context of robust learning, I will describe how ideas from multiaccuracy, combined with no-regret optimization, lead to efficient algorithms achieving the information-theoretically optimal error of $\eta+\epsilon$ under an $\eta$-fraction of adversarial contamination, improving over the classical $2\eta+\epsilon$ bound.

   I will then turn to learning with distribution shift, where we introduce shift multiaccuracy as a new error benchmark. This notion yields sharper domain adaptation bounds and leads to a strengthened formulation of testable learning with distribution shift, establishing new connections to the computational and statistical complexity of agnostic learning.

6. 12:30 – 1:30pm
   Lunch
7. 1:30 – 2:15pm

   Cassandra Marcussen (Harvard University)

   Characterizing the Distinguishability of Product Distributions through Multicalibration

8. 2:15 – 3:00pm

   Lunjia Hu (Northeastern University)

   Generalized and Unified Equivalences between Hardness and Pseudoentropy

9. 3:00 – 3:30pm
   Break
10. 3:30 – 4:15pm

    Madhur Tulsiani (TTIC)

    List Decoding Expander-Based Codes up to Capacity in Near-Linear Time

11. 4:15 – 5:00pm

    Mark Bedaywi (UC Berkeley)

    Computationally Efficient Collaborative Communication via Regularity-Based Coarsening

    Abstract

    We will show that the existence of a short high-utility communication protocol already suffices for computationally efficient communication.

    In particular, in a game with $n$ possible observations and $m$ actions, for any achievable target utility $\alpha$, we give an algorithm with $\mathrm{poly}(n, m, 1/\epsilon)$ runtime that designs a protocol achieving utility at least $\alpha-\epsilon$ using only $2^{\mathcal O(CC_\alpha(G))}/\epsilon^2$ bits of communication. Here, $CC_\alpha(G)$ is the minimum number of bits used by any protocol, even a computationally inefficient one, to achieve utility $\alpha$.

    To do this, we generalize the weak regularity lemma and use it to show that for every communication game $G$, we can construct a game $\hat G$ that is a “coarsening” of the agents' observation spaces into constant-size partitions, such that $G$ and $\hat G$ are “indistinguishable” with respect to every short communication protocol.