論文の概要: Linear Regression with Self-Selection Bias in Polynomial Time
- arxiv url: http://arxiv.org/abs/2611.17228v1
- Date: Thu, 12 Nov 2026 18:21:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.585084
- Title: Linear Regression with Self-Selection Bias in Polynomial Time
- Title(参考訳): 多項式時間における自己選択バイアスによる線形回帰
- Abstract要約: 我々は、最大自己選択基準を持つ誤り$varepsilon$まで、$n$次元の自己選択バイアスで$k$線形回帰器を推定する問題を再検討する。
我々の主な成果は、この問題の未知のインデックス変種に対する$mathrmpoly(n,k,1/varepsilon)$ timeアルゴリズムである。
- 参考スコア(独自算出の注目度): 2.0607844057825324
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the problem of estimating $k$ linear regressors with self-selection bias in $n$ dimensions up to error $\varepsilon$ with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on $k$. Prior works exhaustively search over a $k$-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-$(\log n)$ Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.
- Abstract(参考訳): 我々は、Cherapanamjeri, Daskalakis, Ilyas, Zampetakis [CDIZ23, STOC] が導入した最大自己選択基準による$n$次元の自己選択バイアスを持つ$k$線形回帰器を誤差まで推定する問題を再検討する。
その結果、Gaitonde と Mossel [GM24] と Kalavasis, Mehrotra, Zhou (KMZ26, COLT) による最もよく知られたアルゴリズムの実行時間を改善することができる。
提案アルゴリズムは回帰器間の相関雑音の存在に成功し,最大アフィン回帰の関連設定を捉える。
したがって、この問題に対する最初の多項式時間アルゴリズムも提供し、Ghosh, Pananjady, Guntuboyina, Ramchandran (GPGR22, IEEE Transactions on Information Theory) と Gaitonde と Mossel (GM24) の先行研究を k$ に指数関数依存で改善する。
事前の作業は、テスト候補に対する応答の条件モーメントを使用して、回帰器によって分散された$k$次元のサブスペースを徹底的に探索する。
対照的に、我々のアルゴリズムは共変量モーメントの理解の向上によって駆動される。
我々は、大きな応答値を持つ観測に限定して、余変数の次数-$(\log n)$ Hermite モーメントが、回帰器のテンソルパワーの和としておよそ分解されることを示す。
このアルゴリズムの最初のステップは、これらの暗黙的に表現された高次テンソルに対するテンソル分解アルゴリズムと見なすことができる。
通常の最小二乗の単純変量に基づく二次ステップは、これらの単位ベクトルが与えられた回帰器の見積もりを抽出する。
分析的洞察とアルゴリズム的コンポーネントは、他の潜在変数問題に対する効率的なアルゴリズムの設計に応用できると考えている。
関連論文リスト
- Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time [56.773730898972225]
この学習課題に対して,最初の完全多項式時間アルゴリズムを提案する。
我々のアルゴリズムは、$mathrmpoly(d, k, 1/)$サンプルを描画し、$mathrmpoly(d, k, 1/)$タイムで実行し、高い確率でターゲット概念に$-closeの仮説を出力する。
論文 参考訳(メタデータ) (2026-10-23T17:34:15Z) - Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
本稿では,各ラウンドにおける損失が任意の有界要素によって誘導される逆カーネルバンドイット問題について検討する。
我々の主な結果は、$widetildeObig(sqrtT, d_*(),log|X|big)$, ここでは$d_*()$は有効次元の広く解釈された概念である。
論文 参考訳(メタデータ) (2026-05-26T06:10:24Z) - A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。
提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
論文 参考訳(メタデータ) (2025-10-31T05:02:33Z) - The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
この研究において、ラベルは(ガウス)$d$-次元入力にのみ依存し、低次元$r = O_d(1)$部分空間への射影を通して得られる。
生成的跳躍指数 $kstar$, [Damian et al.'24] から生成的指数の自然拡張をマルチインデックス設定に導入する。
論文 参考訳(メタデータ) (2025-06-05T18:34:56Z) - Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond [11.884593048693507]
我々は,$doperator次元の自己選択バイアスを持つ線形回帰器を$k$で推定する問題を再検討する。
我々の主な結果は、この問題に対する$namepoly(d,k,1/varepsilon) + kO(k)$ time algorithmである。
論文 参考訳(メタデータ) (2025-04-06T20:59:12Z) - Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
本研究では, 勾配勾配勾配(SGD)を一定のステップサイズで解くことで, 密接な凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を、反復数$n$に対して拡張する。
我々の分析は、時相マルコフ連鎖と見なされるSGDの特性に依存している。
論文 参考訳(メタデータ) (2024-10-07T15:02:48Z) - Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
本稿では,高次元線形回帰問題における反復アルゴリズムから得られた繰り返し$hbb1,dots,hbbT$について検討する。
解析および提案した推定器は、GD(Gradient Descent)、GD(GD)およびFast Iterative Soft-Thresholding(FISTA)などの加速変種に適用できる。
論文 参考訳(メタデータ) (2024-04-27T10:20:41Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳(メタデータ) (2021-03-04T19:01:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。