論文の概要: Efficient Testing Implies Structured Symmetry

• arxiv url: http://arxiv.org/abs/2511.03653v1
• Date: Wed, 05 Nov 2025 17:10:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-06 18:19:32.502569
• Title: Efficient Testing Implies Structured Symmetry
• Title（参考訳）: 効率的な試験インプリス構造対称性
• Authors: Cynthia Dwork, Pranay Tankala,
• Abstract要約: 少ないサンプルから効率的に検証できる性質と、構造化対称性を持つ性質の同値性を示す。 この結果は任意の領域上での高エントロピー分布試験に一般化される。
• 参考スコア（独自算出の注目度）: 4.110863713353763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a small random sample of $n$-bit strings labeled by an unknown Boolean function, which properties of this function can be tested computationally efficiently? We show an equivalence between properties that are efficiently testable from few samples and properties with structured symmetry, which depend only on the function's average values on parts of a low-complexity partition of the domain. Without the efficiency constraint, a similar characterization in terms of unstructured symmetry was obtained by Blais and Yoshida (2019). Our main technical tool is supersimulation, which builds on methods from the algorithmic fairness literature to approximate arbitrarily complex functions by small-circuit simulators that fool significantly larger distinguishers. We extend the characterization along other axes as well. We show that allowing parts to overlap exponentially reduces their required number, broadening the scope of the construction from properties testable with $O(\log n)$ samples to properties testable with $O(n)$ samples. For larger sample sizes, we show that any efficient tester is essentially checking for indistinguishability from a bounded collection of small circuits, in the spirit of a characterization of testable graph properties. Finally, we show that our results for Boolean function testing generalize to high-entropy distribution testing on arbitrary domains.
• Abstract（参考訳）: 未知のブール関数でラベル付けされた$n$-bit文字列の小さなランダムサンプルが与えられたとき、この関数の特性を計算的に効率的にテストできるだろうか? 少ないサンプルから効率的に検証できる性質と、その領域の低複雑さ分割の部分における関数の平均値にのみ依存する構造的対称性を持つ性質との同値性を示す。 効率の制約がなければ、非構造対称性の観点からも同様の特徴づけがBreis and Yoshida (2019) によって得られた。 我々の主な技術ツールはスーパーシミュレーションであり、これはアルゴリズムフェアネスの文献から、かなり大きな微分器を騙す小回路シミュレータによる任意の複雑な関数を近似する手法に基づいている。 キャラクタリゼーションも他の軸に沿って拡張します。 我々は、部品の重複が指数関数的に減少し、$O(\log n)$サンプルでテスト可能なプロパティから$O(n)$サンプルでテスト可能なプロパティまで、構造の範囲が広がることを示した。 より大きなサンプルサイズについては、テスト可能なグラフ特性の特徴づけの精神において、効率的なテスタは、本質的に小さな回路の束縛された集合から不明瞭さをチェックしていることが示される。 最後に,ブール関数テストの結果が任意の領域上での高エントロピー分布テストに一般化されることを示す。

関連論文リスト

• Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group [0.0]
  未知のユニタリ演算の性質を推定することは、量子情報科学の基本的な課題である。 任意の可積分関数の標本効率推定のための統一的なフレームワークを提案する。 提案手法は,アダマール試験を一般化し,表現理論からツールを利用する。
  論文  参考訳（メタデータ） (2025-09-06T13:09:50Z)
• On the Structure of Replicable Hypothesis Testers [26.31630129580797]
  仮説テストアルゴリズムは、同じ分布から2つの異なるサンプルを走らせると、高い確率で同じ出力を生成する場合に複製可能である。 レプリカ可能なテスタのサンプル複雑性に対して,下限と上限を証明するための一般的なツールを構築します。 正準特性の集合を同定し、これらの特性を満たすために任意のレプリカブルなテストアルゴリズムを変更可能であることを証明する。
  論文  参考訳（メタデータ） (2025-07-03T17:51:31Z)
• On dimensionality of feature vectors in MPNNs [49.32130498861987]
  我々は、メッセージパッシンググラフニューラルネットワーク(MPNN)がWeisfeiler--Leman(WL)同型テストに対する識別力に等しいというモリスら(AAAI'19)の古典的な結果を再考する。
  論文  参考訳（メタデータ） (2024-02-06T12:56:55Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)

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

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