論文の概要: Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
- arxiv url: http://arxiv.org/abs/2608.30254v1
- Date: Mon, 31 Aug 2026 05:04:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:31.239535
- Title: Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
- Title（参考訳）: ベクトル値線形回帰における重み付きデータ選択のための厳密な回復閾値
- Abstract要約: 有限データセットの完全なデータ損失を回復する重み付き例の最小予算は、正確に$n*(d,m)=(m+1)d$であることを示す。
直近の未送付プリプリントで循環する誤ったクレームを補正すると、$m=2$の明示的なデータセットが示され、2d$ポイントの重み付き選択がなければ、最適損失が回復する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We resolve the threshold part of Question 4 of the COLT 2025 open problem "Data Selection for Regression Tasks" of Hanneke, Moran, Shlimovich and Yehudayoff. In vector-valued linear regression with square loss $\ell_{(x,y)}(W)=|Wx-y|_2^2$, where $x\in\mathbb{R}^d$, $y\in\mathbb{R}^m$ and the learner is the empirical risk minimizer of minimal Frobenius norm, we prove that the minimal budget of weighted examples that recovers the full-data loss on every finite dataset is exactly $n^*(d,m)=(m+1)d$. We further determine two more values of the weighted selection profile $F_w(d,m,n)$: at the near-threshold budget, $F_w(d,m,(m+1)d-1)=1+\frac{1}{dm^2}$, and at the spanning budget, $F_w(d,m,d)=d+1$ for every $m$, while $F_w(d,m,n)=\infty$ for $n<d$. For the smallest open intermediate cell $(d,m)=(2,2)$ we prove $F_w(2,2,3)\in[13/8,15/8]$ and $F_w(2,2,4)\in[5/4,3/2]$, reduce the conjectured exact values $13/8$ and $5/4$ to a finite moment problem on the circle with at most seven atoms, and establish strong structural evidence for the conjecture. The upper-bound techniques (a fixed-basis conic compression lemma, a determinant-facet rigidity theorem for maximal certificates, and sharp sparsification lemmas for zero-mean weighted point systems) are of independent interest. As a byproduct we correct an erroneous claim circulating in a recent unrefereed preprint, exhibiting an explicit dataset with $m=2$ on which no weighted selection of $2d$ points recovers the optimal loss. All results are new only for $m\ge 2$; the scalar case $m=1$ is due to Hanneke et al.
- Abstract（参考訳）: 我々は,ハネケ,モラン,シュリモヴィチ,イェーダホフのCOLT 2025オープン問題「回帰タスクのデータ選択」の質問4のしきい値部分を解決する。
平方損失$\ell_{(x,y)}(W)=|Wx-y|_2^2$, where $x\in\mathbb{R}^d$, $y\in\mathbb{R}^m$, and the learner is the empirical risk minimalr of minimal Frobenius norm, we prove that the minimal budget of weighted examples that recovery the full-data loss on every finite dataset is exactly $n^*(d,m)=(m+1)d$。
F_w(d,m,n)$: the near-threshold budget, $F_w(d,m,(m+1)d-1)=1+\frac{1}{dm^2}$, and the spaning budget, $F_w(d,m,d)=d+1$ for every $m$, and $F_w(d,m,n)=\infty$ for $n<d$。
最小の開中間セル $(d,m)=(2,2)$ に対して、$F_w(2,2,3)\in[13/8,15/8]$ と $F_w(2,2,4)\in[5/4,3/2]$ を証明し、予想された正確な値が 113/8$ と 5/4$ を、少なくとも7つの原子を持つ円上の有限モーメント問題に還元し、予想の強い構造的証拠を確立する。
上行法(固定基底円錐圧縮補題、最大証明に対する決定的面剛性定理、ゼロ平均重み付き点系に対するシャープなスパーシフィケーション補題)は独立な関心事である。
副産物として、直近の未送付プリプリントで循環する誤ったクレームを補正し、$m=2$の明示的なデータセットを示し、2d$ポイントの重み付き選択が最適損失を回復しない。
すべての結果は$m\ge 2$に対してのみ新しく、スカラーの場合$m=1$はHannekeらによる。
関連論文リスト
- Exact Risk Ratios for Weighted Data Selection in Linear Regression [0.0]
Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) は以下の未解決問題を提示した。
セレクタは有限データセット $D subseteq mathbbRd times mathbbR$ を見て、非負の重みとともに少なくとも$n$の例を選び、重み付き最小二乗の目的を最小ノルム ERM に渡す。
いくつかの短い経路が失敗することを示す明示的な反例と、証明された全てのケースに対する構成的なサインタイム選択アルゴリズムを示す。
論文 参考訳（メタデータ） (2026-08-28T07:19:17Z) - Algorithms for adaptive and heteroskedastic linear regression at the computational threshold [2.2359088001899736]
本研究では, 有限サンプル線形回帰法について検討した。
適応線形回帰では、誤差は未知の分布から引き出される。
計算非効率な)適応推定器を導入し、$p$が$k対称対数対数対数の混合である限り達成する。
論文 参考訳（メタデータ） (2026-08-19T00:17:22Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
ヘビーテール付きバンディットには、ヘビーテール付きノイズ、トランケーション、中央値の2つの基本戦略が導入されている。
本稿では,オンラインミラー降下フレームワークに基づくEmphone-passアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-03-01T09:41:45Z) - Conditional regression for the Nonlinear Single-Variable Model [4.565636963872865]
次元の統計的および計算的呪いなしで、$mathbbRd$に$F$を回帰するには、特別な統計モデルが必要である。
ここで、モデル $F(X):=f(Pi_gamma X)$ ここで $Pi_gamma:mathbbRdto[0,textrmlen_gamma]$ は正則曲線のパラメータへの最も近い点射影である。
論文 参考訳（メタデータ） (2024-11-14T18:53:51Z) - 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) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data [22.233705161499273]
我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。
我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。
我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
論文 参考訳（メタデータ） (2022-01-10T08:17:05Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。