論文の概要: Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing

• arxiv url: http://arxiv.org/abs/2611.03599v1
• Date: Mon, 02 Nov 2026 18:40:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:38:09.25427
• Title: Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing
• Title（参考訳）: データを組み合わせるべきか? プライベートなデータ共有評価のためのアルゴリズムと限界
• Abstract要約: AliceとBobの2人のエージェントは、それぞれ機密ラベル付きデータセットを持ち、与えられた仮説クラスから分類器をトレーニングしたい。 この問題を, $operatornameopt_mathcalH$ を用いて学習論的視点から定式化する。 最適な$t$は$tilde(log m/varepsilon)$であり、プライベートにしきい値を学ぶのに必要な$(log m/varepsilon)$サンプルよりも指数関数的に小さい。
• 参考スコア（独自算出の注目度）: 25.359800288042678
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study when two parties should pool their data to train a machine learning model. Two agents, Alice and Bob, each hold a sensitive labeled dataset and want to train a classifier from a given hypothesis class $\mathcal{H}$. Even when each party's dataset can be perfectly classified on its own, the two parties may follow conflicting labeling standards or have selection biases that affect their features and label sets, such that no single classifier in $\mathcal{H}$ fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in $\mathcal{H}$ can jointly fit both datasets---without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via $\operatorname{opt}_\mathcal{H}$, the minimum \emph{number of mistakes} made by any hypothesis in $\mathcal{H}$ on their pooled data. Through interactive communication, the agents must distinguish $\operatorname{opt}_\mathcal{H}=0$ (compatible datasets) from $\operatorname{opt}_\mathcal{H}\geq t$ (conflicting datasets) under pure $\varepsilon$-two-party differential privacy. A trusted curator could do this with $t=O(1/\varepsilon)$, and we ask how small $t$ can be without one. For thresholds on the real line over a domain of size $m$, we show that the optimal $t$ is $\tildeΘ(\log\log m/\varepsilon)$, exponentially smaller than the $Θ(\log m/\varepsilon)$ samples needed to privately learn thresholds, even with a curator. For halfspaces in $\mathbb{R}^d$, the dependence on $m$ jumps to $\log(m)$: we give a protocol with $t=\tilde{O}(d^3\log m/\varepsilon)$ and show that some domains require $t=Ω(d\log(m/d)/\varepsilon)$.
• Abstract（参考訳）: 本稿では,機械学習モデルをトレーニングするために,両者がデータをプールすべき時期について検討する。 Alice と Bob の2つのエージェントは、それぞれ機密ラベル付きデータセットを持ち、所定の仮説クラス $\mathcal{H}$ から分類器をトレーニングしたい。 各パーティのデータセットがそれ自体で完全に分類できるとしても、両者は競合するラベル標準に従うか、それぞれの特徴やラベルセットに影響を与える選択バイアスを持つ可能性がある。 データ共有にコミットする前に、Alice氏とBob氏は、$\mathcal{H}$の1つの分類器が、個々のデータポイントを互いに明らかにすることなく、両方のデータセットに共同で適合できるかどうかをテストしたいと考えた。 我々は、この問題を、プールデータ上の$\mathcal{H}$の任意の仮説によって作られた最小値の誤り数である$\operatorname{opt}_\mathcal{H}$を介して学習論的視点から定式化する。 対話的なコミュニケーションを通じて、エージェントは$\operatorname{opt}_\mathcal{H}=0$(互換データセット)と$\operatorname{opt}_\mathcal{H}\geq t$(競合データセット)を純粋な$\varepsilon$-two-party差分プライバシーの下で区別する必要がある。 信頼できるキュレーターは$t=O(1/\varepsilon)$でこれを行うことができる。 m$ の領域上の実数直線上のしきい値について、最適$t$ は $\tilde'(\log\log m/\varepsilon)$ であり、指数関数的に $(\log m/\varepsilon)$ よりも小さい。 $\mathbb{R}^d$ のハーフスペースに対して、$m$ は $\log(m)$ にジャンプする: $t=\tilde{O}(d^3\log m/\varepsilon)$ のプロトコルを与え、あるドメインが $t=Ω(d\log(m/d)/\varepsilon)$ を必要とすることを示す。

関連論文リスト

• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
  一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。 We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。 また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
  論文  参考訳（メタデータ） (2025-03-26T03:36:36Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
  論文  参考訳（メタデータ） (2025-02-20T18:32:02Z)
• Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples [24.45016514352055]
  我々は、関数クラス$mathcal F times Mathcal G$から、T+1$関数$f_star(t) circ g_star$を学習する際のサンプル複雑度について研究する。 タスク数が$T$になるにつれて、サンプル要件とリスクバウンドの両方が$r$次元回帰に収束することを示す。
  論文  参考訳（メタデータ） (2024-10-15T03:20:19Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [72.69498649272347]
  条件分布は機械学習の中心的な問題です ペアデータとペアデータの両方を統合する新しいパラダイムを提案する。 提案手法は任意の誤差で理論上真の条件分布を復元可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-03T16:12:59Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• An Algorithm for Learning Smaller Representations of Models With Scarce Data [0.0]
  本稿では,データセットが問題を完全に表現していない場合のバイナリ分類問題の解法を提案する。 我々のアルゴリズムは、基礎となる分布の支持にある多様体をホモロジーに再構成することで機能する。
  論文  参考訳（メタデータ） (2020-10-15T19:17:51Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)

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

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