Computer Science PhD student & Knight-Hennessy scholar at @stanford.edu.
Prev.: @ox.ac.uk with @rhodeshouse.ox.ac.uk, @harvard.edu '23, @maxplanck.de, @ethz.ch, IBM Research.
Theory CS for Trustworthy AI
https://silviacasacuberta.com
Sílvia Casacuberta
Loading...
...other multigroup fairness notions) has recently been shown to be powerful in other settings in TCS, including in omniprediction (arxiv.org/abs/2501.17205), in pseudoentropy characterizations (arxiv.org/abs/2507.05972), and in robust learning (arxiv.org/abs/2604.02555).
They shed light on why multiaccuracy and global calibration, although not particularly powerful by themselves, together yield considerably stronger notions. Moreover, the primitive of calibrated multiaccuracy (which is quite cheap and easy to obtain, compared to...
In this new paper, we show that we can obtain hardcore measures with optimal density from the weaker notion of calibrated multiaccuracy.
In both the learning and complexity settings, our proofs demonstrate the complementary roles played by multiaccuracy and calibration.
In a previous work with Cynthia Dwork and Salil Vadhan (arxiv.org/abs/2312.17223, presented at STOC 2024), we showed that from multicalibration we get a stronger and more general Hardcore Lemma, from which we derive the original Hardcore Lemma with optimal density 2*delta.
A similar picture emerges in the setting of complexity theory. We know, from the work of Trevisan, Tulsiani, and Vadhan, that from the Regularity Lemma (= multiaccuracy theorem) we can prove Impagliazzo’s Hardcore Lemma, albeit with suboptimal density delta.
That is, in certain cases there is no way to post-process a multiaccurate predictor to get a weak learner, even assuming the best hypothesis in C has high correlation. However, when we also require p to be calibrated, we recover not just weak, but strong agnostic learning.
We show that for many classes C we can construct a predictor p that is perfectly C-multiaccurate, yet p is completely uncorrelated with the labels (even though some concepts in C do have high correlation with the labels).
We know that we can construct multiaccurate and multicalibrated predictors from weak agnostic learning, and also that a C-multicalibrated predictor is a strong agnostic learner for the class C. But what learning guarantees does multiaccuracy (= computational indistinguishability) offer?
If you would like to know more, here is our recorded talk for FOCS: youtube.com/watch?v=qm3R....
For an expository presentation of our results, see: ora.ox.ac.uk/objects/uuid....
It was great to attend @forcconf.bsky.social at Harvard this past week!
I gave a talk on our paper “How Global Calibration Strengthens Multiaccuracy” (joint work with Parikshit Gopalan, Varun Kanade, and Omer Reingold), which we presented at FOCS this past December.
arxiv.org/abs/2504.15206
