論文の概要: Near-Optimal Generalized Private Testing

• arxiv url: http://arxiv.org/abs/2605.21601v1
• Date: Wed, 20 May 2026 18:06:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 16:35:41.947513
• Title: Near-Optimal Generalized Private Testing
• Title（参考訳）: 準最適一般化プライベートテスト
• Authors: Anamay Chaturvedi, Monika Henzinger, Jalaj Upadhyay,
• Abstract要約: 一般化されたプライベートテストのための一般閾値保持機構(GTM)を紹介する。 $varepsilon>0$と$(varepsilon_t,_t)$-DPメカニズムの場合、GTMは$varepsilon$-DPである。
• 参考スコア（独自算出の注目度）: 18.22976606091004
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In differential privacy (DP), the generalized private testing problem was introduced by Liu and Talwar (STOC 2019). Given a dataset $X \in \mathcal{X}$ and a sequence of black-box $\varepsilon_t$-DP mechanisms $M_t:\mathcal{X}\to\{+1,-1\}$, the analyst must accept the first mechanism whose success probability $p_t=\Pr[M_t(X)=+1]$ exceeds a given threshold $p^*\in(0,1)$, while achieving DP. Accuracy is measured by the gap between $p^*$ and a rejection threshold $\bar{p}$, such that with probability $1-β$ for all $t\geq1$, if $p_t\leq\bar{p}$, then $M_t$ is rejected, and if $p_t\geq p^*$, then it is accepted. This generalizes the standard private testing problem, whose solution, the Sparse Vector Technique, is ubiquitous in DP. We introduce the Generalized Thresholding Mechanism (GTM) for generalized private testing. For $\varepsilon>0$ and any sequence of $(\varepsilon_t,δ_t)$-DP mechanisms $M_t$, the GTM is pure $\varepsilon$-DP. For $θ>0$, $γ\in(1,2]$, and $β\in(0,1)$, $\bar{p}_t=\max(p^*/γΛ_t, 1 - γΛ_t(1-p^*))-δ_t/\varepsilon_t$ for $Λ_t=(5t\ln^3(t+2))^{(2+θ)\varepsilon_t/\varepsilon}(4/β)^{(3+θ+2/θ)\varepsilon_t/\varepsilon}$. With probability $1-β$, the number of evaluations of $M_t$ is at most $O((\ln(t/β)/(γ-1)^2)\max(Λ_t/p^*,(1-p^*)^{-1}))$ for all $t\geq 1$. Our lower bounds prove near-optimality of our accuracy and sample complexity guarantees. Via the GTM, we give a black-box reduction for DP optimization from the continual observation (CO) setting to the batch setting. This gives us the first DP-CO algorithms for many maximization problems. Further, the GTM permits an adaptive choice of acceptance thresholds $(p^*_t)_{t\geq1}$, addressing a challenge mentioned in prior work on using generalized private testing for hyperparameter optimization (Papernot and Steinke (ICLR 2022)).
• Abstract（参考訳）: 差分プライバシー (DP) では、Liu と Talwar (STOC 2019) によって一般化されたプライベートテスト問題が導入された。 データセット $X \in \mathcal{X}$ とブラックボックス $\varepsilon_t$-DP メカニズム $M_t:\mathcal{X}\to\{+1,-1\}$ が与えられた場合、アナリストは成功確率 $p_t=\Pr[M_t(X)=+1]$ が与えられた閾値 $p^*\in(0,1)$ を超える最初のメカニズムを受け入れなければならない。 p^*$と拒絶しきい値$\bar{p}$とのギャップによって測定され、全ての$t\geq1$に対して確率が1-β$であれば、$p_t\leq\bar{p}$ならば、$M_t$は拒否され、$p_t\geq p^*$であれば受け入れられる。 これにより、標準的なプライベートテストの問題を一般化し、そのソリューションであるスパースベクトル技術はDP内でユビキタスである。 一般化されたプライベートテストのための一般閾値保持機構(GTM)を紹介する。 $\varepsilon>0$と$(\varepsilon_t,δ_t)$-DPメカニズムの場合、GTMは純粋な$\varepsilon$-DPである。 for $θ>0$, $γ\in(1,2]$, and $β\in(0,1)$, $\bar{p}_t=\max(p^*/γ _t, 1 - γ _t(1-p^*))-δ_t/\varepsilon_t$ for $\_t=(5t\ln^3(t+2))^{(2+θ)\varepsilon_t/\varepsilon}(4/β)^{(3+θ+2/θ)\varepsilon_t/\varepsilon}$ 確率 $1-β$ の場合、$M_t$ の評価回数は、すべての$t\geq 1$ に対して、最高$O((\ln(t/β)/(γ-1)^2)\max(\_t/p^*,(1-p^*)^{-1}))$である。 我々の下限は精度とサンプルの複雑さの保証のほぼ最適性を証明している。 GTMでは,連続観測(CO)設定からバッチ設定まで,DP最適化のためのブラックボックスの削減を行う。 これにより、多くの最大化問題に対する最初のDP-COアルゴリズムが得られる。 さらに、GTMは受け入れしきい値の適応的選択を$(p^*_t)_{t\geq1}$で許可し、ハイパーパラメータ最適化のための一般化プライベートテスト(Papernot and Steinke (ICLR 2022))に先立って言及された課題に対処する。

関連論文リスト

• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。 本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
  論文  参考訳（メタデータ） (2022-09-06T23:37:31Z)
• Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
  最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。 新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
  論文  参考訳（メタデータ） (2022-04-22T07:03:13Z)
• 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)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
  人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。 第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
  論文  参考訳（メタデータ） (2021-07-31T22:23:39Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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