論文の概要: Exact Risk Ratios for Weighted Data Selection in Linear Regression

• arxiv url: http://arxiv.org/abs/2608.28007v1
• Date: Fri, 28 Aug 2026 07:19:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-31 17:16:04.23652
• Title: Exact Risk Ratios for Weighted Data Selection in Linear Regression
• Title（参考訳）: 線形回帰における重み付きデータ選択のための厳密なリスク比
• Abstract要約: Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) は以下の未解決問題を提示した。 セレクタは有限データセット $D subseteq mathbbRd times mathbbR$ を見て、非負の重みとともに少なくとも$n$の例を選び、重み付き最小二乗の目的を最小ノルム ERM に渡す。 いくつかの短い経路が失敗することを示す明示的な反例と、証明された全てのケースに対する構成的なサインタイム選択アルゴリズムを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed the following open problem. A selector sees a finite dataset $D \subseteq \mathbb{R}^d \times \mathbb{R}$, picks at most $n$ examples together with nonnegative weights, and hands the weighted least squares objective to the minimum-norm ERM. Writing $F_w(d,n)$ for the worst-case ratio between the loss of the returned predictor on all of $D$ and the optimal loss, they proved $F_w(d,n)=\infty$ for $n<d$, $F_w(d,d)=d+1$ and $F_w(d,n)=1$ for $n \ge 2d$, and asked for the value in the open regime $d<n<2d$. We determine this value in several cases. For every $d$ we prove $F_w(d,2d-1)=1+1/d$, which confirms a claim stated without proof in the original note. We further prove $F_w(3,4)=5/3$ and $F_w(4,5)=2$, the two smallest cells not covered by the endpoint formula. For every intermediate budget $n=d+k$ we prove the lower bound $F_w(d,d+k) \ge 1+Γ_{d,k}$, where $Γ_{d,k}$ is an explicit harmonic quantity over balanced partitions, and we show that this bound is the exact minimax value over the class of datasets whose whitened gradient systems carry an orthogonal circuit-block structure. All three exact values match $1+Γ_{d,k}$, and we conjecture that equality holds throughout the open regime. The upper bound proofs run on a common geometric spine: a rigidity theorem for positive spanning configurations of loss gradients, classifications and structural reductions of small positive bases in $\mathbb{R}^3$ and $\mathbb{R}^4$, and a dimension-free extremal-basis argument that converts sign-cone geometry into five-point selections. We also give explicit counterexamples showing that several shorter routes fail, and constructive polynomial-time selection algorithms for all proved cases.
• Abstract（参考訳）: Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) は以下の未解決問題を提示した。 セレクタは有限データセット $D \subseteq \mathbb{R}^d \times \mathbb{R}$ を見て、非負の重みとともに少なくとも$n$の例を選び、重み付き最小二乗を最小ノルム ERM に渡す。 F_w(d,n)$ for the worst-case ratio for the loss of $D$ on the all of $F_w(d,n)=\infty$ for $n<d$, $F_w(d,d)=d+1$ and $F_w(d,n)=1$ for $n \ge 2d$, and asked the value in the open regime $d<n<2d$。 この値はいくつかのケースで決定します。 すべての$d$に対して$F_w(d,2d-1)=1+1/d$を証明します。 さらに$F_w(3,4)=5/3$と$F_w(4,5)=2$という2つの最小のセルがエンドポイント式でカバーされていないことを証明します。 任意の中間予算 $n=d+k$ に対して、下界 $F_w(d,d+k) \ge 1+\_{d,k}$ を証明し、この値がバランスの取れた分割に対する明示的な調和量であり、この境界は、白色勾配系が直交回路ブロック構造を持つデータセットのクラスに対する正確な最小値であることを示す。 3つの正確な値はいずれも$1+\_{d,k}$と一致し、我々は公理全体を通して等式が成り立つと推測する。 上界証明は一般的な幾何学的スピン上で動作し、損失勾配の正のスパンニング構成のための剛性定理、$\mathbb{R}^3$と$\mathbb{R}^4$の小さな正の基底の分類と構造的縮小、および手根幾何学を5点選択に変換する次元自由極小基底論である。 また、いくつかの短い経路が失敗することを示す明示的な反例や、すべての証明されたケースに対する構成的多項式時間選択アルゴリズムも提示する。

関連論文リスト

• Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression [0.0]
  有限データセットの完全なデータ損失を回復する重み付き例の最小予算は、正確に$n*(d,m)=(m+1)d$であることを示す。 直近の未送付プリプリントで循環する誤ったクレームを補正すると、$m=2$の明示的なデータセットが示され、2d$ポイントの重み付き選択がなければ、最適損失が回復する。
  論文  参考訳（メタデータ） (2026-08-31T05:04:49Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck、Li、Nagarajは、一般的なデータでは、ノイズラベルに適合する$m$のニューロンを持つ任意の2層ニューラルネットワークは、リプシッツ定数を持つ必要があると推測した。 予想法則を1つの対数係数まで証明し、特にReLUネットワークにおいて連続的な片方向線形活性化を行う。
  論文  参考訳（メタデータ） (2026-07-08T17:44:15Z)
• The Exact Worst-Case Tail Probability under Bounded Kurtosis [39.91890433860882]
  片側テールコントロールのために、クルトーシスバウンドが何を買うか、正確に決定する。 平均$0$、分散$1$、そして少なくとも$$4の4モーメントを持つ実乱変数のクラス$mathcalC()$の場合、歪みは自由のままである。
  論文  参考訳（メタデータ） (2026-07-06T15:40:54Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
  論文  参考訳（メタデータ） (2026-03-09T22:27:00Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• $O(k)$-Equivariant Dimensionality Reduction on Stiefel Manifolds [2.0818404738530525]
  多くの実世界のデータセットは、高次元のスティーフェル多様体とグラスマン多様体に、それぞれ$V_k(mathbbRN)$と$Gr(k, mathbbRN)$で存在する。 我々はtextitPrincipal Stiefel Coordinates (PSC) というアルゴリズムを提案し、データ次元を$V_k(mathbbRN)$から$V_k(mathbbRn)$に減らした。
  論文  参考訳（メタデータ） (2023-09-19T17:21:12Z)
• Near-Optimal Model Discrimination with Non-Disclosure [19.88145627448243]
  まず、二乗損失を持つよく特定された線形モデルについて考察する。 類似した形態のサンプルの複雑さは、たとえ不特定であっても引き起こされる。
  論文  参考訳（メタデータ） (2020-12-04T23:52:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。