論文の概要: When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory
- arxiv url: http://arxiv.org/abs/2608.14020v1
- Date: Fri, 14 Aug 2026 07:07:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-17 20:14:29.301183
- Title: When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory
- Title（参考訳）: 正しいデータ処理はいつ行うか? -挿入安定性と次元理論の限界-
- Abstract要約: クリーンPAC率よりも高い対数係数であるTheta((d/n)log(en/d))よりも予測される誤差を保証できないことを示す。
より正確にラベル付けされた例を入力すれば,学習者の挿入安定度は低下する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Adding data known to be correct ought to be safe. Not always. Larsen, Pabbaraju and Shetty model the failure with a monotone adversary, which reads an i.i.d. training sample and may append as many further examples as it likes, provided the target hypothesis labels them all. Mehrotra has since settled the cost, showing that for classes of VC dimension d >= 2 no learner can guarantee expected error better than Theta((d/n)log(en/d)), a logarithmic factor above the clean PAC rate. Because that rate is a worst case over all classes, it says nothing about which classes actually suffer the penalty, and the answer turns on the learner. We call a learner insertion-stable if feeding it more correctly labeled examples can only shrink the region where it errs. Such learners are immune to the adversary, since on any given sample the risk after insertions never exceeds the risk on the clean part alone, however much is added and however cleverly it is chosen. High- probability guarantees carry over unchanged, and because Closure is insertion-stable every intersection-closed class keeps its clean rate of E[Err] <= (21d+34)/n. Immunity is not something the classical dimensions can predict. Two classes can agree on VCdim = Ldim = 2 and still split, one at Theta(1/n) and the other at Theta(log(en)/n), while intervals have unbounded Littlestone dimension and are immune anyway. On Mehrotra's hard class we prove more than the failure of a single algorithm, showing that no monotone permutation-invariant compression scheme of any finite size attains the clean rate. The question is therefore not whether a class is hard, nor whether a learner is good, but whether the two suit each other. Given an insertion-stable learner that is optimal on clean data, correct additions are free, and without one the cost belongs to the class, so changing the learner will not avoid it.
- Abstract（参考訳）: 正しいことがわかっているデータを追加することは安全であるべきだ。
いつもではない。
Larsen, Pabbaraju と Shetty は、単調な逆数体で失敗をモデル化し、i.d.のトレーニングサンプルを読み、さらに多くのサンプルを追加することができる。
その後、Mehrotraはコストを下げ、VC次元 d >= 2 のクラスでは、クリーン PAC よりも高い対数係数である Theta((d/n)log(en/d)) よりも期待されるエラーを保証できないことを示した。
この率はすべてのクラスで最悪のケースであるため、どのクラスが実際にペナルティに苦しむかについては何も述べておらず、答えは学習者によって変わる。
より正確にラベル付けされた例を入力すれば,学習者の挿入安定度は低下する。
このような学習者は、あらゆるサンプルにおいて、挿入後のリスクは、クリーンな部分のみのリスクを超えることはないが、多くが追加され、巧妙に選択されるため、敵に免疫がある。
クロージャは挿入安定であるため、交叉閉クラスはE[Err] <= (21d+34)/n のクリーンレートを保持する。
免疫は古典的な次元が予測できるものではない。
2つのクラスは VCdim = Ldim = 2 で一致し、1つは Theta(1/n) で、もう1つは Theta(log(en)/n) で一致する。
メロトラのハードクラスでは、1つのアルゴリズムの失敗以上のことを証明し、任意の有限サイズのモノトーン置換不変圧縮スキームがクリーンレートに達することが示される。
したがって、クラスが難しいのか、学習者が良いのか、あるいは2つのクラスが互いに合うのかは問わない。
クリーンなデータに最適な挿入安定学習者が与えられた場合、正しい追加は無料であり、それなしでは、コストはクラスに属するので、学習者を変更することは避けられない。
関連論文リスト
- Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
モノトン対向は、i.i.d.ラベル付きサンプルを観察し、その選択の有限個の例を付加する。
すべてのサンプルは正しくラベル付けされているが、挿入はクリーンサンプルに依存するため、組み合わせたサンプルは交換できない。
このモデルを導入したLarsen、Pabbaraju、およびShettyは、VC次元$d$のクラスに対して、経験的リスク最小化が予測誤差$O((d/n)log(n/d))$に達することを示した。
論文 参考訳（メタデータ） (2026-08-06T17:45:32Z) - Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
本研究では,マッサートノイズの存在下での漂流概念の学習問題について検討する。
このフレームワークでは、オンライン学習者は独立したサンプルの履歴にアクセスすることができる。
目標は、各ラウンドで小さな予測誤差の仮説を出力することである。
論文 参考訳（メタデータ） (2026-06-09T17:35:18Z) - Distribution-Free Sequential Prediction with Abstentions [7.110627876507878]
本研究では, 敵が任意の数の敵インスタンスを任意に注入することを許容する逐次予測問題について検討する。
各ラウンドにおいて、学習者はインスタンスが実際に破損した場合、ペナルティを発生させることなく予測を行うことも強調できる。
本稿では,弱い学習者の強化手順に基づくtextscAbstainBoostを提案する。
論文 参考訳（メタデータ） (2026-02-20T00:28:27Z) - Partial Feedback Online Learning [88.27143767009376]
我々は、偏見フィードバックオンライン学習と呼ばれる新しい学習プロトコルについて研究する。
各インスタンスは許容できるラベルのセットを許可するが、学習者は1ラウンドごとに許容できるラベルを1つだけ観察する。
論文 参考訳（メタデータ） (2026-01-29T09:39:11Z) - Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。
そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
論文 参考訳（メタデータ） (2025-02-14T18:41:53Z) - Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs [32.29254118429081]
我々は,帯域幅フィードバックの下での最適誤りが,全情報ケースの最適誤りよりも少なくとも$O(k)$倍高いことを示す。
また、ランダム化学習者と決定論的学習者の間のギャップに対して、$tildeTheta(k)$のほぼ最適な境界を示す。
論文 参考訳（メタデータ） (2024-02-12T07:20:05Z) - Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
そこで我々はShrinkMatchと呼ばれる新しい手法を提案し、不確実なサンプルを学習する。
それぞれの不確実なサンプルに対して、元の Top-1 クラスを単に含むスランク類空間を適応的に求める。
次に、スランク空間における強と弱に強化された2つのサンプル間の整合正則化を課し、識別的表現を試みます。
論文 参考訳（メタデータ） (2023-08-13T14:05:24Z) - Lethal Dose Conjecture on Data Poisoning [122.83280749890078]
データ中毒は、悪意のある目的のために機械学習アルゴリズムのトレーニングセットを歪ませる敵を考える。
本研究は, 致死線量導出法(Lethal Dose Conjecture)とよばれるデータ中毒の基礎について, 1つの予想を立証するものである。
論文 参考訳（メタデータ） (2022-08-05T17:53:59Z) - Equivariance and Invariance Inductive Bias for Learning from
Insufficient Data [65.42329520528223]
不十分なデータがモデルを、通常テストとは異なる限られたトレーニング環境にバイアスしやすくする理由が示されています。
従来のIRMにおける環境アノテーションの欠如を効果的に解決するクラスワイド不変リスク最小化(IRM)を提案する。
論文 参考訳（メタデータ） (2022-07-25T15:26:19Z) - Chaos is a Ladder: A New Theoretical Understanding of Contrastive
Learning via Augmentation Overlap [64.60460828425502]
コントラスト学習の下流性能に関する新たな保証を提案する。
我々の新しい理論は、攻撃的なデータ強化の下で、異なるクラス内サンプルのサポートがより重なり合うという知見に基づいている。
本稿では、下流の精度とよく一致した教師なしモデル選択距離ARCを提案する。
論文 参考訳（メタデータ） (2022-03-25T05:36:26Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。