論文の概要: Dimension-free Remez Inequalities and norm designs
- arxiv url: http://arxiv.org/abs/2310.07926v5
- Date: Wed, 20 Dec 2023 18:35:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 03:34:56.862558
- Title: Dimension-free Remez Inequalities and norm designs
- Title（参考訳）: 次元フリー remez の不等式とノルム設計
- Authors: Lars Becker, Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang
- Abstract要約: ドメインのクラスが$X$で、テストセットが$Y$で、Emphnormと呼ばれ、次元のないRemez型の見積もりを楽しむ。
ポリトーラスに$f$が拡張されたとき、$f$の上限は$mathcalO(log K)2d$以上増加しないことを示す。
- 参考スコア（独自算出の注目度）: 48.5897526636987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The classical Remez inequality bounds the supremum of a bounded-degree
polynomial on an interval $X$ by its supremum on any subset $Y\subset X$ of
positive Lebesgue measure.
There are many multivariate generalizations of the Remez inequality, but most
have constants that depend strongly on dimension.
Here we show that a broad class of domains $X$ and test sets $Y$ -- termed
\emph{norm designs} -- enjoy dimension-free Remez-type estimates.
Instantiations of this theorem allow us for example \emph{a}) to bound the
supremum of an $n$-variate degree-$d$ polynomial on the solid cube $[0,1]^n$ by
its supremum on the regular grid $\{0,1/d,2/d,\ldots, 1\}^n$ independent of
dimension; and \emph{b}) in the case of a degree-$d$ polynomial
$f:\mathbf{Z}_K^n\to\mathbf{C}$ on the $n$-fold product of cyclic groups of
order $K$, to show the supremum of $f$ does not increase by more than
$\mathcal{O}(\log K)^{2d}$ when $f$ is extended to the polytorus as
$f:\mathbf{T}^n\to\mathbf{C}$.
- Abstract（参考訳）: 古典的 Remez の不等式は、任意の部分集合 $Y\subset X$ の正のルベーグ測度上の上限で、境界次多項式の上限を区間 $X$ で有界とする。
レメス不等式には多変量一般化が多数存在するが、その多くは次元に強く依存する定数を持つ。
ここで、x$ と test の広いクラスが \emph{norm design} と呼ばれる $y$ を設定していることを示す。
Instantiations of this theorem allow us for example \emph{a}) to bound the supremum of an $n$-variate degree-$d$ polynomial on the solid cube $[0,1]^n$ by its supremum on the regular grid $\{0,1/d,2/d,\ldots, 1\}^n$ independent of dimension; and \emph{b}) in the case of a degree-$d$ polynomial $f:\mathbf{Z}_K^n\to\mathbf{C}$ on the $n$-fold product of cyclic groups of order $K$, to show the supremum of $f$ does not increase by more than $\mathcal{O}(\log K)^{2d}$ when $f$ is extended to the polytorus as $f:\mathbf{T}^n\to\mathbf{C}$.
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。