論文の概要: Online Optimization with Untrusted Predictions
- arxiv url: http://arxiv.org/abs/2202.03519v1
- Date: Mon, 7 Feb 2022 21:08:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-09 16:20:47.725177
- Title: Online Optimization with Untrusted Predictions
- Title（参考訳）: 信頼できない予測によるオンライン最適化
- Authors: Daan Rutten, Nico Christianson, Debankur Mukherjee, Adam Wierman
- Abstract要約: 本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。
本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
- 参考スコア（独自算出の注目度）: 7.895232155155041
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We examine the problem of online optimization, where a decision maker must
sequentially choose points in a general metric space to minimize the sum of
per-round, non-convex hitting costs and the costs of switching decisions
between rounds. The decision maker has access to a black-box oracle, such as a
machine learning model, that provides untrusted and potentially inaccurate
predictions of the optimal decision in each round. The goal of the decision
maker is to exploit the predictions if they are accurate, while guaranteeing
performance that is not much worse than the hindsight optimal sequence of
decisions, even when predictions are inaccurate. We impose the standard
assumption that hitting costs are globally $\alpha$-polyhedral. We propose a
novel algorithm, Adaptive Online Switching (AOS), and prove that, for any
desired $\delta > 0$, it is $(1+2\delta)$-competitive if predictions are
perfect, while also maintaining a uniformly bounded competitive ratio of
$2^{\tilde{\mathcal{O}}(1/(\alpha \delta))}$ even when predictions are
adversarial. Further, we prove that this trade-off is necessary and nearly
optimal in the sense that any deterministic algorithm which is
$(1+\delta)$-competitive if predictions are perfect must be at least
$2^{\tilde{\Omega}(1/(\alpha \delta))}$-competitive when predictions are
inaccurate.
- Abstract（参考訳）: オンライン最適化の問題点を考察し,ラウンド間における決定の切り替えコストと非凸打撃コストの和を最小化するために,一般的な距離空間内のポイントを順次選択しなければならない。
意思決定者は、機械学習モデルのようなブラックボックスのオラクルにアクセスでき、各ラウンドにおける最適な決定の信頼できない、潜在的に不正確な予測を提供する。
意思決定者の目標は、予測が正確である場合の予測を活用し、予測が不正確である場合でも、後続の最適な決定シーケンスよりもパフォーマンスを保証することである。
我々は、打撃コストが全世界で$\alpha$-polyhedralであると仮定する。
本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$(1+2\delta)$-competitiveであること,また予測が逆である場合でも$2^{\tilde{\mathcal{O}}(1/(\alpha \delta))を均一に有界な競合比として維持することを証明する。
さらに、予測が完全であれば(1+\delta)$-競合である決定論的アルゴリズムは、予測が不正確である場合には少なくとも2^{\tilde{\omega}(1/(\alpha \delta))}$-競合でなければならないという意味で、このトレードオフは必要であり、ほぼ最適であることを示す。
関連論文リスト
- Fair Secretaries with Unfair Predictions [12.756552522270198]
予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。
私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
論文 参考訳（メタデータ） (2024-11-15T00:23:59Z) - Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。
適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文 参考訳（メタデータ） (2024-05-24T11:22:19Z) - Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。
この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。
我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
論文 参考訳（メタデータ） (2024-05-06T17:38:20Z) - Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。
我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
論文 参考訳（メタデータ） (2023-05-16T07:52:08Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Learning-Augmented Algorithms for Online TSP on the Line [4.636538620253008]
本研究では,オンライントラベリングセールスマン問題 (TSP) を,機械学習による予測を付加した線上で研究する。
古典的な問題では、実際の行に沿って時間をかけてリリースされるリクエストのストリームがあります。
オープンな変種とクローズドな変種を区別し、全ての要求を処理した後、アルゴリズムに元の値を返すように要求する。
論文 参考訳（メタデータ） (2022-06-01T17:47:26Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Almost Tight L0-norm Certified Robustness of Top-k Predictions against
Adversarial Perturbations [78.23408201652984]
トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。
我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。
例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
論文 参考訳（メタデータ） (2020-11-15T21:34:44Z) - Online Page Migration with ML Advice [26.929268665630342]
提案手法は,エムページマイグレーション問題に対するオンラインアルゴリズムで,予測が不完全である可能性があり,その性能向上を図っている。
アルゴリズムが入力シーケンスの予測を与えられると、競合比が1ドルになることを示す。
我々の成果は、機械学習を使って古典的なアルゴリズムの性能を向上させる、最近の仕事の本体に追加される。
論文 参考訳（メタデータ） (2020-06-09T03:15:34Z) - Toward Optimal Adversarial Policies in the Multiplicative Learning
System with a Malicious Expert [87.12201611818698]
専門家のアドバイスを組み合わせて真の結果を予測する学習システムについて考察する。
専門家の一人が悪意があり、システムに最大損失を課すことを目指していると推測されている。
誤予測を常に報告する単純な欲求ポリシーは、近似比が1+O(sqrtfracln NN)$で最適であることを示す。
悪意のある専門家がその判断を適応的に行うことができるオンライン環境では、最適のオンラインポリシーを$O(N3)$で動的プログラムを解くことで効率的に計算できることが示される。
論文 参考訳（メタデータ） (2020-01-02T18:04:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。