論文の概要: Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time?
- arxiv url: http://arxiv.org/abs/2406.02970v1
- Date: Wed, 5 Jun 2024 05:54:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 19:49:25.098737
- Title: Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time?
- Title（参考訳）: ガウス点雲のどの例外的な低次元射影が多項式時間で見つかるか。
- Authors: Andrea Montanari, Kangjie Zhou,
- Abstract要約: 反復アルゴリズムのクラスで実現可能な分布のサブセット$mathscrF_m,alpha$について検討する。
統計物理学の非厳密な手法は、一般化されたパリの公式の言葉で$mathscrF_m,alpha$の間接的な特徴づけを与える。
- 参考スコア（独自算出の注目度）: 8.74634652691576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given $d$-dimensional standard Gaussian vectors $\boldsymbol{x}_1,\dots, \boldsymbol{x}_n$, we consider the set of all empirical distributions of its $m$-dimensional projections, for $m$ a fixed constant. Diaconis and Freedman (1984) proved that, if $n/d\to \infty$, all such distributions converge to the standard Gaussian distribution. In contrast, we study the proportional asymptotics, whereby $n,d\to \infty$ with $n/d\to \alpha \in (0, \infty)$. In this case, the projection of the data points along a typical random subspace is again Gaussian, but the set $\mathscr{F}_{m,\alpha}$ of all probability distributions that are asymptotically feasible as $m$-dimensional projections contains non-Gaussian distributions corresponding to exceptional subspaces. Non-rigorous methods from statistical physics yield an indirect characterization of $\mathscr{F}_{m,\alpha}$ in terms of a generalized Parisi formula. Motivated by the goal of putting this formula on a rigorous basis, and to understand whether these projections can be found efficiently, we study the subset $\mathscr{F}^{\rm alg}_{m,\alpha}\subseteq \mathscr{F}_{m,\alpha}$ of distributions that can be realized by a class of iterative algorithms. We prove that this set is characterized by a certain stochastic optimal control problem, and obtain a dual characterization of this problem in terms of a variational principle that extends Parisi's formula. As a byproduct, we obtain computationally achievable values for a class of random optimization problems including `generalized spherical perceptron' models.
- Abstract（参考訳）: d$-次元標準ガウスベクトル $\boldsymbol{x}_1,\dots, \boldsymbol{x}_n$ が与えられたとき、その$m$-次元射影のすべての経験的分布の集合を考える。
Diaconis and Freedman (1984) は、$n/d\to \infty$ ならば、そのような分布は標準ガウス分布に収束することを示した。
対照的に、比例漸近について研究し、$n,d\to \infty$を$n/d\to \alpha \in (0, \infty)$とする。
この場合、典型的なランダム部分空間に沿ったデータポイントの射影は再びガウス的であるが、集合 $\mathscr{F}_{m,\alpha}$ は例外部分空間に対応する非ガウス分布を含む。
統計物理学の非厳密な手法は、一般化されたパリの公式の言葉で$\mathscr{F}_{m,\alpha}$の間接的な特徴づけを与える。
この式を厳密な基準で配置し、これらの射影が効率的に発見できるかどうかを理解するために、部分集合 $\mathscr{F}^{\rm alg}_{m,\alpha}\subseteq \mathscr{F}_{m,\alpha}$ を反復アルゴリズムのクラスで実現できる分布について研究する。
この集合は確率的最適制御問題によって特徴づけられることを証明し、パリの公式を拡張する変分原理の観点からこの問題の双対的特徴付けを得る。
副産物として、「一般化球面パーセプトロン」モデルを含むランダム最適化問題のクラスに対して計算的に達成可能な値を得る。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [37.208622097149714]
すべての$d inmathbb N$に対して、すべての中心部分ガウス分布 $mathcal D$ on $mathbb Rd$, and every even $p inmathbb N$, $d-optimal inmathbb N$, $d-optimal inmathbb N$ が成り立つような普遍定数 $C>0$ が存在することを証明している。
これは、すべてのサブガウス分布がemphS-certifiably subgaussianであることを示す。
論文 参考訳（メタデータ） (2024-10-28T16:36:58Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Products [12.047053875716506]
マルチインデックスモデルに対する十分な次元削減の問題を考察する。
高速パラメトリック収束速度が$C_d cdot n-1/2$であることを示す。
論文 参考訳（メタデータ） (2023-12-24T12:28:07Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文 参考訳（メタデータ） (2023-02-21T17:52:23Z) - High-dimensional Location Estimation via Norm Concentration for Subgamma
Vectors [15.802475232604667]
位置推定では、既知の分布から$n$のサンプルが与えられます。
漸近的に、最大推定は誤差$mathcal N(0, frac1nmathcal I)$のクラム・ラオ境界を達成する。
我々は、Emphsmoothed estimator を用いて、$mathcal I_r$, the Fisher information of the $r$-smoothed の有限$n$の誤差を束縛する理論を構築した。
論文 参考訳（メタデータ） (2023-02-05T22:17:04Z) - Overparametrized linear dimensionality reductions: From projection
pursuit to two-layer neural networks [10.368585938419619]
$mathbbRd$に$n$のデータポイントのクラウドが与えられると、$mathbbRd$の$m$次元部分空間へのすべての射影を考える。
この確率分布の集まりは、$n,d$が大きくなるとどのように見えるか?
この極限の低次元射影として生じる $mathbbRm$ の確率分布の集合の α$ を $mathscrF_m で表すと、$mathscrF_ に新たな内界と外界を確立する。
論文 参考訳（メタデータ） (2022-06-14T00:07:33Z) - 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) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。