論文の概要: Digital Computers Break the Curse of Dimensionality: Adaptive Bounds via
Finite Geometry
- arxiv url: http://arxiv.org/abs/2402.05576v1
- Date: Thu, 8 Feb 2024 11:23:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-09 15:29:41.531871
- Title: Digital Computers Break the Curse of Dimensionality: Adaptive Bounds via
Finite Geometry
- Title（参考訳）: デジタルコンピュータは次元の呪いを破る:有限幾何学による適応境界
- Authors: Anastasis Kratsios, A. Martina Neuman, Gudmund Pammer
- Abstract要約: デジタルコンピュータは$mathbbRd$で有限グリッドで動作する。
実コンピュータにモデルを実装すると,統計的学習における次元性の呪いが体系的に壊れることを示す。
- 参考スコア（独自算出の注目度）: 8.28720658988688
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many of the foundations of machine learning rely on the idealized premise
that all input and output spaces are infinite, e.g.~$\mathbb{R}^d$. This core
assumption is systematically violated in practice due to digital computing
limitations from finite machine precision, rounding, and limited RAM. In short,
digital computers operate on finite grids in $\mathbb{R}^d$. By exploiting
these discrete structures, we show the curse of dimensionality in statistical
learning is systematically broken when models are implemented on real
computers. Consequentially, we obtain new generalization bounds with
dimension-free rates for kernel and deep ReLU MLP regressors, which are
implemented on real-world machines.
Our results are derived using a new non-asymptotic concentration of measure
result between a probability measure over any finite metric space and its
empirical version associated with $N$ i.i.d. samples when measured in the
$1$-Wasserstein distance. Unlike standard concentration of measure results, the
concentration rates in our bounds do not hold uniformly for all sample sizes
$N$; instead, our rates can adapt to any given $N$. This yields significantly
tighter bounds for realistic sample sizes while achieving the optimal
worst-case rate of $\mathcal{O}(1/N^{1/2})$ for massive. Our results are built
on new techniques combining metric embedding theory with optimal transport
- Abstract（参考訳）: 機械学習の基礎の多くは、すべての入力空間と出力空間が無限であるという理想化された前提に依存している。
このコア仮定は、有限機械の精度、丸め、ramの制限によるデジタルコンピューティングの限界のために、実際には体系的に違反している。
要するに、デジタルコンピュータは有限格子上で$\mathbb{r}^d$で動作します。
これらの離散構造を利用して、実コンピュータ上でモデルを実装すると、統計的学習における次元性の呪いが体系的に壊れることを示す。
その結果,実世界のマシンに実装されたカーネルと深部ReLU MLPレジストレータの次元自由率を持つ新たな一般化境界が得られた。
この結果は、任意の有限距離空間上の確率測度と、1ドル=ワッサーシュタイン距離で測定された場合の、N$ i.d.サンプルに関連する経験的バージョンとの間の新しい非漸近的な測定結果の濃度を用いて導出される。
測定結果の標準濃度とは異なり、我々の境界における濃度速度はすべてのサンプルサイズに対して均一に保たず、代わりに与えられた任意の$N$に適応することができる。
これにより、現実的なサンプルサイズに対して、より厳密な境界が得られ、かつ、最大最悪のケースレートが$\mathcal{O}(1/N^{1/2})$である。
我々の結果は、計量埋め込み理論と最適輸送を組み合わせた新しい手法に基づいている。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - Learning linear dynamical systems under convex constraints [4.4351901934764975]
線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。
A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
論文 参考訳（メタデータ） (2023-03-27T11:49:40Z) - Classical shadows of fermions with particle number symmetry [0.0]
我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。
ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
論文 参考訳（メタデータ） (2022-08-18T17:11:12Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳（メタデータ） (2021-05-28T17:49:39Z) - Universal Regular Conditional Distributions via Probability
Measure-Valued Deep Neural Models [3.8073142980733]
提案したフレームワークを用いて構築されたモデルはすべて、$C(mathcalX,mathcalP_1(mathcalY))$で密集している。
提案モデルはまた、ほとんどのランダム化された機械学習モデルに存在するアレラトリック不確かさを汎用的に表現できることも示している。
論文 参考訳（メタデータ） (2021-05-17T11:34:09Z) - 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) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳（メタデータ） (2020-08-01T19:23:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。