論文の概要: Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

• arxiv url: http://arxiv.org/abs/2610.10499v1
• Date: Wed, 07 Oct 2026 17:49:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:23.093216
• Title: Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
• Title（参考訳）: Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
• Abstract要約: 我々は,$$の知識を伴わずに,サブ線形後悔を実現するオラクル効率のアルゴリズムを提案する。 提案アルゴリズムはFollow-The-Perturbed-Leaderをベースとしたパラメータフリーで,ERM次元$d$のバイナリクラスに対して,1ラウンド当たりのオラクルへの単一の呼び出しで,後悔の$widetilde O(dsqrtT/)$を達成する。
• 参考スコア（独自算出の注目度）: 64.81005278014266
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however, comes at a steep price, introducing significant statistical and computational barriers. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully adversarial and fully stochastic settings by assuming that the conditional law of each covariate has density at most $1/σ$ with respect to some fixed base measure $μ$, and it is known to match the statistical and computational guarantees of classical learning while still allowing for much of the flexibility of online learning. However, existing oracle-efficient algorithms require either (i) sampling access to the base measure $μ$ or (ii) labels that are perfectly predicted by a fixed hypothesis. Both assumptions limit the applicability of these algorithms, in contrast to statistical learning, where empirical risk minimization (ERM) learns efficiently in the agnostic setting without any knowledge of the data distribution. We show that neither assumption is necessary, giving the first oracle-efficient algorithm that achieves sublinear regret in the agnostic setting without knowledge of $μ$. Our algorithm, based on Gaussian Follow-The-Perturbed-Leader, is parameter-free: it requires no knowledge of $μ$, the smoothing parameter $σ$, or the horizon $T$, and it achieves regret $\widetilde O(d\sqrt{T/σ})$ for binary classes of VC dimension $d$ with a single call to an ERM oracle per round, which is optimal up to a $\sqrt{d}$ factor. En route to establishing the regret bound, we introduce several new techniques that may be of independent interest.
• Abstract（参考訳）: オンライン学習は多くのドメインにおいて魅力的なフレームワークである。 しかし、この一般化は急激な価格となり、統計的および計算上の障壁を生じさせる。 近年、スムーズなオンライン学習は、各共変数の条件法則が少なくとも1/σ$の密度を1/σ$と仮定して、完全な逆と完全に確率的な設定を補う有望な枠組みとして現れており、従来の学習の統計的保証と計算的保証とを一致させながら、オンライン学習の柔軟性の多くを許容していることが知られている。 しかし、既存のオラクル効率のアルゴリズムはどちらも必要である。 (i)基本単位の$μ$又は (ii)固定仮説によって完全に予測されるラベル。 どちらの仮定もこれらのアルゴリズムの適用性を制限するが、統計学習とは対照的に、経験的リスク最小化(ERM)はデータ分布の知識を必要とせずに、不可知的な環境で効率的に学習する。 いずれの仮定も不要であることを示し、μ$の知識を伴わずに、サブ線形後悔を実現する最初のオラクル効率アルゴリズムを与える。 我々のアルゴリズムはガウスのFollow-The-Perturbed-Leaderに基づいており、パラメータフリーである:$μ$、滑らかなパラメータ$σ$、あるいは地平線$T$の知識は不要であり、VC次元のバイナリクラスに対して$d$に対して$\widetilde O(d\sqrt{T/σ})$は$d$となる。 後悔の限界を確立するために、我々は、独立した関心を持つ可能性のある新しいテクニックをいくつか導入する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Agnostic Smoothed Online Learning without Knowledge of the Base Measure [5.167069404528051]
  本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。 R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
  論文  参考訳（メタデータ） (2024-10-07T15:25:21Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Online non-parametric likelihood-ratio estimation by Pearson-divergence functional minimization [55.98760097296213]
  iid 観測のペア $(x_t sim p, x'_t sim q)$ が時間の経過とともに観測されるような,オンラインな非パラメトリック LRE (OLRE) のための新しいフレームワークを提案する。 本稿では,OLRE法の性能に関する理論的保証と,合成実験における実証的検証について述べる。
  論文  参考訳（メタデータ） (2023-11-03T13:20:11Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)

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

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