論文の概要: Efficient Certificates of Anti-Concentration Beyond Gaussians

• arxiv url: http://arxiv.org/abs/2405.15084v2
• Date: Mon, 28 Oct 2024 16:13:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:16:13.244444
• Title: Efficient Certificates of Anti-Concentration Beyond Gaussians
• Title（参考訳）: ガウシアンを超える抗濃度の有効証明書
• Authors: Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan,
• Abstract要約: この研究は、反濃縮のための新しい(そしておそらく最も自然な)定式化を提示する。 非ガウス分布の幅広いクラスを保った反集中の正方形証明を検証できる準多項式時間を与える。 提案手法は,意図された応用とは無関係に,正準2乗緩和の反集中と解析のための正準整数プログラムを構築する。
• 参考スコア（独自算出の注目度）: 15.709968227246453
• License:
• Abstract: A set of high dimensional points $X=\{x_1, x_2,\ldots, x_n\} \subset R^d$ in isotropic position is said to be $\delta$-anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying $|\langle x_i,v \rangle |\leq \delta$ is at most $O(\delta)$. Motivated by applications to list-decodable learning and clustering, recent works have considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points $X$ corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures, yet remain limited to rotationally invariant distributions. This work presents a new (and arguably the most natural) formulation for anti-concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over $L_p$ balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to such distributions. Our approach constructs a canonical integer program for anti-concentration and analysis a sum-of-squares relaxation of it, independent of the intended application. We rely on duality and analyze a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions.
• Abstract（参考訳）: 等方的位置における高次元点の集合 $X=\{x_1, x_2,\ldots, x_n\} \subset R^d$ が、すべての方向 $v$ に対して、X$ の点分が $|\langle x_i,v \rangle |\leq \delta$ が少なくとも $O(\delta)$ であるとき、$\delta$-anti となる。 近年の研究では,ガウス分布のサンプルに対応する点の集合をX$とした場合に,平均的な場合において,効率の良い集中防止証明書を構築するという課題が検討されている。 彼らの証明は、リスト復調可能な学習に関するアルゴリズム的頑健な統計学においていくつかの重要な役割を担い、任意のガウス混合の頑健な学習性を定着させたが、それでも回転不変分布に限られていた。 この研究は、反濃縮のための新しい(そしておそらく最も自然な)定式化を提示する。 この定式化を用いて、反集中的有界積分布や$L_p$ボール(およびそれらのアフィン変換)上の一様分布を含む幅広い種類の非ガウス分布を保ち、正方形の反集中の証明を検証できる準多項式時間を与える。 その結果,提案手法はアルゴリズムによるロバストな統計量,例えばリストデコダブル学習,クラスタリングを,そのような分布にアップグレードし,拡張する。 提案手法は,意図された応用とは無関係に,正準2乗緩和の反集中と解析のための正準整数プログラムを構築する。 我々は双対性に依存し、ある方向に小さな値を取る入力点の大きい部分集合の擬似予想を分析する。 本分析では, 多項式再重み付け法を用いて, 解析的な高密度あるいはスパース方向のみの解析を行う。

関連論文リスト

• 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)
• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
  統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。 この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
  論文  参考訳（メタデータ） (2020-05-06T17:24:27Z)

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

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