論文の概要: Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws

• arxiv url: http://arxiv.org/abs/2610.00101v1
• Date: Tue, 08 Sep 2026 20:44:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-05 14:48:16.370456
• Title: Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws
• Title（参考訳）: 重み付きデータ選択:シャープな上半身法則と5次元法則
• Abstract要約: 最小ノルム学習者を持つ有限重み付き最小二乗に対して、$lceil3d/2rceilleq nleq2d-1$ の厳密な法則を証明します。 この保証は、観測されたすべての特徴ランクをカバーし、全特徴範囲を保存する選択を使用する。
• 参考スコア（独自算出の注目度）: 4.211691393530721
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How much risk does a small reweighted training support retain? For finite weighted least squares with the minimum-norm learner, we prove the exact law $Γ_d(n)=3-n/d$ throughout $\lceil3d/2\rceil\leq n\leq2d-1$. The guarantee covers every observed feature rank and uses selections that preserve the full feature span. Balanced simplex anchors reduce dimension; positive-weight lifting and independent-line compression close the risk bound. Shifted coordinate pairs attain the matching lower bound. The complete dataset-level upper bound and sharpness construction are verified in Lean 4. At the smaller budget $(d,n)=(5,6)$, we also prove $Γ_5(6)=11/5$, matching the simplex-block prediction from $5=3+2$ over arbitrary interacting configurations. Circuit covers, comparison second moments, and circuit-plane probabilities give the sharp excess $6/5$, while polar-face geometry resolves shared rank-three circuits. The general simplex-block frontier connects these laws within the intermediate-budget selection problem.
• Abstract（参考訳）: 小さな再重み付きトレーニングサポートは、どの程度のリスクを維持できるのか? 最小ノルムの学習者を持つ有限重み付き最小二乗に対して、厳密な法則を$\lceil3d/2\rceil\leq n\leq2d-1$で証明する。 この保証は、観測されたすべての特徴ランクをカバーし、全特徴範囲を保存する選択を使用する。 バランスの取れた単純なアンカーは寸法を減らし、正重持ち上げと独立ライン圧縮はリスクバウンドを閉じる。 シフト座標対は一致した下界に達する。 完全なデータセットレベルの上限とシャープネスの構成はLean 4で検証されます。 より小さな予算である$(d,n)=(5,6)$でも、任意の相互作用構成に対して5=3+2$の単純なブロック予測と一致する、$\_5(6)=11/5$を証明します。 サーキットカバー、比較第2モーメント、およびサーキットプレーン確率は、シャープな6/5$を与え、一方極面幾何学は共有ランク3サーキットを分解する。 一般の単純ブロックフロンティアは、中間予算選択問題の中でこれらの法則を接続する。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization [55.29259818039367]
  我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。 コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
  論文  参考訳（メタデータ） (2026-09-23T22:25:52Z)
• A Sub-4 Approximation for Fair $k$-Means [18.61347737579578]
  ユークリッド空間における公平な$k$-meansクラスタリングについて検討し、各クラスタにおける保護群の割合は、指定された下限と上限内にある必要がある。 本稿では,線形プログラミング緩和と入力の幾何学変換を組み合わせた近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-09-07T20:54:36Z)
• 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)
• A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification [0.0]
  PALACEはOrbitHS5k(91.3pm 1.0%$, matching Persformer)上で最強の閉形式ダイアグラムベースの方法である ドメインインフレーションが8ドルになると、均等グリッドが崩壊する一方、プレースメントは94%$を維持している(4クラスデータでは25%$) PALACEはOrbitHS5k(91.3pm 1.0%$, matching Persformer)上で最強の閉形式ダイアグラムベースの手法である。
  論文  参考訳（メタデータ） (2026-05-05T17:59:18Z)
• On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling [6.908972852063454]
  相関クラスタリング(CC)は基本的な教師なし学習プリミティブである。 LPベースの保証を維持するためには,どの程度のエッジ情報が必要であるかを検討する。 ヤオのミニマックス原理を通して、擬距離構造がなければ、任意のアルゴリズムが$o(n)$一様ランダムエッジを観測すると近似比が生じることを示す。
  論文  参考訳（メタデータ） (2026-02-14T09:12:15Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)

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

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