Fugu-MT 論文翻訳(概要): Locality Bounds for Sampling Hamming Slices

論文の概要: Locality Bounds for Sampling Hamming Slices

arxiv url: http://arxiv.org/abs/2402.14278v1
Date: Thu, 22 Feb 2024 04:36:49 GMT
ステータス: 処理完了
システム内更新日: 2024-02-23 16:20:19.712584
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 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)
Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting [35.78863301525758]
任意の仮説クラスにおける補間子の一般化誤差に対して一様収束を保証する。ユークリッド標準球への一般境界の適用は、最小ノルム補間器に対するBartlett et al. (2020) の一貫性を回復する。我々は、少なくともいくつかの設定において、ノルムベースの一般化境界がどのように説明され、良性過剰適合の分析に使用されるかを示す。
論文参考訳（メタデータ） (2021-06-17T06:58:10Z)
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)

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