論文の概要: Near Optimal Heteroscedastic Regression with Symbiotic Learning
- arxiv url: http://arxiv.org/abs/2306.14288v2
- Date: Sat, 1 Jul 2023 16:36:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-04 12:14:51.795841
- Title: Near Optimal Heteroscedastic Regression with Symbiotic Learning
- Title（参考訳）: 共生学習による最適ヘテロシドスティック回帰
- Authors: Dheeraj Baby and Aniket Das and Dheeraj Nagaraj and Praneeth
Netrapalli
- Abstract要約: 我々は不連続線形回帰の問題を考察する。
正則ノルムにおいて$mathbfw*$を$tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$の誤差まで推定し、一致する下界を証明できる。
- 参考スコア（独自算出の注目度）: 29.16456701187538
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of heteroscedastic linear regression, where, given
$n$ samples $(\mathbf{x}_i, y_i)$ from $y_i = \langle \mathbf{w}^{*},
\mathbf{x}_i \rangle + \epsilon_i \cdot \langle \mathbf{f}^{*}, \mathbf{x}_i
\rangle$ with $\mathbf{x}_i \sim N(0,\mathbf{I})$, $\epsilon_i \sim N(0,1)$, we
aim to estimate $\mathbf{w}^{*}$. Beyond classical applications of such models
in statistics, econometrics, time series analysis etc., it is also particularly
relevant in machine learning when data is collected from multiple sources of
varying but apriori unknown quality. Our work shows that we can estimate
$\mathbf{w}^{*}$ in squared norm up to an error of
$\tilde{O}\left(\|\mathbf{f}^{*}\|^2 \cdot \left(\frac{1}{n} +
\left(\frac{d}{n}\right)^2\right)\right)$ and prove a matching lower bound
(upto log factors). This represents a substantial improvement upon the previous
best known upper bound of $\tilde{O}\left(\|\mathbf{f}^{*}\|^2\cdot
\frac{d}{n}\right)$. Our algorithm is an alternating minimization procedure
with two key subroutines 1. An adaptation of the classical weighted least
squares heuristic to estimate $\mathbf{w}^{*}$, for which we provide the first
non-asymptotic guarantee. 2. A nonconvex pseudogradient descent procedure for
estimating $\mathbf{f}^{*}$ inspired by phase retrieval. As corollaries, we
obtain fast non-asymptotic rates for two important problems, linear regression
with multiplicative noise and phase retrieval with multiplicative noise, both
of which are of independent interest. Beyond this, the proof of our lower
bound, which involves a novel adaptation of LeCam's method for handling
infinite mutual information quantities (thereby preventing a direct application
of standard techniques like Fano's method), could also be of broader interest
for establishing lower bounds for other heteroscedastic or heavy-tailed
statistical problems.
- Abstract（参考訳）: n$サンプル$(\mathbf{x}_i, y_i)$ from $y_i = \langle \mathbf{w}^{*}, \mathbf{x}_i \rangle + \epsilon_i \cdot \langle \mathbf{f}^{*}, \mathbf{x}_i \rangle$ with $\mathbf{x}_i \sim N(0,\mathbf{I})$, $\epsilon_i \sim N(0,1)$$$$$$\mathbf{w}^{*}$を推定する。
統計学、計量学、時系列分析などにおけるそのようなモデルの古典的な応用以外にも、データは様々なが未知の品質の複数のソースから収集される場合、機械学習にも特に関係している。
我々の研究は、$\tilde{o}\left(\|\mathbf{f}^{*}\|^2 \cdot \left(\frac{1}{n} + \left(\frac{d}{n}\right)^2\right)\right)$の誤差により二乗ノルムにおいて$\mathbf{w}^{*}$を推定し、一致する下界(対数係数)を証明できることを示した。
これは、以前の最もよく知られた上限である$\tilde{O}\left(\|\mathbf{f}^{*}\|^2\cdot \frac{d}{n}\right)$に対する実質的な改善である。
我々のアルゴリズムは2つのキーサブルーチンを持つ交代最小化手順である
1. 古典的重み付き最小二乗ヒューリスティックの適応により$\mathbf{w}^{*}$を推定し、これが最初の非漸近的保証を与える。
2. 位相検索にインスパイアされた$\mathbf{f}^{*}$を推定するための非凸擬勾配降下手順。
本稿では,2つの重要な問題に対する高速な非漸近速度,乗法雑音による線形回帰,乗法雑音による位相検索,それぞれが独立な関心事である。
これ以外にも、無限の相互情報量を扱うLeCam法(ファノ法のような標準手法の直接適用を防ぐことによって)の新たな適応を含む下界の証明は、他のヘテロ代数学的あるいは重み付き統計問題に対する下界の確立にも大きな関心を持つ可能性がある。
関連論文リスト
- Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳（メタデータ） (2024-02-22T02:20:24Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。
階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
論文 参考訳（メタデータ） (2023-05-11T16:07:47Z) - Misspecified Phase Retrieval with Generative Priors [15.134280834597865]
単一のインデックスモデル $y の $m$ i.d.realization から$n$-dimensional signal $mathbfx$ を推定する。
どちらのステップも、適切な条件下では、$sqrt(klog L)cdot (log m)/m$の統計的レートを享受できることが示される。
論文 参考訳（メタデータ） (2022-10-11T16:04:11Z) - 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) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical
Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。
我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文 参考訳（メタデータ） (2021-01-11T17:23:24Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。