論文の概要: Efficient Matroid Bandit Linear Optimization Leveraging Unimodality

• arxiv url: http://arxiv.org/abs/2512.00605v1
• Date: Sat, 29 Nov 2025 19:41:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:34.320405
• Title: Efficient Matroid Bandit Linear Optimization Leveraging Unimodality
• Title（参考訳）: 一様性を利用した効率的なマトロイド帯域線形最適化
• Authors: Aurélien Delage, Romaric Gaudel,
• Abstract要約: 本稿では,その基礎となる一方向構造を利用して,マトロイド半帯域問題に新たな光を当てる。 様々なマトロイドベンチマーク実験(すなわち、最先端のアプローチと比較して後悔の損失はない)では、最先端のアプローチと比べて後悔の損失は見られなかった。
• 参考スコア（独自算出の注目度）: 3.620281545470954
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the combinatorial semi-bandit problem under matroid constraints. The regret achieved by recent approaches is optimal, in the sense that it matches the lower bound. Yet, time complexity remains an issue for large matroids or for matroids with costly membership oracles (e.g. online recommendation that ensures diversity). This paper sheds a new light on the matroid semi-bandit problem by exploiting its underlying unimodal structure. We demonstrate that, with negligible loss in regret, the number of iterations involving the membership oracle can be limited to \mathcal{O}(\log \log T)$. This results in an overall improved time complexity of the learning process. Experiments conducted on various matroid benchmarks show (i) no loss in regret compared to state-of-the-art approaches; and (ii) reduced time complexity and number of calls to the membership oracle.
• Abstract（参考訳）: マトロイド制約下での組合せ半帯域問題について検討する。 最近のアプローチによって達成された後悔は、下界と一致するという意味で最適である。 しかし、大きなマトロイドや高価なメンバーシップオラクル(例えば多様性を保証するオンラインレコメンデーション)を持つマトロイドにとって、時間的複雑さは依然として問題である。 本稿では,その基礎となる一方向構造を利用して,マトロイド半帯域問題に新たな光を当てる。 残念なことに、メンバーシップのオラクルを含む反復の数は \mathcal{O}(\log \log T)$ に制限できることを示した。 これにより、学習プロセスの全体的な時間的複雑さが向上する。 各種マトロイドベンチマーク実験 一 最先端のアプローチに比較して後悔の欠如がないこと、 (II)会員宣誓供述書への呼び出しの時間的複雑さと呼び出し回数を減少させる。

関連論文リスト

• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  本論文は、連続マルチアーマッドバンド(MAB)の分野である。 我々は,腕の期待される報酬が単調に非減少性であり,結束する残留包帯の特定の症例について検討した。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2024-11-06T22:00:46Z)
• Accelerating Matroid Optimization through Fast Imprecise Oracles [40.94053997358159]
  汚いオラクルの品質について,クリーンなクエリをほとんど使用しない実用的なアルゴリズムを解析する。 特に、我々のアルゴリズムは、多くの点で、最も有益であることを示す。 我々は、他のマトロイドオラクルタイプ、非自由な汚いオークル、その他のマトロイド問題への拡張を概説する。
  論文  参考訳（メタデータ） (2024-02-05T07:14:18Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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