論文の概要: Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions

• arxiv url: http://arxiv.org/abs/2006.05876v2
• Date: Wed, 14 Apr 2021 06:35:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-23 04:40:06.370195
• Title: Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
• Title（参考訳）: 強凸関数と滑らか関数の動的後悔に関する改良解析
• Authors: Peng Zhao and Lijun Zhang
• Abstract要約: OMGDの動的な後悔は、少なくとも$mathcalO(minmathcalP_T,mathcalS_T)$であり、$mathcalP_T$と$mathcalS_T$はパス長と2乗パス長である。 我々は、改良された解析により、OMGDの動的後悔を$mathcalO(minmathcalP_T,mathcalS_T,mathcalに改善できることを実証した。
• 参考スコア（独自算出の注目度）: 24.445848532264307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present an improved analysis for dynamic regret of strongly convex and smooth functions. Specifically, we investigate the Online Multiple Gradient Descent (OMGD) algorithm proposed by Zhang et al. (2017). The original analysis shows that the dynamic regret of OMGD is at most $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T\})$, where $\mathcal{P}_T$ and $\mathcal{S}_T$ are path-length and squared path-length that measures the cumulative movement of minimizers of the online functions. We demonstrate that by an improved analysis, the dynamic regret of OMGD can be improved to $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T,\mathcal{V}_T\})$, where $\mathcal{V}_T$ is the function variation of the online functions. Note that the quantities of $\mathcal{P}_T, \mathcal{S}_T, \mathcal{V}_T$ essentially reflect different aspects of environmental non-stationarity -- they are not comparable in general and are favored in different scenarios. Therefore, the dynamic regret presented in this paper actually achieves a \emph{best-of-three-worlds} guarantee and is strictly tighter than previous results.
• Abstract（参考訳）: 本稿では,強い凸関数と滑らか関数の動的後悔に関する解析を改良した。 具体的には Zhang et al. (2017) が提案した Online Multiple Gradient Descent (OMGD) アルゴリズムについて検討する。 元々の分析によれば、omgdの動的後悔は最大で$\mathcal{o}(\min\{\mathcal{p}_t,\mathcal{s}_t\})$であり、ここで$\mathcal{p}_t$ と $\mathcal{s}_t$ はオンライン関数の最小値の累積運動を測定する経路長と二乗経路長である。 我々は、OMGDの動的後悔を改良した分析により、$\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T,\mathcal{V}_T\})$に改善できることを示した。 ただし、$\mathcal{p}_t, \mathcal{s}_t, \mathcal{v}_t$ の量は基本的に環境非定常性の異なる側面を反映している。 したがって、本論文で提示された動的後悔は、実際には「三世界最強」保証を達成し、以前の結果よりも厳密である。

関連論文リスト

• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties [21.141544548229774]
  我々は$min_x max_y f(x, y) という形式で、$mathcalN$ は Hadamard である。 我々は、勾配収束定数を減少させることにより、グローバルな関心が加速されることを示す。
  論文  参考訳（メタデータ） (2023-05-25T15:43:07Z)
• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。 我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。 本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
  論文  参考訳（メタデータ） (2023-05-19T15:02:10Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization [40.19608203064051]
  本稿では,SEAモデルに対する楽観的オンラインミラー降下(OMD)の理論的保証について検討する。 強い凸と滑らかな関数に対して、$mathcalO(sigma_max2 + Sigma_max2) log T よりも優れた $mathcalO(sigma_max2 + Sigma_max2) log T を確立する。 非定常シナリオにおける静的な後悔境界よりも有利な凸関数と滑らかな関数を持つモデルに対する最初の動的後悔保証を確立する。
  論文  参考訳（メタデータ） (2023-02-09T10:42:11Z)
• Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP [46.86114958340962]
  我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。 我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
  論文  参考訳（メタデータ） (2022-07-22T15:00:15Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• 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)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Combinatorial Semi-Bandit in the Non-Stationary Environment [27.394284055156795]
  スイッチングケースと動的ケースの両方において,非定常半帯域問題について検討する。 別の手法を用いることで、我々のアルゴリズムは $mathcal S$ あるいは $mathcal V$ のパラメータをもはや知る必要がなくなるが、後悔する境界は準最適になる可能性がある。
  論文  参考訳（メタデータ） (2020-02-10T07:10:56Z)

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

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