从掩码信道出发统一刻画学习难度的新理论框架
Universal Hardness From Masking Channels
一页理论论文，把 1995 年的 hardcore lemma 推广到任意凸损失和多类分类，还和 omnipredictors 对上了，做学习理论的朋友可以看看。
arXiv 论文将 Impagliazzo 在 1995 年提出的 hardcore lemma 推广为更一般的学习理论框架。作者把经典 hardcore measure 等价看作一种输入相关的掩码信道（masking channel），信道的 fidelity 对应测度的密度。该框架通过凸对偶，可以刻画非布尔函数在多种凸损失下用函数类 C 学习的难度，并给出多类分类版的 hardcore lemma。论文还证明掩码信道与 Gopalan 等人 2022 年提出的 omnipredictors 互为对偶，并用 MaxEnt 算法给出伪熵的紧致刻画。
Universal Hardness From Masking Channels
We prove a broad learning-theoretic generalization of the celebrated hardcore lemma concerning the average-case complexity of computing a Boolean function (Impagliazzo, 1995). Our starting point is the observation that the classic notion of a hardcore measure, which reweights a function's input distribution, is equivalent to an input-dependent masking channel that injects randomness into the function's output distribution until it appears fully pseudorandom. The analogue of density of the measure is the fidelity of the channel. From this viewpoint, we develop a general framework for certifying hardness that allows for non-Boolean functions $f$ and a wide range of notions of hardness besides the classic 0-1 loss, by choosing the right notion of fidelity via convex duality. We show the difficulty of learning $f$ using a class $\mathcal{C}$ to minimize a convex loss is tightly characterized by the maximum fidelity possible for a masking channel, which measures the least amount of noise the channel must add to hide the structure of $f$ and make it $\mathcal{C}$-indistinguishable from random noise. Using our framework, we derive a number of multiclass generalizations of the hardcore lemma, and reveal some unexpected subtleties in going to larger alphabets. We construct a universal masking channel that applies to many natural notions of hardness simultaneously. Such channels are dual to omnipredictors, which optimize multiple losses at once (Gopalan, Kalai, Reingold, Sharan, and Wieder, 2022). We observe a symmetry between masking channels and generalizations of the hardcore lemma using pseudoentropy. We present a tight characterization of pseudoentropy using the MaxEnt algorithm from machine learning. A long line of research has shown that learning and hardness are two sides of the same coin; our framework gives a crisp and general formulation of this principle via convex duality.