論文の概要: Competitive strategies to use "warm start" algorithms with predictions
- arxiv url: http://arxiv.org/abs/2405.03661v1
- Date: Mon, 6 May 2024 17:38:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-07 12:46:34.802655
- Title: Competitive strategies to use "warm start" algorithms with predictions
- Title（参考訳）: ウォームスタート」アルゴリズムと予測を用いた競合戦略
- Authors: Vaidehi Srinivas, Avrim Blum,
- Abstract要約: 本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。
この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。
我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
- 参考スコア（独自算出の注目度）: 12.970501425097645
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of learning and using predictions for warm start algorithms with predictions. In this setting, an algorithm is given an instance of a problem, and a prediction of the solution. The runtime of the algorithm is bounded by the distance from the predicted solution to the true solution of the instance. Previous work has shown that when instances are drawn iid from some distribution, it is possible to learn an approximately optimal fixed prediction (Dinitz et al, NeurIPS 2021), and in the adversarial online case, it is possible to compete with the best fixed prediction in hindsight (Khodak et al, NeurIPS 2022). In this work we give competitive guarantees against stronger benchmarks that consider a set of $k$ predictions $\mathbf{P}$. That is, the "optimal offline cost" to solve an instance with respect to $\mathbf{P}$ is the distance from the true solution to the closest member of $\mathbf{P}$. This is analogous to the $k$-medians objective function. In the distributional setting, we show a simple strategy that incurs cost that is at most an $O(k)$ factor worse than the optimal offline cost. We then show a way to leverage learnable coarse information, in the form of partitions of the instance space into groups of "similar" instances, that allows us to potentially avoid this $O(k)$ factor. Finally, we consider an online version of the problem, where we compete against offline strategies that are allowed to maintain a moving set of $k$ predictions or "trajectories," and are charged for how much the predictions move. We give an algorithm that does at most $O(k^4 \ln^2 k)$ times as much work as any offline strategy of $k$ trajectories. This algorithm is deterministic (robust to an adaptive adversary), and oblivious to the setting of $k$. Thus the guarantee holds for all $k$ simultaneously.
- Abstract（参考訳）: 本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。
この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。
アルゴリズムのランタイムは、予測された解からインスタンスの真の解までの距離によって制限される。
従来の研究では、ある分布からインスタンスをiidに引いた場合、ほぼ最適な固定予測(Dinitz et al, NeurIPS 2021)を学習でき、対向オンラインの場合、後向きの最良の固定予測と競合することができる(Khodak et al, NeurIPS 2022)。
この研究では、より強いベンチマークに対して、$k$の予測セットを$\mathbf{P}$とする競合保証を与える。
つまり、$\mathbf{P}$ のインスタンスを解く「最適オフラインコスト」とは、真解から $\mathbf{P}$ の最も近い元への距離である。
これは$k$-mediansの目的関数に類似している。
分布設定では、最適オフラインコストよりも高い$O(k)$係数のコストを発生させる単純な戦略を示す。
次に、学習可能な粗い情報を、インスタンス空間を「類似した」インスタンスのグループに分割する形で活用する方法を示します。
最後に、オンライン版の問題を考慮し、オフライン戦略と競合し、$k$の予測や“トラジェクトリ”の移動セットを維持でき、予測の移動量について課金される。
我々は、少なくとも$O(k^4 \ln^2 k)$のアルゴリズムを、$k$トラジェクトリの任意のオフライン戦略の倍の処理を行う。
このアルゴリズムは決定論的(適応的敵に悪影響を与える)であり、$k$の設定には不適当である。
したがって、保証はすべての$k$を同時に保持する。
関連論文リスト
- Mixing predictions for online metric algorithms [34.849039387367455]
我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。
我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。
我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
論文 参考訳（メタデータ） (2023-04-04T13:18:00Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-19T01:09:24Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Learning-Augmented Maximum Flow [3.0712335337791288]
本稿では,予測を用いて最大流れ計算を高速化するフレームワークを提案する。
我々は,$m$のエッジフローネットワークと予測フローが与えられた場合,最大フローを$O(meta)$時間で計算するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-26T14:02:41Z) - Scheduling with Speed Predictions [10.217102227210669]
本稿では,ジョブの処理時間ではなく,マシンの速度が不明な速度ロスのスケジューリング問題について検討する。
我々の主な結果は、$mineta2 (1+epsilon)2 (1+epsilon)(2+2/alpha)$近似を達成するアルゴリズムである。
予測が正確であれば、この近似は以前最もよく知られた2-1/m$の近似よりも改善される。
論文 参考訳（メタデータ） (2022-05-02T23:39:41Z) - Online Optimization with Untrusted Predictions [7.895232155155041]
本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。
本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
論文 参考訳（メタデータ） (2022-02-07T21:08:02Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。