論文の概要: A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise
- arxiv url: http://arxiv.org/abs/2209.02856v1
- Date: Tue, 6 Sep 2022 23:37:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-08 13:07:59.884059
- Title: A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise
- Title（参考訳）: 未知共分散・不均質雑音をもつ重項劣化回帰に対するスペクトル最小二乗型法
- Authors: Roberto I. Oliveira and Zoraida F. Rico and Philip Thompson
- Abstract要約: 重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
- 参考スコア（独自算出の注目度）: 2.019622939313173
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We revisit heavy-tailed corrupted least-squares linear regression assuming to
have a corrupted $n$-sized label-feature sample of at most $\epsilon n$
arbitrary outliers. We wish to estimate a $p$-dimensional parameter $b^*$ given
such sample of a label-feature pair $(y,x)$ satisfying $y=\langle
x,b^*\rangle+\xi$ with heavy-tailed $(x,\xi)$. We only assume $x$ is $L^4-L^2$
hypercontractive with constant $L>0$ and has covariance matrix $\Sigma$ with
minimum eigenvalue $1/\mu^2>0$ and bounded condition number $\kappa>0$. The
noise $\xi$ can be arbitrarily dependent on $x$ and nonsymmetric as long as
$\xi x$ has finite covariance matrix $\Xi$. We propose a near-optimal
computationally tractable estimator, based on the power method, assuming no
knowledge on $(\Sigma,\Xi)$ nor the operator norm of $\Xi$. With probability at
least $1-\delta$, our proposed estimator attains the statistical rate
$\mu^2\Vert\Xi\Vert^{1/2}(\frac{p}{n}+\frac{\log(1/\delta)}{n}+\epsilon)^{1/2}$
and breakdown-point $\epsilon\lesssim\frac{1}{L^4\kappa^2}$, both optimal in
the $\ell_2$-norm, assuming the near-optimal minimum sample size
$L^4\kappa^2(p\log p + \log(1/\delta))\lesssim n$, up to a log factor. To the
best of our knowledge, this is the first computationally tractable algorithm
satisfying simultaneously all the mentioned properties. Our estimator is based
on a two-stage Multiplicative Weight Update algorithm. The first stage
estimates a descent direction $\hat v$ with respect to the (unknown)
pre-conditioned inner product $\langle\Sigma(\cdot),\cdot\rangle$. The second
stage estimate the descent direction $\Sigma\hat v$ with respect to the (known)
inner product $\langle\cdot,\cdot\rangle$, without knowing nor estimating
$\Sigma$.
- Abstract（参考訳）: 重み付き最小二乗線形回帰は、少なくとも$\epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルが破損したと仮定して再検討する。
p$-次元パラメータ $b^*$ をラベル-函数対 $(y,x)$ のそのようなサンプルとして、重み付き $(x,\xi)$ で $y=\langle x,b^*\rangle+\xi$ を満たすと見積もる。
x$ が $l^4-l^2$ であり、定数 $l>0$ であり、分散行列 $\sigma$ と最小固有値 $1/\mu^2>0$ と有界条件番号 $\kappa>0$ と仮定する。
ノイズ $\xi$ は任意に $x$ に依存し、$\xi x$ が有限共分散行列 $\xi$ を持つ限り非対称である。
本稿では,$(\Sigma,\Xi)$に関する知識や,$\Xi$の演算ノルムを仮定して,電力法に基づくほぼ最適に計算可能な推定器を提案する。
少なくとも 1-\delta$ の確率で、提案する推定値は、統計量 $\mu^2\vert\xi\vert^{1/2}(\frac{p}{n}+\frac{\log(1/\delta)}{n}+\epsilon)^{1/2}$ および分解点 $\epsilon\lesssim\frac{1}{l^4\kappa^2}$ となり、どちらも$\ell_2$-norm において最適であり、最小の最小サンプルサイズ $l^4\kappa^2(p\log p + \log(1/\delta))\lesssim n$ となる。
我々の知る限りでは、このアルゴリズムは上記の全ての特性を同時に満たす最初の計算可能なアルゴリズムである。
我々の推定値は2段階の乗法重み更新アルゴリズムに基づいている。
第一段階は、(未知の)プレ条件内積 $\langle\Sigma(\cdot),\cdot\rangle$ に対する降下方向 $\hat v$ を推定する。
第2段階は、(既知の)内部積 $\langle\cdot,\cdot\rangle$ に対する降下方向 $\Sigma\hat v$ を、$\Sigma$ を知らずに推定する。
関連論文リスト
- Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - Statistically Optimal Robust Mean and Covariance Estimation for
Anisotropic Gaussians [3.5788754401889014]
強い$varepsilon$-contaminationモデルでは、元のガウスサンプルのベクトルの$varepsilon$分を他のベクトルに置き換えたと仮定する。
我々は、少なくとも1-デルタの確率で満足するコフラ行列 $Sigma の推定器 $widehat Sigma を構築する。
論文 参考訳（メタデータ） (2023-01-21T23:28:55Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳（メタデータ） (2020-06-23T20:21:27Z) - $\lambda$-Regularized A-Optimal Design and its Approximation by
$\lambda$-Regularized Proportional Volume Sampling [1.256413718364189]
本稿では,$lambda$-regularized $A$-optimal design problemについて検討し,$lambda$-regularized proportional volume sample algorithmを紹介する。
この問題は、リッジ回帰モデルにおける真の係数からリッジ回帰予測器の2乗誤差を最小化しようとする、リッジ回帰の最適設計から動機づけられている。
論文 参考訳（メタデータ） (2020-06-19T15:17:57Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。