論文の概要: Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians

• arxiv url: http://arxiv.org/abs/2410.01656v1
• Date: Wed, 2 Oct 2024 15:21:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-04 16:13:24.584849
• Title: Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
• Title（参考訳）: 未知のトリニケート、多項式時間アルゴリズムを用いた効率的な統計学 : ガウシアンを超えて
• Authors: Jane H. Lee, Anay Mehrotra, Manolis Zampetakis,
• Abstract要約: 本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。 我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
• 参考スコア（独自算出の注目度）: 7.04316974339151
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the estimation of distributional parameters when samples are shown only if they fall in some unknown set $S \subseteq \mathbb{R}^d$. Kontonis, Tzamos, and Zampetakis (FOCS'19) gave a $d^{\mathrm{poly}(1/\varepsilon)}$ time algorithm for finding $\varepsilon$-accurate parameters for the special case of Gaussian distributions with diagonal covariance matrix. Recently, Diakonikolas, Kane, Pittas, and Zarifis (COLT'24) showed that this exponential dependence on $1/\varepsilon$ is necessary even when $S$ belongs to some well-behaved classes. These works leave the following open problems which we address in this work: Can we estimate the parameters of any Gaussian or even extend beyond Gaussians? Can we design $\mathrm{poly}(d/\varepsilon)$ time algorithms when $S$ is a simple set such as a halfspace? We make progress on both of these questions by providing the following results: 1. Toward the first question, we give a $d^{\mathrm{poly}(\ell/\varepsilon)}$ time algorithm for any exponential family that satisfies some structural assumptions and any unknown set $S$ that is $\varepsilon$-approximable by degree-$\ell$ polynomials. This result has two important applications: 1a) The first algorithm for estimating arbitrary Gaussian distributions from samples truncated to an unknown $S$; and 1b) The first algorithm for linear regression with unknown truncation and Gaussian features. 2. To address the second question, we provide an algorithm with runtime $\mathrm{poly}(d/\varepsilon)$ that works for a set of exponential families (containing all Gaussians) when $S$ is a halfspace or an axis-aligned rectangle. Along the way, we develop tools that may be of independent interest, including, a reduction from PAC learning with positive and unlabeled samples to PAC learning with positive and negative samples that is robust to certain covariate shifts.
• Abstract（参考訳）: サンプルが未知の集合 $S \subseteq \mathbb{R}^d$ に該当する場合にのみ、分布パラメータを推定する。 Kontonis, Tzamos, and Zampetakis (FOCS'19) は、対角共分散行列を持つガウス分布の特別な場合の$\varepsilon$-正確なパラメータを見つけるための$d^{\mathrm{poly}(1/\varepsilon)} の時間アルゴリズムを与えた。 最近、Diakonikolas, Kane, Pittas, Zarifis (COLT'24) は、1/\varepsilon$ に対する指数関数的依存は、S$ がいくつかのよく定義されたクラスに属する場合でも必要であることを示した。 これらの研究は、我々がこの研究で取り組んだ以下のオープンな問題を残している: ガウスのパラメータを推定できるか、あるいはガウスを超えて拡張できるのか? S$がハーフスペースのような単純な集合であるとき、$\mathrm{poly}(d/\varepsilon)$タイムアルゴリズムを設計できますか? 最初の質問に向けて、いくつかの構造的仮定を満たす指数族に対して$d^{\mathrm{poly}(\ell/\varepsilon)}$時間アルゴリズムを与え、未知の集合として$S$を$\varepsilon$-approximable by degree-$\ell$ polynomials を与える。 この結果には2つの重要な応用がある: 1a) 未知の$S$にtruncatedされたサンプルから任意のガウス分布を推定する最初のアルゴリズム、1b) 未知のトランケーションとガウス特徴を持つ線形回帰のための最初のアルゴリズム。 2つ目の問題に対処するため、S$が半空間あるいは軸方向の矩形であるとき、指数族(すべてのガウスを含む)の集合に対して機能する実行時$\mathrm{poly}(d/\varepsilon)$のアルゴリズムを提供する。 その過程で, 正・未ラベルのサンプルによるPAC学習から, 正・負のサンプルによるPAC学習へ, 特定の共変量シフトに対して頑健なツールを開発する。

関連論文リスト

• Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
  2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。 2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
  論文  参考訳（メタデータ） (2024-10-31T13:51:59Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• List-Decodable Covariance Estimation [1.9290392443571387]
  共分散推定アルゴリズムを初めて提案する。 この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
  論文  参考訳（メタデータ） (2022-06-22T09:38:06Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• 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)
• 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)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing [22.337756118270217]
  基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。 最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。 私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
  論文  参考訳（メタデータ） (2020-06-12T07:45:38Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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