論文の概要: Computationally and Statistically Efficient Truncated Regression
- arxiv url: http://arxiv.org/abs/2010.12000v1
- Date: Thu, 22 Oct 2020 19:31:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 08:35:43.069406
- Title: Computationally and Statistically Efficient Truncated Regression
- Title（参考訳）: 計算的および統計的に効率的なトランケート回帰
- Authors: Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis
Zampetakis
- Abstract要約: 計算的かつ統計的に効率的な線形回帰の古典的問題に対する推定器を提供する。
提案手法では, トランキャット標本の負の対数類似度に代わることなく, プロジェクテッド・Descent Gradient (PSGD) を用いて推定する。
本稿では,SGDが単一層ニューラルネットワークの雑音活性化関数のパラメータを学習することを示す。
- 参考スコア（独自算出の注目度）: 36.3677715543994
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a computationally and statistically efficient estimator for the
classical problem of truncated linear regression, where the dependent variable
$y = w^T x + \epsilon$ and its corresponding vector of covariates $x \in R^k$
are only revealed if the dependent variable falls in some subset $S \subseteq
R$; otherwise the existence of the pair $(x, y)$ is hidden. This problem has
remained a challenge since the early works of [Tobin 1958, Amemiya 1973,
Hausman and Wise 1977], its applications are abundant, and its history dates
back even further to the work of Galton, Pearson, Lee, and Fisher. While
consistent estimators of the regression coefficients have been identified, the
error rates are not well-understood, especially in high dimensions.
Under a thickness assumption about the covariance matrix of the covariates in
the revealed sample, we provide a computationally efficient estimator for the
coefficient vector $w$ from $n$ revealed samples that attains $l_2$ error
$\tilde{O}(\sqrt{k/n})$. Our estimator uses Projected Stochastic Gradient
Descent (PSGD) without replacement on the negative log-likelihood of the
truncated sample. For the statistically efficient estimation we only need
oracle access to the set $S$.In order to achieve computational efficiency we
need to assume that $S$ is a union of a finite number of intervals but still
can be complicated. PSGD without replacement must be restricted to an
appropriately defined convex cone to guarantee that the negative log-likelihood
is strongly convex, which in turn is established using concentration of
matrices on variables with sub-exponential tails. We perform experiments on
simulated data to illustrate the accuracy of our estimator.
As a corollary, we show that SGD learns the parameters of single-layer neural
networks with noisy activation functions.
- Abstract（参考訳）: そこでは、従属変数 $y = w^T x + \epsilon$ とその対応ベクトル $x \in R^k$ が、従属変数がある部分集合 $S \subseteq R$ に該当する場合のみ、従属変数 $(x, y)$ の存在が隠される。
この問題は(Tobin 1958, Amemiya 1973, Hausman and Wise 1977)の初期の研究から問題であり、その応用は豊富であり、その歴史はGalton, Pearson, Lee, Fisherの業績にまでさかのぼる。
回帰係数の一貫した推定器が同定されているが、誤差率はよく理解されていない。
明らかにされたサンプル中の共変量の共分散行列に関する厚みの仮定の下で、係数ベクトル $w$ を$n$ から計算効率良く推定し、$l_2$ 誤差 $\tilde{o}(\sqrt{k/n})$ を得る。
提案手法では, ストランキャット標本の負の対数類似性に代えてPSGD(Projected Stochastic Gradient Descent)を用いた。
統計的に効率的な見積は、oracleがセットした$s$に対してのみアクセスする必要がある。
計算効率を達成するためには、$s$ を有限個の区間の和と仮定する必要があるが、それでも複雑である。
置換のないpsgdは、負の対流が強い凸であることを保証するために適切に定義された凸円錐に制限されなければならず、これは、部分指数尾を持つ変数上の行列の集中によって確立される。
シミュレーションデータを用いて,推定器の精度を示す実験を行った。
本稿では,SGDが単一層ニューラルネットワークの雑音活性化関数のパラメータを学習することを示す。
関連論文リスト
- Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
無限次元線形回帰セットアップにおけるスケーリング法則の理論について検討する。
テストエラーの再現可能な部分は$Theta(-(a-1) + N-(a-1)/a)$であることを示す。
我々の理論は経験的ニューラルスケーリング法則と一致し、数値シミュレーションによって検証される。
論文 参考訳（メタデータ） (2024-06-12T17:53:29Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - The Adaptive $τ$-Lasso: Robustness and Oracle Properties [12.06248959194646]
本稿では,高次元データセット解析のためのロバストな$tau$-regression推定器の正規化版を紹介する。
得られた推定器はアダプティブ $tau$-Lasso と呼ばれ、外れ値や高平均点に対して堅牢である。
外れ値と高平均点に直面して、適応 $tau$-Lasso と $tau$-Lasso 推定器は、最高のパフォーマンスまたは最も近いパフォーマンスを達成する。
論文 参考訳（メタデータ） (2023-04-18T21:34:14Z) - Efficient Truncated Linear Regression with Unknown Noise Variance [26.870279729431328]
雑音のばらつきが不明な場合に, 線形回帰の計算的, 統計的に効率的な推定器を提案する。
提案手法は, トランキャット標本の負の類似度に対して, プロジェクテッド・グラディエント・ディフレッシュを効果的に実装することに基づく。
論文 参考訳（メタデータ） (2022-08-25T12:17:37Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳（メタデータ） (2021-11-04T15:59:44Z) - SLOE: A Faster Method for Statistical Inference in High-Dimensional
Logistic Regression [68.66245730450915]
実用データセットに対する予測の偏見を回避し、頻繁な不確実性を推定する改善された手法を開発している。
私たちの主な貢献は、推定と推論の計算時間をマグニチュードの順序で短縮する収束保証付き信号強度の推定器SLOEです。
論文 参考訳（メタデータ） (2021-03-23T17:48:56Z) - Outlier-robust sparse/low-rank least-squares regression and robust
matrix completion [1.0878040851637998]
ヘテロジニアス雑音を伴う統計的学習フレームワークにおける高次元最小二乗回帰について検討する。
また, 製品プロセスの新たな応用に基づいて, 行列分解を伴う新しいトレーサリグレス理論を提案する。
論文 参考訳（メタデータ） (2020-12-12T07:42:47Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。