論文の概要: The VC-dimension of k-vertex d-polytopes
- arxiv url: http://arxiv.org/abs/2004.04841v2
- Date: Mon, 13 Apr 2020 21:44:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-15 03:34:51.156833
- Title: The VC-dimension of k-vertex d-polytopes
- Title(参考訳): k-vertex d-ポリトープのvc次元
- Authors: Andrey Kupavskii
- Abstract要約: 我々は、$mathbb Rd$ の $k$-vertex polytopes クラスの VC 次元は、少なくとも 8d2klogk$ であり、Long と Warmuth の古い疑問に答える。
- 参考スコア(独自算出の注目度): 1.0660480034605242
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this short note, we show that the VC-dimension of the class of $k$-vertex
polytopes in $\mathbb R^d$ is at most $8d^2k\log_2k$, answering an old question
of Long and Warmuth.
- Abstract(参考訳): ここでは、$\mathbb R^d$ の $k$-vertex polytopes クラスの VC-次元は、少なくとも 8d^2k\log_2k$ であり、Long と Warmuth の古い疑問に答える。
関連論文リスト
- Dimension-free Remez Inequalities and norm designs [48.5897526636987]
ドメインのクラスが$X$で、テストセットが$Y$で、Emphnormと呼ばれ、次元のないRemez型の見積もりを楽しむ。
ポリトーラスに$f$が拡張されたとき、$f$の上限は$mathcalO(log K)2d$以上増加しないことを示す。
論文 参考訳(メタデータ) (2023-10-11T22:46:09Z) - 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) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。
境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。
治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文 参考訳(メタデータ) (2022-08-12T15:05:07Z) - Optimally compressing VC classes [0.0]
Littlestone と Warmuth の予想を解くと、VC-dimension $d$ の任意の概念クラスは、サンプル圧縮スキームが$d$ であることを示す。
論文 参考訳(メタデータ) (2022-01-11T18:56:08Z) - Eluder Dimension and Generalized Rank [48.27338656415236]
eluder次元は$sigma$-rankよりも指数関数的に大きいことが分かる。
sigma$ が $mathrmrelu$ の活性化であるとき、 eluder 次元は $sigma$-rank よりも指数関数的に大きいことが示される。
論文 参考訳(メタデータ) (2021-04-14T16:53:13Z) - Binary strings of finite VC dimension [0.0]
本稿では、P(x+y)$ が有限VC次元を持つような述語 $P$ によって与えられる部分集合について検討する。
我々は、有界なVC次元の文字列が実体のトポロジーにおいて意味があることを証明し、文字列のVC次元を境界付けるための単純なルールを提供し、VC次元$d$の二無限文字列が非ソソシフト空間であることを示した。
論文 参考訳(メタデータ) (2021-01-16T17:51:52Z) - 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) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。
例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
論文 参考訳(メタデータ) (2020-08-06T09:50:29Z) - The VC-Dimension of Axis-Parallel Boxes on the Torus [0.0]
我々は、$d$次元軸、箱および立方体のファミリーのVC次元がともに$d log_2(d)$であることを示す。
VC次元は通常、同様の設定で$d$で線形に成長するので、これは特に驚きだ。
論文 参考訳(メタデータ) (2020-04-28T21:41:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。