Fugu-MT 論文翻訳(概要): Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

論文の概要: Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

arxiv url: http://arxiv.org/abs/2609.02880v1
Date: Wed, 02 Sep 2026 17:56:39 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-03 17:53:18.486525
Title: Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries
Title（参考訳）: 異なるプライベートな線形クエリに対するランダム性-ユーティリティトレードオフの克服
Abstract要約: 我々は、ハルトとタルワルの $| cdot |_K$-norm 機構のランダムネス係数のアナログを提供する。 for the $ell_infty$-error, our algorithm can answer $d$ linear query with $O(d / varepsilon)$ error using $O(log d)$ random bits。
参考スコア（独自算出の注目度）: 37.158613306509956
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\| \cdot \|_K$-norm mechanism of Hardt and Talwar [HT10]. For the $\ell_\infty$-error, our algorithm can answer $d$ linear queries with $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\varepsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.
Abstract（参考訳）: 本稿では,少数(予測)ランダムビットを用いた線形クエリに差分プライバシで応答する問題について検討する。我々は、ハルトとタルワル[HT10]の$\| \cdot \|_K$-ノルム機構のランダムネス効率のアナログを提供する。我々のアルゴリズムは$O(d / \varepsilon)$ error with $O(\log d)$ random bits, improve on algorithm of Canonne et al and Ghentiyala [CSV25, Ghe26]; これは$\varepsilon \le 1/d$が最適である。また,誤差の乗算的増加に対して$O(\log d)$O(\log d)で計算効率のよいアルゴリズムも提供する。

関連論文リスト

Private Continual Counting of Unbounded Streams [11.941250828872189]
入力サイズ$n$が予め分かっていないような非有界な環境では、差分プライベートな連続数え上げの問題について検討する。一般的な2倍のトリックを使用すると、$n$の知識は避けられるが、最適でないエラーと非滑らかなエラーにつながる。先行研究で研究された関数 $frac1sqrt1-z$ の対数摂動に基づく新しい行列分解を導入する。
論文参考訳（メタデータ） (2025-06-17T23:09:53Z)
Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
論文参考訳（メタデータ） (2025-05-29T17:21:20Z)
Differentially Private Set Representations [13.576656322669098]
本研究では,大宇宙からの大きさの集合を$k$で表すために,差分プライベート(DP)機構の問題を考察する。最初の構成では、$(epsilon,delta)$-DP表現を生成し、エラー確率は1/(eepsilon + 1)$で、少なくとも1.05 k epsilon cdot log(e)$ bitsで空間を使用する。また、最大$k epsilon cdot log(e)$ bitsの空間を用いて、同じエラーを持つ純粋な$epsilon$-DP表現のための第2のアルゴリズムも提示する。
論文参考訳（メタデータ） (2025-01-28T03:29:00Z)
Differentially Private Approximate Pattern Matching [0.0]
我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。 1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
論文参考訳（メタデータ） (2023-11-13T15:53:45Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文参考訳（メタデータ） (2021-11-09T16:50:18Z)
Testing Boolean Functions Properties [1.5924410290166868]
関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
論文参考訳（メタデータ） (2021-09-14T15:27:38Z)
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)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-04-08T18:00:01Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)
Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits [13.32560004325655]
古典的な$K$武器の線形文脈包帯問題の逆変法を考える。 $d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
論文参考訳（メタデータ） (2020-02-01T22:49:46Z)

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