論文の概要: Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization

• arxiv url: http://arxiv.org/abs/2303.12921v1
• Date: Wed, 22 Mar 2023 21:35:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-24 16:17:29.008529
• Title: Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
• Title（参考訳）: 安定性は安定 - 再現性、プライバシ、適応的一般化のつながり
• Authors: Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell, Satchit Sivakumar
• Abstract要約: 複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。 データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。 我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
• 参考スコア（独自算出の注目度）: 26.4468964378511
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The notion of replicable algorithms was introduced in Impagliazzo et al. [STOC '22] to describe randomized algorithms that are stable under the resampling of their inputs. More precisely, a replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. Using replicable algorithms for data analysis can facilitate the verification of published results by ensuring that the results of an analysis will be the same with high probability, even when that analysis is performed on a new data set. In this work, we establish new connections and separations between replicability and standard notions of algorithmic stability. In particular, we give sample-efficient algorithmic reductions between perfect generalization, approximate differential privacy, and replicability for a broad class of statistical problems. Conversely, we show any such equivalence must break down computationally: there exist statistical problems that are easy under differential privacy, but that cannot be solved replicably without breaking public-key cryptography. Furthermore, these results are tight: our reductions are statistically optimal, and we show that any computational separation between DP and replicability must imply the existence of one-way functions. Our statistical reductions give a new algorithmic framework for translating between notions of stability, which we instantiate to answer several open questions in replicability and privacy. This includes giving sample-efficient replicable algorithms for various PAC learning, distribution estimation, and distribution testing problems, algorithmic amplification of $\delta$ in approximate DP, conversions from item-level to user-level privacy, and the existence of private agnostic-to-realizable learning reductions under structured distributions.
• Abstract（参考訳）: レプリカブルアルゴリズムの概念は、Impagliazzo et alで導入された。 [STOC '22]は入力の再サンプリングの下で安定なランダム化アルゴリズムを記述する。 より正確には、replicableアルゴリズムは、ランダム性が固定され、同じ分布から新しいi.i.d.サンプル上で実行される場合に、高い確率で同じ出力を与える。 データ解析にレプリカブルアルゴリズムを用いることで、新たなデータセット上で解析を行う場合でも、分析結果が高い確率で同じになるようにして、公開結果の検証を容易にすることができる。 本研究では,複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。 特に、完全な一般化、近似微分プライバシー、幅広い統計問題に対する再現性の間のサンプル効率の高いアルゴリズム還元を与える。 逆に、そのような等価性は計算的に分解しなければならない: 差分プライバシー下では容易であるが、公開鍵暗号を破ることなく複製的に解決できない統計問題が存在する。 さらに、これらの結果は、統計的に最適であり、DPと複製性の間の計算的分離が一方向関数の存在を示唆していることを示す。 我々の統計的削減は、安定性の概念を翻訳するための新しいアルゴリズムの枠組みを与え、複製性とプライバシに関するいくつかのオープンな疑問に即座に答えられるようにします。 これには、様々なpac学習、分布推定、分布テスト問題のためのサンプル効率の高いレプリカブルアルゴリズム、近似dpにおける$\delta$のアルゴリズム増幅、アイテムレベルからユーザレベルのプライバシへの変換、構造化分布下での非依存から実現可能な学習削減の存在が含まれる。

関連論文リスト

• Replicability in High Dimensional Statistics [18.543059748500358]
  本稿では,いくつかの基本的高次元統計課題に対する再現性の計算的および統計的コストについて検討する。 我々の主な貢献は、最適なレプリカブルアルゴリズムと高次元等尺波の計算的および統計的等価性を確立することである。
  論文  参考訳（メタデータ） (2024-06-04T00:06:42Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• On Correlation Detection and Alignment Recovery of Gaussian Databases [5.33024001730262]
  相関検出は仮説テストの問題であり、ヌル仮説ではデータベースは独立であり、代替仮説では相関する。 我々は,タイプIとタイプIIの誤差確率のバウンダリを開発し,解析された検出器が最近提案した検出器よりも優れた性能を示すことを示す。 データベースが相関として受け入れられると、アルゴリズムは与えられたデータベース間の部分的なアライメントを復元する。
  論文  参考訳（メタデータ） (2022-11-02T12:01:42Z)
• Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation [8.9598796481325]
  本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。 プライベートスパース平均推定のための情報計算ギャップを確立する。 また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
  論文  参考訳（メタデータ） (2022-11-01T20:03:41Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。 目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。 提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
  論文  参考訳（メタデータ） (2020-07-07T18:25:25Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。 本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
  論文  参考訳（メタデータ） (2020-03-27T05:13:29Z)
• Statistically Guided Divide-and-Conquer for Sparse Factorization of Large Matrix [2.345015036605934]
  統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。 第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。 第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
  論文  参考訳（メタデータ） (2020-03-17T19:12:21Z)

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

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