論文の概要: Robust and Learned Online Matching in Growing Trees

• arxiv url: http://arxiv.org/abs/2609.40077v1
• Date: Wed, 30 Sep 2026 16:26:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.063253
• Title: Robust and Learned Online Matching in Growing Trees
• Title（参考訳）: 成長樹におけるロバストとオンラインマッチングの学習
• Abstract要約: 本研究は, 連続した葉のアタッチメントで示される樹木における, 最大心電図整合性について検討した。 非負の次数強化を伴う決定論的アフィン付着予測では、最適しきい値ポリシーは累積条件の総偏差誤差の2倍の誤差で失われる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret $O(\sqrt{n}\log^2 n)$, using $O(n^2\log n)$ arithmetic operations and $O(n)$ stored entries. The exact minimax rate remains open.
• Abstract（参考訳）: 本研究は, 葉の連続着生によって明らかにされた木において, 未特定または不明な地平線と外生生生長則により, 無効な最大心長整合性について検討した。 非負の次数強化を伴う決定論的アフィン付着予測において、最適しきい値ポリシは、実際の成長法を把握したオンラインオラクルと比較して、累積条件の総変量誤差を少なくとも2倍失う。 これはベルマン連続点の単位スパン性から続き、追加の地平線係数を持たない。 4頂点の例は、指定された決定論的ポリシーの係数2を獲得し、2モデル引数は、一般的な不特定性の下での任意のポリシーのモデルエラー予算において、より低い境界線を与える。 一様述語アタッチメントの場合、局所誤差はリーフカウントを通して正確な表現を持つ。 定数混合パラメータが未知の場合、同じ成長木から推定し、幾何学的な時間にしきい値ポリシーを更新する。 個々のベルマン価格と均一度モーメント推定に対するパラメータ感度境界は、$O(n^2\log n)$算術演算と$O(n)$ストアドエントリを用いて、期待された後悔の$O(\sqrt{n}\log^2n)$を生成する。 正確なミニマックスレートは未定である。

関連論文リスト

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Dirichlet Process Mixtures of Trees with Gaussian Process Splits: A Bayesian Nonparametric Framework with Posterior Contraction Rate [0.9176056742068814]
  本稿では,ディリクレ過程に先行する回帰木の非パラメトリック混合法を提案する。 各端末ノード内のガウス過程の後方予測によって駆動される新しい分割規則は、柔軟で滑らかな決定境界を生成する。 QSAR毒性、犯罪、リボフラビン、小麦ゲノム学、空気質への応用は、信頼性の高い信頼区間と自動間隔を確認する。
  論文  参考訳（メタデータ） (2026-08-22T08:47:23Z)
• Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning [0.9558392439655014]
  定数対応比較プロトコルを導入し、MPPを通信するための明示的な有限下位証明書を導出する。 共通閉形式エンベロープは有限フロンティアで発行された係数を0.015$に改善する。
  論文  参考訳（メタデータ） (2026-08-07T19:28:58Z)
• Tokens-per-Parameter Coverage Is Critical for Robust LLM Scaling Law Extrapolation [45.56738584872585]
  ニューラルスケーリング法則は、パラメータカウント$N$とトークンカウント$D$のパワーロー関数として、言語モデルの損失を近似する。 本稿では,コリニア設計がガウス・ニュートン最小二乗問題に固有の不条件を生じさせることを示す。 これを4つのスケーリング法則形式に対して証明し、十分に条件付き推定に十分必要な閉形式TPP多様性閾値を導出する。
  論文  参考訳（メタデータ） (2026-05-08T23:00:17Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees [73.0940890296463]
  確率値は、決定木の局所的な予測値を説明する特徴のランク付けに使用される。 TreeGradは、共同目的の多重線型拡張の勾配を$O(L)$時間で計算する。 TreeGrad-Rankerは、機能ランキングを生成するために共同目標を最適化しながら、勾配を集約する。 TreeGrad-Shapは、積分パラメータを持つベータシェープ値を計算するための数値的に安定なアルゴリズムである。
  論文  参考訳（メタデータ） (2026-02-12T06:17:12Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Random Planted Forest: a directly interpretable tree ensemble [0.0]
  回帰設定における予測のための新しい解釈可能な木ベースアルゴリズムを提案する。 シミュレーション研究により,無作為植林手法の予測と可視化特性について検討した。
  論文  参考訳（メタデータ） (2020-12-29T01:51:59Z)

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

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