論文の概要: Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression

• arxiv url: http://arxiv.org/abs/2502.13115v2
• Date: Wed, 05 Nov 2025 17:25:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-06 16:07:39.3864
• Title: Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression
• Title（参考訳）: 共分散行列を超えて: 線形回帰の統計的複雑さ
• Authors: Fan Chen, Jiachun Li, Alexander Rakhlin, David Simchi-Levi,
• Abstract要約: プライバシー制約の下では、プライベート線形回帰の複雑さは通常の共分散行列によって捉えられる。 最適率を達成するための情報重み付け回帰手法を提案する。 特に、我々の結果は、共同プライバシーは追加費用がほとんどないことを示している。
• 参考スコア（独自算出の注目度）: 66.93988594607842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the statistical complexity of private linear regression under an unknown, potentially ill-conditioned covariate distribution. Somewhat surprisingly, under privacy constraints the intrinsic complexity is \emph{not} captured by the usual covariance matrix but rather its $L_1$ analogues. Building on this insight, we establish minimax convergence rates for both the central and local privacy models and introduce an Information-Weighted Regression method that attains the optimal rates. As application, in private linear contextual bandits, we propose an efficient algorithm that achieves rate-optimal regret bounds of order $\sqrt{T}+\frac{1}{\alpha}$ and $\sqrt{T}/\alpha$ under joint and local $\alpha$-privacy models, respectively. Notably, our results demonstrate that joint privacy comes at almost no additional cost, addressing the open problems posed by Azize and Basu (2024).
• Abstract（参考訳）: 未知, 潜在的に条件のない共変量分布の下で, プライベート線形回帰の統計的複雑性について検討する。 驚くべきことに、プライバシーの制約の下では、固有の複雑さは通常の共分散行列によってキャプチャされるが、代わりに$L_1$類似物である。 この知見に基づいて、我々は、中央および局所のプライバシモデルの両方に対して最小収束率を確立し、最適なレートを達成する情報重み回帰法を導入する。 応用として、プライベート線形文脈帯域において、次数 $\sqrt{T}+\frac{1}{\alpha}$ と $\sqrt{T}/\alpha$ をそれぞれジョイントモデルと局所 $\alpha$-privacyモデルの下で、レート最適後悔境界を達成する効率的なアルゴリズムを提案する。 特に,Azize と Basu (2024) によるオープンな問題に対処するため,共同プライバシがほぼ追加コストで提供されることを示す結果が得られた。

関連論文リスト

• Towards Optimal Differentially Private Regret Bounds in Linear MDPs [0.0]
  我々は、LSVI-UCB++を民営化し、オフラインRLから分散認識解析に適応させることにより、新しい微分プライベートアルゴリズムを設計する。 我々のアルゴリズムは、$widetildeO(d sqrtH3 K + H15/4 d7/6 K1/2 / epsilon)$の後悔の限界を達成し、従来のプライベートメソッドよりも改善した。
  論文  参考訳（メタデータ） (2025-04-12T20:51:51Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。 トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。 証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
  論文  参考訳（メタデータ） (2025-02-19T07:10:32Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits [8.908421753758475]
  高次元スパース線形帯域は、シーケンシャルな意思決定問題の効率的なモデルとして機能する。 データプライバシの懸念により、我々は、共同でプライベートな高次元の疎線形帯域について検討する。 FLIPHATは,プライバシパラメータの点で最適に後悔することを示す。
  論文  参考訳（メタデータ） (2024-05-22T22:19:12Z)
• On the Optimal Regret of Locally Private Linear Contextual Bandit [18.300225068036642]
  局所的なプライベートな文脈的帯域に対して,$tilde O(sqrtT)$ regret upper bound を達成可能であることを示す。 我々の解決策は、いくつかの新しいアルゴリズム的および分析的アイデアに依存している。
  論文  参考訳（メタデータ） (2024-04-15T02:00:24Z)
• The Challenge of Differentially Private Screening Rules [32.18582226044492]
  線形回帰とロジスティック回帰のための最初の微分プライベートスクリーニングルールを開発する。 そこで我々は,プライバシーを確保するために付加されるノイズの量によって,有用なプライベートスクリーニングルールを策定する作業の難しさを発見する。
  論文  参考訳（メタデータ） (2023-03-18T01:45:34Z)
• On Differentially Private Online Predictions [74.01773626153098]
  オンラインプロセスを扱うために,共同微分プライバシーのインタラクティブなバリエーションを導入する。 グループプライバシ、コンポジション、ポストプロセッシングの(適切なバリエーション)を満たすことを実証する。 次に、オンライン分類の基本設定において、インタラクティブな共同プライバシーのコストについて検討する。
  論文  参考訳（メタデータ） (2023-02-27T19:18:01Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• Locally Differentially Private (Contextual) Bandits Learning [55.63825598391525]
  本論文では,局所的差分性(LDP)バンディット学習について検討する。 我々は,DP保証を用いて,文脈自由な帯域幅学習問題を解くことのできる,シンプルなブラックボックス削減フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-06-01T04:02:00Z)

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

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