論文の概要: Private Evaluation of High-Dimensional Functions

• arxiv url: http://arxiv.org/abs/2610.24477v1
• Date: Sat, 17 Oct 2026 05:46:38 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 11:50:56.451848
• Title: Private Evaluation of High-Dimensional Functions
• Title（参考訳）: 高次元関数のプライベート評価
• Abstract要約: 任意の高次元関数の差分プライベートブラックボックス評価について検討する。 我々は、純粋および近似微分プライバシーのための一般的なブラックボックス評価器を設計する。
• 参考スコア（独自算出の注目度）: 10.128709855221096
• License:
• Abstract: We study differentially private black-box evaluation of arbitrary high-dimensional functions. Given a dataset $S$ and query access to a function $f$---whose sensitivity may be unknown or unbounded---the goal is to privately output an approximation to $f(S)$. The black-box evaluator can only query the value of $f$ over a down neighborhood of $S$ (i.e., those subsets of $S$ that are obtained by removing a bounded number of elements from $S$). We design generic black-box evaluators for both pure and approximate differential privacy through a reduction to high-dimensional private quasi-concave optimization (QCO). Our black-box evaluator enjoys a geometric notion of utility. Consider the vectors obtained by applying $f$ on sets in a down neighborhood of $S$. With high probability, the evaluator's output is guaranteed to be in the convex hull of these vectors. Our work generalizes the result of Linder et al. [LRSS25] for real-valued function evaluation to high dimensions. It also recovers the private center-point guarantees of Beimel et al. [BMNS19], with an explicit additive approximation to maximum Tukey depth. We also apply our evaluators to user-level quasi-concave and convex optimization, showing how they can improve upon the sample-and-aggregate baseline of Nissim et al. [NRS07] by replacing the multiplicative data overhead with an additive overhead. Finally, we show that our formulation of high dimensional black-box evaluation and high dimensional private QCO are equivalent up to a factor of the dimension: the hardest private evaluation instances already arise from the cases that $f$ is a (non-private) quasi-concave optimizer.
• Abstract（参考訳）: 任意の高次元関数の差分プライベートブラックボックス評価について検討する。 データセット $S$ と、関数 $f$-- に対するクエリアクセスが与えられた場合、その感度は未知あるいは非有界である可能性がある。 ブラックボックス評価器は、$S$のダウン近所で$f$の値しかクエリできない(つまり、$S$のサブセットは、$S$から有界な要素を除去することで得られる)。 我々は、高次元プライベート準凹最適化(QCO)への還元により、純粋および近似微分プライバシーのための汎用ブラックボックス評価器を設計する。 私たちのブラックボックス評価器は、幾何学的な実用性の概念を楽しみます。 ダウン近傍の$S$の集合に$f$を適用することで得られるベクトルを考える。 高い確率で、評価器の出力はこれらのベクトルの凸殻にあることが保証される。 本研究では,Linder et al [LRSS25] による実数値関数評価の結果を高次元に一般化する。 また、Beimel et al [BMNS19] のプライベートセンターポイント保証を復元し、最大テューキー深さへの明示的な加算近似を行う。 また,ユーザレベルの準凹と凸最適化に評価器を適用し,Nissim et al [NRS07] のサンプル・アグリゲートベースラインを改善する方法を示し,乗算データのオーバーヘッドを付加的なオーバーヘッドに置き換えた。 最後に、高次元のブラックボックス評価と高次元のプライベートQCOの定式化は、この次元の要素に匹敵することを示す:最も難しいプライベート評価インスタンスは、$f$が(非プライベートな)準コンケーブ最適化器である場合から既に発生している。

関連論文リスト

• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。 本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。 実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
  論文  参考訳（メタデータ） (2026-06-04T16:04:31Z)
• Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism [1.4999444543328293]
  本稿では,新しいコストと報酬関数推定器に基づくモデルベースアルゴリズムを提案する。 我々のアルゴリズムは、$widetildemathcalO((bar C - bar C_b)-1H2.5 SsqrtAK)$の残念な上限を達成する。
  論文  参考訳（メタデータ） (2024-10-14T04:51:06Z)
• DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning [58.79085525115987]
  以前の研究でよく知られたユーティリティ境界は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3)$である。 本稿では,差分プライベートフレームワークを構築した mphDIFF2 (DIFFerential private via DIFFs) という新しい差分プライベートフレームワークを提案する。 大域的な降下を持つ$mphDIFF2は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3の効用を達成する
  論文  参考訳（メタデータ） (2023-02-08T05:19:01Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Tight and Robust Private Mean Estimation with Few Users [16.22135057266913]
  ユーザレベルの差分プライバシーに基づく高次元平均推定について検討する。 可能な限り少数のユーザを使って、$(eps,delta)$-differentially privateメカニズムを設計します。
  論文  参考訳（メタデータ） (2021-10-22T16:02:21Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• A One-bit, Comparison-Based Gradient Estimator [29.600975900977343]
  正規化勾配の頑健で信頼性の高い推定器を構築するために、1ビット圧縮センシングのツールを利用する方法を示す。 勾配降下法において,この推定器を用いたSCOBOというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-06T05:01:38Z)

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

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