論文の概要: On the Limits of Sparse Linear Model with Shuffled Differential Privacy

• arxiv url: http://arxiv.org/abs/2610.32822v2
• Date: Mon, 26 Oct 2026 14:24:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:13.22147
• Title: On the Limits of Sparse Linear Model with Shuffled Differential Privacy
• Title（参考訳）: シャッフル微分プライバシーを持つスパース線形モデルの限界について
• Abstract要約: 本稿では,非対話型SDPプロトコルと対話型SDPプロトコルの両方における疎線形回帰について検討する。 2ラウンドの対話型アルゴリズムが開発され、まず重いヒットターステップでサポートを回復し、パラメータを推定する。 スコアアタックフレームワークをユーザデータに拡張することにより、新しい下位境界$(sqrtfracklog(d/k)nm + fracklog(d/k)nsqrtm )$は、任意のユーザレベルの$(,)$-DPに対して確立される。
• 参考スコア（独自算出の注目度）: 11.620979233461624
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse linear regression is a fundamental problem in high-dimensional statistics, and its private counterparts leave a large gap between the central and the local model of differential privacy. Shuffled differential privacy (SDP) sits between the two, offering accuracy closer to the central model without the trust requirement of a central curator. This paper studies sparse linear regression under both non-interactive and interactive SDP protocols. In the non-interactive setting, any non-interactive $(ε,δ)$-SDP protocol is shown to incur an $\ell_2$-norm estimation error of $Ω( \frac{\sqrt{dk}}{nε} )$ with dimension $d$, sparsity $k$, and $n$ users, revealing an inherent dimensionality barrier. In addition, a non-interactive algorithm is proposed that achieves an $\ell_2$-norm upper bound of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{n}} + \frac{d\sqrt{k}}{nε})$. To overcome this barrier, we turn to the interactive user-level setting, where each user holds $m$ samples. A two-round interactive algorithm is developed that first recovers the support through a heavy hitter step and then estimates the parameter, achieving an error of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{nm}} + \frac{k}{n\sqrt{m}ε} )$ with no polynomial dependence on $d$. Furthermore, by extending the score attack framework to user-level data, a new lower bound $Ω( \sqrt{\frac{k\log(d/k)}{nm}} + \frac{k\log(d/k)}{n\sqrt{m}ε} )$ is established for any user-level $(ε,δ)$-DP, showing that the proposed algorithm is near-optimal with only a gap of the factor $\log(d/k)$.
• Abstract（参考訳）: 疎線形回帰は高次元統計学の基本的な問題であり、その個人的回帰は偏微分プライバシーの中央モデルと局所モデルの間に大きなギャップを残している。 シャッフル微分プライバシー(SDP)は、中央キュレーターの信頼性を必要とせず、中央モデルに近い精度を提供する。 本稿では,非対話型SDPプロトコルと対話型SDPプロトコルの両方における疎線形回帰について検討する。 非インタラクティブな設定では、任意の非インタラクティブな$(ε,δ)$-SDPプロトコルが$Ω( \frac{\sqrt{dk}}{nε} )$の$\ell_2$-norm推定誤差を生じさせる。 さらに、$\tilde{\mathcal{O}}( \sqrt {\frac{k}{n}} + \frac{d\sqrt{k}}{nε})$の$\ell_2$-norm上限を達成する非相互作用アルゴリズムが提案されている。 この障壁を克服するために、各ユーザが$m$のサンプルを保持する対話型ユーザレベル設定に目を向ける。 2ラウンドの対話的アルゴリズムは、まず重いヒットターステップでサポートを回復し、次にパラメータを推定し、$d$の多項式依存のない$$\tilde{\mathcal{O}}( \sqrt {\frac{k}{nm}} + \frac{k}{n\sqrt{m}ε} )$の誤差を達成する。 さらに、スコアアタックフレームワークをユーザレベルのデータに拡張することにより、新しい下限の$Ω( \sqrt {\frac{k\log(d/k)}{nm}} + \frac{k\log(d/k)}{n\sqrt{m}ε} )$が、任意のユーザレベルの$(ε,δ)$-DPに対して確立され、提案アルゴリズムは、$\log(d/k)$のギャップのみでほぼ最適であることを示す。

関連論文リスト

• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Nearly Optimal Differentially Private ReLU Regression [18.599299269974498]
  微分プライバシ(DP)モデルにおいて、最も基本的な非学習問題の1つ、ReLU回帰について検討する。 我々は,1パスのミニバッチ一般化モデルパーセプトロンアルゴリズムを提案し,解析することで,$epsilon$と公開データの要求を緩和する。
  論文  参考訳（メタデータ） (2025-03-08T02:09:47Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model [38.66115499136791]
  局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。 そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。 その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
  論文  参考訳（メタデータ） (2023-10-11T10:34:52Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• 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)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)

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

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