論文の概要: Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

• arxiv url: http://arxiv.org/abs/2502.16355v1
• Date: Sat, 22 Feb 2025 21:04:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:51:40.315109
• Title: Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
• Title（参考訳）: サブキューブ条件付き高次元分布の単調性試験
• Authors: Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten,
• Abstract要約: サブキューブ条件下での1,1n$の高次元分布の単調性試験について検討した。 本研究は,関数単調性テストのために開発された有向等尺不等式を用いて分布試験アルゴリズムを解析した最初のものである。
• 参考スコア（独自算出の注目度）: 10.903818216004703
• License:
• Abstract: We study monotonicity testing of high-dimensional distributions on $\{-1,1\}^n$ in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio~\cite{CRS15} and Bhattacharyya and Chakraborty~\cite{BC18}. Previous work shows that the \emph{sample complexity} of monotonicity testing must be exponential in $n$ (Rubinfeld, Vasilian~\cite{RV20}, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee~\cite{AGPRY19}). We show that the subcube \emph{query complexity} is $\tilde{\Theta}(n/\varepsilon^2)$, by proving nearly matching upper and lower bounds. Our work is the first to use directed isoperimetric inequalities (developed for function monotonicity testing) for analyzing a distribution testing algorithm. Along the way, we generalize an inequality of Khot, Minzer, and Safra~\cite{KMS18} to real-valued functions on $\{-1,1\}^n$. We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio~\cite{RS09} , using subcube conditioning. We show that the query complexity is $\tilde{\Theta}(\sqrt{n}/\varepsilon^2)$. Our work proves the lower bound, which matches (up to poly-logarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten~\cite{CCKLW21}). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.
• Abstract（参考訳）: サブキューブ条件下での高次元分布の単調性試験を,Canonne, Ron, Servedio~\cite{CRS15} と Bhattacharyya および Chakraborty~\cite{BC18} で提案し,研究した。 以前の研究は、単調性テストの 'emph{sample complexity} が指数関数的に$n$(Rubinfeld, Vasilian~\cite{RV20}, Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee~\cite{AGPRY19})でなければならないことを示している。 サブキューブ \emph{query complexity} が$\tilde{\Theta}(n/\varepsilon^2)$であることを示す。 本研究は,関数単調性テストのために開発された有向等尺不等式を用いて分布試験アルゴリズムを解析した最初のものである。 その過程で、Khot, Minzer, Safra~\cite{KMS18} の不等式を$\{-1,1\}^n$ 上の実数値関数に一般化する。 また、サブキューブ条件付けを用いて、ルビンフェルトが導入した問題である単調分布の均一性試験についても検討する。 クエリの複雑さは$\tilde{\Theta}(\sqrt{n}/\varepsilon^2)$であることを示す。 我々の研究は、一般分布 (Canonne, Chen, Kamath, Levi, Waingarten~\cite{CCKLW21}) に対する一様性テストの上界に一致する下界を証明する。 したがって、単調性は対数的因子を超えて、サブキューブ条件付きクエリによる分布の均一性をテストするのに役に立たないことを示す。

関連論文リスト

• Replicable Uniformity Testing [1.5883812630616523]
  この研究は、アルゴリズムの複製性という枠組みの下で一様性テストを再考する。 我々は, $tildeO(sqrtn varepsilon-2 rho-1)$サンプルのみを用いて複製可能なテスタを得る。
  論文  参考訳（メタデータ） (2024-10-12T02:55:17Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
  一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。 1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。 衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
  論文  参考訳（メタデータ） (2022-06-21T20:43:53Z)
• Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
  我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。 繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。 要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
  論文  参考訳（メタデータ） (2021-12-29T14:47:56Z)
• 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)
• Learning and Testing Junta Distributions with Subcube Conditioning [11.464622619555222]
  本研究では,一様分布に関して,1,1n$のユンタ分布の学習と試験の問題点について検討する。 主な寄与は、サブキューブ条件付き$k$-junta分布における関連する座標を見つけるアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-26T22:52:53Z)

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

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