Fugu-MT 論文翻訳(概要): Outlier Robust Multivariate Polynomial Regression

論文の概要: Outlier Robust Multivariate Polynomial Regression

arxiv url: http://arxiv.org/abs/2403.09465v1
Date: Thu, 14 Mar 2024 15:04:45 GMT
ステータス: 処理完了
システム内更新日: 2024-03-15 20:07:46.983708
Title: Outlier Robust Multivariate Polynomial Regression
Title（参考訳）: Outlier Robust Multivariate Polynomial Regression
Authors: Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman,
Abstract要約: 1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
参考スコア（独自算出の注目度）: 27.03423421704806
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the problem of robust multivariate polynomial regression: let $p\colon\mathbb{R}^n\to\mathbb{R}$ be an unknown $n$-variate polynomial of degree at most $d$ in each variable. We are given as input a set of random samples $(\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R}$ that are noisy versions of $(\mathbf{x}_i,p(\mathbf{x}_i))$. More precisely, each $\mathbf{x}_i$ is sampled independently from some distribution $\chi$ on $[-1,1]^n$, and for each $i$ independently, $y_i$ is arbitrary (i.e., an outlier) with probability at most $\rho < 1/2$, and otherwise satisfies $|y_i-p(\mathbf{x}_i)|\leq\sigma$. The goal is to output a polynomial $\hat{p}$, of degree at most $d$ in each variable, within an $\ell_\infty$-distance of at most $O(\sigma)$ from $p$. Kane, Karmalkar, and Price [FOCS'17] solved this problem for $n=1$. We generalize their results to the $n$-variate setting, showing an algorithm that achieves a sample complexity of $O_n(d^n\log d)$, where the hidden constant depends on $n$, if $\chi$ is the $n$-dimensional Chebyshev distribution. The sample complexity is $O_n(d^{2n}\log d)$, if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most $O(\sigma)$, and the run-time depends on $\log(1/\sigma)$. In the setting where each $\mathbf{x}_i$ and $y_i$ are known up to $N$ bits of precision, the run-time's dependence on $N$ is linear. We also show that our sample complexities are optimal in terms of $d^n$. Furthermore, we show that it is possible to have the run-time be independent of $1/\sigma$, at the cost of a higher sample complexity.
Abstract（参考訳）: p\colon\mathbb{R}^n\to\mathbb{R}$を未知の$n$-変数多項式とする。ランダムサンプルの集合 $(\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R}$ は $(\mathbf{x}_i,p(\mathbf{x}_i))$ のうるさいバージョンである。より正確には、各$\mathbf{x}_i$ は、ある分布 $\chi$ on $[-1,1]^n$ から独立にサンプリングされ、各$i$ に対して、$y_i$ は任意の(すなわち、外れ値)であり、確率は $\rho < 1/2$ であり、そうでなければ $|y_i-p(\mathbf{x}_i)|\leq\sigma$ を満たす。目的は多項式 $\hat{p}$ を各変数の次数$d$ で、最大$O(\sigma)$ の $\ell_\infty$-距離で$p$ から出力することである。 Kane, Karmalkar, and Price [FOCS'17] はこの問題を$n=1$で解いた。それらの結果を$n$-variate設定に一般化し、$O_n(d^n\log d)$のサンプル複雑性を達成するアルゴリズムを示し、もし$\chi$が$n$次元チェビシェフ分布であれば、隠れ定数は$n$に依存する。サンプルの複雑さは$O_n(d^{2n}\log d)$である。近似誤差は最大$O(\sigma)$で保証され、実行時間は$\log(1/\sigma)$に依存する。それぞれの$\mathbf{x}_i$と$y_i$が$N$ビットの精度で知られている場合、ランタイムの$N$への依存は線形である。また、サンプル複素数は$d^n$の点で最適であることを示す。さらに,1/\sigma$を1/\sigma$から独立したランタイムを,より高いサンプル複雑性のコストで実現可能であることを示す。

関連論文リスト

Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-01T17:59:53Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
Faster Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文参考訳（メタデータ） (2022-06-19T11:33:07Z)
TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。本稿では,この数値をほぼ最適に推定する手法を提案する。
論文参考訳（メタデータ） (2022-02-15T03:49:28Z)
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。我々はこの$d$への依存が対数的要因まで最適であることを示す。また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文参考訳（メタデータ） (2021-11-09T00:20:01Z)
The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文参考訳（メタデータ） (2020-07-16T04:23:57Z)
Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文参考訳（メタデータ） (2020-06-23T20:21:27Z)
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)
Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文参考訳（メタデータ） (2020-04-13T08:06:29Z)
Sample Amplification: Increasing Dataset Size even when Learning is Impossible [15.864702679819544]
未知のディストリビューションから引き出されたデータである$D$が、このデータセットを増幅し、さらに大きなサンプルセットを$D$から抽出したように見えるように出力することは、どの程度まで可能か? この問題は次のように定式化する: $left(n, n + Theta(fracnsqrtk)right)$アンプが存在するが、小さな定数全変動距離への分布を学習するには$Theta(d)$サンプルが必要である。
論文参考訳（メタデータ） (2019-04-26T21:42:44Z)

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

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