論文の概要: Smoothed Online Combinatorial Optimization Using Imperfect Predictions

• arxiv url: http://arxiv.org/abs/2204.10979v1
• Date: Sat, 23 Apr 2022 02:30:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-27 09:39:21.212363
• Title: Smoothed Online Combinatorial Optimization Using Imperfect Predictions
• Title（参考訳）: 不完全予測を用いたオンライン組合せ最適化
• Authors: Kai Wang, Zhao Song, Georgios Theocharous, Sridhar Mahadevan
• Abstract要約: 本研究では,不完全な予測モデルが利用できる場合のスムーズなオンライン最適化問題について検討する。 有限時間地平線計画に予測を用いることで, 全体の予測不確かさと追加の切り替えコストに依存して, 後悔を招くことを示す。 本アルゴリズムは,合成オンライン分散ストリーミング問題において,他のベースラインと比較して,累積的後悔度が大幅に向上したことを示す。
• 参考スコア（独自算出の注目度）: 27.201074566335222
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Smoothed online combinatorial optimization considers a learner who repeatedly chooses a combinatorial decision to minimize an unknown changing cost function with a penalty on switching decisions in consecutive rounds. We study smoothed online combinatorial optimization problems when an imperfect predictive model is available, where the model can forecast the future cost functions with uncertainty. We show that using predictions to plan for a finite time horizon leads to regret dependent on the total predictive uncertainty and an additional switching cost. This observation suggests choosing a suitable planning window to balance between uncertainty and switching cost, which leads to an online algorithm with guarantees on the upper and lower bounds of the cumulative regret. Lastly, we provide an iterative algorithm to approximately solve the planning problem in real-time. Empirically, our algorithm shows a significant improvement in cumulative regret compared to other baselines in synthetic online distributed streaming problems.
• Abstract（参考訳）: Smoothed Online combinatorial Optimization(英語版)は、未知の変動コスト関数を最小化する組合せ決定を繰り返し選択する学習者が連続ラウンドでの切り替え決定にペナルティを課す。 本研究では,不完全な予測モデルが存在する場合のオンライン組合せ最適化問題を円滑に検討し,不確実性のある将来のコスト関数を予測する。 有限時間地平線計画に予測を用いることで, 全体の予測不確かさと追加の切り替えコストに依存する後悔につながることを示す。 この観察は、不確実性と切り替えコストのバランスをとるのに適したプランニングウィンドウを選択することを示唆し、累積的後悔の上下境界を保証したオンラインアルゴリズムに繋がる。 最後に,計画問題をほぼリアルタイムで解くための反復アルゴリズムを提案する。 提案アルゴリズムは, オンライン分散ストリーミング問題における他のベースラインと比較して, 累積的後悔を著しく改善したことを示す。

関連論文リスト

• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  機械学習における予測-Then-Forecast(PtO)パラダイムは、下流の意思決定品質を最大化することを目的としている。 本稿では,PtO法を拡張して,OWA(Nondifferentiable Ordered Weighted Averaging)の目的を最適化する。 この結果から,不確実性の下でのOWA関数の最適化とパラメトリック予測を効果的に統合できることが示唆された。
  論文  参考訳（メタデータ） (2024-02-12T16:33:35Z)
• Online Joint Assortment-Inventory Optimization under MNL Choices [14.530542487845732]
  本稿では,MNL(Multinomial Logit)選択モデルに従えば,各顧客の選択行動が従うと仮定する,オンラインジョイント・アソート・インベントリ最適化問題について考察する。 本稿では,オンラインの品揃えと在庫の意思決定における探索と搾取を効果的にバランスさせる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-04T09:25:34Z)
• Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
  我々は、強い適応的後悔を最小限に抑える新しいオンライン共形予測手法を開発した。 提案手法は,すべての区間において,ほぼ最適に適応的な後悔を同時に達成できることを実証する。 実験により,本手法は実世界のタスクにおける既存の手法よりも,より優れたカバレッジと予測セットが得られることがわかった。
  論文  参考訳（メタデータ） (2023-02-15T18:59:30Z)
• A Note on Task-Aware Loss via Reweighing Prediction Loss by Decision-Regret [11.57423546614283]
  我々は予測最適化の意思決定対応版を提案する。 コストの(非重みのない)パイロット推定器が犯した決定の後悔による予測誤差を再検討する。 このアプローチは"予測を最適化する"フレームワークよりも改善する可能性があることを示す。
  論文  参考訳（メタデータ） (2022-11-09T18:59:35Z)
• Online Convex Optimization with Long Term Constraints for Predictable Sequences [5.964436882344728]
  我々は,長期的制約を伴うOCOと呼ばれるOCOの特定の枠組みについて検討する。 長期的制約は、オンライン最適化における更新ステップ毎に、プロジェクションの複雑さを減らす代替手段として導入される。 我々は,次の関数の情報をシーケンスで供給できる予測器を用いて,予測なしで達成できる率よりも厳密に少ない,全体的な後悔と制約違反率を達成することができることを示した。
  論文  参考訳（メタデータ） (2022-10-30T03:50:53Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
  オンライン学習における自由とは、後ろ向きの最適決定に対するアルゴリズムの適応性を指す。 本稿では,パラメータフリーで要求される楽観的な更新を,スイッチングコストを前提として,そのようなアルゴリズムを設計する。 本稿では,オンライン線形最適化 (OLO) のための簡易かつ強力なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-13T18:44:27Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2022-05-02T08:48:22Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• DJEnsemble: On the Selection of a Disjoint Ensemble of Deep Learning Black-Box Spatio-Temporal Models [0.8347559086129669]
  ブラックボックス予測器の非結合アンサンブルの自動選択とアロケーションのためのコストベースアプローチを提案する。 我々のモデルは、実際の最良の計画に近い性能で計画を作成することを示す。
  論文  参考訳（メタデータ） (2020-05-22T10:37:16Z)

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

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