論文の概要: Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity

• arxiv url: http://arxiv.org/abs/2510.01291v1
• Date: Wed, 01 Oct 2025 04:49:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:20.795217
• Title: Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity
• Title（参考訳）: 準最適サンプル複素数をもつプライベート・ライズブル・ツー・アグノスティック変換
• Authors: Bo Li, Wei Wang, Peng Ye,
• Abstract要約: 実現可能-認識可能変換は、現実化可能な設定のプライベート学習者を、不可知な設定のプライベート学習者に変換する一般的なメカニズムを提供する。 本研究では、$varepsilon$への依存をなくす改良された構成を与える。 その結果、プライベートな学習では、プライバシコストは実現可能な部分でのみ重要であることが判明した。
• 参考スコア（独自算出の注目度）: 13.129167404736137
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The realizable-to-agnostic transformation (Beimel et al., 2015; Alon et al., 2020) provides a general mechanism to convert a private learner in the realizable setting (where the examples are labeled by some function in the concept class) to a private learner in the agnostic setting (where no assumptions are imposed on the data). Specifically, for any concept class $\mathcal{C}$ and error parameter $\alpha$, a private realizable learner for $\mathcal{C}$ can be transformed into a private agnostic learner while only increasing the sample complexity by $\widetilde{O}(\mathrm{VC}(\mathcal{C})/\alpha^2)$, which is essentially tight assuming a constant privacy parameter $\varepsilon = \Theta(1)$. However, when $\varepsilon$ can be arbitrary, one has to apply the standard privacy-amplification-by-subsampling technique (Kasiviswanathan et al., 2011), resulting in a suboptimal extra sample complexity of $\widetilde{O}(\mathrm{VC}(\mathcal{C})/\alpha^2\varepsilon)$ that involves a $1/\varepsilon$ factor. In this work, we give an improved construction that eliminates the dependence on $\varepsilon$, thereby achieving a near-optimal extra sample complexity of $\widetilde{O}(\mathrm{VC}(\mathcal{C})/\alpha^2)$ for any $\varepsilon\le 1$. Moreover, our result reveals that in private agnostic learning, the privacy cost is only significant for the realizable part. We also leverage our technique to obtain a nearly tight sample complexity bound for the private prediction problem, resolving an open question posed by Dwork and Feldman (2018) and Dagan and Feldman (2020).
• Abstract（参考訳）: 実現不可能な変換(Beimel et al , 2015; Alon et al , 2020)は、現実的な環境でプライベートラーナーを(概念クラスである関数によってラベル付けされている場合)、(データに仮定が課されない場合)プライベートラーナーに変換する一般的なメカニズムを提供する。 具体的には、任意の概念クラス $\mathcal{C}$ とエラーパラメータ $\alpha$ に対して、$\mathcal{C}$ のプライベートリアライズ可能な学習者は、サンプルの複雑さを $\widetilde{O}(\mathrm{VC}(\mathcal{C})/\alpha^2)$ だけ増加しながら、プライベートな非依存の学習者に変換することができる。 しかし、$\varepsilon$が任意の場合、標準のプライバシー増幅・サブサンプリング技術(Kasiviswanathan et al , 2011)を適用する必要があり、その結果、$\widetilde{O}(\mathrm{VC}(\mathcal{C})/\alpha^2\varepsilon)$が1/\varepsilon$ファクターとなる。 この研究では、$\varepsilon$への依存を排除し、任意の$\varepsilon\le 1$に対して$\widetilde{O}(\mathrm{VC}(\mathcal{C})/\alpha^2)$のほぼ最適サンプル複雑性を達成するための改善された構成を与える。 さらに,私的な不可知学習においては,プライバシコストは実現可能な部分においてのみ重要であることが明らかとなった。 また,Dwork と Feldman (2018) と Dagan と Feldman (2020) が提案したオープンな質問を解くことで,私的予測問題に縛られたほぼ厳密なサンプル複雑性を得る。

関連論文リスト

• Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs [35.22742439337603]
  Proposed Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) algorithm using entropy and quadratic regularizers to reach this goal。 PDR-ANPGは、パラメータ化されたポリシークラスに変換互換性の近似誤差を持たせるため、最終値の$epsilon$Optimity gapを達成できる。 これは、汎用パラメータ化CMDPの最先端最終保証の大幅な改善である。
  論文  参考訳（メタデータ） (2024-08-21T10:44:57Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• \~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization [23.547605262139957]
  しきい値関数の学習問題は、機械学習の基本的な問題である。 Kaplan et al による $tildeO(log* |X|)1.5) のほぼタイトな上界を提供する。 また、プライベート準凹の加法誤差(関連するより一般的な問題)に対して$tildeTheta(2log*|X|)$の上限と下限のマッチングも提供する。
  論文  参考訳（メタデータ） (2022-11-11T18:16:46Z)
• On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
  本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。 注目すべきは,上界が決定論的学習者によって達成できることである。
  論文  参考訳（メタデータ） (2022-10-06T06:49:48Z)
• Private and polynomial time algorithms for learning Gaussians and beyond [13.947461378608525]
  本稿では,$(varepsilon, delta)$differentially private (DP) 統計的推定を非私的推定に還元する枠組みを提案する。 我々は、(制限のない)ガウスの堅牢な学習のための$(varepsilon, delta)$-DPアルゴリズムを初めて提供する。
  論文  参考訳（メタデータ） (2021-11-22T16:25:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Private Query Release Assisted by Public Data [96.6174729958211]
  本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
  論文  参考訳（メタデータ） (2020-04-23T02:46:37Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

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

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