論文の概要: Sample-Efficient Linear Regression with Self-Selection Bias
- arxiv url: http://arxiv.org/abs/2402.14229v1
- Date: Thu, 22 Feb 2024 02:20:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 16:43:54.861898
- Title: Sample-Efficient Linear Regression with Self-Selection Bias
- Title（参考訳）: 自己選択バイアスを考慮したサンプル効率線形回帰
- Authors: Jason Gaitonde and Elchanan Mossel
- Abstract要約: 未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
- 参考スコア（独自算出の注目度）: 7.605563562103568
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of linear regression with self-selection bias in the
unknown-index setting, as introduced in recent work by Cherapanamjeri,
Daskalakis, Ilyas, and Zampetakis [STOC 2023]. In this model, one observes $m$
i.i.d. samples $(\mathbf{x}_{\ell},z_{\ell})_{\ell=1}^m$ where
$z_{\ell}=\max_{i\in [k]}\{\mathbf{x}_{\ell}^T\mathbf{w}_i+\eta_{i,\ell}\}$,
but the maximizing index $i_{\ell}$ is unobserved. Here, the
$\mathbf{x}_{\ell}$ are assumed to be $\mathcal{N}(0,I_n)$ and the noise
distribution $\mathbf{\eta}_{\ell}\sim \mathcal{D}$ is centered and independent
of $\mathbf{x}_{\ell}$. We provide a novel and near optimally sample-efficient
(in terms of $k$) algorithm to recover $\mathbf{w}_1,\ldots,\mathbf{w}_k\in
\mathbb{R}^n$ up to additive $\ell_2$-error $\varepsilon$ with polynomial
sample complexity $\tilde{O}(n)\cdot \mathsf{poly}(k,1/\varepsilon)$ and
significantly improved time complexity
$\mathsf{poly}(n,k,1/\varepsilon)+O(\log(k)/\varepsilon)^{O(k)}$. When
$k=O(1)$, our algorithm runs in $\mathsf{poly}(n,1/\varepsilon)$ time,
generalizing the polynomial guarantee of an explicit moment matching algorithm
of Cherapanamjeri, et al. for $k=2$ and when it is known that
$\mathcal{D}=\mathcal{N}(0,I_k)$. Our algorithm succeeds under significantly
relaxed noise assumptions, and therefore also succeeds in the related setting
of max-linear regression where the added noise is taken outside the maximum.
For this problem, our algorithm is efficient in a much larger range of $k$ than
the state-of-the-art due to Ghosh, Pananjady, Guntuboyina, and Ramchandran
[IEEE Trans. Inf. Theory 2022] for not too small $\varepsilon$, and leads to
improved algorithms for any $\varepsilon$ by providing a warm start for
existing local convergence methods.
- Abstract（参考訳）: 近年のcherapanamjeri, daskalakis, ilyas, zampetakis [stoc 2023] による研究で紹介されたように,未知インデックス設定における自己選択バイアスを伴う線形回帰の問題を考える。
このモデルでは、$m$ i.i.d. sample $(\mathbf{x}_{\ell},z_{\ell})_{\ell=1}^m$ where $z_{\ell}=\max_{i\in [k]}\mathbf{x}_{\ell}^T\mathbf{w}_i+\eta_{i,\ell}$を観測するが、最大化指数$i_{\ell}$は観測されない。
ここで、$\mathbf{x}_{\ell}$は$\mathcal{N}(0,I_n)$と仮定され、ノイズ分布$\mathbf{\eta}_{\ell}\sim \mathcal{D}$は$\mathbf{x}_{\ell}$の中心であり、独立である。
我々は、新しい($k$)アルゴリズムで、$\mathbf{w}_1,\ldots,\mathbf{w}_k\in \mathbb{R}^n$ up to additive $\ell_2$-error $\varepsilon$ with polynomial sample complexity $\tilde{O}(n)\cdot \mathsf{poly}(k,1/\varepsilon)$と大幅に改善された時間複雑性 $\mathsf{poly}(n,k,1/\varepsilon)+O(\log(k)/\varepsilon)^{O(k)$を提供する。
k=O(1)$ の場合、我々のアルゴリズムは $\mathsf{poly}(n,1/\varepsilon)$ time で実行され、Cherapanamjeri などの明示的なモーメントマッチングアルゴリズムの多項式保証を$k=2$ で一般化し、$\mathcal{D}=\mathcal{N}(0,I_k)$ が知られている。
提案アルゴリズムは雑音の仮定をかなり緩めることに成功し, 付加雑音を最大外へ取り出す最大線形回帰の関連設定にも成功している。
この問題に対して、我々のアルゴリズムは、Ghosh, Pananjady, Guntuboyina, Ramchandran [IEEE Trans. Inf. Theory 2022] による最先端技術よりもはるかに広い範囲の$k$で効率的であり、既存の局所収束法の温かいスタートを提供することにより、任意の$\varepsilon$に対するアルゴリズムの改善につながる。
関連論文リスト
- Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳（メタデータ） (2023-10-02T16:44:47Z) - Matrix Completion in Almost-Verification Time [37.61139884826181]
99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。
本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
論文 参考訳（メタデータ） (2023-08-07T15:24:49Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳（メタデータ） (2020-06-23T20:21:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。