論文の概要: A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners
- arxiv url: http://arxiv.org/abs/2610.28747v1
- Date: Tue, 20 Oct 2026 18:00:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-23 00:40:06.110428
- Title: A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners
- Title（参考訳）: 逆ゴールド理論:基板境界を持つコントラスト学習者による正値同定
- Abstract要約: ゴールドの定理は、学習者が正の表現だけで超有限クラスの任意の言語を識別できないことを示している。
我々は異なる形状の肯定的な結果を証明する。
我々は、置換可能な文脈自由言語 citepclarkeyraud2007 の仮説と準正則クラス citepheinz2010,hayashikamigaito2025 の仮説をインスタンス化する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Gold's theorem shows that no learner can identify an arbitrary language in a superfinite class from positive presentations alone. We prove a positive result of a different shape. Fix an innate \emph{recursive contrast operator} $R$ mapping any string to a finite set of structurally bounded perturbations of it, and a discriminative scorer of bounded capacity trained by InfoNCE-style contrastive estimation \citep{vandenoord2018,macollins2018} on self-generated perturbations. Under a faithfulness condition relating operator, scorer, and target, the trained scorer achieves \emph{PAC conditional identification} from positive data alone: with high probability it ranks all but an $\varepsilon$-fraction of positives above every out-of-language perturbation in their own orbit, with sample complexity polynomial in the capacity, the orbit size, the score bound, and $1/\varepsilon$. The negatives are constructed by the learner, not supplied by an oracle, and no global normalizing constant over strings is ever computed. The misranking bound follows from the geometry of the contrastive loss---per-example loss floors plus a definite loss increment under misranking---yielding an $\varepsilon^{-2}$ rate, together with an explicit approximation gap that quantifies the cost of in-language (``colliding'') perturbations and vanishes for orbit-pure operators. The ranking guarantee lifts to a global membership classifier under a margin condition, and the same operator composed with the learned scorer is a normalization-free Metropolis--Hastings generator. We instantiate the hypotheses for substitutable context-free languages \citep{clarkeyraud2007} and the subregular classes \citep{heinz2010,hayashikamigaito2025}, and state an open conjecture locating the construction in the mildly context-sensitive hierarchy.
- Abstract（参考訳）: ゴールドの定理は、学習者が正の表現だけで超有限クラスの任意の言語を識別できないことを示している。
我々は異なる形状の肯定的な結果を証明する。
固有な \emph{recursive contrast operator} $R$ 任意の文字列をその構造的有界摂動の有限集合にマッピングし、InfoNCE スタイルのコントラスト推定 \citep{vandenoord2018,macollins2018} によって訓練された有界容量の判別スコアラを自己生成摂動にマッピングする。
トレーニングされたスコアラーは正のデータだけで「emph{PAC 条件同定」を達成し、高い確率では、自身の軌道上のすべての言語外摂動の上の正値の$-fraction(英語版)を除いて、容量、軌道サイズ、スコア境界、および1/\varepsilon$(英語版)を除く全ての値にランク付けする。
負は学習者によって構成され、オラクルによって供給されず、文字列上でのグローバルな正規化定数は計算されない。
間違った階数境界は、対照的な損失の幾何学、-例の損失フロアと、間違った階数の下での明確な損失増加、---$\varepsilon^{-2}$レートの収差と、言語内摂動のコストを定量化する明示的な近似差(`colliding'')と、軌道-純粋作用素の消滅から導かれる。
ランキング保証は、マージン条件下でグローバルメンバシップ分類器にリフトし、学習したスコアラーで構成された同じオペレータは、正規化不要のメトロポリス−ハスティングスジェネレータである。
我々は、置換可能な文脈自由言語 \citep{clarkeyraud2007} と部分正則クラス \citep{heinz2010,hayashikamigaito2025} の仮説をインスタンス化し、軽度に文脈に敏感な階層の構造を示すオープン予想を述べる。
関連論文リスト
- On the tradeoff between robustness and geometric accuracy in adversarial training [0.602178723698266]
我々は、ロバストな分類器が、基礎となるベイズ分類器の規則性に応じて、少なくとも$O(sqrtvarepsilon)$または$O(varepsilon)$の精度で犠牲になることを示す。
この結果はユークリッド空間上の任意のノルムによって決定される逆数と、無限のデータ設定と有限データ設定の両方に適用される。
論文 参考訳（メタデータ） (2026-10-16T05:27:47Z) - Spectral Indistinguishability and Learning-Curve Identifiability in Quadratic Networks [0.16921396880325776]
中心2次ネットワークにおけるスペクトル要約とスカラー学習曲線について検討する。
非ゼロサイクル不変な選択された一般教師の場合、行列乗法を保たないため、その分解された損失曲線が異なる。
固定次元と無秩序な教師和に対して、次元最小の正確な観測は、一般的な局所的な局所的な回復を与える。
論文 参考訳（メタデータ） (2026-10-14T16:01:20Z) - The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。
ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。
我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
論文 参考訳（メタデータ） (2026-05-28T09:12:20Z) - Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
自己正規化マルティンガレのスケール不変上界が可能であることを示す。
通常の正規化ペナルティを含まない自己正規化濃度不等式を導出する。
論文 参考訳（メタデータ） (2026-05-02T22:39:00Z) - Exact Structural Abstraction and Tractability Limits [0.0]
正確な正確性は、誘導されたクラス $s sim_R simation' iff MathrmAdm_R(s)$ にのみ依存する。
決定、探索、近似、統計的、ランダム化された地平線、分布保証は全て同じ商-回復問題に還元される。
論文 参考訳（メタデータ） (2026-04-08T17:59:47Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳（メタデータ） (2026-02-19T17:21:15Z) - Harmful Overfitting in Sobolev Spaces [49.47221415754556]
ソボレフ空間$Wk, p(mathbbRd)$における関数の一般化挙動を、ノイズの多いトレーニングデータセットに完全に適合するものとして研究する。
約ノルム最小化補間器は、滑らかさバイアスによって選択される正準解であり、有害なオーバーフィッティングを示す。
我々の証明では,ソボレフの不等式を用いたトレーニングデータの有害な近傍を同定する幾何学的議論を用いている。
論文 参考訳（メタデータ） (2026-01-31T17:40:56Z) - Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
有限状態マルコフ鎖を$n$状態と遷移行列$P$で研究する。
すべての非退化モードが実周辺不変部分空間 $mathcalK(P)$ によってキャプチャされ、商空間 $mathbbRn/mathcalK(P) 上の誘導作用素が厳密に収縮し、ユニークな商解が得られることを示す。
論文 参考訳（メタデータ） (2026-01-31T02:57:01Z) - Transformer Injectivity & Geometric Robustness - Analytic Margins and Bi-Lipschitz Uniformity of Sequence-Level Hidden States [0.0]
離散的プロンプトから終点隠れ状態への写像は、有限プロンプト集合に対して一般射影的であることを示す。
本研究では, 層間, シーケンス長, モデルスケール, 8ビットおよび4ビットのアクティベーション量子化について検討した。
論文 参考訳（メタデータ） (2025-11-17T19:39:15Z) - Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。