論文の概要: Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates

• arxiv url: http://arxiv.org/abs/2608.06762v1
• Date: Fri, 07 Aug 2026 03:32:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-10 16:21:25.339286
• Title: Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates
• Title（参考訳）: 近似近接近傍による準量子バイシレーションメトリクス:カバレッジ強化保証と計算可能な2段階認証
• Abstract要約: 我々は,境界遷移をサポートするMPPに対して,証明書を搬送するサブクワッドラティックな方法を提案する。 近似アレスト近傍指数は、正確に制限された演算子によって更新されたペアを選択する。 ローカルインデックスの品質だけでは、グローバルエラーを制御できない。
• 参考スコア（独自算出の注目度）: 1.2891210250935148
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Bisimulation metrics quantify behavioral similarity in Markov decision processes, but their Wasserstein fixed-point operator updates every state pair and incurs quadratic pairwise work. We give a certificate-carrying sub-quadratic method for MDPs with bounded transition support and a useful low-dimensional indexing representation: an approximate-nearest-neighbor index selects the pairs updated by the exact restricted operator, while monotone lower and upper runs enclose the exact metric at every sweep. The main analytical result is a coverage-augmented anytime bound: local index quality alone cannot control global error, because uncovered pairs retain their initialization gap. The limiting error is at most $\max(ρ,\eop/(1-γ))$, and with exact covered backups the lower arm satisfies $\|\dann-d\|_\infty=ρ$. Because $ρ$ depends on the unknown exact metric, the algorithm returns the observable sandwich width instead; agreement of the induced lower and upper clusterings certifies exact recovery of the covered aggregation. A reward-oblivious lower bound shows sub-quadratic index-first coverage cannot remove the coverage term, while a separate adaptive lower bound requires $Ω(|\Scal|)$ pair evaluations. Exact-operator experiments verify the identity and enclosure in every seeded run, and timing experiments recover quadratic versus sub-quadratic scaling under both cheap and full Wasserstein backups. On the grouped $|\Scal|=64$ benchmark, exact restricted refinement reaches the exact-metric skyline once retrieval covers roughly half of all pairs, while independently trained MICo and DBC baselines stay $22$-$33\times$ above that skyline at every retrieval budget. Taxi shows the certificate abstaining under an uninformative embedding, while a $2500$-state gridworld improves over a reward-only metric by $28.6\%$ using $12.8\%$ of one quadratic sweep.
• Abstract（参考訳）: ビシミュレーション測度はマルコフ決定過程における行動類似性を定量化するが、ワッサーシュタインの不動点作用素は状態対を全て更新し、2次対の処理を発生させる。 我々は,境界遷移支援と有用な低次元インデックス表現を備えたMDPに対して,証明付きサブクワッドラティックな方法を与える: 近似型アネレスト近傍インデックスは,厳密な制限演算子によって更新されたペアを選択するが,モノトーン下と上は全スイープで正確な距離を囲む。 ローカルインデックスの品質だけでは、グローバルエラーを制御できない。 制限誤差は最大$\max(ρ,\eop/(1-γ))$で、正確にカバーされたバックアップで下腕は$\|\dann-d\|_\infty=ρ$を満たす。 ρ$は未知の正確な計量に依存するため、アルゴリズムは代わりに観測可能なサンドイッチ幅を返す。 報酬に満ちた下限は、部分四進指数-第一被覆はカバレッジ項を除去できないが、別の適応的下限は$Ω(|\Scal|)$ペア評価を必要とする。 実運用実験は、シードラン毎の同一性と囲いを検証し、タイミング実験は、安価なワッサーシュタインバックアップと完全なワッサーシュタインバックアップの両方の下で二次的および準二次的スケーリングを回復する。 グループ化された$|\Scal|=64$ベンチマークでは、厳密な制限された改善は、検索がすべてのペアのほぼ半分をカバーし、個別に訓練されたMICoとDBCのベースラインは、すべての検索予算において、そのスカイラインの上位に22ドル-33ドルである。 タクシーは、不正な埋め込みで証明書を棄権し、2500ドルのグリッドワールドは、報酬のみのメートル法を228.6.%で改善し、1つの2次スイープの12.8.%ドルである。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs [28.99342075394145]
  CAST(Canonical Approximate Schur Tree)を導入する。 すべての実現は接続され、正確にd-1エッジを含むが、選択された各エッジを木非包含確率の逆数で重み付けすることで更新は不偏となる。 結果として得られた更新は未バイアスで接続され、正確に$O(d)$時間にサンプリングでき、正規化されたローカルSchurエラーの第2モーメントに1/$のバインドを満足する。
  論文  参考訳（メタデータ） (2026-09-08T15:12:01Z)
• Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
  大規模言語モデルの記憶は、形式的関係が不明な定義の動物園を通じて測定される。 差分プライバシー(DP)は,これらすべてに対して同時にプロキシとして扱われることを示す。
  論文  参考訳（メタデータ） (2026-08-27T23:28:08Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。 我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
  論文  参考訳（メタデータ） (2026-08-06T19:49:48Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。 理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
  論文  参考訳（メタデータ） (2026-06-30T06:10:25Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• The Security Budget of Code-LLM Prompt Hardening: Provable Limits Under Pass-Only Acceptance [0.0]
  本稿では,emphTri-Audit Protocolとしてフロアを運用する。このプロトコルは,プロンプト側推論レジストリ属性をモデル側実証ログから分離する2軸レポーティングプロトコルである。 CodeLlama-7B, Qwen2.5-Coder-7B/1.5B and DeepSeek-Coder-6.7B at $n=164$ yields the emphCross-Model Tri-Audit Invariance: of 28 pass-serving rows, 12-changed-of-record learned-can
  論文  参考訳（メタデータ） (2026-06-02T08:22:14Z)
• A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification [0.0]
  PLACE(Persistence-Landmark Analytic Classification Engine)は、点雲とグラフを分類するためのクローズドフォームパイプラインである。 3つの量的保証 -- マージンベースの過剰リスク率、クローズドフォーム記述子選択ルール、プレディションごとの証明書 -- は、トレーニングラベルのみから導かれる。
  論文  参考訳（メタデータ） (2026-05-04T17:15:01Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  そこで本研究では,単一プロトコルステップを正確なマッチングタスクで監査するためのペアアウトカム計測インタフェースを提案する。 各インスタンスについて、インターフェースはベースラインの正当性ビットと後ステップの正当性ビットを記録する。 これらのレートは精度の変化を予測し、種、混合物、パイプライン間でテスト可能な再利用可能な経験的インターフェースを定義する。
  論文  参考訳（メタデータ） (2026-04-20T13:25:40Z)
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm [31.539921770584005]
  本研究では,高収束率を確保しつつ制約を適切に管理するPrimal-Dual Natural Actor-Criticアルゴリズムを提案する。 この結果はマルコフ決定過程の理論的下限と一致し、平均報酬CMDPの理論的探索において新しいベンチマークを確立する。
  論文  参考訳（メタデータ） (2025-05-21T05:49:11Z)
• MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
  多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。 最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。 一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
  論文  参考訳（メタデータ） (2024-05-29T18:36:59Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)

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

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