論文の概要: Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff

• arxiv url: http://arxiv.org/abs/2610.37361v1
• Date: Tue, 27 Oct 2026 14:56:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-28 21:04:31.667178
• Title: Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff
• Title（参考訳）: 2値予測によるオンライン区間選択:最適一貫性と連続ロバスト性トレードオフ
• Abstract要約: 最終的な最適解法として,オンライン区間選択を二元予測を用いて検討する。 報酬が区間長に比例すると、有限厳密性の下での最良の整合性は$d=(3+sqrt5)/2$である。
• 参考スコア（独自算出の注目度）: 0.5922488908114023
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online interval selection with binary predictions of membership in a final optimal solution. Requests arrive in arbitrary order; accepted requests may be revoked, but rejected or revoked requests cannot be recovered. With rewards proportional to interval length, the best consistency under finite strict robustness is $d=(3+\sqrt5)/2$ when both guarantees hold almost surely on each fixed input, including for randomized algorithms. A continuous lower bound forces consistency strictly above $d$ at every robustness budget below $4\varphi+3\approx9.472$, whereas our deterministic algorithm attains $d$ with exact robustness $\varphi^5\approx11.090$, where $\varphi=(1+\sqrt5)/2$. Each held interval inherits a ledger recording positive prediction mass lost through irrevocable decisions. A tunable replacement cost gives a continuous family with exact consistency throughout and exact robustness on two parameter intervals, including $(C,R)=(25/9,10)$ and $(4,7)$. Randomization permits expected consistency approaching one with finite expected robustness, whereas almost-sure robustness forces expected consistency strictly above two at every finite budget.
• Abstract（参考訳）: 最終的な最適解法として,オンライン区間選択を二元予測を用いて検討する。 リクエストは任意の順序で到着する。承認されたリクエストは取り消されるが、拒否または取り消されるリクエストは回収できない。 区間長に比例する報酬の場合、有限厳密性の下での最良の整合性は$d=(3+\sqrt5)/2$である。 連続的な下界は、全てのロバスト性予算において$d$より厳密に$4\varphi+3\approx9.472$未満で一貫性を保ち、一方、決定論的アルゴリズムは、正確なロバスト性を持つ$d$を$\varphi^5\approx11.090$で達成する。 各保持間隔は、無効な決定によって失われた正の予測質量を記録する台帳を継承する。 調整可能な代替コストは、$(C,R)=(25/9,10)$と$(4,7)$を含む2つのパラメータ区間における正確な一貫性と正確な堅牢性を持つ連続族を与える。 ランダム化は、有限の強靭性を持つものへの期待整合性を許容する一方、ほぼ確実な堅牢性は、全ての有限の予算において2より厳密な整合性を期待する。

関連論文リスト

• Bayesian Fixed-Confidence Best-Arm Identification with Abstention [51.253617466579335]
  本研究では,学習者が端末の推薦を控えることができるベイジアン固定自信ベストアーム識別問題について検討する。 目標誤差確率$$および棄権予算$に対して、S&C(Screen-and-Confirm)を提案し、その予測停止時間を分析する。
  論文  参考訳（メタデータ） (2026-10-21T19:45:09Z)
• Reliable Scale-Free Bandits via Empirical Likelihood [2.5361601273217973]
  ほぼ確実に後悔の保証は、最終的な学習を記述しているが、パフォーマンスや有限実行時の大きな後悔のリスクを期待していない。 我々は,Cowan と Katehakis の $g-Forcing Policy (2020) の任意の経験的拡張である $textttEL-F$ を紹介する。 実験では、挑戦的なインスタンスに対する$g$-Forcingと比較して、長時間の最適部分割り当ての削減が示されている。
  論文  参考訳（メタデータ） (2026-10-13T09:43:54Z)
• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
  マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。 本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。 本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
  論文  参考訳（メタデータ） (2026-09-29T15:39:50Z)
• A Convergence Framework for Deep $V$-Learning: Error Propagation and Sharp Action-Gap Bounds [0.0]
  更新エラーを、フィッティング、遷移再利用、ターゲット構築、リプレイ、アクション選択、探索の6つの残差に分解する。 次数$n-$の統計的誤差境界に対して、最適連続割り当てと、制約された最適値の係数2$以内の整数割り当てを導出する。 これらの結果から, FIFO/インターリーブされたSGDに対して, 厳密な動作スコアを有する固定水平生成-リセット近似-ERM法に対して, 期待されるポリシ-ロス一貫性が得られた。
  論文  参考訳（メタデータ） (2026-09-16T15:03:46Z)
• Data Driven Block Replacement Scheduling [0.0]
  我々は、テキストブロック置換ポリシーの下で、$N$独立同一マシンを維持するためのデータ駆動アルゴリズムを開発した。 目標は、寿命分布が不明な場合に運用データからコスト最小化間隔$k*$を学習することである。 補完的なKaplan-Meier更新アルゴリズムは、検閲されたデータから寿命分布を非センセーショナルに推定し、ほぼ確実にポリシーの整合性を達成し、長い地平線で経験的にほぼゼロに近い漸進的後悔を達成する。
  論文  参考訳（メタデータ） (2026-07-16T17:31:15Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)

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

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