論文の概要: Local Regularization Does Not Characterize Multiclass PAC Learnability
- arxiv url: http://arxiv.org/abs/2607.23449v1
- Date: Sun, 26 Jul 2026 04:25:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-28 22:34:15.10602
- Title: Local Regularization Does Not Characterize Multiclass PAC Learnability
- Title（参考訳）: 局所正規化はマルチクラスPAC学習性を特徴付けない
- Authors: Eric Hou,
- Abstract要約: 局所正規化は各仮説にテストポイント依存スコアを割り当て、サンプルと一致する最小スコア仮説で予測する。
Daniely--Shalev-Shwartz の可算クラスがあり、PACサンプルの複雑性が実現可能である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample. Asilis et al. asked whether this principle characterizes multiclass PAC learnability. We give a negative answer. There is a countable class of Daniely--Shalev-Shwartz dimension at most two with realizable PAC sample complexity \[ O\!\left(\frac{1}{\varepsilon}\log\frac{1}δ\right), \] that no local regularizer learns. Hypotheses are edges of complete graphs and instances are tournaments. At a test tournament, the scores fix an edge ranking while the training sample independently removes competitors. Cyclic triangles force enough inversions that surviving competitors produce constant population error at arbitrarily large sample sizes.
- Abstract（参考訳）: 局所正規化は各仮説にテストポイント依存スコアを割り当て、サンプルと一致する最小スコア仮説で予測する。
Asilisらは、この原則が多クラスPAC学習可能性の特徴であるかどうかを尋ねた。
私たちは否定的な答えを出します。
Daniely--Shalev-Shwartz 次元の可算クラスが少なくとも 2 つあり、PAC サンプルの複雑性は \[O\!
\left(\frac{1}{\varepsilon}\log\frac{1}δ\right), \] 局所正規化器が学習しない。
仮説は完全なグラフのエッジであり、インスタンスはトーナメントである。
テストトーナメントでは、スコアがエッジランキングを固定し、トレーニングサンプルが独立して競合相手を除去する。
循環三角形は、生き残った競合相手が任意に大きなサンプルサイズで一定の人口誤差を発生させるのに十分な反転を強制する。
関連論文リスト
- A Complexity Measure for Active Learning in Multi-group Mean Estimation [8.550300650352732]
マルチグループ平均バンドレート$d$-armed banditsにおけるemphmax-riskによるアクティブラーニングの目的について検討した。
学習者は、最悪の不確実性指数を最小限に抑えるために、$d$グループ全体で$T$サンプルの予算を適応的に割り当てる。
滑らかなクラスに対しては、$mathrmVLC$ は分散-フィッシャー情報の再パラメータ化であり、共通族に対する閉形式値を持つ。
論文 参考訳（メタデータ） (2026-06-12T17:54:26Z) - Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness [13.802167452101909]
以前の研究は、このようなインスタンス標的の毒殺攻撃による最適エラーが$Theta(deta)$とスケールすることを確立した。
最適余剰誤差が $tildeTheta(sqrtdeta)$ であることを示し、Hannekeらによって残された主要な開問題の一つに答える。
論文 参考訳（メタデータ） (2025-06-03T16:53:20Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
そこで我々はShrinkMatchと呼ばれる新しい手法を提案し、不確実なサンプルを学習する。
それぞれの不確実なサンプルに対して、元の Top-1 クラスを単に含むスランク類空間を適応的に求める。
次に、スランク空間における強と弱に強化された2つのサンプル間の整合正則化を課し、識別的表現を試みます。
論文 参考訳（メタデータ） (2023-08-13T14:05:24Z) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳（メタデータ） (2022-12-08T11:57:30Z) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳（メタデータ） (2022-05-12T14:40:18Z) - Adjusted chi-square test for degree-corrected block models [13.122543280692641]
次数補正ブロックモデル(DCSBM)の適合性テストを提案する。
単純な調整により、$d_i$ の調和平均が無限に成長する限り、統計は null の下で分布に収束する。
我々の分布結果は漸近的ではなく、明示的な定数を持ち、目標分布へのコルモゴロフ-スミルノフ距離の有限サンプル境界を与える。
論文 参考訳（メタデータ） (2020-12-30T05:20:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。