論文の概要: Learning-Augmented Online Bidding in Stochastic Settings

• arxiv url: http://arxiv.org/abs/2510.25582v1
• Date: Wed, 29 Oct 2025 14:47:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-30 15:50:45.710175
• Title: Learning-Augmented Online Bidding in Stochastic Settings
• Title（参考訳）: 確率的環境下での学習支援型オンライン自転車
• Authors: Spyros Angelopoulos, Bertrand Simon,
• Abstract要約: 予測オラクルやアルゴリズム自体を組み込んだ学習強化された環境下でのオンライン入札について検討する。 まず、ロバスト性予測に基づく入札について検討し、アルゴリズムの一貫性と分布の最良のトレードオフを提供するアルゴリズムを見つける。 第2部では、ランダム化入札アルゴリズムのパワーと限界について、一貫性/ロバスト性トレードオフの上下境界を提示することによって検討する。
• 参考スコア（独自算出の注目度）: 34.40612230021777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online bidding is a classic optimization problem, with several applications in online decision-making, the design of interruptible systems, and the analysis of approximation algorithms. In this work, we study online bidding under learning-augmented settings that incorporate stochasticity, in either the prediction oracle or the algorithm itself. In the first part, we study bidding under distributional predictions, and find Pareto-optimal algorithms that offer the best-possible tradeoff between the consistency and the robustness of the algorithm. In the second part, we study the power and limitations of randomized bidding algorithms, by presenting upper and lower bounds on the consistency/robustness tradeoffs. Previous works focused predominantly on oracles that do not leverage stochastic information on the quality of the prediction, and deterministic algorithms.
• Abstract（参考訳）: オンライン入札は古典的な最適化問題であり、オンライン意思決定、割り込み可能なシステムの設計、近似アルゴリズムの解析などいくつかの応用がある。 本研究では,確率性を考慮した学習強化された環境下でのオンライン入札について,予測オラクルやアルゴリズム自体で検討する。 まず、分布予測に基づく入札について検討し、アルゴリズムの一貫性と堅牢性の間の最良のトレードオフを提供するパレート最適アルゴリズムを求める。 第2部では、ランダム化入札アルゴリズムのパワーと限界について、一貫性/ロバスト性トレードオフの上下境界を提示することによって検討する。 これまでの研究は主に、予測の質に関する確率的な情報や決定論的アルゴリズムを活用できないオラクルに焦点を当てていた。

関連論文リスト

• Prediction-Specific Design of Learning-Augmented Algorithms [10.918779264590297]
  予測固有の性能基準は、一貫性と堅牢性という粗い概念よりも大きな性能改善を可能にすることを示す。 我々は,強最適化アルゴリズムを体系的に設計できる汎用的な二段階最適化フレームワークを開発した。 この結果から,予測固有で強い最適化アルゴリズムは,様々なオンライン意思決定環境における性能を著しく向上させることができることが示された。
  論文  参考訳（メタデータ） (2025-10-16T17:06:53Z)
• Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms [8.793721044482613]
  本稿では,アルゴリズムの不整合性性能と不整合性オラクルに関連するリスクとのトレードオフをバランスさせる決定論的尺度と尺度の両方に基づくアプローチを提案する。 我々は,オンライン意思決定,スキーレンタール,ワンマックス検索,契約スケジューリングの3つのよく知られた問題に適用する。
  論文  参考訳（メタデータ） (2025-01-29T15:16:27Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
  我々は、オンラインアルゴリズムの原始二重法を拡張し、次のアクションについてオンラインアルゴリズムにアドバイスする予測を組み込む。 我々のアルゴリズムは、予測が正確である場合にも、予測が誤解を招くとき、適切な保証を維持しながら、どのオンラインアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-22T11:58:47Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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