論文の概要: Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint

• arxiv url: http://arxiv.org/abs/2412.10703v2
• Date: Tue, 14 Jan 2025 06:02:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 02:44:50.360384
• Title: Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint
• Title（参考訳）: 制約付きオンライン学習のための二重境界キュー:損失と制約のダイナミクスによる痛みの維持
• Authors: Juncheng Wang, Bingjie Yan, Yituo Liu,
• Abstract要約: 二重有界キューを用いた制約付きオンライン学習(COLDQ)という効率的なアルゴリズムを提案する。 我々は、新しいリアプノフドリフト解析により、COLDQが$O(Tfrac1+V_x2)$動的後悔と$O(TV_g)$ハード制約違反を達成することを証明した。 強い凸損失関数の場合、COLDQはよく知られた$O(logT)$静的後悔と一致し、$O(TV_g)$ハード制約違反を維持している。
• 参考スコア（独自算出の注目度）: 5.505634045241289
• License:
• Abstract: We consider online convex optimization with time-varying constraints and conduct performance analysis using two stringent metrics: dynamic regret with respect to the online solution benchmark, and hard constraint violation that does not allow any compensated violation over time. We propose an efficient algorithm called Constrained Online Learning with Doubly-bounded Queue (COLDQ), which introduces a novel virtual queue that is both lower and upper bounded, allowing tight control of the constraint violation without the need for the Slater condition. We prove via a new Lyapunov drift analysis that COLDQ achieves $O(T^\frac{1+V_x}{2})$ dynamic regret and $O(T^{V_g})$ hard constraint violation, where $V_x$ and $V_g$ capture the dynamics of the loss and constraint functions. For the first time, the two bounds smoothly approach to the best-known $O(T^\frac{1}{2})$ regret and $O(1)$ violation, as the dynamics of the losses and constraints diminish. For strongly convex loss functions, COLDQ matches the best-known $O(\log{T})$ static regret while maintaining the $O(T^{V_g})$ hard constraint violation. We further introduce an expert-tracking variation of COLDQ, which achieves the same performance bounds without any prior knowledge of the system dynamics. Simulation results demonstrate that COLDQ outperforms the state-of-the-art approaches.
• Abstract（参考訳）: 我々は,時間的制約を伴うオンライン凸最適化と,オンラインソリューションベンチマークに対する動的後悔と,時間とともに補償された違反を許さないハード制約違反という,2つの厳密な指標を用いたパフォーマンス解析を考察する。 本稿では,制約違反をスレーター条件を必要とせずに厳密に制御できる,下界と上界の両方の新たな仮想キューを導入する,制約付きオンライン学習と二重境界キュー(COLDQ)という効率的なアルゴリズムを提案する。 我々は、新しいリアプノフドリフト解析により、COLDQ が $O(T^\frac{1+V_x}{2})$ dynamic regret と $O(T^{V_g})$ hard constraint violation, ここで、$V_x$ と $V_g$ は損失と制約関数のダイナミクスをキャプチャする。 2つの境界は、損失と制約のダイナミクスが減少するにつれて、初めて最もよく知られた$O(T^\frac{1}{2})$後悔と$O(1)$違反にスムーズに近づく。 強い凸損失関数の場合、COLDQはよく知られた$O(\log{T})$静的後悔と一致し、$O(T^{V_g})$ハード制約違反を維持している。 さらに,システムダイナミクスの事前知識を必要とせずに,同じ性能バウンダリを実現するCOLDQのエキスパート追跡変異を導入する。 シミュレーションの結果、COLDQは最先端のアプローチよりも優れていることが示された。

関連論文リスト

• Multi-point Feedback of Bandit Convex Optimization with Hard Constraints [1.8130068086063336]
  本研究では,学習者が損失関数の部分的情報に基づいて決定列を生成することを目的とした制約付き帯域凸最適化について検討する。 我々は、累積的テクスト制約違反を制約違反の指標として採用する。 我々のアルゴリズムは、凸損失関数と時間変化制約に対して、$O(d2Tmaxc,1-c)$ regret bounds と $O(d2T1-fracc2)$ cumulative hard constraint violation bounds を得る。
  論文  参考訳（メタデータ） (2023-10-17T02:43:22Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。 我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
  論文  参考訳（メタデータ） (2023-01-26T18:04:26Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
  本稿では,長期的制約を伴うオンライン凸最適化について考察する。 新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
  論文  参考訳（メタデータ） (2021-06-09T15:18:06Z)
• Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization [24.97580261894342]
  本稿では,エージェントネットワーク上の時間的制約を伴う分散オンライン凸最適化問題について考察する。 フルインフォメーションとバンディットフィードバックの2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-01T18:28:53Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。 有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。 我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
  論文  参考訳（メタデータ） (2020-07-13T16:30:47Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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