論文の概要: Linear Regression with Unknown Truncation Beyond Gaussian Features
- arxiv url: http://arxiv.org/abs/2602.12534v1
- Date: Fri, 13 Feb 2026 02:29:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-16 23:37:53.8162
- Title: Linear Regression with Unknown Truncation Beyond Gaussian Features
- Title（参考訳）: ガウス的特徴を超えた未知のトラニケーションを持つ線形回帰
- Authors: Alexandros Kouridakis, Anay Mehrotra, Alkis Kalavasis, Constantine Caramanis,
- Abstract要約: truncated linear regression では、サンプル $(x,y)$ は、結果 $y$ が特定の生存セット $Sstar$ 内にある場合にのみ表示される。
未知のサバイバルセットが$mathrmpoly (d/varepsilon)$ timeで実行されるような、トランカットされた線形回帰の最初のアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 66.1580269813084
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In truncated linear regression, samples $(x,y)$ are shown only when the outcome $y$ falls inside a certain survival set $S^\star$ and the goal is to estimate the unknown $d$-dimensional regressor $w^\star$. This problem has a long history of study in Statistics and Machine Learning going back to the works of (Galton, 1897; Tobin, 1958) and more recently in, e.g., (Daskalakis et al., 2019; 2021; Lee et al., 2023; 2024). Despite this long history, however, most prior works are limited to the special case where $S^\star$ is precisely known. The more practically relevant case, where $S^\star$ is unknown and must be learned from data, remains open: indeed, here the only available algorithms require strong assumptions on the distribution of the feature vectors (e.g., Gaussianity) and, even then, have a $d^{\mathrm{poly} (1/\varepsilon)}$ run time for achieving $\varepsilon$ accuracy. In this work, we give the first algorithm for truncated linear regression with unknown survival set that runs in $\mathrm{poly} (d/\varepsilon)$ time, by only requiring that the feature vectors are sub-Gaussian. Our algorithm relies on a novel subroutine for efficiently learning unions of a bounded number of intervals using access to positive examples (without any negative examples) under a certain smoothness condition. This learning guarantee adds to the line of works on positive-only PAC learning and may be of independent interest.
- Abstract（参考訳）: truncated linear regression において、サンプル $(x,y)$ は、結果 $y$ が特定の生存セット $S^\star$ 内にある場合にのみ示され、その目標は未知の $d$-次元回帰器 $w^\star$ を推定することである。
この問題には、統計学と機械学習における長い研究の歴史があり(Galton, 1897; Tobin, 1958)、最近では e g , (Daskalakis et al , 2019; 2021; Lee et al , 2023; 2024) に遡る。
しかし、この長い歴史にもかかわらず、ほとんどの先行研究は、$S^\star$が正確に知られている特別な場合に限定されている。
S^\star$が未知で、データから学ばなければならない、より実践的なケースは、依然としてオープンである: ここでは、利用可能な唯一のアルゴリズムは、特徴ベクトルの分布(例えば、ガウス性)について強い仮定を必要とし、なおかつ、$d^{\mathrm{poly} (1/\varepsilon)} を持つ。
この研究では、特徴ベクトルがガウス以下であることが要求されるだけで、$\mathrm{poly} (d/\varepsilon)$ time で実行される未知生存集合を持つ留置線形回帰の最初のアルゴリズムを与える。
我々のアルゴリズムは、ある滑らかな条件下で正の例(負の例は含まない)にアクセスして、有界区間の結合を効率的に学習する新しいサブルーチンに依存している。
この学習保証は、肯定的なPAC学習の研究のラインに追加され、独立した関心を持つ可能性がある。
関連論文リスト
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。
我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
論文 参考訳（メタデータ） (2024-10-02T15:21:07Z) - 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) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Truncated Linear Regression in High Dimensions [26.41623833920794]
truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
論文 参考訳（メタデータ） (2020-07-29T00:31:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。