論文の概要: List Sample Compression and Uniform Convergence

• arxiv url: http://arxiv.org/abs/2403.10889v1
• Date: Sat, 16 Mar 2024 10:49:27 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 21:15:47.017754
• Title: List Sample Compression and Uniform Convergence
• Title（参考訳）: リストサンプル圧縮と一様収束
• Authors: Steve Hanneke, Shay Moran, Tom Waknine,
• Abstract要約: リスト学習の文脈における一般化に関連する古典的原理を考察する。 この結果から,一様収束はPAC学習環境における学習可能性と等価であることが示唆された。
• 参考スコア（独自算出の注目度）: 28.42548870013324
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: List learning is a variant of supervised classification where the learner outputs multiple plausible labels for each instance rather than just one. We investigate classical principles related to generalization within the context of list learning. Our primary goal is to determine whether classical principles in the PAC setting retain their applicability in the domain of list PAC learning. We focus on uniform convergence (which is the basis of Empirical Risk Minimization) and on sample compression (which is a powerful manifestation of Occam's Razor). In classical PAC learning, both uniform convergence and sample compression satisfy a form of `completeness': whenever a class is learnable, it can also be learned by a learning rule that adheres to these principles. We ask whether the same completeness holds true in the list learning setting. We show that uniform convergence remains equivalent to learnability in the list PAC learning setting. In contrast, our findings reveal surprising results regarding sample compression: we prove that when the label space is $Y=\{0,1,2\}$, then there are 2-list-learnable classes that cannot be compressed. This refutes the list version of the sample compression conjecture by Littlestone and Warmuth (1986). We prove an even stronger impossibility result, showing that there are $2$-list-learnable classes that cannot be compressed even when the reconstructed function can work with lists of arbitrarily large size. We prove a similar result for (1-list) PAC learnable classes when the label space is unbounded. This generalizes a recent result by arXiv:2308.06424.
• Abstract（参考訳）: リスト学習は教師付き分類の一種であり、学習者は1つだけではなく、各インスタンスに対して複数の可算ラベルを出力する。 リスト学習の文脈における一般化に関連する古典的原理を考察する。 我々の第一の目的は、PAC設定における古典的原則がPAC学習の分野における適用性を維持するかどうかを決定することである。 我々は,一様収束(経験的リスク最小化の基礎)とサンプル圧縮(オッカムのラザーの強力な表現)に焦点を当てる。 古典的なPAC学習では、一様収束とサンプル圧縮の両方が「完全性」の形式を満たす: クラスが学習可能であればいつでも、これらの原則に従う学習規則によっても学習することができる。 リスト学習設定において、同じ完全性が真であるかどうかを問う。 この結果から,一様収束はPAC学習環境における学習可能性と等価であることが示唆された。 ラベル空間が$Y=\{0,1,2\}$の場合、圧縮できない2-list-learnableクラスが存在することを証明します。 このことはLittlestone and Warmuth (1986) によるサンプル圧縮予想のリストバージョンを否定する。 さらに、再構成された関数が任意の大きさのリストを扱える場合でも、圧縮できない2$リスト学習可能なクラスが存在することを示す。 ラベル空間が非有界である場合、 (1-list) PAC 学習可能なクラスに対して同様の結果を示す。 これは最近の結果をarXiv:2308.06424で一般化する。

関連論文リスト

• Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
  また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。 具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
  論文  参考訳（メタデータ） (2023-11-02T21:10:16Z)
• Provable Advantage in Quantum PAC Learning [3.291862617649511]
  PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。 多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
  論文  参考訳（メタデータ） (2023-09-19T19:26:20Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。 本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
  論文  参考訳（メタデータ） (2023-07-02T19:26:58Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。 まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。 第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
  論文  参考訳（メタデータ） (2023-02-06T02:52:36Z)
• 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)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。 また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
  論文  参考訳（メタデータ） (2022-10-11T13:54:41Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。 すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
  論文  参考訳（メタデータ） (2022-05-12T14:40:18Z)
• 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)

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

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