論文の概要: On Optimal Consistency-Robustness Trade-Off for Learning-Augmented
Multi-Option Ski Rental
- arxiv url: http://arxiv.org/abs/2312.02547v1
- Date: Tue, 5 Dec 2023 07:33:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-06 16:28:37.049077
- Title: On Optimal Consistency-Robustness Trade-Off for Learning-Augmented
Multi-Option Ski Rental
- Title（参考訳）: 学習型マルチオプティオンスキーレンタルにおける最適一貫性-ロバスト性トレードオフについて
- Authors: Yongho Shin, Changyeol Lee, Hyung-Chan An
- Abstract要約: 学習強化型マルチオプションスキーレンタル問題は、古典的なスキーレンタル問題を2つの方法で一般化する。
ランダム化アルゴリズムでは、一貫性-ロバスト性トレードオフに対する最初の非自明な下界を示す。
私たちのアルゴリズムは、一貫性が 1.086 であるとき、e/2 の係数の範囲内のロバスト性に対する低い境界と一致します。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The learning-augmented multi-option ski rental problem generalizes the
classical ski rental problem in two ways: the algorithm is provided with a
prediction on the number of days we can ski, and the ski rental options now
come with a variety of rental periods and prices to choose from, unlike the
classical two-option setting. Subsequent to the initial study of the
multi-option ski rental problem (without learning augmentation) due to Zhang,
Poon, and Xu, significant progress has been made for this problem recently in
particular. The problem is very well understood when we relinquish one of the
two generalizations -- for the learning-augmented classical ski rental problem,
algorithms giving best-possible trade-off between consistency and robustness
exist; for the multi-option ski rental problem without learning augmentation,
deterministic/randomized algorithms giving the best-possible competitiveness
have been found. However, in presence of both generalizations, there remained a
huge gap between the algorithmic and impossibility results. In fact, for
randomized algorithms, we did not have any nontrivial lower bounds on the
consistency-robustness trade-off before.
This paper bridges this gap for both deterministic and randomized algorithms.
For deterministic algorithms, we present a best-possible algorithm that
completely matches the known lower bound. For randomized algorithms, we show
the first nontrivial lower bound on the consistency-robustness trade-off, and
also present an improved randomized algorithm. Our algorithm matches our lower
bound on robustness within a factor of e/2 when the consistency is at most
1.086.
- Abstract（参考訳）: 学習強化型マルチオプションスキーレンタル問題は、従来のスキーレンタル問題を2つの方法で一般化する: このアルゴリズムは、スキーできる日数を予測し、スキーレンタルオプションには、古典的な2オプション設定とは異なり、さまざまなレンタル期間と価格が提供される。
Zhang, Poon, Xu によるマルチオプションスキーレンタル問題(学習増強なし)の初期研究以降,この問題,特に近年において顕著な進展がみられた。
この問題は、学習強化された古典スキーレンタル問題、一貫性と堅牢性の間の最良のトレードオフを与えるアルゴリズム、そして、学習増強を伴わないマルチオプションスキーレンタル問題、最良の競争力を与える決定論的/ランダム化アルゴリズムの2つの一般化のうちの1つを放棄した時に非常によく理解されている。
しかし、両方の一般化が存在する場合、アルゴリズムと不可能な結果の間には大きなギャップが残っていた。
実のところ、ランダム化アルゴリズムでは、一貫性-ロバスト性トレードオフに非自明な下限は存在しなかった。
本稿では,決定論的アルゴリズムとランダム化アルゴリズムのギャップを橋渡しする。
決定論的アルゴリズムでは、既知の下界と完全に一致した最も有望なアルゴリズムを提案する。
ランダム化アルゴリズムでは, 整合性のトレードオフに対する最初の非自明な下界を示すとともに, 改良されたランダム化アルゴリズムを示す。
我々のアルゴリズムは、一貫性が 1.086 であるとき、e/2 の係数の範囲内のロバスト性に対する低い境界と一致する。
関連論文リスト
- Learning-Augmented Algorithms for the Bahncard Problem [12.852098444482426]
本研究では,Bahncard問題に対する学習強化アルゴリズムについて検討する。
PFSUMは、オンライン意思決定を改善するために、歴史と短期の両方を取り入れている。
論文 参考訳（メタデータ） (2024-10-20T02:55:15Z) - Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental
Problem via Best-Possible Competitive Analysis [0.1529342790344802]
マルチオプションスキーレンタル問題に対する学習向上アルゴリズムを提案する。
提案アルゴリズムは,この問題に対して最も有効なランダム化競合アルゴリズムに基づいている。
論文 参考訳（メタデータ） (2023-02-14T05:05:03Z) - HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。
HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
論文 参考訳（メタデータ） (2022-10-31T14:06:11Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。