論文の概要: Online Convex Optimization with Long Term Constraints for Predictable Sequences

• arxiv url: http://arxiv.org/abs/2210.16735v1
• Date: Sun, 30 Oct 2022 03:50:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-01 19:58:33.032500
• Title: Online Convex Optimization with Long Term Constraints for Predictable Sequences
• Title（参考訳）: 予測可能なシーケンスに対する長期制約付きオンライン凸最適化
• Authors: Deepan Muthirayan, Jianjun Yuan, and Pramod P. Khargonekar
• Abstract要約: 我々は,長期的制約を伴うOCOと呼ばれるOCOの特定の枠組みについて検討する。 長期的制約は、オンライン最適化における更新ステップ毎に、プロジェクションの複雑さを減らす代替手段として導入される。 我々は,次の関数の情報をシーケンスで供給できる予測器を用いて,予測なしで達成できる率よりも厳密に少ない,全体的な後悔と制約違反率を達成することができることを示した。
• 参考スコア（独自算出の注目度）: 5.964436882344728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate the framework of Online Convex Optimization (OCO) for online learning. OCO offers a very powerful online learning framework for many applications. In this context, we study a specific framework of OCO called {\it OCO with long term constraints}. Long term constraints are introduced typically as an alternative to reduce the complexity of the projection at every update step in online optimization. While many algorithmic advances have been made towards online optimization with long term constraints, these algorithms typically assume that the sequence of cost functions over a certain $T$ finite steps that determine the cost to the online learner are adversarially generated. In many circumstances, the sequence of cost functions may not be unrelated, and thus predictable from those observed till a point of time. In this paper, we study the setting where the sequences are predictable. We present a novel online optimization algorithm for online optimization with long term constraints that can leverage such predictability. We show that, with a predictor that can supply the gradient information of the next function in the sequence, our algorithm can achieve an overall regret and constraint violation rate that is strictly less than the rate that is achievable without prediction.
• Abstract（参考訳）: 本稿では,オンライン学習のためのオンライン凸最適化(OCO)の枠組みを検討する。 OCOは多くのアプリケーションに対して非常に強力なオンライン学習フレームワークを提供する。 この文脈では、長期制約付き OCO と呼ばれる OCO の特定の枠組みについて検討する。 長期的制約は、オンライン最適化における更新ステップ毎のプロジェクションの複雑さを軽減する代替手段として一般的に導入される。 長期的制約を伴うオンライン最適化に向けて多くのアルゴリズムが進歩してきたが、これらのアルゴリズムは通常、オンライン学習者に対するコストを決定するための一定のT$有限ステップ上のコスト関数列が逆向きに生成されると仮定する。 多くの状況において、コスト関数のシーケンスは無関係ではなく、従って観測されたものからある時点まで予測可能である。 本稿では,シーケンスの予測可能な設定について検討する。 本稿では,このような予測可能性を活用するオンライン最適化アルゴリズムを提案する。 本研究では,次関数の次関数の勾配情報を逐次供給できる予測器を用いることで,予測なしで達成できる速度よりも厳密に少ない,全体的な後悔と制約違反率を達成することができることを示す。

関連論文リスト

• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
  この研究は、複雑性という新しい概念、一般化ブラケット数を導入し、空間の大きさに対する敵の制約を結婚させる。 次に、オンライン予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化する。
  論文  参考訳（メタデータ） (2023-02-10T18:45:52Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints [27.84415856657607]
  我々はLAAU(Learning-Assisted Algorithm Unrolling)と呼ばれる新しい機械学習支援アンローリング手法を提案する。 バックプロパゲーションによる効率的なトレーニングには、時間とともに決定パイプラインの勾配を導出します。 また、トレーニングデータがオフラインで利用可能で、オンラインで収集できる場合の2つのケースの平均的なコスト境界も提供します。
  論文  参考訳（メタデータ） (2022-12-03T20:56:29Z)
• Learning-Augmented Algorithms for Online Linear and Semidefinite Programming [9.849604820019394]
  Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。 SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。 予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
  論文  参考訳（メタデータ） (2022-09-21T19:16:29Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2022-05-02T08:48:22Z)
• Smoothed Online Combinatorial Optimization Using Imperfect Predictions [27.201074566335222]
  本研究では,不完全な予測モデルが利用できる場合のスムーズなオンライン最適化問題について検討する。 有限時間地平線計画に予測を用いることで, 全体の予測不確かさと追加の切り替えコストに依存して, 後悔を招くことを示す。 本アルゴリズムは,合成オンライン分散ストリーミング問題において,他のベースラインと比較して,累積的後悔度が大幅に向上したことを示す。
  論文  参考訳（メタデータ） (2022-04-23T02:30:39Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Online estimation and control with optimal pathlength regret [52.28457815067461]
  オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。 OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
  論文  参考訳（メタデータ） (2021-10-24T22:43:15Z)
• Delay-Tolerant Constrained OCO with Application to Network Resource Allocation [44.67787270821051]
  マルチスロットフィードバック遅延によるオンライン凸最適化(OCO)を検討します。 エージェントは、時間変動凸損失関数の蓄積を最小限に抑えるために、一連のオンライン決定を行う。 情報フィードバックと意思決定の更新の非同期性に取り組むために,二重正規化による新たな制約ペナルティを用いた遅延耐性制約OCOを提案する。
  論文  参考訳（メタデータ） (2021-05-09T19:32:33Z)

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

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