論文の概要: Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

• arxiv url: http://arxiv.org/abs/2605.06014v1
• Date: Thu, 07 May 2026 11:11:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-08 22:27:11.714111
• Title: Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
• Title（参考訳）: ランダムなアダマール変換による量子化:効率的なヒューリスティックが誕生
• Authors: Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher, Amit Portnoy, Shay Vargaftik,
• Abstract要約: 均一ランダム回転(URR)は、現代の量子化手法における一般的な前処理ステップである。 実際には、URRはランダム化されたアダマール変換(RHT)に置き換えられることが多い。 2つのRHTはURRと同等の性能を発揮するが、2つのRHTはベクトル量子化(VQ)に十分でない可能性がある。 本稿では,実行時に使用するRHTの数を動的に適応させて性能を向上させるために,入力モーメントの線形時間$O(d)$チェックを提案する。
• 参考スコア（独自算出の注目度）: 16.408056537803308
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression, model weight quantization, and approximate nearest-neighbor search in vector databases. In practice, URRs are often replaced by randomized Hadamard transforms (RHTs), which preserve orthogonality while admitting fast implementations. The remaining issue is the performance for worst-case inputs. With a URR, each coordinate is individually distributed as a shifted beta distribution, which converges to a Gaussian distribution in high dimensions. Generally, one RHT is not suitable in the worst case, as individual coordinates can be far from these distributions. We show that after composing two RHTs on any $d$-sized input vector, the marginal distribution of every fixed coordinate of the normalized rotated vector is within $O(d^{-1/2})$ of a standard Gaussian both in Kolmogorov distance and in $1$-Wasserstein distance. We then plug these bounds into the analyses of modern compression schemes, namely DRIVE and QUIC-FL, and show that two RHTs achieve performance that asymptotically matches URRs. However, we show that two RHTs may not be sufficient for Vector Quantization (VQ), which often requires weak correlation across fixed-size blocks of coordinates (as opposed to only marginal distribution convergence for single coordinates). We prove that a composition of three RHTs leads to decaying coordinate covariance. This ensures that any fixed, bounded, multi-dimensional VQ codebook optimized for URRs has the same expected error when using three RHTs, up to an additive term that vanishes with the dimension. Finally, because practical inputs are rarely adversarial, we propose a linear-time ${O}(d)$ check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.
• Abstract（参考訳）: 均一ランダムローテーション(URR)は、勾配圧縮、推論加速度、KV-cache圧縮、モデルウェイト量子化、ベクトルデータベースにおける近似近傍探索に使用される現代の量子化手法における一般的な前処理ステップである。 実際には、URRは高速な実装を認めながら直交性を維持するランダム化アダマール変換(RHT)に置き換えられることが多い。 残る問題は、最悪のケースインプットのパフォーマンスです。 URRでは、各座標はシフトベータ分布として個別に分布し、高次元のガウス分布に収束する。 一般に、1つのRHTは、個々の座標がこれらの分布から遠く離れているため、最悪の場合には適さない。 任意の$d$サイズの入力ベクトル上で2つのRHTを合成した後、正規化された回転ベクトルのすべての固定座標の辺分布は、コルモゴロフ距離と1ドル=ワッサーシュタイン距離の両方で標準ガウス空間の$O(d^{-1/2})$以内であることが示される。 次に、これらの境界をDRIVEとQUIC-FLという現代の圧縮スキームの解析に挿入し、2つのRHTがURRと漸近的に一致する性能を発揮することを示す。 しかし、2つのRHTはベクトル量子化(VQ)に十分でない可能性を示し、これは(単一座標の辺分布収束のみとは対照的に)固定サイズの座標ブロック間の弱い相関を必要とすることが多い。 3つのRHTの組成が崩壊する座標共分散をもたらすことを証明している。 これにより、URRに最適化された固定された多次元のVQコードブックは、3つのRHTを使用する場合と同じエラーを犯す。 最後に,実用的な入力は滅多に敵対しないため,実行時に使用するRHTの数を動的に適応して性能を向上させるために,入力モーメントの線形時間${O}(d)$チェックを提案する。

関連論文リスト

• Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions [0.8307668828380427]
  一様ランダムローテーションは、高速なJohnson-Lindenstrauss埋め込み、カーネル近似、通信効率の学習、最近のAI圧縮パイプラインなどのアプリケーションで有用なプリミティブである。 一般的な実践的な置き換えは、ウォルシュ・ハダマール変換とランダムサインから構築された繰り返し構造化されたランダムな回転である。 構造化ランダム回転を2回適用することは実証的に有用であることが示されているが、支持理論はまだ限られている。
  論文  参考訳（メタデータ） (2026-04-25T19:22:42Z)
• Analysis of Nystrom method with sequential ridge leverage scores [69.32538992633842]
  大規模なカーネルリッジ回帰(KRR)は、大規模なカーネルマトリックスK_tを格納する必要があるため制限される。 近年の研究では、尾根レバレッジスコア(RLS)に比例するサンプリング分布が、近似に強い再構成保証をもたらすことが示されている。 本稿では,LS推定値を漸進的に計算するINK-ESTIMATEアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-22T00:49:25Z)
• Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching [66.39914384073145]
  本稿では,安価な拡散サンプリング推論をステップレベル候補の再利用プールに変換する自己整合性フレームワークを提案する。 ステップレベルの再結合は、難しい問題に対して最も有益であることがわかった。 トレーニング不要のフレームワークは、6つの数学およびコーディングタスクの平均精度を最大2倍改善します。
  論文  参考訳（メタデータ） (2026-02-26T11:08:39Z)
• VAE with Hyperspherical Coordinates: Improving Anomaly Detection from Hypervolume-Compressed Latent Space [56.362776482614976]
  変分オートエンコーダ(VAE)は、これらのベクトルをデータに復号する前に、データを低次元の潜在ベクトルに符号化する。 本稿では,超球面座標を用いてVAEの潜伏変数を定式化し,超球面上の所定の方向に向かって潜伏ベクトルを圧縮する手法を提案する。 これにより、VAEの完全な教師なしおよびOOD異常検出能力が向上し、検討したデータセット上で最高のパフォーマンスを達成できることが示される。
  論文  参考訳（メタデータ） (2026-01-25T03:10:24Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference [29.589117191576875]
  DDPMはRTKのガウス近似を用いており、結果としてサブプロブレム当たりの複雑さは低く、多くのセグメントを必要とする。 我々は、よりバランスの取れたサブプロブレム分解を可能にする一般的なRTKフレームワークを開発し、その結果、$tilde O(1)$サブプロブレムとなる。 そこで我々は,2つの高速サンプリングアルゴリズムであるMetropolis-Adjusted Langevin Algorithm (MALA) とUnderdamped Langevin Dynamics (ULD) を用いて,これらの強い対数対数のサブプロブレムの解法を提案する。
  論文  参考訳（メタデータ） (2024-05-26T00:26:57Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Distributed Random Reshuffling over Networks [7.013052033764372]
  凸関数と滑らかな対象関数の問題を解くために分散resh-upr (D-RR) アルゴリズムを提案する。 特に、滑らかな凸対象関数に対して、D-RRはD-T収束率(T がエポック数を数える)を大域ドライブ間の距離で達成する。
  論文  参考訳（メタデータ） (2021-12-31T03:59:37Z)
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo [7.464874233755718]
  高速収束を提供するランゲヴィン・モンテカルロ(LMC)は勾配近似の計算を必要とする。 実際には、有限差分近似を代理として使用し、高次元では高価である。 本稿では,新しい分散低減手法であるCoordinates Averaging Descent (RCAD)を導入し,過度に損傷を受けたLCCと過度に損傷を受けたLCCを併用する。
  論文  参考訳（メタデータ） (2020-06-10T21:08:38Z)

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

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