論文の概要: A Computational Separation between Private Learning and Online Learning

• arxiv url: http://arxiv.org/abs/2007.05665v1
• Date: Sat, 11 Jul 2020 02:41:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-11 13:09:45.017581
• Title: A Computational Separation between Private Learning and Online Learning
• Title（参考訳）: プライベートラーニングとオンラインラーニングの計算的分離
• Authors: Mark Bun
• Abstract要約: 概念クラスは、オンライン学習可能であれば、かつ、オンライン学習可能であれば、プライベートに学習可能である。 この等価性は、サンプルと計算効率の両方に大きな損失をもたらす。 単方向関数の存在を前提として、そのような効率的な変換は、サンプル複雑性を持つ純粋にプライベートな学習者にとって不可能であることを示す。
• 参考スコア（独自算出の注目度）: 19.001036556917818
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent line of work has shown a qualitative equivalence between differentially private PAC learning and online learning: A concept class is privately learnable if and only if it is online learnable with a finite mistake bound. However, both directions of this equivalence incur significant losses in both sample and computational efficiency. Studying a special case of this connection, Gonen, Hazan, and Moran (NeurIPS 2019) showed that uniform or highly sample-efficient pure-private learners can be time-efficiently compiled into online learners. We show that, assuming the existence of one-way functions, such an efficient conversion is impossible even for general pure-private learners with polynomial sample complexity. This resolves a question of Neel, Roth, and Wu (FOCS 2019).
• Abstract（参考訳）: 最近の研究の行は、微分プライベートPAC学習とオンライン学習の質的な等価性を示している: 概念クラスが、有限な誤り境界でオンライン学習可能である場合に限って、プライベートに学習可能である。 しかし、この等価性の両方の方向は、サンプルと計算効率の両方に大きな損失をもたらす。 この接続の特別なケースを調べた結果、Goen, Hazan, Moran (NeurIPS 2019) は、一様あるいは高効率の純私的学習者はオンライン学習者に時間効率でコンパイルできることを示した。 単方向関数の存在を仮定すると、多項式サンプル複雑性を持つ一般の純粋プライベート学習者であっても、そのような効率的な変換は不可能であることを示す。 これはNeel、Roth、Wu(FOCS 2019)の問題を解決する。

関連論文リスト

• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Private PAC Learning May be Harder than Online Learning [14.180842831990999]
  リトルストーン次元の任意の概念クラス$d$は、$mathrmpoly(d)$サンプルを用いてプライベートにPACが学習できることを示す。 これにより、オンライン学習者からプライベートPAC学習者への汎用的な変換が存在するかどうかという自然な疑問が提起される。
  論文  参考訳（メタデータ） (2024-02-16T22:44:52Z)
• Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning [20.546589699647416]
  プライバシは、スクラッチから再トレーニングするための統計的不明瞭さとして定義される。 勾配勾配に基づくアンラーニングフレームワークであるランゲヴィン・アンラーニングを提案する。
  論文  参考訳（メタデータ） (2024-01-18T20:35:47Z)
• 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)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Multiclass versus Binary Differentially Private PAC Learning [32.22526322514124]
  多クラス差分プライベートPAC学習からバイナリプライベートPAC学習への一般化について述べる。 我々の証明は、Ben-Davidらによる[JCSS '95]で定義された$Psi$-dimensionの概念をオンライン設定に拡張し、その一般的な性質を探求する。
  論文  参考訳（メタデータ） (2021-07-22T18:06:39Z)
• 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)
• On the Equivalence between Online and Private Learnability beyond Binary Classification [26.400891660337777]
  プライベートな学習性は、両方の設定においてオンライン学習性を意味することを示す。 オンライン学習が多クラス分類において個人的学習可能性を示す一方で、現在の証明手法は回帰設定において重大なハードルに直面していることを示す。
  論文  参考訳（メタデータ） (2020-06-02T23:30:41Z)
• An Equivalence Between Private Classification and Online Prediction [43.37646702577754]
  有限リトルストーン次元を持つすべての概念クラスは、(近似)微分プライベートアルゴリズムによって学習可能であることを証明している。 我々は「グローバル安定性」と呼ばれる新しい安定性の概念を導入し、これは我々の証明に不可欠であり、独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2020-03-01T19:20:37Z)

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

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