論文の概要: Prediction-Specific Design of Learning-Augmented Algorithms

• arxiv url: http://arxiv.org/abs/2510.14887v1
• Date: Thu, 16 Oct 2025 17:06:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-17 21:15:14.963624
• Title: Prediction-Specific Design of Learning-Augmented Algorithms
• Title（参考訳）: 学習強化アルゴリズムの予測特異設計
• Authors: Sizhe Li, Nicolas Christianson, Tongxin Li,
• Abstract要約: 予測固有の性能基準は、一貫性と堅牢性という粗い概念よりも大きな性能改善を可能にすることを示す。 我々は,強最適化アルゴリズムを体系的に設計できる汎用的な二段階最適化フレームワークを開発した。 この結果から,予測固有で強い最適化アルゴリズムは,様々なオンライン意思決定環境における性能を著しく向上させることができることが示された。
• 参考スコア（独自算出の注目度）: 10.918779264590297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithms with predictions} has emerged as a powerful framework to combine the robustness of traditional online algorithms with the data-driven performance benefits of machine-learned (ML) predictions. However, most existing approaches in this paradigm are overly conservative, {as they do not leverage problem structure to optimize performance in a prediction-specific manner}. In this paper, we show that such prediction-specific performance criteria can enable significant performance improvements over the coarser notions of consistency and robustness considered in prior work. Specifically, we propose a notion of \emph{strongly-optimal} algorithms with predictions, which obtain Pareto optimality not just in the worst-case tradeoff between robustness and consistency, but also in the prediction-specific tradeoff between these metrics. We develop a general bi-level optimization framework that enables systematically designing strongly-optimal algorithms in a wide variety of problem settings, and we propose explicit strongly-optimal algorithms for several classic online problems: deterministic and randomized ski rental, and one-max search. Our analysis reveals new structural insights into how predictions can be optimally integrated into online algorithms by leveraging a prediction-specific design. To validate the benefits of our proposed framework, we empirically evaluate our algorithms in case studies on problems including dynamic power management and volatility-based index trading. Our results demonstrate that prediction-specific, strongly-optimal algorithms can significantly improve performance across a variety of online decision-making settings.
• Abstract（参考訳）: 予測を伴うアルゴリズムは、従来のオンラインアルゴリズムの堅牢性と、機械学習(ML)予測によるデータ駆動のパフォーマンスメリットを組み合わせる強力なフレームワークとして登場した。 しかし、このパラダイムの既存のアプローチのほとんどは過度に保守的であり、例えば、予測特異的な方法で性能を最適化するために問題構造を利用しないためである。 本稿では,このような予測固有の性能基準が,事前の作業で考慮された一貫性と堅牢性という粗い概念に対して,大幅な性能向上を可能にすることを示す。 具体的には、ロバスト性と整合性の間の最悪のトレードオフだけでなく、これらの指標間の予測特異的トレードオフにおいてもパレート最適性が得られるような予測付き「emph{strongly-optimal}アルゴリズム」の概念を提案する。 我々は,様々な問題設定で強最適化アルゴリズムを体系的に設計できる汎用的な二段階最適化フレームワークを開発し,決定論的かつランダムなスキーレンタル,一マックス探索といった古典的なオンライン問題に対して,強最適化アルゴリズムを明示的に提案する。 我々の分析では、予測固有の設計を活用することで、予測をオンラインアルゴリズムに最適に統合する方法に関する新たな構造的洞察を明らかにした。 提案手法の利点を検証するため,動的電力管理やボラティリティに基づく索引取引といった問題に対するケーススタディにおいて,提案手法を実証的に評価した。 この結果から,予測に特有な強最適化アルゴリズムは,様々なオンライン意思決定環境における性能を著しく向上させることができることが示された。

関連論文リスト

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Explainable Benchmarking for Iterative Optimization Heuristics [0.8192907805418583]
  我々は、様々な最適化アルゴリズムの性能を分析し、理解するためのIOH-Xplainerソフトウェアフレームワークを紹介する。 さまざまなアルゴリズムコンポーネントと構成の影響を調査し、さまざまなシナリオにおけるパフォーマンスに関する洞察を提供する。
  論文  参考訳（メタデータ） (2024-01-31T14:02:26Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• 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)
• Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization [23.359363844344408]
  最適化過程において,最適化誤差フラックスと統計的誤差フラックスとの相互作用を管理するアルゴリズムフレームワークを導入する。 我々のフレームワークとその分析は、異なる局所的滑らかさの仮定を満たす関数と分割の大きなファミリーに適用できる。 理論的には、局所的滑らかさの仮定が異なる条件下で、アルゴリズムが速度-最適後悔境界を楽しむことを証明する。
  論文  参考訳（メタデータ） (2021-06-17T02:37:39Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。 信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。 最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
  論文  参考訳（メタデータ） (2021-04-06T05:23:20Z)
• Integrated Optimization of Predictive and Prescriptive Tasks [0.0]
  予測タスクを記述タスクとして直接統合する新しいフレームワークを提案する。 予測アルゴリズムのパラメータを2レベル最適化技術により、処方問題内でトレーニングします。
  論文  参考訳（メタデータ） (2021-01-02T02:43:10Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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