論文の概要: SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

• arxiv url: http://arxiv.org/abs/2412.21203v1
• Date: Mon, 30 Dec 2024 18:59:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:04:09.543270
• Title: SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
• Title（参考訳）: SoS Certificates for Sparse Singular Values and their Applications: Robust Statistics, Subspace Distortionなど
• Authors: Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel,
• Abstract要約: 我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
• 参考スコア（独自算出の注目度）: 37.208622097149714
• License:
• Abstract: We study $\textit{sparse singular value certificates}$ for random rectangular matrices. If $M$ is an $n \times d$ matrix with independent Gaussian entries, we give a new family of polynomial-time algorithms which can certify upper bounds on the maximum of $\|M u\|$, where $u$ is a unit vector with at most $\eta n$ nonzero entries for a given $\eta \in (0,1)$. This basic algorithmic primitive lies at the heart of a wide range of problems across algorithmic statistics and theoretical computer science. Our algorithms certify a bound which is asymptotically smaller than the naive one, given by the maximum singular value of $M$, for nearly the widest-possible range of $n,d,$ and $\eta$. Efficiently certifying such a bound for a range of $n,d$ and $\eta$ which is larger by any polynomial factor than what is achieved by our algorithm would violate lower bounds in the SQ and low-degree polynomials models. Our certification algorithm makes essential use of the Sum-of-Squares hierarchy. To prove the correctness of our algorithm, we develop a new combinatorial connection between the graph matrix approach to analyze random matrices with dependent entries, and the Efron-Stein decomposition of functions of independent random variables. As applications of our certification algorithm, we obtain new efficient algorithms for a wide range of well-studied algorithmic tasks. In algorithmic robust statistics, we obtain new algorithms for robust mean and covariance estimation with tradeoffs between breakdown point and sample complexity, which are nearly matched by SQ and low-degree polynomial lower bounds (that we establish). We also obtain new polynomial-time guarantees for certification of $\ell_1/\ell_2$ distortion of random subspaces of $\mathbb{R}^n$ (also with nearly matching lower bounds), sparse principal component analysis, and certification of the $2\rightarrow p$ norm of a random matrix.
• Abstract（参考訳）: ランダムな矩形行列に対して$\textit{sparse singular value certificates}$を研究する。 M$が独立ガウス成分を持つ$n \times d$行列であれば、$u$は与えられた$\eta \in (0,1)$に対して少なくとも$\eta n$非零成分を持つ単位ベクトルである、最大$\|M u\|$の上界を証明できる多項式時間アルゴリズムの族を与える。 この基本的なアルゴリズムプリミティブは、アルゴリズム統計学と理論計算機科学の幅広い問題の中心にある。 我々のアルゴリズムは、最も広い範囲の$n,d,$および$\eta$に対して、最大特異値$M$で与えられるネーブよりも漸近的に小さい境界を証明している。 任意の多項式係数によってより大きい$n,d$ および $\eta$ の範囲でのそのような境界を効果的に証明することは、SQ および低次多項式モデルにおける低い境界に反する。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。 アルゴリズムの正しさを証明するため,グラフ行列法と独立確率変数の関数のEfron-Stein分解の組合せ関係を新たに開発した。 認証アルゴリズムの応用として,多種多様なよく研究されたアルゴリズムタスクに対して,新しい効率的なアルゴリズムを得る。 アルゴリズムによるロバストな統計学では、分解点とサンプルの複雑さのトレードオフによるロバストな平均値と共分散推定のための新しいアルゴリズムが得られ、これはSQと低次多項式の下界にほぼ一致する。 また、$\ell_1/\ell_2$のランダム部分空間の歪み(ほぼ一致する下界を持つ)の証明、スパース主成分分析、およびランダム行列の2-rightarrow p$ノルムの証明のための新しい多項式時間保証を得る。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm [41.03423042792559]
  我々は、相対的なフロベニウスノルムにおいて、$Sigma$に近い仮説のリストを作成する。 結論として,ガウス混合モデルのロバストな部分クラスタリングのための効率的なスペクトルアルゴリズムを得る。 提案手法は, GMM を頑健に学習する最初の Sum-of-Squares-free アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-01T17:54:35Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• 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)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。