論文の概要: The Fast Mixing Mechanism for Differential Privacy
- arxiv url: http://arxiv.org/abs/2605.30600v1
- Date: Thu, 28 May 2026 21:48:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-01 20:56:50.253684
- Title: The Fast Mixing Mechanism for Differential Privacy
- Title（参考訳）: 微分プライバシーのための高速混合機構
- Authors: Omri Lev, Moshe Shenfeld, Vishwak Srinivasan, Katrina Ligett, Ashia C. Wilson,
- Abstract要約: 我々は高速変換に基づく新しいDPスケッチ機構を導入し、場合によっては古典的な高速スケッチ手法のランタイムと一致する。
我々は、このメカニズムの最先端のプライバシー保証を証明し、有利な体制では、ガウスのスケッチと一定の要素まで一致していることを示す。
- 参考スコア（独自算出の注目度）: 7.344623287743932
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Randomized sketching is a central tool for compressing large-scale optimization problems while preserving accuracy. In particular, sketches that are based on structured matrices, such as the Hadamard matrix, can be applied efficiently and often yield solutions that approximate those of the original problem at much lower computational cost. In differential privacy (DP), Gaussian sketching has been used to solve DP linear regression, beginning with \citet{sheffet2017differentially, sheffet2019old} and later refined by \citet{lev2025gaussianmix, lev2026near}. However, although these methods achieve strong utility guarantees, they usually do not improve runtime over classical DP approaches. In this work, we introduce a new DP sketching mechanism based on fast transforms, which, in certain cases, matches the runtime of classical fast sketching methods. We prove state-of-the-art privacy guarantees for this mechanism and show that, in favorable regimes, they match those of the Gaussian sketch up to a constant factor. As an application, we combine this mechanism with recent sketch-based methods for DP linear regression to obtain a new algorithm with strong utility and improved runtime. We establish privacy and accuracy guarantees for this algorithm, yielding, to the best of our knowledge, the first fast method for DP ordinary least squares.
- Abstract（参考訳）: ランダム化されたスケッチは、精度を保ちながら大規模な最適化問題を圧縮する中心的なツールである。
特に、アダマール行列のような構造化行列に基づくスケッチは効率よく適用でき、しばしば元の問題を計算コストよりもはるかに低い方法で近似する解が得られる。
ディファレンシャルプライバシ(DP)では、ガウスのスケッチはDP線形回帰(英語版)の解決に用いられており、最初に \citet{sheffet2017differentially, sheffet2019old} から始まり、後に \citet{lev2025gaussianmix, lev2026near} によって洗練されている。
しかしながら、これらの手法は強力なユーティリティ保証を実現するが、通常、従来のDPアプローチよりも実行時を改善することはない。
本研究では,高速変換に基づく新しいDPスケッチ機構を導入する。
我々は、このメカニズムの最先端のプライバシー保証を証明し、有利な体制では、ガウスのスケッチと一定の要素まで一致していることを示す。
アプリケーションとして,この機構を最近のDP線形回帰法と組み合わせて,強力なユーティリティと改良されたランタイムを持つ新しいアルゴリズムを得る。
我々は、このアルゴリズムに対するプライバシーと精度の保証を確立し、その結果、私たちの知る限り、DPの通常の最小二乗法としては初めての高速な方法である。
関連論文リスト
- Near-Optimal Private Linear Regression via Iterative Hessian Mixing [7.344623287743932]
有界データを用いた分極最小二乗法(DP-OLS)について検討した。
AdaSSP (Adaptive enough- perturbation) は、十分な統計量に適応的に選択された摂動を追加する。
本稿では,ガウススケッチに依存する新しいDP-OLSアルゴリズムである反復ヘッセンミキシングを導入し,反復ヘッセンスケッチアルゴリズムに着想を得た。
論文 参考訳（メタデータ） (2026-01-12T13:50:15Z) - Distributed Least Squares in Small Space via Sketching and Bias Reduction [0.0]
マトリックススケッチは、大きなデータ行列のサイズを減らす強力なツールである。
誤差よりも推定器のバイアスを最小限に抑えるスケッチ手法を設計することで,これらの制限を分散環境で回避できることを示す。
特に、最適空間と現在の行列乗算時間で動作するスパーススケッチ法を提案し、2つのパスデータを用いて、ほぼ偏りのない最小二乗推定器を復元する。
論文 参考訳（メタデータ） (2024-05-08T18:16:37Z) - Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - Fast Kernel Methods for Generic Lipschitz Losses via $p$-Sparsified
Sketches [3.3379026542599934]
カーネル法(カーネルほう、英: Kernel method)は、計算上の重要な制約に悩まされながら、固い理論の基礎を享受する学習アルゴリズムである。
散在したガウス(およびラデマッハ)のスケッチは、理論上有意な近似を生成する。
単一および複数出力のカーネル問題に対して過剰なリスク境界を導出し、汎用的なリプシッツ損失を与える。
論文 参考訳（メタデータ） (2022-06-08T11:50:23Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳（メタデータ） (2022-03-18T05:49:13Z) - 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) - Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
従来のスケッチ手法に対する新しい近似保証を導出し、分散スケッチにおけるパラメータ平均化の精度を解析する。
大規模実験によるサーバレスコンピューティングプラットフォームにおける分散スケッチのパフォーマンスについて説明する。
論文 参考訳（メタデータ） (2020-02-16T08:35:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。