論文の概要: Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee

• arxiv url: http://arxiv.org/abs/2608.26552v1
• Date: Thu, 27 Aug 2026 02:43:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-28 16:30:58.219801
• Title: Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee
• Title（参考訳）: コーディネート的保証を有する最小方形に対するアダマールフラッテニングとガウスプールスケッチ
• Abstract要約: ランダム化されたスケッチと解法アルゴリズムは、入力を小さな問題に置き換えることで、過剰に制約された$ell$レグレッションを加速する。 我々のスケッチは$ell_infty$ guarantee with $m=O(-2dlog d)$ rows, using one Hadamard pass with a padded internal dimension $N=widetildeO(n+-2d3)$, and is effective to apply。
• 参考スコア（独自算出の注目度）: 12.89814955033651
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a smaller problem. Standard subspace embeddings guarantee that the cost of the regression is nearly preserved, but coordinate-wise accuracy of the solution is more delicate: we want the solution vector itself to be close to the optimal solution in $\ell_\infty$ norm. In particular, we want to find a vector $x'\in \mathbb{R}^d$ such that $\|x'-x^*\|_\infty\leq \fracε{\sqrt d}\cdot \|Ax^\star-b\|_2\cdot \|A^\dagger\|_{\rm op}$. Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2} d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee. A subsequent work of Song, Ye, Yin and Zhang claimed to improve the row count to $O(ε^{-2}d\log^3 n)$. Unfortunately, their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform, which combines a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression in which the noise is independent of the entire sketched design; this conditional independence is exactly what the earlier argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, uses one Hadamard pass with a padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$, and is efficient to apply: the sketched pair $(SA, Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.
• Abstract（参考訳）: ランダム化されたスケッチと解法アルゴリズムは、入力を小さな問題に置き換えることで、過剰に制約された$\ell_2$レグレッションを加速する。 標準部分空間埋め込みは回帰のコストがほぼ保存されていることを保証しているが、解の座標的精度はより繊細である:我々は、解ベクトル自体が$\ell_\infty$ノルムの最適解に近づくことを望んでいる。 特に、$\|x'-x^*\|_\infty\leq \fracε{\sqrt d}\cdot \|Ax^\star-b\|_2\cdot \|A^\dagger\|_{\rm op}$ となるようなベクトル $x'\in \mathbb{R}^d$ を求める。 Price, Song and Woodruff はこの問題の研究を開始し、$O(ε^{-2} d^{1+\(\sqrt{\log\log n/\log d})} のサブサンプルランダム化アダマール変換 (SRHT) がこの保証を達成することを示した。 その後のSong, Ye, Yin, Zhangの業績は、行数を$O(ε^{-2}d\log^3 n)$に改善すると主張した。 残念なことに、それらの証明は一般には成立しない独立性の仮定に依存しており、我々はそれが失敗する明確な事例を示す。 真にほぼ線形で$$$の行数を達成するために、ランダム化されたアダマール平坦化、ランダムな置換、バランスの取れた非結合なガウスプールを組み合わせた、高速で高密度なランダム化変換を導入する。 アダマール・アンド・パーミューテーションの段階で条件付きで、スケッチされた問題は、ノイズがスケッチされた設計全体から独立している正確なガウス回帰となる。 我々のスケッチは$\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows, using one Hadamard pass with a padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$, and is efficient to apply: the sketched pair $(SA, Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.

関連論文リスト

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Sparse Linear Regression is Easy on Random Supports [20.128442161507582]
  我々は mathbbRN times d$ で設計行列 $X を入力し、 mathbbRN times d$ で測定やラベル $y を入力します。 w*$がランダムに選択されると、およそ$N = O(klog d/epsilon)$サンプルで予測エラー$epsilon$が得られる。
  論文  参考訳（メタデータ） (2025-11-09T03:48:21Z)
• Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
  多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。 我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
  論文  参考訳（メタデータ） (2024-03-05T12:28:00Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
  行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。 このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。 我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
  論文  参考訳（メタデータ） (2023-02-01T05:22:40Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• 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 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)

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

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