論文の概要: Multi-Objective $\textit{min-max}$ Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2510.13560v1
- Date: Wed, 15 Oct 2025 13:59:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-16 20:13:28.691222
- Title: Multi-Objective $\textit{min-max}$ Online Convex Optimization
- Title（参考訳）: Multi-Objective $\textit{min-max}$ Online Convex Optimization
- Authors: Rahul Vaze, Sumiran Mishra,
- Abstract要約: オンライン凸最適化(OCO)では、1つの損失関数列がT$の時間的水平線上で明らかにされる。
本稿では,多目的OCOについて考察する。
期待されている$textitmin-max$ regretが$O(sqrtT log K)$であることを示す。
- 参考スコア（独自算出の注目度）: 4.6838063911731025
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In online convex optimization (OCO), a single loss function sequence is revealed over a time horizon of $T$, and an online algorithm has to choose its action at time $t$, before the loss function at time $t$ is revealed. The goal of the online algorithm is to incur minimal penalty (called $\textit{regret}$ compared to a static optimal action made by an optimal offline algorithm knowing all functions of the sequence in advance. In this paper, we broaden the horizon of OCO, and consider multi-objective OCO, where there are $K$ distinct loss function sequences, and an algorithm has to choose its action at time $t$, before the $K$ loss functions at time $t$ are revealed. To capture the tradeoff between tracking the $K$ different sequences, we consider the $\textit{min-max}$ regret, where the benchmark (optimal offline algorithm) takes a static action across all time slots that minimizes the maximum of the total loss (summed across time slots) incurred by each of the $K$ sequences. An online algorithm is allowed to change its action across time slots, and its {\it min-max} regret is defined as the difference between its $\textit{min-max}$ cost and that of the benchmark. The $\textit{min-max}$ regret is a stringent performance measure and an algorithm with small regret needs to `track' all loss function sequences closely at all times. We consider this $\textit{min-max}$ regret in the i.i.d. input setting where all loss functions are i.i.d. generated from an unknown distribution. For the i.i.d. model we propose a simple algorithm that combines the well-known $\textit{Hedge}$ and online gradient descent (OGD) and show via a remarkably simple proof that its expected $\textit{min-max}$ regret is $O(\sqrt{T \log K})$.
- Abstract（参考訳）: オンライン凸最適化(OCO)では、1つの損失関数シーケンスがT$の時間軸で明らかにされ、オンラインアルゴリズムは、損失関数がt$になる前に、そのアクションをt$で選択する必要がある。
オンラインアルゴリズムの目標は最小限のペナルティ($\textit{regret}$と呼ばれる)を、前もってシーケンスのすべての機能を知る最適のオフラインアルゴリズムが行う静的な最適動作と比較することである。
本稿では,OCOの地平線を広げ,多目的OCOを考える。ここでは,損失関数列は$K$で,アルゴリズムは時間で$t$で,時間で$K$の損失関数が明らかにされる前に,その動作を選択する必要がある。
ここでは、ベンチマーク(最適オフラインアルゴリズム)がすべての時間スロットにまたがる静的なアクションを採り、K$の各シーケンスによって引き起こされる総損失(タイムスロットにまたがる)の最大値を最小限にする。
オンラインアルゴリズムは時間帯で動作を変更することができ、その後悔は$\textit{min-max}$コストとベンチマークの違いとして定義される。
$\textit{min-max}$ regretは厳密なパフォーマンス尺度であり、小さな後悔を伴うアルゴリズムは全ての損失関数列を常に「追跡」する必要がある。
この$\textit{min-max}$ regret in the i.i.d. input set where all loss function are i.i.d. generated from a unknown distribution。
i.d.モデルでは、よく知られた$\textit{Hedge}$とオンライン勾配降下(OGD)を組み合わせた単純なアルゴリズムを提案し、予想される$\textit{min-max}$後悔が$O(\sqrt{T \log K})$であることを驚くほど単純な証明で示す。
関連論文リスト
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback [6.390468088226495]
曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。
次数$minsigma_maxln T, sqrtd_mathrmtot$を後悔する規則化リーダの変種を提案する。
次に、exp-concave損失を検討し、適応的な学習率チューニングで遅延を処理するためにOnline Newton Stepアルゴリズムを拡張した。
論文 参考訳（メタデータ） (2025-06-09T09:49:54Z) - Near-Optimal Algorithms for Omniprediction [6.874077229518565]
オンライン設定とオフライン設定の両方で、オムニプレディションのためのほぼ最適学習アルゴリズムを提供します。
オンライン学習アルゴリズムは、様々な尺度でほぼ最適な複雑さを実現する。
オフライン学習アルゴリズムは効率的な$(mathcalL_mathrmBV,mathcalH,varepsilon(m)$)を返す
論文 参考訳（メタデータ） (2025-01-28T02:58:37Z) - An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
逆制約を伴うオンライン凸最適化(OCO)について検討する。
本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。
以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
論文 参考訳（メタデータ） (2024-12-11T03:06:42Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - An Efficient Interior-Point Method for Online Convex Optimization [31.771131314017385]
アルゴリズムは適応的であり、後悔のバウンドは1,ldots,T$だけでなく、すべてのサブインターバル$s,s+1,ldots,t$に対しても保持される。
アルゴリズムの実行時間は、新しいインテリアポイントアルゴリズムと一致し、後悔の最小化を行う。
論文 参考訳（メタデータ） (2023-07-21T16:12:46Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。
我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
論文 参考訳（メタデータ） (2022-11-27T20:38:47Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。