論文の概要: Near-Optimal Private Linear Regression via Iterative Hessian Mixing

• arxiv url: http://arxiv.org/abs/2601.07545v1
• Date: Mon, 12 Jan 2026 13:50:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:01.420089
• Title: Near-Optimal Private Linear Regression via Iterative Hessian Mixing
• Title（参考訳）: Iterative Hessian Mixing による準最適線形回帰
• Authors: Omri Lev, Moshe Shenfeld, Vishwak Srinivasan, Katrina Ligett, Ashia C. Wilson,
• Abstract要約: 有界データを用いた分極最小二乗法(DP-OLS)について検討した。 AdaSSP (Adaptive enough- perturbation) は、十分な統計量に適応的に選択された摂動を追加する。 本稿では,ガウススケッチに依存する新しいDP-OLSアルゴリズムである反復ヘッセンミキシングを導入し,反復ヘッセンスケッチアルゴリズムに着想を得た。
• 参考スコア（独自算出の注目度）: 7.344623287743932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study differentially private ordinary least squares (DP-OLS) with bounded data. The dominant approach, adaptive sufficient-statistics perturbation (AdaSSP), adds an adaptively chosen perturbation to the sufficient statistics, namely, the matrix $X^{\top}X$ and the vector $X^{\top}Y$, and is known to achieve near-optimal accuracy and to have strong empirical performance. In contrast, methods that rely on Gaussian-sketching, which ensure differential privacy by pre-multiplying the data with a random Gaussian matrix, are widely used in federated and distributed regression, yet remain relatively uncommon for DP-OLS. In this work, we introduce the iterative Hessian mixing, a novel DP-OLS algorithm that relies on Gaussian sketches and is inspired by the iterative Hessian sketch algorithm. We provide utility analysis for the iterative Hessian mixing as well as a new analysis for the previous methods that rely on Gaussian sketches. Then, we show that our new approach circumvents the intrinsic limitations of the prior methods and provides non-trivial improvements over AdaSSP. We conclude by running an extensive set of experiments across standard benchmarks to demonstrate further that our approach consistently outperforms these prior baselines.
• Abstract（参考訳）: 有界データを用いた分極最小二乗法(DP-OLS)について検討した。 AdaSSP (Adaptive enough-statistics perturbation) は、十分な統計量、すなわち行列 $X^{\top}X$ とベクトル $X^{\top}Y$ に適応的に選択された摂動を加える。 対照的に、ランダムなガウス行列でデータを事前乗算することで差分プライバシーを確保するガウス・スケッチに依存する手法は、フェデレーションや分散回帰において広く用いられているが、DP-OLSでは比較的一般的ではない。 本研究では,ガウスのスケッチに依存する新しいDP-OLSアルゴリズムである反復ヘッセンミキシングを導入し,反復ヘッセンのスケッチアルゴリズムに着想を得た。 我々は、反復ヘッセン混合のためのユーティリティ分析と、ガウススケッチに依存する以前の手法に対する新しい分析を提供する。 そして,本手法は従来の手法の本質的な限界を回避し,AdaSSPに対する非自明な改善をもたらすことを示す。 我々は、標準ベンチマークにまたがって広範な実験を行うことで、我々のアプローチがこれらの以前のベースラインを一貫して上回っていることを示す。

関連論文リスト

• The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches [13.972860872034525]
  本稿では,Renyi Differential Privacy (RDP) のレンズを用いて,この操作を再考する。 この改良された解析が、異なる線形回帰設定における性能改善にどのように寄与するかを実証する。 経験的に、我々の手法は複数のデータセットのパフォーマンスを改善し、いくつかのケースではランタイムを削減します。
  論文  参考訳（メタデータ） (2025-05-30T13:52:48Z)
• Better Rates for Private Linear Regression in the Proportional Regime via Aggressive Clipping [19.186034457189162]
  一般的なアプローチは、サンプルごとの勾配の予想基準よりもクリッピング定数をはるかに大きく設定することである。 しかし、分析を単純化する一方で、これは経験的証拠がパフォーマンスを最適化することを示唆しているものとは対照的である。 我々の研究は、クリッピングが頻繁に起こる体制において、理論と実践のギャップを埋める。
  論文  参考訳（メタデータ） (2025-05-22T07:34:27Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  その結果, DP-ShuffleGはDP-SGDと比較して, データのシャッフル処理により過大なリスクが生じることがわかった。 我々は、プライベートな最適化に公開データサンプルを統合するハイブリッドアプローチである textitInterleaved-ShuffleG を提案する。
  論文  参考訳（メタデータ） (2025-02-05T22:30:00Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  emphdone right -- 最適化とカーネルコミュニティからの具体的な洞察を使用するという意味で -- が、勾配降下は非常に効果的であることを示している。 本稿では,直感的に設計を記述し,設計選択について説明する。 本手法は,分子結合親和性予測のための最先端グラフニューラルネットワークと同程度にガウス過程の回帰を配置する。
  論文  参考訳（メタデータ） (2023-10-31T16:15:13Z)
• Generalizing Gaussian Smoothing for Random Search [23.381986209234164]
  ガウススムースティング(英: Gaussian smoothing、GS)は、現在のベンチマークの摂動を用いて対象の勾配を推定する微分自由最適化アルゴリズムである。 そこで本研究では,MSEが比較的小さいような分布の誤差を最小限に抑えた摂動分布を選択することを提案する。
  論文  参考訳（メタデータ） (2022-11-27T04:42:05Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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