Fugu-MT 論文翻訳(概要): Nearly-Optimal Private Selection via Gaussian Mechanism

論文の概要: Nearly-Optimal Private Selection via Gaussian Mechanism

arxiv url: http://arxiv.org/abs/2511.06871v1
Date: Mon, 10 Nov 2025 09:17:33 GMT
ステータス: 翻訳完了
システム内更新日: 2025-11-11 21:18:45.180078
Title: Nearly-Optimal Private Selection via Gaussian Mechanism
Title（参考訳）: ガウス機構による準最適私選
Authors: Ethan Leeman, Pasin Manurangsi,
Abstract要約: 指数的機構の$(log log |mathcalY|)O(1)$の係数内にある$tildeO(log |mathcalY|)$の誤差を保証する。これは、$O(log3/2 |mathcalY|)$の誤差を達成するスタインケのメカニズムを改善する。
参考スコア（独自算出の注目度）: 25.777692723130244
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Steinke (2025) recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invoking Gaussian mechanism on low-sensitivity queries? We resolve this question positively. In particular, for a candidate set $\mathcal{Y}$, we achieve error guarantee of $\tilde{O}(\log |\mathcal{Y}|)$, which is within a factor of $(\log \log |\mathcal{Y}|)^{O(1)}$ of the exponential mechanism (McSherry and Talwar, 2007). This improves on Steinke's mechanism which achieves an error of $O(\log^{3/2} |\mathcal{Y}|)$.
Abstract（参考訳）: Steinke氏 (2025) は、最近、次のような興味深いオープンな質問をした: 低感度クエリでガウスのメカニズムを(適宜)呼び出すことで、ほぼ最適誤差で微分的にプライベートな選択問題を解くことができるか? 私たちはこの問題を肯定的に解決する。特に、候補集合 $\mathcal{Y}$ に対して、指数的機構の $(\log \log |\mathcal{Y}|)^{O(1)}$ の係数である $\tilde{O}(\log |\mathcal{Y}|)$ の誤差保証を達成する(McSherry and Talwar, 2007)。これは、$O(\log^{3/2} |\mathcal{Y}|)$の誤差を達成するスタインケのメカニズムを改善する。

関連論文リスト

Private Continual Counting of Unbounded Streams [11.941250828872189]
入力サイズ$n$が予め分かっていないような非有界な環境では、差分プライベートな連続数え上げの問題について検討する。一般的な2倍のトリックを使用すると、$n$の知識は避けられるが、最適でないエラーと非滑らかなエラーにつながる。先行研究で研究された関数 $frac1sqrt1-z$ の対数摂動に基づく新しい行列分解を導入する。
論文参考訳（メタデータ） (2025-06-17T23:09:53Z)
Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems [10.228439000828722]
準凹関数の微分プライベート最適化のサンプル複雑性について検討する。我々は、下界が一連の自然問題に対してバイパス可能であることを示す。
論文参考訳（メタデータ） (2025-04-26T19:04:00Z)
Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy [17.711455925206298]
HuとMehta(2024年)は、オープンな問題を提起した:$varepsilon$-differential privacyの下で、決定論的オンライン学習($K$アクションと$T$ラウンドを含む)の最適なインスタンス依存率は何ですか?
論文参考訳（メタデータ） (2025-02-16T05:13:51Z)
Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文参考訳（メタデータ） (2023-09-27T17:09:36Z)
Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。上記の境界は本質的に最良であることを示す。
論文参考訳（メタデータ） (2022-10-27T05:08:07Z)
Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文参考訳（メタデータ） (2022-05-27T00:34:03Z)
Private Convex Optimization via Exponential Mechanism [16.867534746193833]
我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
論文参考訳（メタデータ） (2022-03-01T06:51:03Z)
On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文参考訳（メタデータ） (2021-10-12T09:36:41Z)
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文参考訳（メタデータ） (2020-12-16T17:58:45Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)

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