論文の概要: A dimension-free discrete Remez inequality on multi-tori
- arxiv url: http://arxiv.org/abs/2310.07926v2
- Date: Fri, 13 Oct 2023 16:11:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-16 16:27:20.113108
- Title: A dimension-free discrete Remez inequality on multi-tori
- Title（参考訳）: マルチトリの次元自由離散レメズ不等式
- 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アンサンブル上の低次量子可観測性を学ぶための時間効率とサンプル最適アルゴリズムを与える。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Noncompact uniform universal approximation [0.0]
普遍近似定理は、(コンパクトでない)入力空間 $mathbbRn$ 上の一様収束に一般化される。
無限大で消えるすべての連続関数は、ニューラルネットワークによって一様に近似することができる。
論文 参考訳（メタデータ） (2023-08-07T08:54:21Z) - Higher rank antipodality [0.0]
一般確率論に動機づけられて、集合 $X$ in $mathbbRd$ はランク $k$ のエンファンティポッドであると言う。
k=1$ の場合、Klee が導入した(ペアワイズで)反ポッド性の概念と一致する。
論文 参考訳（メタデータ） (2023-07-31T17:15:46Z) - 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) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳（メタデータ） (2022-06-23T16:23:59Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - 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) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Some convergent results for Backtracking Gradient Descent method on
Banach spaces [0.0]
bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。
$mathcalC$ を $f$ の臨界点の集合とする。
論文 参考訳（メタデータ） (2020-01-16T12:49:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。