論文の概要: On the Computational Complexity of Private High-dimensional Model
Selection via the Exponential Mechanism
- arxiv url: http://arxiv.org/abs/2310.07852v1
- Date: Wed, 11 Oct 2023 19:53:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-14 14:05:42.304982
- Title: On the Computational Complexity of Private High-dimensional Model
Selection via the Exponential Mechanism
- Title(参考訳): 指数メカニズムによるプライベート高次元モデル選択の計算複雑性について
- Authors: Saptarshi Roy, Ambuj Tewari
- Abstract要約: 差分プライバシーの枠組みの下で,高次元線形回帰モデルにおけるモデル選択の問題を考える。
我々は、最良のモデルを選択するためのよく知られた指数的メカニズムを採用し、あるマージン条件の下では、その強力なモデル回復特性を確立する。
この課題を克服するために、サンプリングステップのためのメトロポリス・ハスティングスアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 22.702730258341166
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of model selection in a high-dimensional sparse
linear regression model under the differential privacy framework. In
particular, we consider the problem of differentially private best subset
selection and study its utility guarantee. We adopt the well-known exponential
mechanism for selecting the best model, and under a certain margin condition,
we establish its strong model recovery property. However, the exponential
search space of the exponential mechanism poses a serious computational
bottleneck. To overcome this challenge, we propose a Metropolis-Hastings
algorithm for the sampling step and establish its polynomial mixing time to its
stationary distribution in the problem parameters $n,p$, and $s$. Furthermore,
we also establish approximate differential privacy for the final estimates of
the Metropolis-Hastings random walk using its mixing property. Finally, we also
perform some illustrative simulations that echo the theoretical findings of our
main results.
- Abstract(参考訳): 微分プライバシーの枠組みの下では,高次元スパース線形回帰モデルにおけるモデル選択の問題を考える。
特に、微分プライベートなベストサブセット選択の問題を検討し、その実用性保証について検討する。
最善のモデルを選択するためのよく知られた指数関数的メカニズムを採用し、ある限界条件下では、その強いモデル回復特性を確立する。
しかし、指数的機構の指数的探索空間は深刻な計算ボトルネックを引き起こす。
この課題を克服するために、サンプリングステップのためのMetropolis-Hastingsアルゴリズムを提案し、問題パラメータ$n,p$および$s$の定常分布に対する多項式混合時間を確立する。
さらに,metropolis-hastingsランダムウォークの最終推定のための近似微分プライバシーを,その混合特性を用いて確立する。
最後に, 主結果の理論的知見を反映する数値シミュレーションも実施する。
関連論文リスト
- Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳(メタデータ) (2024-04-16T20:01:10Z) - Differentially Private Gradient Flow based on the Sliced Wasserstein
Distance for Non-Parametric Generative Modeling [61.65137699747604]
確率測度空間におけるパラメータフリー勾配流に基づく、新しい微分プライベートな生成モデリング手法を提案する。
提案手法は,ジェネレータベースモデルと比較して,低プライバシー予算で高忠実度データを生成可能であることを示す。
論文 参考訳(メタデータ) (2023-12-13T15:47:30Z) - Best-Subset Selection in Generalized Linear Models: A Fast and
Consistent Algorithm via Splicing Technique [0.6338047104436422]
ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。
軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。
我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
論文 参考訳(メタデータ) (2023-08-01T03:11:31Z) - Differentiating Metropolis-Hastings to Optimize Intractable Densities [51.16801956665228]
我々はメトロポリス・ハスティングス検層の自動識別アルゴリズムを開発した。
難解な対象密度に対する期待値として表現された目的に対して勾配に基づく最適化を適用する。
論文 参考訳(メタデータ) (2023-06-13T17:56:02Z) - Fast Feature Selection with Fairness Constraints [49.142308856826396]
モデル構築における最適特徴の選択に関する基礎的問題について検討する。
この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。
適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。
提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
論文 参考訳(メタデータ) (2022-02-28T12:26:47Z) - Time varying regression with hidden linear dynamics [74.9914602730208]
線形力学系に従って未知のパラメータが進化することを前提とした時間変化線形回帰モデルを再検討する。
反対に、基礎となる力学が安定である場合、このモデルのパラメータは2つの通常の最小二乗推定と組み合わせることで、データから推定できることが示される。
論文 参考訳(メタデータ) (2021-12-29T23:37:06Z) - Model Selection for Bayesian Autoencoders [25.619565817793422]
本稿では,オートエンコーダの出力と経験的データ分布との分散スライス-ワッサーシュタイン距離を最適化することを提案する。
我々のBAEは、フレキシブルなディリクレ混合モデルを潜在空間に適合させることにより、生成モデルに変換する。
我々は,教師なしの学習課題に対する膨大な実験的キャンペーンを質的かつ定量的に評価し,先行研究が重要となる小規模データ体制において,我々のアプローチが最先端の結果をもたらすことを示す。
論文 参考訳(メタデータ) (2021-06-11T08:55:00Z) - High-Dimensional Differentially-Private EM Algorithm: Methods and
Near-Optimal Statistical Guarantees [8.089708900273804]
高次元潜在変数モデルにおける差分プライベート期待最大化(EM)アルゴリズムを設計するための一般的なフレームワークを開発している。
各モデルにおいて、差分プライバシー制約による収束のほぼ最適度を確立する。
この設定では、差分プライバシーを保証する近レート最適EMアルゴリズムを提案します。
論文 参考訳(メタデータ) (2021-04-01T04:08:34Z) - Community Detection in the Stochastic Block Model by Mixed Integer
Programming [3.8073142980733]
Degree-Corrected Block Model (DCSBM) は、コミュニティ構造を持つランダムグラフを生成する一般的なモデルである。
DCSBMに基づくコミュニティ検出の標準的なアプローチは、最大推定(MLE)により観測されたネットワークデータを生成する可能性が最も高いモデルパラメータを探索することである。
本稿では,モデルパラメータと最大確率のコミュニティ割当を観測グラフから確実に求める数学的計画式と厳密解法を提案する。
論文 参考訳(メタデータ) (2021-01-26T22:04:40Z) - Control as Hybrid Inference [62.997667081978825]
本稿では、反復推論と償却推論のバランスを自然に仲介するCHIの実装について述べる。
連続的な制御ベンチマークでアルゴリズムのスケーラビリティを検証し、強力なモデルフリーおよびモデルベースラインを上回る性能を示す。
論文 参考訳(メタデータ) (2020-07-11T19:44:09Z) - Uncertainty Modelling in Risk-averse Supply Chain Systems Using
Multi-objective Pareto Optimization [0.0]
サプライチェーンモデリングにおける困難なタスクの1つは、不規則な変動に対して堅牢なモデルを構築することである。
我々は、不確実性を扱うためのパレート最適化(Pareto Optimization)という新しい手法を導入し、これらの不確実性のエントロピーをアプリオリ仮定の下で明示的にモデル化することで拘束する。
論文 参考訳(メタデータ) (2020-04-24T21:04:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。