論文の概要: Optimal Rates for Learning with Monotone Adversaries

• arxiv url: http://arxiv.org/abs/2608.06337v1
• Date: Thu, 06 Aug 2026 17:45:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-07 15:25:20.988526
• Title: Optimal Rates for Learning with Monotone Adversaries
• Title（参考訳）: モノトーンによる学習における最適率
• Abstract要約: モノトン対向は、i.i.d.ラベル付きサンプルを観察し、その選択の有限個の例を付加する。 すべてのサンプルは正しくラベル付けされているが、挿入はクリーンサンプルに依存するため、組み合わせたサンプルは交換できない。 このモデルを導入したLarsen、Pabbaraju、およびShettyは、VC次元$d$のクラスに対して、経験的リスク最小化が予測誤差$O((d/n)log(n/d))$に達することを示した。
• 参考スコア（独自算出の注目度）: 7.053805156684374
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error $O((d/n)\log(n/d))$ for classes of VC dimension $d$, and that every known optimal learner can be pushed away from the $Θ(d/n)$ rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension $d$ and over known finite insertion budgets, the minimax expected error is $Θ(1/n)$ at $d=1$ and $Θ((d/n)\log(n/d))$ for $d\geq 2$. The same rates hold with Littlestone dimension $d_{\mathrm L}$ in place of $d$, so the clean online-to-batch rate $O(d_{\mathrm L}/n)$ is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.
• Abstract（参考訳）: 単調逆数(英語版)は、i.i.d.ラベル付きサンプルを観察し、その選択の有限個の例を追加し、それぞれがターゲット仮説によって正しくラベル付けされる。 学習者は、組み合わせたサンプルの均一なシャッフルを見て、元の分布にスコアを付ける。 すべてのサンプルは正しくラベル付けされているが、挿入はクリーンサンプルに依存するため、組み合わせたサンプルは交換できない。 このモデルを導入したLarsen, Pabbaraju, Shettyの両氏は,VC次元のクラスに対して,経験的リスク最小化が期待誤差$O((d/n)\log(n/d))$を達成し,既知のすべての学習者は,PAC学習に最適な99(d/n)$レートから押し出すことができることを示した。 彼らは、余分な対数がこれらの特定のアルゴリズムの人工物なのか、または交換可能性の欠如による本質的な結果なのかを尋ねた。 私たちは、この追加コストがVC次元1を超えていることを示します。 VC 次元 $d$ および既知の有限挿入予算のクラスに対する最悪の場合、ミニマックス予想誤差は $d=1$ で$d((d/n)\log(n/d))$ for $d\geq 2$ である。 同じレートはLittlestone次元$d_{\mathrm L}$の代わりに$d$で成り立つので、クリーンなオンラインバッチレート$O(d_{\mathrm L}/n)$も達成できない。 このように、正しくラベル付けされた例を追加することは、オンライン学習において有限の誤り境界を持つクラスであっても、対数的因子によって学習を困難にすることができる。 次元1の上界は、分析を行う単純な不適切な学習者によって達成される。 明示的なクラスと、非無視質量の点が異なる2つのターゲット仮説が同じサンプルを生成する前である。

関連論文リスト

• Multiscale Reward Hedging from Correct Demonstrations [1.14219428942199]
  既存の報酬ヘッジ保証は、有限報酬クラスを仮定する。 鍵となるのは、あらゆる精度の尺度で寛容な最適性テストよりも、ひとつの共有投票でヘッジすることです。
  論文  参考訳（メタデータ） (2026-08-07T05:36:22Z)
• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  本研究では,マッサートノイズの存在下での漂流概念の学習問題について検討する。 このフレームワークでは、オンライン学習者は独立したサンプルの履歴にアクセスすることができる。 目標は、各ラウンドで小さな予測誤差の仮説を出力することである。
  論文  参考訳（メタデータ） (2026-06-09T17:35:18Z)
• Hard labels sampled from sparse targets mislead rotation invariant algorithms [6.565070116874382]
  バイナリロジスティック回帰では、フィードバックはデータの真の条件付き確率に対応するソフトラベルか、あるいはハードラベルをサンプリングすることができる。 条件分布$(mathbfx_itopmathbfwstar)$と$mathbfwstar$が$s$-sparseである場合、回転不変アルゴリズムは確実に準最適であることを示す。
  論文  参考訳（メタデータ） (2026-03-21T22:38:24Z)
• Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds [16.636823007179082]
  我々は, [Goel et al. 2017] が導入した対戦型インジェクションモデルを用いてオンライン学習を研究する。 一致する$(sqrtT)$ down bound for VC dimension $1$を証明し、2つの情報体制の鮮明な分離を確立します。 敵の汚染に対する耐性が保たれていることを予測するためのラベル付きサンプルの小さなサブセットである、インプロバストな目撃者によって駆動される潜在的基盤フレームワークを導入する。
  論文  参考訳（メタデータ） (2026-02-23T18:30:48Z)
• Self-Directed Linear Classification [50.659479930171585]
  オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。 そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
  論文  参考訳（メタデータ） (2023-08-06T15:38:44Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  プライバシー制約下でのオンライン分類の問題点を考察する。 この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。 学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
  論文  参考訳（メタデータ） (2021-06-25T09:08:33Z)
• Learning the optimal regularizer for inverse problems [1.763934678295407]
  線形逆問題 $y=Ax+epsilon$ を考えると、$Acolon Xto Y$ は分離可能なヒルベルト空間 $X$ と $Y$ の間の既知の線型作用素である。 この設定は、デノイング、デブロアリング、X線トモグラフィーなど、画像のいくつかの逆問題を含んでいる。 古典的な正規化の枠組みの中では、正規化関数が優先順位を与えられず、データから学習される場合に焦点を当てる。
  論文  参考訳（メタデータ） (2021-06-11T17:14:27Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)

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

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