論文の概要: Between Stochastic and Adversarial Online Convex Optimization: Improved
Regret Bounds via Smoothness
- arxiv url: http://arxiv.org/abs/2202.07554v1
- Date: Tue, 15 Feb 2022 16:39:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-16 14:22:42.635478
- Title: Between Stochastic and Adversarial Online Convex Optimization: Improved
Regret Bounds via Smoothness
- Title（参考訳）: 確率的・対向的オンライン凸最適化:滑らか性による回帰境界の改善
- Authors: Sarah Sachs, H\'edi Hadiji, Tim van Erven, Crist\'obal Guzm\'an
- Abstract要約: 我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。
この目的を達成するために、損失系列に関連する2つの重要な量を導入し、累積分散と対角変動と呼ぶ。
完全な 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 adversarially poisoned rounds or shifts in the data
distribution. To accomplish this goal, we introduce two key quantities
associated with the loss sequence, that we call the cumulative stochastic
variance and the adversarial variation. Our upper bounds are attained by
instances of optimistic follow the regularized leader, and we design adaptive
learning rates that automatically adapt to the cumulative stochastic variance
and adversarial variation. In the fully i.i.d. case, our bounds match the rates
one would expect from results in stochastic acceleration, and in the fully
adversarial case they gracefully deteriorate to match the minimax regret. We
further provide lower bounds showing that our regret upper bounds are tight for
all intermediate regimes for the cumulative stochastic variance and the
adversarial variation.
- Abstract（参考訳）: 確率的データと敵対的データは、オンライン学習において広く研究されている2つの設定である。
しかし、多くの最適化タスクはi.d.でも完全逆数でもないため、これらの極端点の間の世界をより理論的に理解することへの根本的な関心がある。
本研究では,オンライン凸最適化における新たな後悔の限界を,確率的i.i.d.と完全敵対的損失との補間として確立する。
期待損失の滑らかさを活用することで、この境界は最大勾配長への依存性を、以前は線形損失のみとして知られていた勾配の分散に置き換える。
さらに、逆毒のラウンドやデータ分散のシフトを許可することで、i.i.d.の仮定を弱める。
この目的を達成するために、損失系列に関連する2つの重要な量を導入し、累積確率分散と対角変動と呼ぶ。
我々の上限は、定型化リーダに従う楽観的な事例によって達成され、累積確率変動と対角変動に自動的に適応する適応学習率を設計する。
完全なi.d.の場合、我々の境界は確率加速度の結果から期待される速度と一致し、完全な逆数の場合、ミニマックスの後悔と一致するように優雅に劣化する。
さらに, 累積確率的分散と逆変動に対して, 後悔の上限が全ての中間的レジームに対して厳密であることを示す下限を与える。
関連論文リスト
- LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。
我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
論文 参考訳（メタデータ） (2024-08-12T17:08:31Z) - Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。
理論上は魅力的だが、機械学習における優位性の応用は乏しい。
まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。
次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
論文 参考訳（メタデータ） (2024-02-05T03:21:23Z) - TIC-TAC: A Framework for Improved Covariance Estimation in Deep Heteroscedastic Regression [109.69084997173196]
奥行き回帰は、予測分布の平均と共分散を負の対数類似度を用いて共同最適化する。
近年の研究では, 共分散推定に伴う課題により, 準最適収束が生じる可能性が示唆されている。
1)予測共分散は予測平均のランダム性を真に捉えているか?
その結果, TICは共分散を正確に学習するだけでなく, 負の対数類似性の収束性の向上も促進することがわかった。
論文 参考訳（メタデータ） (2023-10-29T09:54:03Z) - 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) - Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。
我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。
具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
論文 参考訳（メタデータ） (2023-04-18T17:57:31Z) - Accelerated Rates between Stochastic and Adversarial Online Convex
Optimization [2.628557920905129]
我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。
完全i.d.の場合、我々の後悔の限界は加速の結果から期待される速度と一致し、オンラインからバッチへの変換によって最適に加速された速度を回復する。
論文 参考訳（メタデータ） (2023-03-06T16:41:57Z) - Regret Minimization and Convergence to Equilibria in General-sum Markov
Games [57.568118148036376]
汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。
我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
論文 参考訳（メタデータ） (2022-07-28T16:27:59Z) - 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) - Pseudo-Convolutional Policy Gradient for Sequence-to-Sequence
Lip-Reading [96.48553941812366]
唇読解は唇運動系列から音声内容を推測することを目的としている。
seq2seqモデルの伝統的な学習プロセスには2つの問題がある。
本稿では,これら2つの問題に対処するために,PCPGに基づく新しい手法を提案する。
論文 参考訳（メタデータ） (2020-03-09T09:12:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。