論文の概要: Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data

• arxiv url: http://arxiv.org/abs/2005.05889v3
• Date: Mon, 13 Sep 2021 17:23:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-03 18:42:07.798070
• Title: Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data
• Title（参考訳）: 離散データのためのプライベートアルゴリズムの一般化誤差の上限
• Authors: Borja Rodr\'iguez-G\'alvez, Germ\'an Bassi, and Mikael Skoglund
• Abstract要約: 情報理論の観点からアルゴリズムの一般化能力について検討する。 特に、$epsilon$-DP および $mu$-GDP アルゴリズムの場合、この戦略で得られた限界を示す。
• 参考スコア（独自算出の注目度）: 31.122671977370416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study the generalization capability of algorithms from an information-theoretic perspective. It has been shown that the expected generalization error of an algorithm is bounded from above by a function of the relative entropy between the conditional probability distribution of the algorithm's output hypothesis, given the dataset with which it was trained, and its marginal probability distribution. We build upon this fact and introduce a mathematical formulation to obtain upper bounds on this relative entropy. Assuming that the data is discrete, we then develop a strategy using this formulation, based on the method of types and typicality, to find explicit upper bounds on the generalization error of stable algorithms, i.e., algorithms that produce similar output hypotheses given similar input datasets. In particular, we show the bounds obtained with this strategy for the case of $\epsilon$-DP and $\mu$-GDP algorithms.
• Abstract（参考訳）: 本研究では,情報理論の観点からアルゴリズムの一般化能力について検討する。 アルゴリズムの予測一般化誤差は、アルゴリズムの出力仮説の条件付き確率分布と、学習したデータセットとその限界確率分布との間の相対エントロピーの関数によって上から有界であることが示されている。 この事実に基づいて、この相対エントロピーの上界を得る数学的定式化を導入する。 データが離散的であると仮定すると、型と典型的な方法に基づいてこの定式化を用いた戦略を開発し、安定アルゴリズムの一般化誤差、すなわち類似の入力データセットを与えられた類似の出力仮説を生成するアルゴリズムの明示的な上界を見つける。 特に,$\epsilon$-DP および $\mu$-GDP アルゴリズムの場合,この戦略で得られた境界を示す。

関連論文リスト

• An Information-Theoretic Approach to Generalization Theory [27.87324770020133]
  学習アルゴリズムと学習データ間の依存度を定量化する情報理論境界を解析する。 一定のプライバシーパラメータを持つ場合であっても,最大リークが制限されたアルゴリズムにより一般化が保証されることを示す。
  論文  参考訳（メタデータ） (2024-08-20T10:08:21Z)
• A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
  中心行列および非標準行列に対するフロベニウスノルムにおける低ランク近似誤差の解析のための枠組みを提案する。 最小限の仮定の下では、期待と確率の正確な境界を導出する。 私たちの境界には、プロパティを導出し、実践的な選択を動機付けるための明確な解釈があります。
  論文  参考訳（メタデータ） (2024-05-08T04:51:56Z)
• Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems [1.5586874069708228]
  本稿では,ランダムな個人境界を持つマーチンゲール差分列のノルムに基づく,次元自由なアゴホフディング型を新たに開発する。 本稿では,提案アルゴリズムであるProb-SARAHにおける勾配ノルム推定器の高確率境界について述べる。
  論文  参考訳（メタデータ） (2024-01-29T05:05:03Z)
• Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure [1.773764539873123]
  データに対する最悪の確率測定は、機械学習アルゴリズムの一般化能力を特徴づけるツールとして紹介される。 予測損失の感度、経験的リスクの感度、一般化ギャップなどの基本的な一般化指標は、クローズドフォーム表現を持つことが示されている。 最悪のデータ生成確率尺度とギブスアルゴリズムとの間には,新たな並列性が確立されている。
  論文  参考訳（メタデータ） (2023-12-19T15:20:27Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  ガウスのプロセスはデータセットのサイズとともに違法にスケールする。 多くの近似法が開発されており、必然的に近似誤差を導入している。 この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。 本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
  論文  参考訳（メタデータ） (2022-05-30T22:16:25Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Bootstrapping the error of Oja's Algorithm [16.017328736786922]
  ストリーム主成分分析のためのOjaのアルゴリズムから,主固有ベクトルの推定誤差の不確かさを定量化する問題を考察する。 オンラインで更新できる乗算ブートストラップアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-28T17:27:26Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  [1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。 我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。 また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
  論文  参考訳（メタデータ） (2020-04-17T12:47:04Z)

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

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