論文の概要: What Makes A Good Fisherman? Linear Regression under Self-Selection Bias

• arxiv url: http://arxiv.org/abs/2205.03246v1
• Date: Fri, 6 May 2022 14:03:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-09 13:13:18.027846
• Title: What Makes A Good Fisherman? Linear Regression under Self-Selection Bias
• Title（参考訳）: 何が良い漁師になるのか? 自己選択バイアス下における線形回帰
• Authors: Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, Manolis Zampetakis
• Abstract要約: 古典的な自己選択の設定では、ゴールは、観測値$(x(i), y(i))$から同時に$k$モデルを学ぶことである。 本研究では,モデルが線形であるこの問題の最も標準的な設定に対して,計算的かつ統計的に効率的な推定アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 32.6588421908864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the classical setting of self-selection, the goal is to learn $k$ models, simultaneously from observations $(x^{(i)}, y^{(i)})$ where $y^{(i)}$ is the output of one of $k$ underlying models on input $x^{(i)}$. In contrast to mixture models, where we observe the output of a randomly selected model, here the observed model depends on the outputs themselves, and is determined by some known selection criterion. For example, we might observe the highest output, the smallest output, or the median output of the $k$ models. In known-index self-selection, the identity of the observed model output is observable; in unknown-index self-selection, it is not. Self-selection has a long history in Econometrics and applications in various theoretical and applied fields, including treatment effect estimation, imitation learning, learning from strategically reported data, and learning from markets at disequilibrium. In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear. In the known-index case, we require poly$(1/\varepsilon, k, d)$ sample and time complexity to estimate all model parameters to accuracy $\varepsilon$ in $d$ dimensions, and can accommodate quite general selection criteria. In the more challenging unknown-index case, even the identifiability of the linear models (from infinitely many samples) was not known. We show three results in this case for the commonly studied $\max$ self-selection criterion: (1) we show that the linear models are indeed identifiable, (2) for general $k$ we provide an algorithm with poly$(d) \exp(\text{poly}(k))$ sample and time complexity to estimate the regression parameters up to error $1/\text{poly}(k)$, and (3) for $k = 2$ we provide an algorithm for any error $\varepsilon$ and poly$(d, 1/\varepsilon)$ sample and time complexity.
• Abstract（参考訳）: 古典的な自己選択の場合、目標は、観察値の$(x^{(i)}, y^{(i)})$から同時に$k$モデルを学習することであり、ここで$y^{(i)}$は入力の$x^{(i)}$上の$k$モデルの出力である。 ランダムに選択されたモデルの出力を観測する混合モデルとは対照的に、観測されたモデルは出力自身に依存し、既知の選択基準によって決定される。 例えば、最高出力、最小出力、または$k$モデルの中央出力を観測することができる。 既知のインデックス自己選択では、観測されたモデル出力の同一性は観測可能である。 自己選択は、治療効果の推定、模倣学習、戦略的に報告されたデータからの学習、不均衡での市場からの学習など、様々な理論および応用分野における計量学および応用において長い歴史を持つ。 本稿では,モデルが線形である問題の最も標準的な設定に対して,最初の計算量および統計効率のよい推定アルゴリズムを提案する。 既知のインデックスの場合、すべてのモデルパラメータを正確に推定するために、poly$(1/\varepsilon, k, d)$サンプルと時間複雑さが必要であり、非常に一般的な選択基準を満たすことができる。 より困難な未知のインデックスの場合、(無限に多くのサンプルから)線形モデルの識別可能性さえ分かっていない。 1) 線形モデルが真に識別可能であること、(2) 一般の $k$ に対して poly$(d) \exp(\text{poly}(k))$ による回帰パラメータを誤差1/\text{poly}(k)$, (3) $k = 2$ 任意の誤差$\varepsilon$ と poly$(d, 1/\varepsilon)$ のサンプルと時間の複雑さを推定するためのアルゴリズムを提供する。

関連論文リスト

• Agnostic Active Learning of Single Index Models with Linear Sample Complexity [27.065175036001246]
  F(mathbf x) = f(langle mathbf w, mathbf xrangle)$。
  論文  参考訳（メタデータ） (2024-05-15T13:11:28Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• $p$-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets [74.37849422071206]
  本稿では, 2次応答に対する一般化線形モデルである,$p$一般化プロビット回帰モデルについて検討する。 p$の一般化されたプロビット回帰に対する最大可能性推定器は、大容量データ上で$(1+varepsilon)$の係数まで効率的に近似できることを示す。
  論文  参考訳（メタデータ） (2022-03-25T10:54:41Z)
• On Model Selection Consistency of Lasso for High-Dimensional Ising Models on Tree-like Graphs [13.14903445595385]
  近傍型最小絶対収縮・選択演算子(Lasso)を用いた高次元イジングモデル選択の問題点を考察する。 常磁性相の任意の木様グラフに対して、サンプルサイズ$n=Omega(d3logp)$で一貫したモデル選択が達成できることは厳密に証明されている。 ラッソの人気と効率性を考えると、厳密な解析はイジングモデル選択における実践的利用の理論的裏付けとなる。
  論文  参考訳（メタデータ） (2021-10-16T07:23:02Z)
• Ising Model Selection Using $\ell_{1}$-Regularized Linear Regression [13.14903445595385]
  モデルの不特定にもかかわらず、$ell_1$-regularized linear regression(ell_1$-LinR)推定器は、$N$変数でIsingモデルのグラフ構造を復元することに成功した。 また,$ell_1$-LinR推定器の非漸近性能を適度な$M$と$N$で正確に予測する計算効率のよい手法を提案する。
  論文  参考訳（メタデータ） (2021-02-08T03:45:10Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• 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)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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