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

• arxiv url: http://arxiv.org/abs/2302.04552v1
• Date: Thu, 9 Feb 2023 10:42:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-10 16:12:46.577352
• Title: Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization
• Title（参考訳）: 確率的および逆オンライン凸最適化のための最適オンラインミラーダイス
• Authors: Sijia Chen, Wei-Wei Tu, Peng Zhao, Lijun Zhang
• Abstract要約: 本稿では,SEAモデルに対する楽観的オンラインミラー降下(OMD)の理論的保証について検討する。 凸関数と滑らか関数に対して同じ$mathcalO(sqrtsigma_1:T2+sqrtSigma_1:T2)$ regret bound, without the convexity requirements of individual function。
• 参考スコア（独自算出の注目度）: 35.68009519688877
• 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}(\min\{\log (\sigma_{1:T}^2+\Sigma_{1:T}^2), (\sigma_{\max}^2 + \Sigma_{\max}^2) \log T\})$ bound, better than their $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log T)$ bound. For \mbox{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 can further extend our result to obtain dynamic regret guarantees, which are more favorable in non-stationary online scenarios. The attained results allow us to recover excess risk bounds of the stochastic setting and regret bounds of the adversarial setting, and derive new guarantees for many intermediate scenarios.
• 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}(\min\{\log (\sigma_{1:T}^2+\Sigma_{1:T}^2), (\sigma_{\max}^2 + \Sigma_{\max}^2) \log T\})$bound を $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log T)$bound とする。 \mbox{exp-concave} と滑らかな函数に対して、新しい $\mathcal{O}(d\log(\sigma_{1:T}^2+\Sigma_{1:T}^2))$bound を達成する。 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)

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

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