論文の概要: 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.の場合、我々の境界は確率加速度の結果から期待される速度と一致し、完全な逆数の場合、ミニマックスの後悔と一致するように優雅に劣化する。
さらに, 累積確率的分散と逆変動に対して, 後悔の上限が全ての中間的レジームに対して厳密であることを示す下限を与える。
関連論文リスト
- Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。
理論上は魅力的だが、機械学習における優位性の応用は乏しい。
まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。
次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
論文 参考訳(メタデータ) (2024-02-05T03:21:23Z) - 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) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。
我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
論文 参考訳(メタデータ) (2023-07-05T13:52:10Z) - 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 [93.71361250701075]
本稿では,スムーズさを生かし,問題依存量による動的後悔の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) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳(メタデータ) (2021-06-06T19:08:53Z) - Pseudo-Convolutional Policy Gradient for Sequence-to-Sequence
Lip-Reading [96.48553941812366]
唇読解は唇運動系列から音声内容を推測することを目的としている。
seq2seqモデルの伝統的な学習プロセスには2つの問題がある。
本稿では,これら2つの問題に対処するために,PCPGに基づく新しい手法を提案する。
論文 参考訳(メタデータ) (2020-03-09T09:12:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。