論文の概要: Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions

• arxiv url: http://arxiv.org/abs/2401.01077v1
• Date: Tue, 2 Jan 2024 07:46:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-03 14:36:59.219872
• Title: Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions
• Title（参考訳）: 制約付きオンライン二段階確率最適化:予測を伴うアルゴリズム
• Authors: Piao Hu, Jiashuo Jiang, Guodong Lyu, Hao Su
• Abstract要約: 有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 19.537289123577022
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider an online two-stage stochastic optimization with long-term constraints over a finite horizon of $T$ periods. At each period, we take the first-stage action, observe a model parameter realization and then take the second-stage action from a feasible set that depends both on the first-stage decision and the model parameter. We aim to minimize the cumulative objective value while guaranteeing that the long-term average second-stage decision belongs to a set. We develop online algorithms for the online two-stage problem from adversarial learning algorithms. Also, the regret bound of our algorithm can be reduced to the regret bound of embedded adversarial learning algorithms. Based on this framework, we obtain new results under various settings. When the model parameters are drawn from unknown non-stationary distributions and we are given machine-learned predictions of the distributions, we develop a new algorithm from our framework with a regret $O(W_T+\sqrt{T})$, where $W_T$ measures the total inaccuracy of the machine-learned predictions. We then develop another algorithm that works when no machine-learned predictions are given and show the performances.
• Abstract（参考訳）: 有限地平線上の長期制約付きオンライン2段階確率最適化をT$周期で検討する。 各期間において、第一段階のアクションをとり、モデルパラメータの実現を観察し、第一段階の決定とモデルパラメータの両方に依存する実行可能セットから第二段階のアクションを取る。 我々は,長期平均2段階決定が集合に属することを保証しながら,累積目標値の最小化を目指す。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。 また、我々のアルゴリズムの後悔の限界は、組込み逆学習アルゴリズムの後悔の限界に還元することができる。 この枠組みに基づいて,様々な設定で新たな結果が得られる。 モデルパラメータが未知の非定常分布から引き出され、その分布の機械学習予測が与えられたとき、我々はこのフレームワークから新たなアルゴリズムを開発し、後悔する$o(w_t+\sqrt{t})$、ここで$w_t$は機械学習予測の完全な不正確性を測定する。 次に、機械学習された予測が与えられず、性能を示す別のアルゴリズムを開発する。

関連論文リスト

• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning [1.994307489466967]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-02-02T10:33:09Z)
• Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments [48.96971760679639]
  マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。 環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。 モデルに基づく手法では、MVPアルゴリズムの変種を設計する。 特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
  論文  参考訳（メタデータ） (2023-01-31T06:54:06Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Online estimation and control with optimal pathlength regret [52.28457815067461]
  オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。 OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
  論文  参考訳（メタデータ） (2021-10-24T22:43:15Z)
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path [29.289190242826688]
  本稿では,最短経路(SSP)モデルにおいて,後悔するアルゴリズムを開発するための汎用テンプレートを提案する。 まず、厳密な正のコストでモデルフリーとミニマックス最適の2つの新しいアルゴリズムを開発する。 どちらのアルゴリズムも高度にスパースな更新を認めており、既存のアルゴリズムよりも計算効率が良い。
  論文  参考訳（メタデータ） (2021-06-15T19:15:17Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Bayes DistNet -- A Robust Neural Network for Algorithm Runtime Distribution Predictions [1.8275108630751844]
  ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。 従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。 この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
  論文  参考訳（メタデータ） (2020-12-14T01:15:39Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。 意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。 この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
  論文  参考訳（メタデータ） (2020-12-13T04:47:37Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)

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

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