論文の概要: Provable Quantization with Randomized Hadamard Transform

• arxiv url: http://arxiv.org/abs/2605.13810v1
• Date: Wed, 13 May 2026 17:38:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:28.209984
• Title: Provable Quantization with Randomized Hadamard Transform
• Title（参考訳）: ランダム化アダマール変換による確率量子化
• Authors: Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov,
• Abstract要約: ディザバージョンのTurboQuantが平均2乗誤差$bigl(sqrt3/2 + obigr) cdot 4-b$ at $b$ bits per coordinate。 ディザバージョンのTurboQuantが平均2乗誤差$bigl(sqrt3/2 + obigr) cdot 4-b$ at $b$ bits per coordinate。
• 参考スコア（独自算出の注目度）: 20.865915882313775
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require $Θ(d^2)$ time. The randomized Hadamard transform $HD$ reduces this cost to $O(d \log d)$, but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we study a variant of this approach: dithered quantization with a single randomized Hadamard transform. Specifically, the quantizer applies $HD$ to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant achieves mean squared error $\bigl(π\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}$ at $b$ bits per coordinate, where the $o(1)$ term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.
• Abstract（参考訳）: ランダムプロジェクションによるベクトル量子化とスカラー量子化は、類似性検索からフェデレーション学習、KVキャッシュ圧縮に至るまで、機械学習における基本的なプリミティブである。 密度のランダムな回転はクリーンな理論的な保証をもたらすが、これらは$(d^2)$時間を必要とする。 ランダム化されたアダマール変換$HD$は、このコストを$O(d \log d)$に削減するが、その離散構造は解析を複雑にし、より弱いまたは純粋に経験的な圧縮保証をもたらす。 本研究では,単一ランダム化アダマール変換を用いた拡張量子化法について検討する。 具体的には、量子化器は入力ベクトルに$HD$を適用し、量子化する前にランダムスカラーオフセットを減算し、無視可能なコストで追加のランダムネスを注入する。 このアプローチは偏りがなく、真にランダムな回転行列で達成可能なものと漸近的に一致する平均二乗誤差境界を提供する。 特に、TurboQuantのディザバージョンが平均二乗誤差 $\bigl(π\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}$ at $b$ bits per coordinate, ここでは、o(1)$項は、量子化レベルが増加するにつれて、すべての単位ベクトルとすべての次元に対して一様に消滅する。

関連論文リスト

• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  量子多体系のシミュレーションを劇的に高速化するマルコフ連鎖モンテカルロ(MCMC)アルゴリズムを導入する。 我々は,量子物理学のベンチマーク問題に対するアルゴリズムの有効性を検証し,既知の理論結果を正確に再現する。 我々の研究は、大規模確率的推論のための強力なツールを提供し、物理学に着想を得た生成モデルのための道を開く。
  論文  参考訳（メタデータ） (2025-10-13T07:57:21Z)
• ButterflyQuant: Ultra-low-bit LLM Quantization through Learnable Orthogonal Butterfly Transforms [21.010238822100135]
  大きな言語モデルは巨大なメモリフットプリントを必要とし、コンシューマハードウェアへのデプロイを著しく制限する。 量子化は低い数値精度でメモリを減少させるが、極端な2ビット量子化は、アクティベーションの異常値による破滅的な性能損失に悩まされる。 本研究では,アダマール回転を学習可能なバタフライ変換に置き換えるバタフライ量子化法を提案する。
  論文  参考訳（メタデータ） (2025-09-11T17:59:51Z)
• Quantum encoder for fixed Hamming-weight subspaces [0.0]
  固定ハミング重み$k$の部分空間に$d=binomnk$valuedの実データベクトルまたは複素データベクトルの正確な$n$-qubit計算基底振幅エンコーダを提示する。 本稿では,粒子弦対称性を含む問題に対する変分量子アルゴリズムの性能向上について述べる。 本研究は,量子化学,量子機械学習,制約付き$k$最適化などの分野に応用可能な量子データ圧縮のための汎用的なフレームワークを構成する。
  論文  参考訳（メタデータ） (2024-05-30T18:26:41Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)

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

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