論文の概要: Characterizing the Distinguishability of Product Distributions through Multicalibration

• arxiv url: http://arxiv.org/abs/2412.03562v1
• Date: Wed, 04 Dec 2024 18:56:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-05 15:06:20.243903
• Title: Characterizing the Distinguishability of Product Distributions through Multicalibration
• Title（参考訳）: マルチキャリブレーションによる製品分布の識別可能性の評価
• Authors: Cassandra Marcussen, Aaron L. Putterman, Salil Vadhan,
• Abstract要約: 我々は、$X_0otimes k$と$X_1otimes k$を効率的に区別するために必要となるサンプル数$k$の新しい厳密な特徴を証明した。 我々のフレームワークはGeier (TCC 2022) の結果の導出に利用できる。
• 参考スコア（独自算出の注目度）: 9.695176684285832
• License:
• Abstract: Given a sequence of samples $x_1, \dots , x_k$ promised to be drawn from one of two distributions $X_0, X_1$, a well-studied problem in statistics is to decide $\textit{which}$ distribution the samples are from. Information theoretically, the maximum advantage in distinguishing the two distributions given $k$ samples is captured by the total variation distance between $X_0^{\otimes k}$ and $X_1^{\otimes k}$. However, when we restrict our attention to $\textit{efficient distinguishers}$ (i.e., small circuits) of these two distributions, exactly characterizing the ability to distinguish $X_0^{\otimes k}$ and $X_1^{\otimes k}$ is more involved and less understood. In this work, we give a general way to reduce bounds on the computational indistinguishability of $X_0$ and $X_1$ to bounds on the $\textit{information-theoretic}$ indistinguishability of some specific, related variables $\widetilde{X}_0$ and $\widetilde{X}_1$. As a consequence, we prove a new, tight characterization of the number of samples $k$ needed to efficiently distinguish $X_0^{\otimes k}$ and $X_1^{\otimes k}$ with constant advantage as \[ k = \Theta\left(d_H^{-2}\left(\widetilde{X}_0, \widetilde{X}_1\right)\right), \] which is the inverse of the squared Hellinger distance $d_H$ between two distributions $\widetilde{X}_0$ and $\widetilde{X}_1$ that are computationally indistinguishable from $X_0$ and $X_1$. Likewise, our framework can be used to re-derive a result of Geier (TCC 2022), proving nearly-tight bounds on how computational indistinguishability scales with the number of samples for arbitrary product distributions.
• Abstract（参考訳）: サンプルの列が$x_1, \dots , x_k$ となると、X_0, X_1$ という2つの分布のうちの1つから引き出されることが約束される。 理論的には、$k$の2つの分布を区別する最大の利点は、$X_0^{\otimes k}$と$X_1^{\otimes k}$の合計変動距離によって得られる。 しかしながら、これらの2つの分布の$\textit{efficient distinguishers}$(つまり、小さな回路)に注意を向けると、$X_0^{\otimes k}$と$X_1^{\otimes k}$を区別する能力はより複雑で理解しにくい。 本研究では、ある特定の関連する変数の$\widetilde{X}_0$ と $\widetilde{X}_1$ の有界値に対して、$X_0$ と $X_1$ の計算不連続値に対する有界値の一般的な方法を与える。 その結果、$X_0^{\otimes k}$ と $X_1^{\otimes k}$ を効率よく区別するのに必要なサンプルの数を新しく、より厳密に評価した: \[k = \Theta\left(d_H^{-2}\left(\widetilde{X}_0, \widetilde{X}_1\right)\right), \] 正方形ヘルリングアー距離 $d_H$ の 2つの分布間の逆数である $\widetilde{X}_0$ と $\widetilde{X}_1$ は、$X_0$ と$X_1$ と計算的に区別できない。 同様に、我々のフレームワークはGeier (TCC 2022) の結果の再帰に利用することができ、任意の製品分布のサンプル数と計算の不一致性がどのようにスケールするかについて、ほぼタイトな境界を証明できる。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
  1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。 目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
  論文  参考訳（メタデータ） (2024-03-14T15:04:45Z)
• Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
  多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。 具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。 本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
  論文  参考訳（メタデータ） (2023-11-22T04:34:09Z)
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
  任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。 また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
  論文  参考訳（メタデータ） (2023-09-25T09:50:15Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)
• Sample Amplification: Increasing Dataset Size even when Learning is Impossible [15.864702679819544]
  未知のディストリビューションから引き出されたデータである$D$が、このデータセットを増幅し、さらに大きなサンプルセットを$D$から抽出したように見えるように出力することは、どの程度まで可能か? この問題は次のように定式化する: $left(n, n + Theta(fracnsqrtk)right)$アンプが存在するが、小さな定数全変動距離への分布を学習するには$Theta(d)$サンプルが必要である。
  論文  参考訳（メタデータ） (2019-04-26T21:42:44Z)

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

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