Fugu-MT 論文翻訳(概要): An Equivalence Between Private Classification and Online Prediction

論文の概要: 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学習能力の等価性をもたらす。我々は「グローバル安定性」と呼ばれる新しいアルゴリズム的安定性の概念を導入し、これは我々の証明に不可欠であり、独立した関心を持つかもしれない。また,この結果の応用により,差動学習者のプライバシーや正確性が向上することを示す。

関連論文リスト

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
論文参考訳（メタデータ） (2026-02-24T06:15:59Z)
Learning Conditional Averages [52.361762722359366]
本稿では,PACフレームワークにおける条件平均学習の問題を紹介する。ターゲットのコンセプトそのものを学ぶのではなく、各インスタンスの平均ラベルをその周辺で予測することが目標だ。より一般的には、PAC学習をいくつかのドメインで発生する学習タスクをキャプチャする設定に拡張する。
論文参考訳（メタデータ） (2026-02-12T13:20:29Z)
Privately Learning Decision Lists and a Differentially Private Winnow [6.7839141352275645]
我々は、学習決定リストと大域半空間の古典的な問題に対して、新たな微分プライベートアルゴリズムを提案する。 PACモデルでは、最良な非私的アルゴリズムよりも最小限のサンプルオーバーヘッドで決定リストを学習するための計算効率の良いアルゴリズムを提供する。オンラインモデルでは、類似次元における誤り有界な多対数性を持つハーフスペースを学習し、マージンにおける逆を学習するために、影響力のあるWinnowアルゴリズムのプライベートなアナログを与える。
論文参考訳（メタデータ） (2026-02-07T05:30:09Z)
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)

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