論文の概要: A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives

• arxiv url: http://arxiv.org/abs/2406.03574v1
• Date: Wed, 5 Jun 2024 18:39:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 19:14:47.870446
• Title: A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
• Title（参考訳）: Concave Objectivesを用いたオンラインパッケージングのための簡易学習支援アルゴリズム
• Authors: Elena Grigorescu, Young-San Lin, Maoyuan Song,
• Abstract要約: 本稿では,線形制約付きオンラインパッキング問題に対する単純な学習拡張アルゴリズムの導入と解析を行う。 さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。
• 参考スコア（独自算出の注目度）: 4.9826534303287335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning-augmented algorithms has been extensively studied recently in the computer-science community, due to the potential of using machine learning predictions in order to improve the performance of algorithms. Predictions are especially useful for online algorithms making irrevocable decisions without knowledge of the future. Such learning-augmented algorithms aim to overcome the limitations of classical online algorithms when the predictions are accurate, and still perform comparably when the predictions are inaccurate. A common approach is to adapt existing online algorithms to the particular advice notion employed, which often involves understanding previous sophisticated algorithms and their analyses. However, ideally, one would simply use previous online solutions in a black-box fashion, without much loss in the approximation guarantees. Such clean solutions that avoid opening up black-boxes are often rare, and may be even missed the first time around. For example, Grigorescu et al. (NeurIPS 22) proposed a learning-augmented algorithms for online covering linear programs, but it later turned out that their results can be subsumed by a natural approach that switches between the advice and an online algorithm given as a black-box, as noted in their paper. In this work, we introduce and analyze a simple learning-augmented algorithm for online packing problems with linear constraints and concave objectives. We exhibit several direct applications of our framework including online packing linear programming, knapsack, resource management benefit, throughput maximization, and network utility maximization. We further raise the problem of understanding necessary and sufficient conditions for when such simple black-box solutions may be optimal. We believe this is an important direction of research that would unify many ad-hoc approaches from the literature.
• Abstract（参考訳）: 学習強化アルゴリズムは、アルゴリズムの性能を向上させるために機械学習予測を使用する可能性があるため、近年、コンピュータサイエンスコミュニティで広く研究されている。 予測は、将来を知ることなく、取り消せない決定をするオンラインアルゴリズムにとって特に有用である。 このような学習強化されたアルゴリズムは、予測が正確である場合の古典的なオンラインアルゴリズムの限界を克服し、予測が不正確である場合の相容れない実行を目標としている。 一般的なアプローチは、既存のオンラインアルゴリズムを特定のアドバイス概念に適応させることである。 しかし、理想的には、従来のオンラインソリューションをブラックボックス方式で単純に使うだけで、近似の保証に大きな損失を被ることはない。 ブラックボックスを開くのを避けるようなクリーンなソリューションは、しばしばまれであり、初めて見逃されることもある。 例えば、Grigorescu et al (NeurIPS 22) は線形プログラムを網羅するオンライン学習アルゴリズムを提案したが、後に彼らの論文で述べられているように、彼らの結果はアドバイスとブラックボックスとして与えられるオンラインアルゴリズムを切り替える自然なアプローチによって仮定できることが判明した。 本研究では,オンラインパッキング問題に対して,線形制約とコンケーブ目的を用いた単純な学習拡張アルゴリズムを導入,解析する。 オンラインパッキングリニアプログラミング、knapsack、リソース管理のメリット、スループットの最大化、ネットワークユーティリティの最大化など、当社のフレームワークの直接的な応用例をいくつか紹介する。 さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。 これは、文献から多くのアドホックなアプローチを統合する研究の重要な方向であると考えています。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Online Algorithms with Uncertainty-Quantified Predictions [11.951228732915936]
  オンラインアルゴリズムの設計における不確実性定量化予測を最適に活用する問題について検討する。 特に,スキーレンタルとオンライン検索の2つの古典的オンライン問題について検討した。 我々は、UQ予測を完全に活用するために、アルゴリズム設計への非自明な修正が必要であることを実証する。
  論文  参考訳（メタデータ） (2023-10-17T20:09:41Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Online Algorithms with Multiple Predictions [17.803569868141647]
  本稿では,複数の機械学習予測を付加したオンラインアルゴリズムについて検討する。 我々のアルゴリズムは、オンラインアルゴリズムの古典的ポテンシャルに基づく分析に予測の利用を取り入れている。
  論文  参考訳（メタデータ） (2022-05-08T17:33:01Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• 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)

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

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