論文の概要: Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
- arxiv url: http://arxiv.org/abs/2407.07765v2
- Date: Wed, 14 Aug 2024 09:52:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-15 17:26:11.333129
- Title: Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
- Title（参考訳）: Ramsey理論と'Private Learning Implies Online Learning'理論
- Authors: Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari,
- Abstract要約: この研究は、差分プライベート(DP)とオンライン学習との関係について研究を続けている。
一般分類タスクにおいては,DP学習性はオンライン学習性を意味することを示す。
- 参考スコア（独自算出の注目度）: 26.292576184028924
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work continues to investigate the link between differentially private (DP) and online learning. Alon, Livni, Malliaris, and Moran (2019) showed that for binary concept classes, DP learnability of a given class implies that it has a finite Littlestone dimension (equivalently, that it is online learnable). Their proof relies on a model-theoretic result by Hodges (1997), which demonstrates that any binary concept class with a large Littlestone dimension contains a large subclass of thresholds. In a follow-up work, Jung, Kim, and Tewari (2020) extended this proof to multiclass PAC learning with a bounded number of labels. Unfortunately, Hodges's result does not apply in other natural settings such as multiclass PAC learning with an unbounded label space, and PAC learning of partial concept classes. This naturally raises the question of whether DP learnability continues to imply online learnability in more general scenarios: indeed, Alon, Hanneke, Holzman, and Moran (2021) explicitly leave it as an open question in the context of partial concept classes, and the same question is open in the general multiclass setting. In this work, we give a positive answer to these questions showing that for general classification tasks, DP learnability implies online learnability. Our proof reasons directly about Littlestone trees, without relying on thresholds. We achieve this by establishing several Ramsey-type theorems for trees, which might be of independent interest.
- Abstract（参考訳）: この研究は、差分プライベート(DP)とオンライン学習との関係について研究を続けている。
Alon, Livni, Malliaris, and Moran (2019) は、二進概念クラスでは、与えられたクラスのDP可学習性は、有限のリトルストーン次元を持つことを意味することを示した。
それらの証明は Hodges (1997) によるモデル理論の結果に依存しており、これは大きなリトルストーン次元を持つ任意の二項概念クラスが大きな閾値のサブクラスを含むことを証明している。
Jung, Kim, and Tewari (2020) はこの証明を、有界なラベルを持つ多クラスPAC学習に拡張した。
残念なことに、Hodgesの結果は、有界ラベル空間を持つマルチクラスPAC学習や部分概念クラスのPAC学習など、他の自然環境には適用されない。
事実、Alon, Hanneke, Holzman, and Moran (2021) は、それを部分的な概念クラスの文脈におけるオープンな質問として明示的に残しており、同じ質問が一般的なマルチクラス設定で開かれている。
本稿では,これらの質問に対する肯定的な回答として,一般分類タスクにおいて,DP学習性はオンライン学習性を意味することを示す。
私たちの証明は、閾値に頼らずに、リトルストーンの木について直接的に理由を定めています。
我々は、木に対していくつかのラムゼー型定理を確立することでこれを達成し、これは独立した関心を持つかもしれない。
関連論文リスト
- When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。
我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。
これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文 参考訳（メタデータ） (2023-10-09T19:40:54Z) - Universal Rates for Multiclass Learning [28.18556410009232]
マルチクラス分類のための普遍的レートについて検討し、全ての仮説クラスに対して最適なレート(ログファクタまで)を確立する。
また、無限のグラフ・リトルストーン(GL)木と無限のナタラジャン・リトルストーン(NL)木との同値性についても、未解決の問題も解決する。
論文 参考訳（メタデータ） (2023-07-05T07:12:58Z) - Multiclass Online Learning and Uniform Convergence [34.21248304961989]
対戦型オンライン学習環境におけるマルチクラス分類について検討する。
任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
論文 参考訳（メタデータ） (2023-03-30T21:35:48Z) - Online Learning and Disambiguations of Partial Concept Classes [0.7264378254137809]
最近の記事で、Alon、Hanneke、Holzman、Moranは、部分的な概念のクラスの学習可能性を研究する統一的なフレームワークを紹介した。
彼らは、PAC学習ではそうではないことを示したが、オンラインの学習可能性というより強い概念のために、問題を解き放った。
我々は、オンライン学習可能な部分概念のクラスを構築することでこの問題を解決するが、全体概念のクラスへの拡張はオンライン学習可能ではない。
論文 参考訳（メタデータ） (2023-03-30T17:46:50Z) - 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) - A Characterization of Multiclass Learnability [18.38631912121182]
DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。
リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。
2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
論文 参考訳（メタデータ） (2022-03-03T07:41:54Z) - Monotone Learning [86.77705135626186]
各学習アルゴリズムAは、同様の性能で単調なクラスに変換可能であることを示す。
これは、パフォーマンスを損なうことなく、確実に非単調な振る舞いを回避できることを示している。
論文 参考訳（メタデータ） (2022-02-10T18:51:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。