論文の概要: Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2302.04552v2
• Date: Tue, 22 Aug 2023 04:36:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-23 21:21:58.028385
• Title: Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization
• Title（参考訳）: 確率的および逆オンライン凸最適化のための最適オンラインミラーダイス
• Authors: Sijia Chen, Yu-Jie Zhang, Wei-Wei Tu, Peng Zhao, Lijun Zhang
• Abstract要約: 本稿では,SEAモデルに対する楽観的オンラインミラー降下(OMD)の理論的保証について検討する。 強い凸と滑らかな関数に対して、$mathcalO(sigma_max2 + Sigma_max2) log T よりも優れた $mathcalO(sigma_max2 + Sigma_max2) log T を確立する。 非定常シナリオにおける静的な後悔境界よりも有利な凸関数と滑らかな関数を持つモデルに対する最初の動的後悔保証を確立する。
• 参考スコア（独自算出の注目度）: 43.12420397778763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastically Extended Adversarial (SEA) model is introduced by Sachs et al. [2022] as an interpolation between stochastic and adversarial online convex optimization. Under the smoothness condition, they demonstrate that the expected regret of optimistic follow-the-regularized-leader (FTRL) depends on the cumulative stochastic variance $\sigma_{1:T}^2$ and the cumulative adversarial variation $\Sigma_{1:T}^2$ for convex functions. They also provide a slightly weaker bound based on the maximal stochastic variance $\sigma_{\max}^2$ and the maximal adversarial variation $\Sigma_{\max}^2$ for strongly convex functions. Inspired by their work, we investigate the theoretical guarantees of optimistic online mirror descent (OMD) for the SEA model. For convex and smooth functions, we obtain the same $\mathcal{O}(\sqrt{\sigma_{1:T}^2}+\sqrt{\Sigma_{1:T}^2})$ regret bound, without the convexity requirement of individual functions. For strongly convex and smooth functions, we establish an $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log (\sigma_{1:T}^2+\Sigma_{1:T}^2))$ bound, better than their $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log T)$ result. For exp-concave and smooth functions, we achieve a new $\mathcal{O}(d\log(\sigma_{1:T}^2+\Sigma_{1:T}^2))$ bound. Owing to the OMD framework, we broaden our work to study dynamic regret minimization and scenarios where the online functions are non-smooth. We establish the first dynamic regret guarantee for the SEA model with convex and smooth functions, which is more favorable than static regret bounds in non-stationary scenarios. Furthermore, to deal with non-smooth and convex functions in the SEA model, we propose novel algorithms building on optimistic OMD with an implicit update, which provably attain static regret and dynamic regret guarantees without smoothness conditions.
• Abstract（参考訳）: Stochastically Extended Adversarial (SEA) モデルは Sachs らによって導入された。 2022] 確率的および逆的オンライン凸最適化の補間である。 滑らかさ条件の下では、楽観的追従正規化リーダ(FTRL)の期待された後悔は、凸函数に対する累積確率分散$\sigma_{1:T}^2$と累積逆変分$\Sigma_{1:T}^2$に依存することを示した。 これらはまた、強凸函数に対して最大確率分散 $\sigma_{\max}^2$ と最大逆変量 $\sigma_{\max}^2$ に基づくわずかに弱い境界を与える。 本研究は,SEAモデルに対する楽観的オンラインミラー降下(OMD)の理論的保証について考察する。 凸函数と滑らかな函数に対しては、個々の函数の凸性要件なしに同じ$\mathcal{O}(\sqrt{\sigma_{1:T}^2}+\sqrt{\Sigma_{1:T}^2})$ regret boundが得られる。 強凸かつ滑らかな函数に対しては、$\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log (\sigma_{1:T}^2+\Sigma_{1:T}^2))$bound を $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log T)$ result とする。 exp-concave と smooth 関数に対しては、新しい $\mathcal{o}(d\log(\sigma_{1:t}^2+\sigma_{1:t}^2))$ bound が得られる。 OMDフレームワークにより、動的後悔の最小化とオンライン機能が非滑らかなシナリオについて研究する作業を広げる。 非定常シナリオでは静的な後悔の限界よりも有利な凸と滑らかな関数を持つseaモデルに対する最初の動的後悔の保証を確立する。 さらに,SEAモデルにおける非平滑関数と凸関数を扱うために,暗黙の更新を施した楽観的OMD上に構築した新しいアルゴリズムを提案する。

関連論文リスト

• Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD [16.019880089338383]
  Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsff
  論文  参考訳（メタデータ） (2024-10-26T10:14:17Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
  実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。 さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
  論文  参考訳（メタデータ） (2023-11-09T14:29:25Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
  オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。 このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。 本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
  論文  参考訳（メタデータ） (2021-02-16T20:54:49Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
  本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
  論文  参考訳（メタデータ） (2020-01-25T14:44:53Z)

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

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