論文の概要: 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})$である。
我々の結果は、計量埋め込み理論と最適輸送を組み合わせた新しい手法に基づいている。
関連論文リスト
- Breaking the Curse of Dimensionality with Distributed Neural Computation [17.571316365665673]
本稿では,複数のマシンに分散可能なニューラルネットワークアルゴリズムを用いて,次元の呪いを克服する理論的アプローチを提案する。
VRAMに少数のパラメータをロードするだけで任意の精度を達成できます。
論文 参考訳(メタデータ) (2024-02-05T19:11:57Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳(メタデータ) (2023-06-26T17:13:31Z) - Spatially heterogeneous learning by a deep student machine [0.0]
多数の調整可能なパラメータを持つディープニューラルネットワーク(DNN)は、ほとんどブラックボックスのままである。
我々は,教師学生設定と呼ばれる統計力学手法を用いて,NL$パーセプトロンと$c$入力からなるDNNと深度$L$の教師学習について検討した。
N gg c gg 1$ and $M gg 1$ with fixed $alpha=M/c$ using the replica method developed in (H. Yoshino,)
論文 参考訳(メタデータ) (2023-02-15T01:09:03Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳(メタデータ) (2021-07-28T04:28:55Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳(メタデータ) (2021-06-06T19:08:53Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳(メタデータ) (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z) - New Bounds For Distributed Mean Estimation and Variance Reduction [25.815612182815702]
本稿では,ローカルな$d$-dimensional vector $x_v を mathbbRd$ で与えられた$n$マシンが分散平均推定(DME)問題を考える。
提案手法は, 従来の手法と比較して, 応用の実践的改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-02-21T13:27:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。