論文の概要: Nonlinear Random Matrices and Applications to the Sum of Squares
Hierarchy
- arxiv url: http://arxiv.org/abs/2302.04462v1
- Date: Thu, 9 Feb 2023 06:52:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 16:39:06.974221
- Title: Nonlinear Random Matrices and Applications to the Sum of Squares
Hierarchy
- Title（参考訳）: 非線形ランダム行列と二乗階層の和への応用
- Authors: Goutham Rajendran
- Abstract要約: 非線形ランダム行列の理論における新しいツールを開発する。
平均ケース問題における正方形階層のサム性能について検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop new tools in the theory of nonlinear random matrices and apply
them to study the performance of the Sum of Squares (SoS) hierarchy on
average-case problems.
The SoS hierarchy is a powerful optimization technique that has achieved
tremendous success for various problems in combinatorial optimization, robust
statistics and machine learning. It's a family of convex relaxations that lets
us smoothly trade off running time for approximation guarantees. In recent
works, it's been shown to be extremely useful for recovering structure in high
dimensional noisy data. It also remains our best approach towards refuting the
notorious Unique Games Conjecture.
In this work, we analyze the performance of the SoS hierarchy on fundamental
problems stemming from statistics, theoretical computer science and statistical
physics. In particular, we show subexponential-time SoS lower bounds for the
problems of the Sherrington-Kirkpatrick Hamiltonian, Planted Slightly Denser
Subgraph, Tensor Principal Components Analysis and Sparse Principal Components
Analysis. These SoS lower bounds involve analyzing large random matrices,
wherein lie our main contributions. These results offer strong evidence for the
truth of and insight into the low-degree likelihood ratio hypothesis, an
important conjecture that predicts the power of bounded-time algorithms for
hypothesis testing.
We also develop general-purpose tools for analyzing the behavior of random
matrices which are functions of independent random variables. Towards this, we
build on and generalize the matrix variant of the Efron-Stein inequalities. In
particular, our general theorem on matrix concentration recovers various
results that have appeared in the literature. We expect these random matrix
theory ideas to have other significant applications.
- Abstract（参考訳）: 非線形ランダム行列の理論における新しいツールを開発し、それを平均ケース問題における正方形(SoS)階層の性能の研究に応用する。
SoS階層は強力な最適化手法であり、組合せ最適化、ロバスト統計学、機械学習の様々な問題において大きな成功を収めた。
これは凸緩和のファミリーで、近似保証のためにランニングタイムをスムーズに取り除くことができます。
近年の研究では,高次元ノイズデータの復元に極めて有用であることが示されている。
それはまた、悪名高いUnique Games Conjectureに反論する最良のアプローチです。
本研究では,統計学,理論計算機科学,統計物理学などの基礎的問題に対するsos階層のパフォーマンスを分析する。
特に, やや密度の高い部分グラフ, テンソル主成分分析, スパース主成分分析を施したシェリントン・カークパトリックハミルトニアン問題に対して, サブ指数時間sos下限を示す。
これらの SoS の下位境界は、我々の主な貢献である大きなランダム行列の分析を含む。
これらの結果は、仮説検証のための有界時間アルゴリズムのパワーを予測する重要な予想である低次度確率比仮説の真理と洞察の強い証拠を提供する。
また,独立確率変数の関数であるランダム行列の挙動を解析するための汎用ツールを開発した。
これに向けて、Efron-Stein不等式の行列多様体を構築し、一般化する。
特に, 行列濃度に関する一般定理は, 文献に現れる様々な結果を復元する。
これらのランダム行列理論のアイデアは、他の重要な応用を期待する。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳（メタデータ） (2022-10-21T13:19:45Z) - Concentration of polynomial random matrices via Efron-Stein inequalities [0.3451964963586458]
多くの応用において、変数がスカラーであるランダム行列を解析する必要がある。
パウリン・マッキー=トロップによって開発された行列 Efron-Stein の不等式に基づいて、そのような境界を得るための一般的な枠組みを提案する。
トレースパワー法を非自明に応用したJonesら[FOCS 2021]が最近取得した"スパースグラフ行列"のバウンダリを導出する。
論文 参考訳（メタデータ） (2022-09-06T17:12:30Z) - When Random Tensors meet Random Matrices [50.568841545067144]
本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。
検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
論文 参考訳（メタデータ） (2021-12-23T04:05:01Z) - Test Set Sizing Via Random Matrix Theory [91.3755431537592]
本稿ではランダム行列理論の手法を用いて、単純な線形回帰に対して理想的なトレーニング-テストデータ分割を求める。
それは「理想」を整合性計量を満たすものとして定義し、すなわち経験的モデル誤差は実際の測定ノイズである。
本論文は,任意のモデルのトレーニングとテストサイズを,真に最適な方法で解決した最初の論文である。
論文 参考訳（メタデータ） (2021-12-11T13:18:33Z) - Statistical limits of dictionary learning: random matrix theory and the
spectral replica method [28.54289139061295]
ベイズ最適設定における行列記述と辞書学習の複雑なモデルについて考察する。
本稿では, 統計力学とランダム行列理論, スペクトル複製法を組み合わせた新しいレプリカ法を提案する。
論文 参考訳（メタデータ） (2021-09-14T12:02:32Z) - Optimization and Sampling Under Continuous Symmetry: Examples and Lie
Theory [26.555110725656963]
リーアンの定理、リー群、リー代数およびハリシュ・チャンドラ-イッツィ積分の公式の例を示す。
次に、連続対称性を捉えるために必要不可欠な数学的ツールキットである最適化理論を紹介する。
論文 参考訳（メタデータ） (2021-09-02T16:44:44Z) - Robust Compressed Sensing using Generative Models [98.64228459705859]
本稿では,Median-of-Means (MOM) にヒントを得たアルゴリズムを提案する。
我々のアルゴリズムは、外れ値が存在する場合でも、重み付きデータの回復を保証する。
論文 参考訳（メタデータ） (2020-06-16T19:07:41Z) - Robust Matrix Completion with Mixed Data Types [0.0]
我々は,データ型が混在する部分的なエントリを持つ構造的低ランク行列を復元する問題を考察する。
ほとんどのアプローチは、基礎となる分布は1つしかないと仮定し、低階の制約は、行列 Satten Norm によって正則化される。
本稿では, 並列化に適したアルゴリズムフレームワークとともに, 高い回復保証を有する計算可能な統計手法を提案し, 混合データ型に対する部分的に観測されたエントリを持つ低階行列を1ステップで復元する。
論文 参考訳（メタデータ） (2020-05-25T21:35:10Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z) - Bridging Convex and Nonconvex Optimization in Robust PCA: Noise,
Outliers, and Missing Data [20.31071912733189]
本稿では,低ランク行列推定における凸プログラミング手法の理論的保証を改良した。
原理的凸プログラムはユークリッド損失とell_infty$損失の両方の観点から、ほぼ最適統計精度を達成することを示す。
論文 参考訳（メタデータ） (2020-01-15T18:54:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。