論文の概要: The Advantages of Fresh Sketching for Ridge Regression

• arxiv url: http://arxiv.org/abs/2609.38565v1
• Date: Tue, 29 Sep 2026 21:24:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:26.75659
• Title: The Advantages of Fresh Sketching for Ridge Regression
• Title（参考訳）: 尾根後退に対するフレッシュ・スケッチ法の有用性
• Abstract要約: カラムサンプリングによる反復尾根回帰に対して,新しいスケッチが有効であることを示す。 新しくスケッチすることで、Gramマトリックス全体を均一に上回るのではなく、現在の残留ソリューションに沿ってエラーを分析することができます。 この方向ビューは、レバレッジスコアとリッジレバレッジスコアサンプリングのためのよりシャープな収束保証を与える。
• 参考スコア（独自算出の注目度）: 6.859102414696438
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Over the past 25 years, sketching and sampling have become widely used tools for accelerating large-scale regression. In iterative randomized solvers, a basic design choice is whether to $\textit{reuse}$ the same sketch or draw $\textit{fresh}$ randomness at every step. For (under-constrained) iterative ridge regression with column sampling, whether fresh sketches offer provable advantages has remained open: $\textit{We show that they do.}$ Fresh sketching lets us analyze error only along the current residual solution, rather than uniformly over the entire Gram matrix. This directional view yields sharper convergence guarantees for leverage score and ridge leverage score sampling and, more importantly, leads to residual-aware sampling rules. By minimizing the variance of the relevant sketched matrix-vector product, we derive an oracle distribution and practical approximations to the oracle distribution, including a mixture sampling distribution with (somewhat weaker) convergence guarantees. Experiments on synthetic and real data, including ridge probes on Qwen2.5 representations, support our theory, showing substantially faster convergence.
• Abstract（参考訳）: 過去25年間で、スケッチとサンプリングは大規模な回帰を加速するためのツールとして広く利用されている。 反復的ランダム化解法において、基本的な設計選択は、同じスケッチを$\textit{reuse}$にするか、すべてのステップで$\textit{fresh}$ランダム性を描くかである。 カラムサンプリングによる(制約下での)反復的リッジ回帰では、新しいスケッチが証明可能なメリットを提供するかどうかはまだ公開されていない。 新しくスケッチすることで、Gramマトリックス全体を均一に扱うのではなく、現在の残留ソリューションに沿ってエラーを分析することができます。 この方向性の見解は、レバレッジスコアとリッジレバレッジスコアのサンプリングに対するよりシャープな収束保証を得られる。 関連するスケッチ行列ベクトル積の分散を最小化することにより、(より弱い)収束保証を伴う混合サンプリング分布を含む、オラクル分布と実用的な近似を導出する。 Qwen2.5表現のリッジプローブを含む合成および実データの実験は、我々の理論を支持し、はるかに高速な収束を示す。

関連論文リスト

• One-Shot Federated Ridge Regression: Exact Recovery via Sufficient Statistic Aggregation [0.7106986689736825]
  フェデレート・リッジ回帰(Federated ridge regression)は、各クライアントが局所的な十分な統計を計算し、一度送信する分散平衡問題である。 我々は、クライアント1回に1回ノイズが注入された場合の差分プライバシー保証を確立し、マルチラウンドプロトコルのプライバシを低下させる構成ペナルティを排除した。 合成ヘテロジニアス回帰の実験では、単発核融合はFedAvgの精度と一致し、通信コストは最大38時間以下であることが示されている。
  論文  参考訳（メタデータ） (2026-01-13T04:47:22Z)
• Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
  ペナル化量子化法と期待回帰法は、高次元データの異方性検出に有用な手段を提供する。 我々は,頑健な期待回帰(退職)を提案し,研究する。 提案手法は半平滑なニュートン座標降下アルゴリズムにより効率よく解けることを示す。
  論文  参考訳（メタデータ） (2022-12-11T18:03:12Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• Saliency Grafting: Innocuous Attribution-Guided Mixup with Calibrated Label Mixing [104.630875328668]
  ミックスアップスキームは、強化されたトレーニングサンプルを作成するために、サンプルのペアを混ぜることを提案する。 両世界のベストを捉えた、斬新だがシンプルなミックスアップ版を提示する。
  論文  参考訳（メタデータ） (2021-12-16T11:27:48Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Ridge Regression with Frequent Directions: Statistical and Optimization Perspectives [1.0152838128195465]
  acrshortfdは、高精度の解が得られる反復的なスキームによって最適化設定に利用できることを示す。 これは、収束のスピードで、イテレーション毎に新しいスケッチの必要性を妥協する必要のあるランダム化されたアプローチを改善する。
  論文  参考訳（メタデータ） (2020-11-06T21:40:38Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。 従来のスケッチ手法に対する新しい近似保証を導出し、分散スケッチにおけるパラメータ平均化の精度を解析する。 大規模実験によるサーバレスコンピューティングプラットフォームにおける分散スケッチのパフォーマンスについて説明する。
  論文  参考訳（メタデータ） (2020-02-16T08:35:48Z)

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

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