論文の概要: SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications

• arxiv url: http://arxiv.org/abs/2410.21194v1
• Date: Mon, 28 Oct 2024 16:36:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:15:23.007128
• Title: SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
• Title（参考訳）: 亜ガウス分布のSOSサーチフィビリティとそのアルゴリズム応用
• Authors: Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel,
• Abstract要約: すべての$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であることを示す。
• 参考スコア（独自算出の注目度）: 37.208622097149714
• License:
• Abstract: We prove that there is a universal constant $C>0$ so that for every $d \in \mathbb N$, every centered subgaussian distribution $\mathcal D$ on $\mathbb R^d$, and every even $p \in \mathbb N$, the $d$-variate polynomial $(Cp)^{p/2} \cdot \|v\|_{2}^p - \mathbb E_{X \sim \mathcal D} \langle v,X\rangle^p$ is a sum of square polynomials. This establishes that every subgaussian distribution is \emph{SoS-certifiably subgaussian} -- a condition that yields efficient learning algorithms for a wide variety of high-dimensional statistical tasks. As a direct corollary, we obtain computationally efficient algorithms with near-optimal guarantees for the following tasks, when given samples from an arbitrary subgaussian distribution: robust mean estimation, list-decodable mean estimation, clustering mean-separated mixture models, robust covariance-aware mean estimation, robust covariance estimation, and robust linear regression. Our proof makes essential use of Talagrand's generic chaining/majorizing measures theorem.
• Abstract（参考訳）: すべての$d \in \mathbb N$に対して、すべての中心部分ガウス分布 $\mathcal D$ on $\mathbb R^d$, and every even $p \in \mathbb N$, $d$-variate polynomial $(Cp)^{p/2} \cdot \|v\|^^p - \mathbb E_{X \sim \mathcal D} \langle v,X\rangle^p$ は平方多項式の和である。 このことは、すべての部分ガウス分布が \emph{SoS-certifiably subgaussian} であることを保証する。 直列法として, 任意の部分ガウス分布からのサンプルを与えられた場合, 正解平均推定, リスト復号化平均推定, クラスタリング平均分離混合モデル, 正解共分散認識平均推定, 正解共分散推定, 正解線形回帰という, 計算効率のよいアルゴリズムを得る。 我々の証明は、タラグランドのジェネリックチェイン/マジョライズ測度定理を必須に活用する。

関連論文リスト

• Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time? [8.74634652691576]
  反復アルゴリズムのクラスで実現可能な分布のサブセット$mathscrF_m,alpha$について検討する。 統計物理学の非厳密な手法は、一般化されたパリの公式の言葉で$mathscrF_m,alpha$の間接的な特徴づけを与える。
  論文  参考訳（メタデータ） (2024-06-05T05:54:56Z)
• Efficient Certificates of Anti-Concentration Beyond Gaussians [15.709968227246453]
  この研究は、反濃縮のための新しい(そしておそらく最も自然な)定式化を提示する。 非ガウス分布の幅広いクラスを保った反集中の正方形証明を検証できる準多項式時間を与える。 提案手法は,意図された応用とは無関係に,正準2乗緩和の反集中と解析のための正準整数プログラムを構築する。
  論文  参考訳（メタデータ） (2024-05-23T22:13:44Z)
• 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)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。 この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。 我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
  論文  参考訳（メタデータ） (2023-02-21T17:52:23Z)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912]
  群分散ロバスト最適化(GDRO) オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。 分布依存収束率を導出できる重み付きGDROの新規な定式化。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
  非ガウス成分分析(NGCA)は分布学習問題である。 我々は,NGCA に対して,$A$ が離散的あるいはほぼ離散的であるような効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-12-16T18:38:02Z)
• 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)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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