論文の概要: Robustness Auditing for Linear Regression: To Singularity and Beyond
- arxiv url: http://arxiv.org/abs/2410.07916v1
- Date: Thu, 10 Oct 2024 13:40:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-31 14:06:15.966662
- Title: Robustness Auditing for Linear Regression: To Singularity and Beyond
- Title（参考訳）: 線形回帰のロバスト性:特異性と超越性
- Authors: Ittai Rubinstein, Samuel B. Hopkins,
- Abstract要約: サンプル除去に対する線形回帰のロバスト性を検証するための効率的なアルゴリズムを提案する。
アルゴリズムを実装し、数百の次元を持ついくつかのランドマークなエコノメトリデータセット上で実行します。
データセット上の分布的仮定の下では、我々のアルゴリズムが生成する境界は1 + o(1)$乗算係数まできついことが証明される。
- 参考スコア（独自算出の注目度）: 6.812390750464419
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It has recently been discovered that the conclusions of many highly influential econometrics studies can be overturned by removing a very small fraction of their samples (often less than $0.5\%$). These conclusions are typically based on the results of one or more Ordinary Least Squares (OLS) regressions, raising the question: given a dataset, can we certify the robustness of an OLS fit on this dataset to the removal of a given number of samples? Brute-force techniques quickly break down even on small datasets. Existing approaches which go beyond brute force either can only find candidate small subsets to remove (but cannot certify their non-existence) [BGM20, KZC21], are computationally intractable beyond low dimensional settings [MR22], or require very strong assumptions on the data distribution and too many samples to give reasonable bounds in practice [BP21, FH23]. We present an efficient algorithm for certifying the robustness of linear regressions to removals of samples. We implement our algorithm and run it on several landmark econometrics datasets with hundreds of dimensions and tens of thousands of samples, giving the first non-trivial certificates of robustness to sample removal for datasets of dimension $4$ or greater. We prove that under distributional assumptions on a dataset, the bounds produced by our algorithm are tight up to a $1 + o(1)$ multiplicative factor.
- Abstract（参考訳）: 最近、多くの非常に影響力のある計量学研究の結論は、そのサンプルのごく一部(しばしば0.5 %以下)を除去することで覆すことができることが判明した。
これらの結論は、典型的には1つ以上のOLS回帰の結果に基づいており、このデータセットに適合するOLSの堅牢性を証明して、与えられたサンプルを削除できるかという疑問を提起する。
ブルートフォースのテクニックは、小さなデータセットでもすぐに崩壊します。
BGM20, KZC21] は低次元の設定を超えて計算的に抽出可能であり [MR22] 、データ分布に非常に強い仮定が必要であり、実際に適切な境界を与えるにはサンプルが多すぎる[BP21, FH23] 。
本稿では, 試料の除去に対する線形回帰の堅牢性を検証するための効率的なアルゴリズムを提案する。
我々はアルゴリズムを実装し、数百の次元と数万のサンプルを持ついくつかの目覚ましい計量的データセット上でそれを実行する。
データセット上の分布的仮定の下では、我々のアルゴリズムが生成する境界は1 + o(1)$乗算係数まできついことが証明される。
関連論文リスト
- Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity [11.412228884390784]
いくつかの測定値から低ランク2次凸行列を再構成する問題について検討した。
スペクトル特異性を持つ分解勾配は標本数と真理に収束することを示す。
論文 参考訳（メタデータ） (2024-08-20T14:09:28Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Weighted Sparse Partial Least Squares for Joint Sample and Feature
Selection [7.219077740523681]
本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。
我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
論文 参考訳（メタデータ） (2023-08-13T10:09:25Z) - Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data [4.971690889257356]
コリンズとナイアーとヴァスワニによって提案された交互最小化・退化スキームの適応について紹介する。
iidにおいてもバニラ変動最小化降下は破滅的に失敗するが, 軽度に非等方性データは得られない。
我々の分析は、事前の作業を統一し、一般化し、幅広いアプリケーションに柔軟なフレームワークを提供する。
論文 参考訳（メタデータ） (2023-08-08T17:56:20Z) - Non-Stochastic CDF Estimation Using Threshold Queries [3.6576781735746513]
実験的な分布を2つの課題で推定する問題に取り組む。
まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。
第二に、データは独立で同一の分散であると仮定されず、代わりにサンプルを生成する任意のプロセスが可能である。
論文 参考訳（メタデータ） (2023-01-13T18:00:57Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。