論文の概要: Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
- arxiv url: http://arxiv.org/abs/2610.17648v1
- Date: Tue, 13 Oct 2026 03:22:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-17 18:00:57.526915
- Title: Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
- Title（参考訳）: フーリエスパースブール関数学習における最適量子サンプル複素度
- Abstract要約: ほぼ最適の$widetildeO(k)$サンプル複雑性を持つ学習者に、入力長$n$とは無関係に与えます。
これにより以前の$O(k3/2log2 k)$上界が改善される。
- 参考スコア（独自算出の注目度）: 1.5736899098702974
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\log^2 k)$ upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity $Θ(nk)$ by combining known sparse-recovery and lower-bound results.
- Abstract（参考訳）: ブール関数を最大で$k$非零フーリエ係数で正確に学習するために必要な一様量子例の数について検討する。
ほぼ最適の$\widetilde{O}(k)$サンプルの複雑さを入力長$n$とは無関係に学習者に与えます。
学習者は個々の例を個別に測定するだけでよい。
これは以前の$O(k^{3/2}\log^2 k)$上界(Arunachalam, Chakraborty, Lee, Paraashar, de Wolf, 2021)を改善する。
主成分は、フーリエ試料の独立群とサブセットの対称差によって形成される候補である。
多線型多数多項式は、不偏乱近似をフーリエの支持がこの集合にある正確な目撃者に結合する。
グラニュラリティ(Granularity)は、Fourierサポート全体を含むようにセットを強制する。
比較のために、既知のスパース・リカバリ結果と低いバウンド結果を組み合わせることで、古典的標本の複雑さを$(nk)$とする。
関連論文リスト
- Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文 参考訳（メタデータ） (2026-08-04T23:38:54Z) - Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials [2.5199066832791535]
ブールハイパーキューブ上でのサロゲートの学習問題について検討する。
通常の$L$型保証よりも、均一な$L_infty$-error保証が必要です。
本結果は,最適化セーフなサロゲートを学習する際のサンプルの複雑さの厳密な証明を提供する。
論文 参考訳（メタデータ） (2026-06-15T22:00:03Z) - Efficient Quantum Fourier Transforms For Semisimple Algebras [1.4744573105338015]
有限群に対する量子フーリエ変換(QFT)を有限次元半単純代数に対するQFTに一般化する。
これらの代数は一般化されたシュル=ワイル双対性、統計物理学、多体系において重要な役割を果たす。
論文 参考訳（メタデータ） (2026-05-06T18:08:12Z) - Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning [51.820005667020354]
有限状態と作用空間を持つ平均回帰型MDPに対して、弱い通信仮定の下で、単純だが効果的なQ-ラーニングアルゴリズムについて検討する。
We proof that the collaborations the per-agent sample complexitys to $widetildeOleft(frac|mathcalA||hstar|_mathsfsp3Mvarepsilon3right)$, with only $widetildeOleft(frac|hstar|_mathsfsp3Mvareps)。
論文 参考訳（メタデータ） (2026-01-20T06:21:54Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文 参考訳（メタデータ） (2022-09-09T23:35:25Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
フーリエスパース集合関数を学習するための新しいアルゴリズム群を提案する。
Walsh-Hadamard変換に焦点をあてた他の研究とは対照的に、我々の新しいアルゴリズムは最近導入された非直交フーリエ変換で機能する。
いくつかの実世界のアプリケーションで有効性を示す。
論文 参考訳（メタデータ） (2020-10-01T14:31:59Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。