論文の概要: Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing

• arxiv url: http://arxiv.org/abs/2503.07775v1
• Date: Mon, 10 Mar 2025 18:57:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:45:54.736163
• Title: Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing
• Title（参考訳）: WassersteinとTotal Variation Distanceのサブ線形アルゴリズム:公正性とプライバシ監査への応用
• Authors: Debabrota Basu, Debarshi Chanda,
• Abstract要約: 本稿では,ガウス分布のPDFとCDFを推定する汎用アルゴリズムフレームワークを提案する。 サブ線形空間W.r.t.を必要とするサンプルのストリームから, 分布のマージ可能な要約を計算する。 これにより、サンプルがストリームや複数のソースから到着している間に、Wasserstein と Total Variation (TV) の距離を2つの準ガウス距離で推定することができる。
• 参考スコア（独自算出の注目度）: 7.81603404636933
• License:
• Abstract: Resource-efficiently computing representations of probability distributions and the distances between them while only having access to the samples is a fundamental and useful problem across mathematical sciences. In this paper, we propose a generic algorithmic framework to estimate the PDF and CDF of any sub-Gaussian distribution while the samples from them arrive in a stream. We compute mergeable summaries of distributions from the stream of samples that require sublinear space w.r.t. the number of observed samples. This allows us to estimate Wasserstein and Total Variation (TV) distances between any two sub-Gaussian distributions while samples arrive in streams and from multiple sources (e.g. federated learning). Our algorithms significantly improves on the existing methods for distance estimation incurring super-linear time and linear space complexities. In addition, we use the proposed estimators of Wasserstein and TV distances to audit the fairness and privacy of the ML algorithms. We empirically demonstrate the efficiency of the algorithms for estimating these distances and auditing using both synthetic and real-world datasets.
• Abstract（参考訳）: 確率分布とそれらの間の距離の表現を資源効率よく計算し、サンプルへのアクセスしか行わないことは、数学の分野において基本的な、有用な問題である。 本稿では,ガウス分布のPDFとCDFを推定する汎用アルゴリズムフレームワークを提案する。 サブ線形空間W.r.t.を必要とするサンプルのストリームから, 分布のマージ可能な要約を計算する。 これにより、2つの準ガウス分布間のワッサーシュタインとトータル変分(TV)距離を推定でき、サンプルはストリームや複数のソース(例えばフェデレート学習)から到着する。 提案アルゴリズムは,超線形時間と線形空間の複素量による距離推定手法を改良した。 さらに、WassersteinとTV距離の推定器を用いて、MLアルゴリズムの公平性とプライバシを監査する。 我々は,これらの距離を推定し,実世界のデータセットを用いた監査を行うアルゴリズムの効率を実証的に実証した。

関連論文リスト

• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Distributed Bayesian Estimation in Sensor Networks: Consensus on Marginal Densities [15.038649101409804]
  連続変数上の確率分布の関数空間において、確率的確率的アルゴリズムを導出する。 これらの結果を利用して、個々のエージェントが観測する変数のサブセットに制限された新しい分散推定器を得る。 これは、協調的なローカライゼーションやフェデレートドラーニングのような応用に関係しており、任意のエージェントで収集されたデータは、関心のあるすべての変数のサブセットに依存する。
  論文  参考訳（メタデータ） (2023-12-02T21:10:06Z)
• Flow-based Distributionally Robust Optimization [23.232731771848883]
  We present a framework, called $textttFlowDRO$, for solve flow-based distributionally robust optimization (DRO) problem with Wasserstein uncertainty set。 我々は、連続した最悪のケース分布(Last Favorable Distribution, LFD)とそれからのサンプルを見つけることを目指している。 本稿では、逆学習、分布論的に堅牢な仮説テスト、およびデータ駆動型分布摂動差分プライバシーの新しいメカニズムを実証する。
  論文  参考訳（メタデータ） (2023-10-30T03:53:31Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Unsupervised Learning of Sampling Distributions for Particle Filters [80.6716888175925]
  観測結果からサンプリング分布を学習する4つの方法を提案する。 実験により、学習されたサンプリング分布は、設計された最小縮退サンプリング分布よりも優れた性能を示すことが示された。
  論文  参考訳（メタデータ） (2023-02-02T15:50:21Z)
• Super-resolution GANs of randomly-seeded fields [68.8204255655161]
  ランダムスパースセンサからフィールド量の推定を行うための,GAN(Super- resolution Generative Adversarial Network)フレームワークを提案する。 このアルゴリズムはランダムサンプリングを利用して、高解像度の基底分布の不完全ビューを提供する。 提案手法は, 流体流動シミュレーション, 海洋表面温度分布測定, 粒子画像速度測定データの合成データベースを用いて検証した。
  論文  参考訳（メタデータ） (2022-02-23T18:57:53Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  粒子フィルタリングは複素系の優れた非線形推定を計算するために用いられる。 粒子フィルタは様々なシナリオにおいて良好な推定値が得られることを示す。
  論文  参考訳（メタデータ） (2021-10-06T16:58:34Z)
• Efficient Discretizations of Optimal Transport [16.996068297291057]
  境界分布に対して与えられた点数で離散化を計算するアルゴリズムを提案する。 我々は近似の限界を証明し、幅広い問題について性能を実証する。
  論文  参考訳（メタデータ） (2021-02-16T04:31:52Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  高次元の2つの確率分布の間のワッサーシュタイン測地線を計算するための新しい定式化と学習戦略を提案する。 ラグランジュ乗算器の手法を最適輸送(OT)問題の動的定式化に適用することにより、サドル点がワッサーシュタイン測地線であるミニマックス問題を導出する。 次に、深層ニューラルネットワークによる関数のパラメータ化を行い、トレーニングのためのサンプルベースの双方向学習アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-02-05T04:25:28Z)

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

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