論文の概要: Quantum and classical low-degree learning via a dimension-free Remez
inequality
- arxiv url: http://arxiv.org/abs/2301.01438v3
- Date: Mon, 18 Dec 2023 14:53:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-21 03:17:28.698372
- Title: Quantum and classical low-degree learning via a dimension-free Remez
inequality
- Title（参考訳）: 無次元レメズ不等式による量子および古典低次学習
- Authors: Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang
- Abstract要約: ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
- 参考スコア（独自算出の注目度）: 52.12931955662553
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent efforts in Analysis of Boolean Functions aim to extend core results to
new spaces, including to the slice $\binom{[n]}{k}$, the hypergrid $[K]^n$, and
noncommutative spaces (matrix algebras). We present here a new way to relate
functions on the hypergrid (or products of cyclic groups) to their harmonic
extensions over the polytorus. We show the supremum of a function $f$ over
products of the cyclic group $\{\exp(2\pi i k/K)\}_{k=1}^K$ controls the
supremum of $f$ over the entire polytorus $(\{z\in\mathbf{C}:|z|=1\}^n)$, with
multiplicative constant $C$ depending on $K$ and $\text{deg}(f)$ only. This
Remez-type inequality appears to be the first such estimate that is
dimension-free (i.e., $C$ does not depend on $n$).
This dimension-free Remez-type inequality removes the main technical barrier
to giving $\mathcal{O}(\log n)$ sample complexity, polytime algorithms for
learning low-degree polynomials on the hypergrid and low-degree observables on
level-$K$ qudit systems. In particular, our dimension-free Remez inequality
implies new Bohnenblust--Hille-type estimates which are central to the learning
algorithms and appear unobtainable via standard techniques. Thus we extend to
new spaces a recent line of work \cite{EI22, CHP, VZ22} that gave similarly
efficient methods for learning low-degree polynomials on the hypercube and
observables on qubits.
An additional product of these efforts is a new class of distributions over
which arbitrary quantum observables are well-approximated by their low-degree
truncations -- a phenomenon that greatly extends the reach of low-degree
learning in quantum science \cite{CHP}.
- Abstract（参考訳）: ブール関数の解析における最近の取り組みは、コア結果を新しい空間に拡張することを目的としており、例えば、slice $\binom{[n]}{k}$、 hypergrid $[K]^n$、および非可換空間(行列代数)などである。
ここでは、超グリッド(あるいは巡回群の積)上の函数をポリトーラス上の調和拡大に関連付ける新しい方法を提案する。
巡回群 $\{\exp(2\pi i k/k)\}_{k=1}^k$ の積よりも関数 $f$ の上限は、ポリトーラス $(\{z\in\mathbf{c}:|z|=1\}^n)$ 全体に対して $f$ の上限を制御し、乗算定数 $c$ は $k$ と $\text{deg}(f)$ に依存する。
このレメズ型不等式は次元を含まない最初の推定値(すなわち、$c$は$n$に依存しない)である。
この次元自由 Remez 型不等式は、$\mathcal{O}(\log n)$サンプル複雑性を与える主な技術的障壁を排除し、超グリッド上の低次多項式を学習するためのpolytimeアルゴリズムとレベル-K$quditシステムでの低次可観測関数を学習する。
特に、次元のないレメズ不等式は、学習アルゴリズムの中心であり、標準技術では観察できない新しいボーネンブラウスト・ヒル型推定を暗示している。
したがって、我々は、超キューブ上の低次多項式と量子ビット上の可観測性を学ぶのと同様に効率的な方法を与えた最近の研究のラインであるcite{EI22, CHP, VZ22} に拡張する。
これらの取り組みの副産物は、任意の量子可観測性がそれらの低次切断によって近似される新しい分布のクラスであり、量子科学における低次学習の範囲を大きく広げる現象である。
関連論文リスト
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - On the Sample Complexity of Two-Layer Networks: Lipschitz vs.
Element-Wise Lipschitz Activation [20.70453775428433]
本研究では,異なるアクティベーション関数を用いた有界二層ニューラルネットワークのサンプル複雑性について検討する。
我々は、$sigma$ が要素ワイドであれば、$mathcalH$ のサンプルの複雑さは、幅の対数依存しか持たないことを証明する。
論文 参考訳（メタデータ） (2022-11-17T16:27:15Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - 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) - Emergent universality in critical quantum spin chains: entanglement
Virasoro algebra [1.9336815376402714]
エンタングルメントエントロピーとエンタングルメントスペクトルは、拡張多体系における量子エンタングルメントの特徴付けに広く用いられている。
シュミットベクトル $|v_alpharangle$ は境界 CFT のヴィラソロ代数の実現に対応する創発的普遍構造を示す。
論文 参考訳（メタデータ） (2020-09-23T21:22:51Z) - Classical Dynamics from Self-Consistency Equations in Quantum Mechanics
-- Extended Version [0.0]
我々は、ボナの非線形量子力学の一般化に対する新しい数学的アプローチを提案する。
自己整合性の中心的な役割を強調します。
いくつかの新しい数学的概念が紹介され、これはおそらくそれ自体が興味深い。
論文 参考訳（メタデータ） (2020-09-10T16:20:25Z) - Q-learning with Uniformly Bounded Variance: Large Discounting is Not a
Barrier to Fast Learning [7.6146285961466]
我々は、すべての$gamma 1$に対して一様に束縛されたサンプル複雑性を持つ新しいアルゴリズムのクラスを導入する。
最適化されたステップサイズシーケンスとQ-ラーニングアルゴリズムの共分散は、1/(1-ガンマ)$の二次関数であることを示す。
論文 参考訳（メタデータ） (2020-02-24T15:12:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。