論文の概要: Accelerated Rates between Stochastic and Adversarial Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2303.03272v1
• Date: Mon, 6 Mar 2023 16:41:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-07 15:18:26.304360
• Title: Accelerated Rates between Stochastic and Adversarial Online Convex Optimization
• Title（参考訳）: 確率的および逆的オンライン凸最適化の高速化
• Authors: Sarah Sachs, Hedi Hadiji, Tim van Erven, Cristobal Guzman
• Abstract要約: 我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 完全i.d.の場合、我々の後悔の限界は加速の結果から期待される速度と一致し、オンラインからバッチへの変換によって最適に加速された速度を回復する。
• 参考スコア（独自算出の注目度）: 2.628557920905129
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic and adversarial data are two widely studied settings in online learning. But many optimization tasks are neither i.i.d. nor fully adversarial, which makes it of fundamental interest to get a better theoretical understanding of the world between these extremes. In this work we establish novel regret bounds for online convex optimization in a setting that interpolates between stochastic i.i.d. and fully adversarial losses. By exploiting smoothness of the expected losses, these bounds replace a dependence on the maximum gradient length by the variance of the gradients, which was previously known only for linear losses. In addition, they weaken the i.i.d. assumption by allowing, for example, adversarially poisoned rounds, which were previously considered in the related expert and bandit settings. In the fully i.i.d. case, our regret bounds match the rates one would expect from results in stochastic acceleration, and we also recover the optimal stochastically accelerated rates via online-to-batch conversion. In the fully adversarial case our bounds gracefully deteriorate to match the minimax regret. We further provide lower bounds showing that our regret upper bounds are tight for all intermediate regimes in terms of the stochastic variance and the adversarial variation of the loss gradients.
• Abstract（参考訳）: 確率的データと敵対的データは、オンライン学習において広く研究されている2つの設定である。 しかし、多くの最適化タスクはi.d.でも完全逆数でもないため、これらの極端点の間の世界をより理論的に理解することへの根本的な関心がある。 本研究では,オンライン凸最適化における新たな後悔の限界を,確率的i.i.d.と完全敵対的損失との補間として確立する。 期待損失の滑らかさを活用することで、この境界は最大勾配長への依存性を、以前は線形損失のみとして知られていた勾配の分散に置き換える。 さらに、彼らはi.d.仮定を弱め、例えば、以前関連する専門家や盗賊の設定で考慮されていた敵に毒を盛ったラウンドを許可する。 完全にi.i.d.の場合、我々の後悔の限界は確率的加速の結果から期待される割合と一致し、オンラインからバッチへの変換によって最適な確率的加速率を回復する。 完全な逆境の場合、我々の限界はミニマックスの後悔に合うように優しく悪化した。 さらに,我々の後悔の上限が,確率的分散と損失勾配の敵対的変動の観点から,すべての中間的レジームに対して厳密であることを示す下限を与える。

関連論文リスト

• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• Expressive Losses for Verified Robustness via Convex Combinations [67.54357965665676]
  本研究では, 過近似係数と異なる表現的損失に対する性能分布の関係について検討した。 表現性が不可欠である一方で、最悪の場合の損失のより良い近似は、必ずしも優れた堅牢性-正確性トレードオフに結びついていないことを示す。
  論文  参考訳（メタデータ） (2023-05-23T12:20:29Z)
• Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
  我々は、強い適応的後悔を最小限に抑える新しいオンライン共形予測手法を開発した。 提案手法は,すべての区間において,ほぼ最適に適応的な後悔を同時に達成できることを実証する。 実験により,本手法は実世界のタスクにおける既存の手法よりも,より優れたカバレッジと予測セットが得られることがわかった。
  論文  参考訳（メタデータ） (2023-02-15T18:59:30Z)
• Distributed Online Non-convex Optimization with Composite Regret [31.53784277195043]
  本稿では,分散オンライン一般損失に対する新たなネットワーク後悔を伴う,新たな複合後悔を提案する。 我々の知る限り、オンラインの非線形学習における最初の後悔である。
  論文  参考訳（メタデータ） (2022-09-21T04:16:33Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness [2.628557920905129]
  我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 この目的を達成するために、損失系列に関連する2つの重要な量を導入し、累積分散と対角変動と呼ぶ。 完全な i.d. の場合、我々の境界は加速の結果から期待される速度と一致し、完全に反対の場合、ミニマックスの後悔と一致するように優雅に劣化する。
  論文  参考訳（メタデータ） (2022-02-15T16:39:33Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers [31.102181563065844]
  量子的(そしてより一般的には、KL)後悔は、最高の個人専門家と競争する目標を緩和し、敵対的なデータに関して、ほとんどの専門家と競争するだけである。 最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全に対人的でも対人的でもないデータを考えることによって、対人的オンライン学習の代替緩和を提供する。 我々は、FTRLと別個のルート対数正規化器を併用したFTRLを用いて、両方のパラダイムにおいて最小限の後悔を達成し、どちらも正規Hedgeの変種と解釈できる。
  論文  参考訳（メタデータ） (2021-10-27T22:38:52Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)

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

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