論文の概要: Universal Hardness From Masking Channels
- arxiv url: http://arxiv.org/abs/2611.05296v1
- Date: Tue, 03 Nov 2026 18:08:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 13:08:09.111475
- Title: Universal Hardness From Masking Channels
- Title（参考訳）: マスキングチャンネルからのユニバーサルハーネス
- Abstract要約: ブール関数の計算における平均ケースの複雑さについて、祝福されたハードコア補題の一般化を証明した。
我々は、多くの自然な硬さの概念に同時に適用できる普遍的なマスキングチャネルを構築した。
機械学習のMaxEntアルゴリズムを用いて擬似エントロピーの厳密なキャラクタリゼーションを提案する。
- 参考スコア（独自算出の注目度）: 5.350879120027826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
- Abstract（参考訳）: ブール関数の計算における平均ケースの複雑さについて、祝福されたハードコア補題の広い学習理論の一般化を証明した(Impagliazzo, 1995)。
我々の出発点は、関数の入力分布を再重み付けする古典的なハードコア測度は、関数の出力分布にランダム性を注入する入力依存マスキングチャネルと同値である、という観察である。
測定値の密度のアナログは、チャネルの忠実さである。
この観点から、凸双対性(convex duality)を介して忠実性(fidelity)の正しい概念を選択することにより、非ブール関数$f$と古典的な0-1損失以外の幅広い硬さの概念を証明できるような、硬さの証明のための一般的なフレームワークを開発する。
コンベックス損失を最小限に抑えるために$f$をクラス$\mathcal{C}$で学習することの難しさは、マスキングチャネルが$f$の構造を隠すために追加する最小のノイズを計測し、$\mathcal{C}$-indistinguishableをランダムノイズと区別できる最大忠実度によって強く特徴付けられる。
我々のフレームワークを用いて、ハードコア補題の多クラス一般化を導出し、より大きなアルファベットに進む際の予期せぬ微妙さを明らかにした。
我々は、多くの自然な硬さの概念に同時に適用できる普遍的なマスキングチャネルを構築した。
このようなチャネルはOmnipredictorと二重であり、同時に複数の損失を最適化する(Gopalan, Kalai, Reingold, Sharan, Wieder, 2022)。
疑似エントロピーを用いてマスキングチャネルとハードコア補題の一般化の対称性を観察する。
機械学習のMaxEntアルゴリズムを用いて擬似エントロピーの厳密なキャラクタリゼーションを提案する。
長い研究の行は、学習と硬さは同じコインの2つの側面であり、我々の枠組みは凸双対性を通してこの原理の鮮明で一般的な定式化を与える。
関連論文リスト
- Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness [0.42970700836450476]
両保証の対数深度は同じアンサンブルで十分であることを示す。
我々は、4つのネイティブ層にハードインスタンスを構築し、それらを典型的なスケジュールに埋め込み、合理的な線形プログラムデコーダを用いてケイリーパスに沿って補間する。
論文 参考訳（メタデータ） (2026-09-30T16:35:44Z) - Classical Capacity and Entanglement Cost of the Amplitude Damping Channel [9.69605985355166]
このクラスは、クラウスランクの全てのqubit-to-qubitチャネルを少なくとも2つ含んでいる。
振幅減衰では、正確な有限ブロックホレボ欠損を導出し、$p1$の唯一の最適平均入力を同定し、均一な形成境界に達する2進クラウス表現を構築する。
論文 参考訳（メタデータ） (2026-09-23T15:19:12Z) - Locally Confident, Globally Stuck: The Quality-Exploration Dilemma in Diffusion Language Models [52.61023005303122]
低信頼度再マッシングは、誘導配列分布のエントロピーを制約しながら、品質のプロキシを改善することを示す。
我々は,デコード時に,この分布をほぼ対象とする簡易なインディペンデント・ハスティングス・サンプリング器を開発した。
論文 参考訳（メタデータ） (2026-04-01T02:01:30Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free [49.34727933066799]
マスク付き離散拡散(マスク付き離散拡散)は、トークンが識別される前に特別なマスクシンボルによって劣化するテキスト生成のフレキシブルパラダイムである。
その結果,Eulerサンプルは,$tildeO(d2epsilon-3/2)$離散スコア評価で,総変量(TV)の$epsilon$-精度を達成できることが判明した。
そこで我々は,有界スコアの仮定を取り除き,偏りのない離散スコア近似を保ったMask-Aware Truncated Uniformization (MATU) アプローチを提案する。
論文 参考訳（メタデータ） (2025-09-26T03:50:17Z) - Foundations of Top-$k$ Decoding For Language Models [19.73575905188064]
我々は、トップ$kの復号化を説明・一般化する理論的枠組みを開発する。
大規模な分岐に対して効率的に最適化する方法を示す。
論文 参考訳（メタデータ） (2025-05-25T23:46:34Z) - Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [49.126395046088014]
有限出力であるが任意の入力アルファベットを持つメモリレスチャネルに対する一般性の問題を考える。
主な発見は、メッセージの最大長が$R,nlog n$、ブロック長$n$と超直線的にスケールすることである。
出力分布のペアの信頼性を保証し、DIコードを構築するのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-14T11:59:30Z) - A duality framework for analyzing random feature and two-layer neural networks [7.400520323325074]
我々は$mathcalF_p,pi$およびBarron空間内の関数の学習問題を考察する。
近似と推定の二重同値を確立し、それを用いて先行する関数空間の学習を研究する。
論文 参考訳（メタデータ） (2023-05-09T17:41:50Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Masksembles for Uncertainty Estimation [60.400102501013784]
ディープニューラルネットワークは、その強みを巧みに実証しているが、その予測の信頼性を推定することは依然として困難である。
深層アンサンブルは不確かさを推定する最良の方法の1つと考えられているが、訓練や評価は非常に高価である。
mc-dropoutも人気の高い代替品で、安価だが信頼性も低い。
論文 参考訳（メタデータ） (2020-12-15T14:39:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。