論文の概要: Locality Bounds for Sampling Hamming Slices
- arxiv url: http://arxiv.org/abs/2402.14278v2
- Date: Tue, 27 Feb 2024 04:45:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 20:37:43.214124
- Title: Locality Bounds for Sampling Hamming Slices
- Title（参考訳）: ハンミングスライスサンプリングのための局所性境界
- Authors: Daniel M. Kane, Anthony Ostuni, Kewen Wu
- Abstract要約: ブール関数の局所性に関する超コンスタントな下界を与えるために、ヴィオラの初期暗黙の結果を明示し、特定のハミング重みのバイナリ列上の一様分布を概ねサンプリングする。
データ構造下限と量子古典的分離への応用について論じる。
- 参考スコア（独自算出の注目度）: 8.53304576950222
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spurred by the influential work of Viola (Journal of Computing 2012), the
past decade has witnessed an active line of research into the complexity of
(approximately) sampling distributions, in contrast to the traditional focus on
the complexity of computing functions.
We build upon and make explicit earlier implicit results of Viola to provide
superconstant lower bounds on the locality of Boolean functions approximately
sampling the uniform distribution over binary strings of particular Hamming
weights, both exactly and modulo an integer, answering questions of Viola
(Journal of Computing 2012) and Filmus, Leigh, Riazanov, and Sokolov (RANDOM
2023). Applications to data structure lower bounds and quantum-classical
separations are discussed.
- Abstract（参考訳）: viola(journal of computing 2012)の影響を受けて、過去10年間、(ほぼ)サンプリング分布の複雑さについて、従来の計算関数の複雑さに焦点を当てた研究が活発に行われてきた。
我々は、viola(journal of computing 2012) と filmus, leigh, riazanov, sokolov(random 2023) の疑問に答え、特定のハミングウェイトの2進文字列上の一様分布をほぼサンプリングするブール関数の局所性に関する超定数下界を提供するために、 viola の初期の暗黙的な結果の上に構築し、明らかにする。
データ構造下限と量子古典的分離への応用について論じる。
関連論文リスト
- Sampling and Integration of Logconcave Functions by Algorithmic Diffusion [8.655526882770742]
任意の対数凹関数のサンプリング,丸化,統合の複雑さについて検討する。
我々の新しいアプローチは、一般的なログコンケーブ関数に対して、20年近くで最初の複雑さの改善を提供する。
論文 参考訳（メタデータ） (2024-11-20T17:10:24Z) - Sampling Complexity of Deep Approximation Spaces [5.946662332228774]
任意の速度でReLU活性化関数を持つニューラルネットワークによって近似できる関数が存在することが示されている。
本研究は、ReQU活性化関数に類似した結果を示すことにより、これらの知見を拡張した。
論文 参考訳（メタデータ） (2023-12-20T19:10:04Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Universal Smoothed Score Functions for Generative Modeling [3.626727150596421]
我々は、$mathbbRd$における未知の関心密度の平滑化に基づく生成モデルの問題を考える。
M-density (M-density) と呼ばれる$mathbbRMd$の滑らかな密度を学習する際の時間的複雑さを特徴付ける。
本稿では,CIFAR-10データセットを用いた生成モデルのサンプル品質について述べる。
論文 参考訳（メタデータ） (2023-03-21T08:23:37Z) - Tighter Information-Theoretic Generalization Bounds from Supersamples [27.14107452619853]
本稿では,学習アルゴリズムのための情報理論の新たな一般化境界について述べる。
提示される境界は平方根境界、高速レート境界を含み、分散と鋭さに基づく境界を含む。
理論的あるいは経験的に、これらの境界は、同じスーパーサンプル設定で知られているすべての情報理論境界よりも厳密であることを示す。
論文 参考訳（メタデータ） (2023-02-05T17:06:27Z) - Newton Cradle Spectra [0.0]
固有値と固有ベクトルの挙動に関する非摂動的な結果を示す。
これらの結果を量子コンピューティングと情報理論に適用する。
論文 参考訳（メタデータ） (2022-06-20T18:00:02Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Local versions of sum-of-norms clustering [77.34726150561087]
本手法はボールモデルにおいて任意に閉じた球を分離できることを示す。
我々は、不連結連結集合のクラスタリングで発生する誤差に定量的な有界性を証明した。
論文 参考訳（メタデータ） (2021-09-20T14:45:29Z) - Spatially Adaptive Inference with Stochastic Feature Sampling and
Interpolation [72.40827239394565]
スパースサンプリングされた場所のみの機能を計算することを提案する。
次に、効率的な手順で特徴写像を密に再構築する。
提案したネットワークは、様々なコンピュータビジョンタスクの精度を維持しながら、かなりの計算を省くために実験的に示されている。
論文 参考訳（メタデータ） (2020-03-19T15:36:31Z) - A General Method for Robust Learning from Batches [56.59844655107251]
本稿では,バッチから頑健な学習を行う一般的なフレームワークについて考察し,連続ドメインを含む任意の領域に対する分類と分布推定の限界について考察する。
本手法は,一括分節分類,一括分節,単調,対数凹,ガウス混合分布推定のための,最初の頑健な計算効率の学習アルゴリズムを導出する。
論文 参考訳（メタデータ） (2020-02-25T18:53:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。