論文の概要: Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing
- arxiv url: http://arxiv.org/abs/2503.07775v2
- Date: Wed, 18 Jun 2025 04:37:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-19 16:34:05.332344
- 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要約: Weibull の確率および累積分布関数 (PDF と CDF) を学習するための汎用フレームワークを提案する。
我々は,サブ線形空間のみを必要としながら,サンプルストリームからの分布のマージ可能な要約を計算する。
提案アルゴリズムは,超線形時間と線形空間の複素量による距離推定手法を改良した。
- 参考スコア（独自算出の注目度）: 7.81603404636933
- License: http://creativecommons.org/licenses/by/4.0/
- 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 framework to learn the probability and cumulative distribution functions (PDFs and CDFs) of a sub-Weibull, i.e. almost any light- or heavy-tailed, distribution while the samples from it arrive in a stream. The idea is to reduce these problems into estimating the frequency of an \textit{appropriately chosen subset} of the support of a \textit{properly discretised distribution}. We leverage this reduction to compute mergeable summaries of distributions from the stream of samples while requiring only sublinear space relative to the number of observed samples. This allows us to estimate Wasserstein and Total Variation (TV) distances between any two distributions while samples arrive in streams and from multiple sources. Our algorithms significantly improves on the existing methods for distance estimation incurring super-linear time and linear space complexities, and further extend the mergeable summaries framework to continuous distributions with possibly infinite support. Our results are tight with respect to the existing lower bounds for bounded discrete distributions. In addition, we leverage our proposed estimators of Wasserstein and TV distances to tightly audit the fairness and privacy of algorithms. We empirically demonstrate the efficiency of proposed algorithms across synthetic and real-world datasets.
- Abstract（参考訳）: 確率分布とそれらの間の距離の表現を資源効率よく計算し、サンプルへのアクセスしか行わないことは、数学の分野において基本的な、有用な問題である。
本稿では,ワイブルの確率分布と累積分布関数(PDFとCDF)を学習するための一般的なフレームワークを提案する。
この考え方は、これらの問題を減らして、 \textit{properly discretized distribution} のサポートの \textit{properly selected subset} の頻度を推定することである。
この削減を利用して、サンプルのストリームからの分布のマージ可能な要約を計算し、観測されたサンプルの数に対して、サブ線形空間のみを必要とする。
これにより、2つの分布間のワッサーシュタインとトータル変量 (TV) 距離を推定でき、サンプルはストリームや複数のソースから到着する。
提案アルゴリズムは,超線形時間と線形空間の複素量による距離推定法を大幅に改善し,さらに,統合可能な要約フレームワークを無限にサポート可能な連続分布へ拡張する。
我々の結果は、有界離散分布に対する既存の下界に関して厳密である。
さらに、提案したワッサースタインとテレビの距離の推定値を利用して、アルゴリズムの公平性とプライバシを厳密に監査する。
合成および実世界のデータセット間で提案アルゴリズムの効率を実証的に実証する。
関連論文リスト
- Learning local neighborhoods of non-Gaussian graphical models: A measure transport approach [0.3749861135832072]
局所マルコフ特性を利用して各変数の条件付き独立関係を推定するスケーラブルなアルゴリズムを提案する。
提案手法は,非ガウス分布 (L-Sing) の局所空間同定 (Localized Sparsity Identification) と名付けられ,フレキシブルなトランスポートマップのクラスを用いてグラフを推定する。
論文 参考訳（メタデータ） (2025-03-18T04:53:22Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。