論文の概要: Robust Linear Regression: Optimal Rates in Polynomial Time
- arxiv url: http://arxiv.org/abs/2007.01394v4
- Date: Fri, 4 Dec 2020 15:18:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 14:32:55.810540
- Title: Robust Linear Regression: Optimal Rates in Polynomial Time
- Title（参考訳）: ロバスト線形回帰:多項式時間における最適速度
- Authors: Ainesh Bakshi and Adarsh Prasad
- Abstract要約: 複数の線形モデルを学習するための頑健で計算効率の良い推定器を得る。
確率変数の独立性の緩和に役立つ解析条件を同定する。
我々の中心となる技術的貢献は、"sum-of-squares"フレームワークにおけるランダム変数の独立性をアルゴリズム的に活用することである。
- 参考スコア（独自算出の注目度）: 11.646151402884215
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We obtain robust and computationally efficient estimators for learning
several linear models that achieve statistically optimal convergence rate under
minimal distributional assumptions. Concretely, we assume our data is drawn
from a $k$-hypercontractive distribution and an $\epsilon$-fraction is
adversarially corrupted. We then describe an estimator that converges to the
optimal least-squares minimizer for the true distribution at a rate
proportional to $\epsilon^{2-2/k}$, when the noise is independent of the
covariates. We note that no such estimator was known prior to our work, even
with access to unbounded computation. The rate we achieve is
information-theoretically optimal and thus we resolve the main open question in
Klivans, Kothari and Meka [COLT'18].
Our key insight is to identify an analytic condition that serves as a
polynomial relaxation of independence of random variables. In particular, we
show that when the moments of the noise and covariates are
negatively-correlated, we obtain the same rate as independent noise. Further,
when the condition is not satisfied, we obtain a rate proportional to
$\epsilon^{2-4/k}$, and again match the information-theoretic lower bound. Our
central technical contribution is to algorithmically exploit independence of
random variables in the "sum-of-squares" framework by formulating it as the
aforementioned polynomial inequality.
- Abstract（参考訳）: 最小分布仮定の下で統計的に最適収束率を達成する線形モデルを学習するための頑健で効率的な推定値を得る。
具体的には、私たちのデータは、$k$-hypercontractive distributionから引き出され、$\epsilon$-fractionが逆向きに破損していると仮定する。
次に、ノイズが共変量とは独立である場合、$\epsilon^{2-2/k}$に比例するレートで真の分布の最適最小二乗最小値に収束する推定器を記述する。
このような推定器は我々の研究以前には知られていなかったが、非有界計算にもアクセスできた。
私たちが達成したレートは情報理論上最適であり、klivans, kothari, meka [colt'18] の主要なオープン問題を解く。
我々の重要な洞察は、確率変数の独立性の多項式緩和として働く解析条件を特定することである。
特に,雑音のモーメントと共変量のモーメントが負の相関関係にある場合,独立雑音と同じ速度が得られることを示す。
さらに、条件が満たされない場合、$\epsilon^{2-4/k}$に比例するレートを取得し、情報理論上の下限に再び一致する。
我々の中心となる技術的貢献は、前述の多項式不等式として定式化することで、"sum-of-squares"フレームワークにおける確率変数の独立性をアルゴリズム的に活用することである。
関連論文リスト
- Optimal minimax rate of learning interaction kernels [7.329333373512536]
広帯域の交換可能な分布に対して最適な収束率を得るための最小二乗推定器(tLSE)を導入する。
以上の結果から, 大きな試料限界の逆問題が保たれた場合, 左テール確率はバイアス分散トレードオフを変化させないことがわかった。
論文 参考訳（メタデータ） (2023-11-28T15:01:58Z) - High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。
解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
論文 参考訳（メタデータ） (2023-10-28T18:53:41Z) - Sparsified Simultaneous Confidence Intervals for High-Dimensional Linear
Models [4.010566541114989]
本稿では,間隔化同時信頼区間という,同時信頼区間の概念を提案する。
我々の区間は、区間の上と下の境界の一部が 0 に切り替わるという意味でスパースである。
提案手法は様々な選択手順と組み合わせることができるため,不確実性を比較するのに最適である。
論文 参考訳（メタデータ） (2023-07-14T18:37:57Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Improved Analysis of Score-based Generative Modeling: User-Friendly
Bounds under Minimal Smoothness Assumptions [9.953088581242845]
2次モーメントを持つ任意のデータ分布に対して,コンバージェンス保証と複雑性を提供する。
我々の結果は、対数共空性や機能的不等式を前提としない。
我々の理論解析は、異なる離散近似の比較を提供し、実際の離散化点の選択を導くかもしれない。
論文 参考訳（メタデータ） (2022-11-03T15:51:00Z) - Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
本研究では, スコアマッチングの統計的効率と推定される分布の等尺性との間に, 密接な関係を示す。
これらの結果はサンプル状態と有限状態の両方で定式化する。
論文 参考訳（メタデータ） (2022-10-03T06:09:01Z) - Distribution-Free Robust Linear Regression [5.532477732693]
共変体の分布を仮定せずにランダムな設計線形回帰を研究する。
最適部分指数尾を持つオーダー$d/n$の過大なリスクを達成する非線形推定器を構築する。
我々は、Gy"orfi, Kohler, Krzyzak, Walk が原因で、truncated least squares 推定器の古典的境界の最適版を証明した。
論文 参考訳（メタデータ） (2021-02-25T15:10:41Z) - Minimax Off-Policy Evaluation for Multi-Armed Bandits [58.7013651350436]
有界報酬を用いたマルチアームバンディットモデルにおけるオフポリシー評価の問題点について検討する。
3つの設定でミニマックスレート・オプティマティックな手順を開発。
論文 参考訳（メタデータ） (2021-01-19T18:55:29Z) - Suboptimality of Constrained Least Squares and Improvements via
Non-Linear Predictors [3.5788754401889014]
有界ユークリッド球における正方形損失に対する予測問題と最良の線形予測器について検討する。
最小二乗推定器に対する$O(d/n)$過剰リスク率を保証するのに十分な分布仮定について論じる。
論文 参考訳（メタデータ） (2020-09-19T21:39:46Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a
Robust Divergence Estimator [95.71091446753414]
最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。
本手法は既存の不一致対策よりも高いロバスト性を実現する。
論文 参考訳（メタデータ） (2020-06-13T06:09:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。