論文の概要: An Equivalence Between Private Classification and Online Prediction

• arxiv url: http://arxiv.org/abs/2003.00563v3
• Date: Tue, 22 Jun 2021 08:52:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-27 12:54:37.175995
• Title: An Equivalence Between Private Classification and Online Prediction
• Title（参考訳）: 個人分類とオンライン予測の等価性
• Authors: Mark Bun and Roi Livni and Shay Moran
• Abstract要約: 有限リトルストーン次元を持つすべての概念クラスは、(近似)微分プライベートアルゴリズムによって学習可能であることを証明している。 我々は「グローバル安定性」と呼ばれる新しい安定性の概念を導入し、これは我々の証明に不可欠であり、独立した関心を持つかもしれない。
• 参考スコア（独自算出の注目度）: 43.37646702577754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. This answers an open question of Alon et al. (STOC 2019) who proved the converse statement (this question was also asked by Neel et al.~(FOCS 2019)). Together these two results yield an equivalence between online learnability and private PAC learnability. We introduce a new notion of algorithmic stability called "global stability" which is essential to our proof and may be of independent interest. We also discuss an application of our results to boosting the privacy and accuracy parameters of differentially-private learners.
• Abstract（参考訳）: 有限小石次元を持つすべての概念クラスは(近似)微分プライベートアルゴリズムによって学習できることを証明する。 この質問はAlon et al. (STOC 2019) のオープンな質問に答え、逆のステートメントを証明した(この質問は Neel et al からも質問された)。 ～(FOCS 2019)。 これら2つの結果は、オンライン学習能力とプライベートpac学習能力の等価性をもたらす。 我々は「グローバル安定性」と呼ばれる新しいアルゴリズム的安定性の概念を導入し、これは我々の証明に不可欠であり、独立した関心を持つかもしれない。 また,この結果の応用により,差動学習者のプライバシーや正確性が向上することを示す。

関連論文リスト

• Learning across Data Owners with Joint Differential Privacy [13.531808240117645]
  データ所有者は、共同微分プライバシーと呼ばれるプライバシー概念の下で、機械学習モデルを協調的に訓練する環境について検討する。 この設定では、各データ所有者のためにトレーニングされたモデルは、プライバシを考慮していない$j$のデータと、異なるプライバシを保証する他の所有者のデータを使用します。 本稿では,DP-SGDの変種であるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-25T05:11:40Z)
• On Differentially Private Online Predictions [74.01773626153098]
  オンラインプロセスを扱うために,共同微分プライバシーのインタラクティブなバリエーションを導入する。 グループプライバシ、コンポジション、ポストプロセッシングの(適切なバリエーション)を満たすことを実証する。 次に、オンライン分類の基本設定において、インタラクティブな共同プライバシーのコストについて検討する。
  論文  参考訳（メタデータ） (2023-02-27T19:18:01Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)
• Debugging Differential Privacy: A Case Study for Privacy Auditing [60.87570714269048]
  監査は、微分プライベートなスキームの欠陥を見つけるためにも利用できることを示す。 このケーススタディでは、微分プライベートなディープラーニングアルゴリズムの最近のオープンソース実装を監査し、99.9999999999%の信頼を得て、この実装が要求される差分プライバシー保証を満たさないことを発見した。
  論文  参考訳（メタデータ） (2022-02-24T17:31:08Z)
• 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)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。 我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。 次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
  論文  参考訳（メタデータ） (2020-07-18T09:12:03Z)
• A Computational Separation between Private Learning and Online Learning [19.001036556917818]
  概念クラスは、オンライン学習可能であれば、かつ、オンライン学習可能であれば、プライベートに学習可能である。 この等価性は、サンプルと計算効率の両方に大きな損失をもたらす。 単方向関数の存在を前提として、そのような効率的な変換は、サンプル複雑性を持つ純粋にプライベートな学習者にとって不可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-11T02:41:54Z)
• On the Equivalence between Online and Private Learnability beyond Binary Classification [26.400891660337777]
  プライベートな学習性は、両方の設定においてオンライン学習性を意味することを示す。 オンライン学習が多クラス分類において個人的学習可能性を示す一方で、現在の証明手法は回帰設定において重大なハードルに直面していることを示す。
  論文  参考訳（メタデータ） (2020-06-02T23:30:41Z)
• Privately Learning Markov Random Fields [44.95321417724914]
  我々は、差分プライバシーの制約の下でランダムフィールド(イジングモデルを含む)を学習する問題を考察する。 私たちは、さまざまなプライバシー制約の下で、両方の問題に対してアルゴリズムと低いバウンダリを提供します。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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