論文の概要: 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ランダムウォークの最終推定のための近似微分プライバシーを,その混合特性を用いて確立する。 最後に, 主結果の理論的知見を反映する数値シミュレーションも実施する。

関連論文リスト

• Continuous Bayesian Model Selection for Multivariate Causal Discovery [22.945274948173182]
  現在の因果的発見アプローチは、構造的識別可能性を確保するために、限定的なモデル仮定や介入データへのアクセスを必要とする。 近年の研究では、ベイズモデルの選択はより柔軟な仮定のために制限的モデリングを交換することで精度を大幅に向上させることができることが示されている。 合成データセットと実世界のデータセットの両方において、我々のアプローチの競争力を実証する。
  論文  参考訳（メタデータ） (2024-11-15T12:55:05Z)
• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  まず最適化モデルを構築し,非単調な選好をモデル化する。 本稿では,情報量測定手法と質問選択戦略を考案し,各イテレーションにおいて最も情報に富む選択肢を特定する。 2つのインクリメンタルな選好に基づくアルゴリズムは、潜在的に単調な選好を学習するために開発された。
  論文  参考訳（メタデータ） (2024-09-04T14:36:20Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。 広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。 本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
  論文  参考訳（メタデータ） (2023-09-05T13:42:11Z)
• Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique [0.6338047104436422]
  ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。 軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。 我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
  論文  参考訳（メタデータ） (2023-08-01T03:11:31Z)
• Regression with Label Differential Privacy [64.21020761920322]
  与えられた回帰損失関数の下で最適なラベルDPランダム化機構を導出する。 我々は、最適メカニズムが「ビンのランダム化応答」の形をとることを証明した。
  論文  参考訳（メタデータ） (2022-12-12T17:41:32Z)
• Feature Selection via the Intervened Interpolative Decomposition and its Application in Diversifying Quantitative Strategies [4.913248451323163]
  本稿では,観測行列の各列がそれぞれの優先度や重要性を持つ補間分解(ID)を計算するための確率論的モデルを提案する。 提案したモデルを,中国A株10株を含む実世界のデータセット上で評価した。
  論文  参考訳（メタデータ） (2022-09-29T03:36:56Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees [8.089708900273804]
  高次元潜在変数モデルにおける差分プライベート期待最大化(EM)アルゴリズムを設計するための一般的なフレームワークを開発している。 各モデルにおいて、差分プライバシー制約による収束のほぼ最適度を確立する。 この設定では、差分プライバシーを保証する近レート最適EMアルゴリズムを提案します。
  論文  参考訳（メタデータ） (2021-04-01T04:08:34Z)
• On Statistical Efficiency in Learning [37.08000833961712]
  モデルフィッティングとモデル複雑性のバランスをとるためのモデル選択の課題に対処する。 モデルの複雑さを順次拡大し、選択安定性を高め、コストを削減するオンラインアルゴリズムを提案します。 実験の結果, 提案手法は予測能力が高く, 計算コストが比較的低いことがわかった。
  論文  参考訳（メタデータ） (2020-12-24T16:08:29Z)
• Control as Hybrid Inference [62.997667081978825]
  本稿では、反復推論と償却推論のバランスを自然に仲介するCHIの実装について述べる。 連続的な制御ベンチマークでアルゴリズムのスケーラビリティを検証し、強力なモデルフリーおよびモデルベースラインを上回る性能を示す。
  論文  参考訳（メタデータ） (2020-07-11T19:44:09Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)

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

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