Metraipolis › archive › dc_bee948e9cbe9

Universal Hardness From Masking Channels — arXiv:2611.05296

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05296
License (as archived)
CC0-1.0
Archived
2026-11-04T18:55:37.914Z
SHA-256 of the archived text
54e9ff10cf61c73ed4590a7d90aaa0a1ce7f6cd5c019bb6135a56698a034e916
Stable URL of this page
https://metraipolis.com/documento/dc_bee948e9cbe9

How to cite

Universal Hardness From Masking Channels — arXiv:2611.05296 — arXiv (en), https://arxiv.org/abs/2611.05296 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bee948e9cbe9 (Metraipolis archive dc_bee948e9cbe9, sha256 54e9ff10cf61c73ed4590a7d90aaa0a1ce7f6cd5c019bb6135a56698a034e916)
BibTeX
@misc{dcbee948e9cbe9,
  title = {Universal Hardness From Masking Channels — arXiv:2611.05296},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05296},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bee948e9cbe9; sha256 54e9ff10cf61c73ed4590a7d90aaa0a1ce7f6cd5c019bb6135a56698a034e916},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05296. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.05296 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:35:37.495Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).