論文の概要: Smoothed Online Learning is as Easy as Statistical Learning

• arxiv url: http://arxiv.org/abs/2202.04690v1
• Date: Wed, 9 Feb 2022 19:22:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-12 08:59:53.634348
• Title: Smoothed Online Learning is as Easy as Statistical Learning
• Title（参考訳）: スムースオンライン学習は統計学習と同じくらい簡単
• Authors: Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin
• Abstract要約: この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
• 参考スコア（独自算出の注目度）: 77.00766067963195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Much of modern learning theory has been split between two regimes: the classical \emph{offline} setting, where data arrive independently, and the \emph{online} setting, where data arrive adversarially. While the former model is often both computationally and statistically tractable, the latter requires no distributional assumptions. In an attempt to achieve the best of both worlds, previous work proposed the smooth online setting where each sample is drawn from an adversarially chosen distribution, which is smooth, i.e., it has a bounded density with respect to a fixed dominating measure. We provide tight bounds on the minimax regret of learning a nonparametric function class, with nearly optimal dependence on both the horizon and smoothness parameters. Furthermore, we provide the first oracle-efficient, no-regret algorithms in this setting. In particular, we propose an oracle-efficient improper algorithm whose regret achieves optimal dependence on the horizon and a proper algorithm requiring only a single oracle call per round whose regret has the optimal horizon dependence in the classification setting and is sublinear in general. Both algorithms have exponentially worse dependence on the smoothness parameter of the adversary than the minimax rate. We then prove a lower bound on the oracle complexity of any proper learning algorithm, which matches the oracle-efficient upper bounds up to a polynomial factor, thus demonstrating the existence of a statistical-computational gap in smooth online learning. Finally, we apply our results to the contextual bandit setting to show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits in the case that contexts arrive in a smooth manner.
• Abstract（参考訳）: 現代の学習理論の多くは、データが独立して到達する古典的な \emph{offline} 設定と、逆向きにデータが到着する \emph{online} 設定の2つのレジームに分かれている。 前者モデルは計算的かつ統計的に抽出可能であることが多いが、後者は分布的な仮定を必要としない。 両世界のベストを達成するために、以前の研究は、各サンプルが反対に選択された分布から引き出される滑らかなオンライン設定を提案した。 ホライズンパラメータと滑らか性パラメータの両方にほぼ最適に依存する非パラメトリック関数クラスを学習するミニマックスの後悔に厳密な境界を与える。 さらに、この設定で最初のoracle効率のよいノンレグレットアルゴリズムも提供します。 特に,水平方向への最適な依存を後悔が達成するオラクル効率な不適切なアルゴリズムと,分類設定において最適な水平方向依存を有する1ラウンド当たりのオラクルコールのみを必要とする適切なアルゴリズムを提案する。 どちらのアルゴリズムも、ミニマックスレートよりも逆数の滑らかさパラメータに指数関数的に依存する。 そして、oracle効率の高い上限を多項式因子までマッチさせるような、任意の適切な学習アルゴリズムのoracle複雑性の下限を証明し、滑らかなオンライン学習における統計計算的ギャップの存在を実証する。 最後に,関数クラスが古典的な設定で学習可能な場合,コンテキストがスムーズな方法で到達した場合に,文脈的バンディットに対するオラクル効率のよい非回帰アルゴリズムが存在することを示すために,文脈的バンディット設定に適用する。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
  この研究は、複雑性という新しい概念、一般化ブラケット数を導入し、空間の大きさに対する敵の制約を結婚させる。 次に、オンライン予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化する。
  論文  参考訳（メタデータ） (2023-02-10T18:45:52Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。 一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
  論文  参考訳（メタデータ） (2022-05-25T21:31:36Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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