論文の概要: Private PAC Learning May be Harder than Online Learning

• arxiv url: http://arxiv.org/abs/2402.11119v1
• Date: Fri, 16 Feb 2024 22:44:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-20 23:26:21.845846
• Title: Private PAC Learning May be Harder than Online Learning
• Title（参考訳）: プライベートPAC学習はオンライン学習より難しいかもしれない
• Authors: Mark Bun, Aloni Cohen, Rathin Desai
• Abstract要約: リトルストーン次元の任意の概念クラス$d$は、$mathrmpoly(d)$サンプルを用いてプライベートにPACが学習できることを示す。 これにより、オンライン学習者からプライベートPAC学習者への汎用的な変換が存在するかどうかという自然な疑問が提起される。
• 参考スコア（独自算出の注目度）: 14.180842831990999
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We continue the study of the computational complexity of differentially private PAC learning and how it is situated within the foundations of machine learning. A recent line of work uncovered a qualitative equivalence between the private PAC model and Littlestone's mistake-bounded model of online learning, in particular, showing that any concept class of Littlestone dimension $d$ can be privately PAC learned using $\mathrm{poly}(d)$ samples. This raises the natural question of whether there might be a generic conversion from online learners to private PAC learners that also preserves computational efficiency. We give a negative answer to this question under reasonable cryptographic assumptions (roughly, those from which it is possible to build indistinguishability obfuscation for all circuits). We exhibit a concept class that admits an online learner running in polynomial time with a polynomial mistake bound, but for which there is no computationally-efficient differentially private PAC learner. Our construction and analysis strengthens and generalizes that of Bun and Zhandry (TCC 2016-A), who established such a separation between private and non-private PAC learner.
• Abstract（参考訳）: 我々は、微分プライベートPAC学習の計算複雑性と、それが機械学習の基礎にあるかの研究を継続する。 最近の研究で、プライベートPACモデルとLittlestoneのオンライン学習のミスバウンドモデルとの質的な等価性を明らかにし、特にLittlestone次元の任意の概念クラス$d$は、$\mathrm{poly}(d)$サンプルを使用してプライベートにPACを学習できることを示した。 これにより、オンライン学習者からプライベートPAC学習者への汎用的な変換が、計算効率も維持するかどうかという自然な疑問が提起される。 我々は、合理的な暗号的仮定の下でこの問題に対する否定的な答えを与える(概して、すべての回路に対して識別不能な難読化を構築することができる)。 多項式の誤りを境界として多項式時間で動作するオンライン学習者を認める概念クラスを示すが,計算効率に優れる差動プライベートpac学習者は存在しない。 我々は,私的・非私的なPAC学習者との分離を確立したBun and Zhandry(TCC 2016-A)を構築・一般化する。

関連論文リスト

• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Provable Advantage in Quantum PAC Learning [3.291862617649511]
  PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。 多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
  論文  参考訳（メタデータ） (2023-09-19T19:26:20Z)
• 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)
• Multiclass versus Binary Differentially Private PAC Learning [32.22526322514124]
  多クラス差分プライベートPAC学習からバイナリプライベートPAC学習への一般化について述べる。 我々の証明は、Ben-Davidらによる[JCSS '95]で定義された$Psi$-dimensionの概念をオンライン設定に拡張し、その一般的な性質を探求する。
  論文  参考訳（メタデータ） (2021-07-22T18:06:39Z)
• A Graph Federated Architecture with Privacy Preserving Learning [48.24121036612076]
  フェデレーション学習は、複数のエージェントと連携してグローバルモデルを見つける中央プロセッサを含む。 複数のクライアントに接続されたサーバの現在のアーキテクチャは、サーバの通信障害や計算過負荷に非常に敏感です。 暗号と差分プライバシーの概念を使用して、グラフ構造に拡張するフェデレーション学習アルゴリズムを民営化します。
  論文  参考訳（メタデータ） (2021-04-26T09:51:24Z)
• 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)
• Reducing Adversarially Robust Learning to Non-Robust PAC Learning [39.51923275855131]
  非ロマンスな学習者を用いて、仮説クラスを頑健に学習できる還元を与える。 $mathcalA$への呼び出しの数は、例ごとに許容される逆の摂動の数に対数的に依存する。
  論文  参考訳（メタデータ） (2020-10-22T20:28:35Z)
• A Computational Separation between Private Learning and Online Learning [19.001036556917818]
  概念クラスは、オンライン学習可能であれば、かつ、オンライン学習可能であれば、プライベートに学習可能である。 この等価性は、サンプルと計算効率の両方に大きな損失をもたらす。 単方向関数の存在を前提として、そのような効率的な変換は、サンプル複雑性を持つ純粋にプライベートな学習者にとって不可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-11T02:41:54Z)
• A Theory of Usable Information Under Computational Constraints [103.5901638681034]
  本稿では,複雑なシステムにおける情報推論のための新しいフレームワークを提案する。 我々の基礎はシャノンの情報理論の変分拡張に基づいている。 計算制約を組み込むことで,データから$mathcalV$-informationを確実に推定できることを示す。
  論文  参考訳（メタデータ） (2020-02-25T06:09:30Z)

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

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