論文の概要: Dimension-free Remez Inequalities and norm designs

• arxiv url: http://arxiv.org/abs/2310.07926v3
• Date: Sun, 12 Nov 2023 22:33:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-14 20:28:55.982556
• Title: Dimension-free Remez Inequalities and norm designs
• Title（参考訳）: 次元フリー remez の不等式とノルム設計
• Authors: Lars Becker, Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang
• Abstract要約: 自由レメス不等式の動機は、量子学習理論から生まれている。 我々の自由次元は、天文学的に多数の変数を学習するための時間効率とサンプルアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 48.5897526636987
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical Remez inequality bounds the maximum of the absolute value of a polynomial of degree $d$ on a segment through the maximum of its absolute value on any subset $E$ of positive Lebesgue measure of this segment. Similarly, in several variables the maximum of the absolute value of a polynomial of degree $d$ over a larger set is bounded by the maximum of the absolute value of a polynomial on a subset. There are many such inequalities in the literature, but all of them get spoiled when dimension grows. This article is devoted to the dimension free estimates of this type, where a subset is a grid or a rather sparse subset of the grid. The motivation for the dimension free Remez inequality came very naturally from the quantum learning theory, where we need to approximately restore with large probability a big matrix by a relatively small number of random queries, see \cite{VZ22}, \cite{SVZ}. Our dimension free inequality gives time-efficient and sample-optimal algorithms for learning low-degree polynomials of astronomically large number of variables as well as low-degree quantum observables on qudit ensembles, see \cite{SVZ} for those applications.
• Abstract（参考訳）: 古典レメズ不等式は、このセグメントの正ルベーグ測度の任意の部分集合 $e$ 上の絶対値の最大値を通じて、あるセグメント上の次数 $d$ の多項式の絶対値の最大値を与える。 同様に、いくつかの変数において、より大きな集合上の次数$d$の多項式の絶対値の最大値は、部分集合上の多項式の絶対値の最大値によって制限される。 文学にはそのような不等式が多数あるが、寸法が大きくなるとすべてが台無しになる。 この記事は、このタイプの次元自由推定に特化しており、ここでは、サブセットはグリッドまたはグリッドの比較的スパースな部分集合である。 次元自由レメズ不等式に対するモチベーションは量子学習理論から非常に自然に生まれており、比較的少数のランダムなクエリによって大きな行列を大確率で復元する必要がある。 我々の次元自由不等式は、天文学的に多量の変数の低次多項式やquditアンサンブル上の低次量子可観測性を学ぶための時間効率とサンプル最適アルゴリズムを与える。

関連論文リスト

• An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
  有限体 $mathbbF_q2$ は$q2$ 要素からなる。 まず、いくつかの重要な単純化を取り入れた電力関数 $f(x) = xq+2$ on $mathbbF_q2$ の微分スペクトルを決定する方法を提案する。
  論文  参考訳（メタデータ） (2024-07-08T14:01:06Z)
• Some new infinite families of non-$p$-rational real quadratic fields [0.0]
  同時に、$p_j$-有理実体の無限族を構成するための単純な方法論を与え、$p_j$の任意の上を無理化する。 これらの技法の1つの特徴は、素体$K=mathbbQ(sqrtD)$を、極大アーベル群のガロア群のトーション群の$p$パワー巡回成分である$p$を超える非有理な外部素数の$K$が$paであるような体を与えるのに使用できることである。
  論文  参考訳（メタデータ） (2024-06-20T18:00:51Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Monogamy of entanglement between cones [68.8204255655161]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
  mathbb Cd$ の正則基底の集合 $k$ は互いに非バイアスな $|langle e,frangle |2 = 1/d$ と呼ばれ、$e$ と $f$ は異なる基底の基底ベクトルである。 この対称性を(解析的に)利用して、半定値プログラムのサイズを縮小し、取り外し可能とする。
  論文  参考訳（メタデータ） (2021-11-10T14:14:53Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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