論文の概要: Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions

• arxiv url: http://arxiv.org/abs/2202.12843v1
• Date: Fri, 25 Feb 2022 17:35:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-28 16:07:13.690385
• Title: Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions
• Title（参考訳）: 比較的滑らかな凸コスト関数に対するオンラインミラー降下の動的後悔
• Authors: Nima Eshraghi and Ben Liang
• Abstract要約: リプシッツ連続性も均一な滑らか性も存在しない場合でも、動的後悔を束縛することは可能であることを示す。 次に、相対的に強い凸性の付加条件により、動的後悔は経路長と勾配変化によって境界付けられることを示す。
• 参考スコア（独自算出の注目度）: 30.412826613009518
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The performance of online convex optimization algorithms in a dynamic environment is often expressed in terms of the dynamic regret, which measures the decision maker's performance against a sequence of time-varying comparators. In the analysis of the dynamic regret, prior works often assume Lipschitz continuity or uniform smoothness of the cost functions. However, there are many important cost functions in practice that do not satisfy these conditions. In such cases, prior analyses are not applicable and fail to guarantee the optimization performance. In this letter, we show that it is possible to bound the dynamic regret, even when neither Lipschitz continuity nor uniform smoothness is present. We adopt the notion of relative smoothness with respect to some user-defined regularization function, which is a much milder requirement on the cost functions. We first show that under relative smoothness, the dynamic regret has an upper bound based on the path length and functional variation. We then show that with an additional condition of relatively strong convexity, the dynamic regret can be bounded by the path length and gradient variation. These regret bounds provide performance guarantees to a wide variety of online optimization problems that arise in different application domains. Finally, we present numerical experiments that demonstrate the advantage of adopting a regularization function under which the cost functions are relatively smooth.
• Abstract（参考訳）: 動的環境におけるオンライン凸最適化アルゴリズムの性能は、時間変動コンパレータのシーケンスに対して決定者のパフォーマンスを測定する動的後悔の観点から表されることが多い。 動的後悔の分析において、先行研究はしばしばコスト関数のリプシッツ連続性や一様滑らかさを仮定する。 しかし、実際にはこれらの条件を満たさない重要なコスト関数が多数存在する。 このような場合、事前解析は適用できず、最適化性能を保証できない。 このレターでは、リプシッツ連続性も均一な滑らか性も存在しない場合でも、動的後悔の束縛が可能であることを示す。 コスト関数に対するより穏やかな要求であるユーザ定義正規化関数に対して、相対的滑らかさの概念を採用する。 まず, 相対的な滑らかさの下では, 動的後悔は経路長と機能的変動に基づいて上限を持つことを示す。 次に、相対的に強い凸性の付加条件により、動的後悔は経路長と勾配変化によって境界付けられることを示す。 これらの残念な境界は、異なるアプリケーションドメインで発生する様々なオンライン最適化問題に対して、パフォーマンスを保証する。 最後に,コスト関数が比較的滑らかな正規化関数を採用する利点を示す数値実験を行う。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Contextual Continuum Bandits: Static Versus Dynamic Regret [70.71582850199871]
  本研究では,学習者が側情報ベクトルを逐次受信し,凸集合内の行動を選択する,文脈連続帯域幅問題について検討する。 線形な静的な後悔を実現するアルゴリズムは,任意のアルゴリズムを拡張して,線形な動的後悔を実現することができることを示す。 インテリアポイント法にインスパイアされ,自己協和障壁を用いるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-09T10:12:08Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization [0.0]
  We study the problem of global optimization, where we analyze the performance of the Piyavskii-Shubert algorithm and its variants。 その結果,提案アルゴリズムはクエリを効率よく決定し,最小限の(ログファクタまで)累積的後悔を実現する。
  論文  参考訳（メタデータ） (2021-08-24T17:36:33Z)
• Value Iteration in Continuous Actions, States and Time [99.00362538261972]
  連続状態と動作に対する連続的適合値反復(cFVI)アルゴリズムを提案する。 非線形制御アフィンダイナミクスに対して最適なポリシを導出することができる。 物理システムのビデオは、urlhttps://sites.google.com/view/value-iteration.comで入手できる。
  論文  参考訳（メタデータ） (2021-05-10T21:40:56Z)
• A closer look at temporal variability in dynamic online learning [19.468067110814808]
  この作品は、完全な情報でオンライン学習の文脈でダイナミックな後悔の設定に焦点を当てています。 損失関数の列は時間とともに大きく変化しないと仮定することにより、既存の結果と比較して改善された後悔境界を導き出すことが可能であることを示す。
  論文  参考訳（メタデータ） (2021-02-15T16:50:16Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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