論文の概要: Toward a Tractability Frontier for Exact Relevance Certification

• arxiv url: http://arxiv.org/abs/2604.07349v1
• Date: Wed, 08 Apr 2026 17:59:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-09 17:30:51.673697
• Title: Toward a Tractability Frontier for Exact Relevance Certification
• Title（参考訳）: 実効性認定のためのトラクタビリティフロンティアを目指して
• Authors: Tristan Simas,
• Abstract要約: 厳密な関連性証明は、座標構造決定問題における最適動作を決定するのにどの座標が必要であるかを問う。 我々は、正確な証明の定理強制閉包法の下で、効率的にチェック可能な構造述語を不変にするための定理を証明する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exact relevance certification asks which coordinates are necessary to determine the optimal action in a coordinate-structured decision problem. The tractable families treated here admit a finite primitive basis, but optimizer-quotient realizability is maximal, so quotient shape alone cannot characterize the frontier. We prove a meta-impossibility theorem for efficiently checkable structural predicates invariant under the theorem-forced closure laws of exact certification. Structural convergence with zero-distortion summaries, quotient entropy bounds, and support-counting arguments explains why those closure laws are canonical. We establish the theorem by constructing same-orbit disagreements for four obstruction families, namely dominant-pair concentration, margin masking, ghost-action concentration, and additive/statewise offset concentration, using action-independent, pair-targeted affine witnesses. Consequently no correct tractability classifier on a closure-closed domain yields an exact characterization over these families. Here closure-orbit agreement is forced by correctness rather than assumed as an invariance axiom. The result therefore applies to correct classifiers on closure-closed domains, not only to classifiers presented through a designated admissibility package.
• Abstract（参考訳）: 厳密な関連性証明は、座標構造決定問題における最適動作を決定するのにどの座標が必要であるかを問う。 ここで扱われるトラクタブル族は有限原始基底を持つが、最適化子商化可能性は極大であり、商形だけではフロンティアを特徴づけることができない。 我々は、正確な証明の定理強化閉包法の下で、効率的にチェック可能な構造述語を不変にするためのメタ不変性定理を証明した。 ゼロ歪和、商エントロピー境界、サポートカウントの議論による構造収束は、これらの閉包法則が正準法則である理由を説明する。 我々は,4つの障害物群,すなわち支配ペア濃度,マージンマスキング,ゴーストアクション濃度,および加法/状態オフセット濃度の同軌道不一致を,アクションに依存しないペアターゲットアフィン証人を用いて構成することにより,定理を確立する。 したがって、閉包領域上の正しいトラクタビリティ分類器はこれらの族に対して正確な特徴を与える。 ここでの閉包軌道合意は、不変公理として仮定されるよりも正確性によって強制される。 この結果は、指定された許容パッケージを通じて提示される分類器だけでなく、クロージャ閉域上の正しい分類器にも適用される。

関連論文リスト

• The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability [0.0]
  有限状態コントローラの固定プローブ族は、観測履歴に擬似的に閉ループのワッサーシュタインを誘導し、家族内のコントローラが区別できないようなプローブ・エクサクタントなマージ履歴を誘導する。 時計を意識したプローブでは、エージェントの観察と行動にのみ依存する目的に対して、決定に十分である。 スケーラブルな決定論的定常実験は、小さな精度のケースで測定されたギャップで引き込み可能な粗大化を研究し、より大きなスケールで経験的に探索した。
  論文  参考訳（メタデータ） (2026-03-22T20:59:31Z)
• Operationally induced preferred basis in unitary quantum mechanics [0.0]
  検知器が一元的にモデル化された場合でも、好ましくも好ましくも、測定問題の定値出力面は持続する。 数学的タイプの変化は、グループベースの運動学からセットベースの数え上げまで、構造的に必要不可欠なインターフェイスである「カット」の中核を構成する。
  論文  参考訳（メタデータ） (2026-01-26T17:22:03Z)
• Transfinite Fixed Points in Alpay Algebra as Ordinal Game Equilibria in Dependent Type Theory [0.0]
  本稿では, 自己参照プロセスの安定な結果が, システムと環境との非有界リビジョン対話のユニークな平衡と同一であることを示すことによって, アルペイ・アルゲブラに寄与する。 固定点論、ゲームセマンティクス、順序解析、型理論から概念を統一することにより、この研究は無限の自己参照システムについての推論において、広くアクセス可能で形式的に厳密な基礎を確立する。
  論文  参考訳（メタデータ） (2025-07-25T13:12:55Z)
• On the Theory of Conditional Feature Alignment for Unsupervised Domain-Adaptive Counting [27.44207520673983]
  オブジェクトカウントモデルは、密度の多様性が異なるドメインにデプロイされるときに苦しむ。 条件付き特徴アライメントの理論的枠組みを提案し,簡単な実装を提供する。
  論文  参考訳（メタデータ） (2025-06-20T16:37:48Z)
• Latent Veracity Inference for Identifying Errors in Stepwise Reasoning [78.29317733206643]
  本稿では、精度割当てに対する離散探索アルゴリズムであるVeracity Search(VS)を紹介する。 その他の方法では、後続の精度値よりも後続の分布において難解な推論を行う。 VSを一般化し、新しいコンテキストで正確なゼロショットの精度推論を可能にする。
  論文  参考訳（メタデータ） (2025-05-17T04:16:36Z)
• When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
  カスケードは、推論コストをサンプル毎に適応的に変化させる古典的な戦略である。 deferralルールは、シーケンス内の次の分類子を呼び出すか、または予測を終了するかを決定する。 カスケードの構造に執着しているにもかかわらず、信頼に基づく推論は実際は極めてうまく機能することが多い。
  論文  参考訳（メタデータ） (2023-07-06T04:13:57Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• GroupifyVAE: from Group-based Definition to VAE-based Unsupervised Representation Disentanglement [91.9003001845855]
  他の誘導バイアスを導入しないと、VAEベースの非監視的非絡み合いは実現できない。 グループ理論に基づく定義から導かれる制約を非確率的帰納的バイアスとして活用し,vaeに基づく教師なし不連続に対処する。 提案手法の有効性を検証するために,5つのデータセット上で,vaeベースモデルが最も目立つ1800モデルをトレーニングした。
  論文  参考訳（メタデータ） (2021-02-20T09:49:51Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  より弱い仮定として, 2$-adjacency faithfulness を提案します。 より弱い仮定の下で適用可能な因果発見のための音方向規則を提案する。
  論文  参考訳（メタデータ） (2020-10-27T13:04:08Z)
• Distribution-free binary classification: prediction sets, confidence intervals and calibration [106.50279469344937]
  分布自由条件における二項分類のための不確実性定量化(キャリブレーション、信頼区間、予測セット)の3つの概念について検討する。 固定幅と一様質量の両双対の双対確率に対する信頼区間を導出する。 我々の「三脚」定理の結果として、双有理確率に対するこれらの信頼区間は分布自由キャリブレーションに繋がる。
  論文  参考訳（メタデータ） (2020-06-18T14:17:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。