論文の概要: How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
- arxiv url: http://arxiv.org/abs/2409.06594v1
- Date: Tue, 10 Sep 2024 15:37:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-11 16:59:09.657306
- Title: How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
- Title（参考訳）: 任意の(合理的な)配電特性の検証方法:配電用音響調合システム
- Authors: Tal Herman, Guy Rothblum,
- Abstract要約: 本研究では,確率的検証器が解析結果がほぼ正しいことを確認するための証明システムについて検討する。
未知の分布が要求される特性を持っていることを検証する。
我々の主な貢献は、検証者と信頼できない証明者との間の対話的プロトコルであり、任意のプロパティを検証するのに使用できる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: As statistical analyses become more central to science, industry and society, there is a growing need to ensure correctness of their results. Approximate correctness can be verified by replicating the entire analysis, but can we verify without replication? Building on a recent line of work, we study proof-systems that allow a probabilistic verifier to ascertain that the results of an analysis are approximately correct, while drawing fewer samples and using less computational resources than would be needed to replicate the analysis. We focus on distribution testing problems: verifying that an unknown distribution is close to having a claimed property. Our main contribution is a interactive protocol between a verifier and an untrusted prover, which can be used to verify any distribution property that can be decided in polynomial time given a full and explicit description of the distribution. If the distribution is at statistical distance $\varepsilon$ from having the property, then the verifier rejects with high probability. This soundness property holds against any polynomial-time strategy that a cheating prover might follow, assuming the existence of collision-resistant hash functions (a standard assumption in cryptography). For distributions over a domain of size $N$, the protocol consists of $4$ messages and the communication complexity and verifier runtime are roughly $\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$. The verifier's sample complexity is $\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$, and this is optimal up to $\polylog(N)$ factors (for any protocol, regardless of its communication complexity). Even for simple properties, approximately deciding whether an unknown distribution has the property can require quasi-linear sample complexity and running time. For any such property, our protocol provides a quadratic speedup over replicating the analysis.
- Abstract（参考訳）: 統計分析が科学、産業、社会の中心となるにつれ、結果の正確性を確保する必要性が高まっている。
解析全体を複製することで、近似の正しさを検証できますが、レプリケーションなしで検証できますか?
近年の成果に基づいて,確率的検証器が解析結果がほぼ正しいことを確認しつつ,少ないサンプルを描画し,解析を再現するために必要な計算資源を少なくする実証システムについて検討している。
我々は,未知の分布が主張する特性にほぼ近いことを検証する,分散テストの問題に焦点をあてる。
我々の主な貢献は、検証者と信頼できない証明者の間の対話的プロトコルであり、このプロトコルは、分布の完全な明示的な記述が与えられた多項式時間で決定できる任意の分布特性の検証に使用できる。
分布が統計的な距離$\varepsilon$であるなら、検証者は高い確率で拒否する。
この音響特性は、衝突耐性ハッシュ関数(暗号における標準的な仮定)の存在を前提として、不正な証明者が従うべき多項式時間戦略に反する。
N$のドメイン上の分散では、プロトコルは4ドルメッセージで構成され、通信の複雑さと検証実行はおよそ$\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$である。
検証器のサンプル複雑性は$\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$であり、通信複雑性に関係なく$\polylog(N)$ factorまで最適である。
単純な性質であっても、未知の分布が性質を持つかどうかを概ね決定するには準線形サンプルの複雑さと実行時間が必要である。
このような特性に対して、我々のプロトコルは解析を複製する2次的なスピードアップを提供する。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Adaptive Data Analysis in a Balanced Adversarial Model [26.58630744414181]
適応データ解析において、メカニズムは未知の分布から$n$、すなわち$D$のサンプルを取得し、正確な推定を行う必要がある。
我々は、それぞれが2つの分離されたアルゴリズムから構成されるアンフバランスドと呼ばれる、より制限された敵を考える。
これらの強い硬さの仮定は、計算的に有界なアンフバランス逆元が公開鍵暗号の存在を示唆するという意味では避けられないことを示す。
論文 参考訳（メタデータ） (2023-05-24T15:08:05Z) - Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文 参考訳（メタデータ） (2023-02-21T17:52:23Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳（メタデータ） (2023-01-09T18:36:49Z) - Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling [5.3098033683382155]
本研究では,高次元分布におけるアイデンティティテスト問題について検討する。
私たちは、$mathsfCoordinate Oracle$という、非常に弱い条件付きサンプリングオラクルを考えています。
エントロピーの近似テンソル化(英語版)として知られる解析的性質が$n$-次元可視分布$mu$に対して成り立つならば、$tildeO(n/varepsilon)$クエリを使用して、隠れ分布$pi$に対して効率的なアイデンティティテストアルゴリズムが存在することを証明している。
論文 参考訳（メタデータ） (2022-07-19T06:49:24Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。