論文の概要: Sample-efficient proper PAC learning with approximate differential privacy

• arxiv url: http://arxiv.org/abs/2012.03893v1
• Date: Mon, 7 Dec 2020 18:17:46 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-16 20:54:01.712244
• Title: Sample-efficient proper PAC learning with approximate differential privacy
• Title（参考訳）: 近似差分プライバシーを用いたサンプル効率の適切なPAC学習
• Authors: Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
• Abstract要約: 近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
• 参考スコア（独自算出の注目度）: 51.09425023771246
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $\tilde O(d^6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2^{O(d)}$ on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.
• Abstract（参考訳）: 本稿では,Littlestone 次元のクラス $d$ を近似微分プライバシーで適切に学習する際のサンプルの複雑さが$\tilde O(d^6)$であり,プライバシと精度のパラメータを無視していることを示す。 この結果はbun et alの疑問に答える。 (FOCS 2020) は, 試料の複雑さに対して 2^{O(d)}$ の上限を改良した。 我々の研究以前には、有限のリトルストーン次元のクラスをプライベートに学習するサンプルの複雑さの有限性は、不適切な個人学習者にのみ知られており、我々の学習者が適切なものであるという事実は、Bousquetらからも質問されたBun et al.の別の疑問に答えている。 (2020年)。 Bousquetらが開発した機械を用いて、二項仮説クラスを衛生化する際のサンプルの複雑さは、そのリトルストーン次元と双対リトルストーン次元のほとんどの多項式であることを示す。 これは、あるクラスがサニタブルであることと、それが有限小石次元を持つことが同値であることを意味する。 我々の証明の重要な要素は、非還元可能性(irreducibility)と呼ばれる二項仮説クラスの新しい性質である。

関連論文リスト

• Private PAC Learning May be Harder than Online Learning [14.180842831990999]
  リトルストーン次元の任意の概念クラス$d$は、$mathrmpoly(d)$サンプルを用いてプライベートにPACが学習できることを示す。 これにより、オンライン学習者からプライベートPAC学習者への汎用的な変換が存在するかどうかという自然な疑問が提起される。
  論文  参考訳（メタデータ） (2024-02-16T22:44:52Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Applications of Littlestone dimension to query learning and to compression [1.9336815376402723]
  我々は、ランダムな反例を持つ同値クエリによる学習のために、2017年のシアングルインのモデルを拡張した。 第二に、このモデルを無作為性のある無限の概念クラスに拡張する。 第三に、Littlestone次元と拡張$d$-compressionスキームを持つクラスとの関係に関する改善された結果を与える。
  論文  参考訳（メタデータ） (2023-10-07T14:04:18Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。 まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。 第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
  論文  参考訳（メタデータ） (2023-02-06T02:52:36Z)
• Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes [5.194264506657145]
  比較学習は、PAC学習における実現可能な設定と不可知な設定の組み合わせとして導入する。 たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。 比較学習のサンプルの複雑さは、相互VC次元$mathsfVC(S,B)$によって特徴づけられる。
  論文  参考訳（メタデータ） (2022-11-16T18:38:24Z)
• Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique [28.57552551316786]
  我々は、VC次元とリトルストーン次元を近似するために、最大(アンバランス)双立問題から簡単な還元を与える。 この接続により、近似結果と時間的下界のランニングの難易度を導出する。
  論文  参考訳（メタデータ） (2022-11-02T19:23:42Z)
• 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)
• Near-tight closure bounds for Littlestone and threshold dimensions [59.245101116396555]
  二つの仮説クラスのリトルストーンおよびしきい値次元の閉包特性について検討する。 我々の上界は、アロンらによって示される類似境界に対して指数的($k$で)改善を与える。
  論文  参考訳（メタデータ） (2020-07-07T17:56:06Z)
• Private Query Release Assisted by Public Data [96.6174729958211]
  本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
  論文  参考訳（メタデータ） (2020-04-23T02:46:37Z)

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

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