論文の概要: 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（参考訳）: ランダム化アダマール変換による確率量子化
• 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)$項は、量子化レベルが増加するにつれて、すべての単位ベクトルとすべての次元に対して一様に消滅する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Near-Optimal Mode Scaling for Finite-Dimensional Boson Sampling via Lie-Algebraic Leakage Bounds [0.8594140167290097]
  物質ベースのプラットフォーム上のボソンサンプリングは、有限次元局所ヒルベルト空間におけるボゾンモードの符号化を必要とする。 コンパクトリー群の既約表現に対する非相互作用サンプリングのための統一的なフレームワークを開発する。 我々は遷移行列のガウスモデルにおいて、そのスペクトルノルムが以前のスピンベースエミュレーションの$O(n)$最悪の場合よりも$tildeO(stn)$に集中していることを証明する。
  論文  参考訳（メタデータ） (2026-07-13T15:36:29Z)
• Random Projections for Multi-Copy Quantum Algorithms [3.995502708329505]
  量子状態の非線形特性を推定することは、量子情報科学における中心的な課題である。 スワップテストに基づく標準プロトコルは、完全なヒルベルト空間上のコヒーレントな操作を必要とする。 低次元部分空間へのランダムなプロジェクションに基づくマルチコピー計測のためのフレームワークを提案する。
  論文  参考訳（メタデータ） (2026-06-18T13:49:14Z)
• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  不変学習は、構造が統計的に識別可能であっても失敗することがある。 ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。 合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
  論文  参考訳（メタデータ） (2026-06-11T05:49:43Z)
• 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)
• Anisotropic local law for non-separable sample covariance matrices [10.181748307494608]
  サンプル共分散行列の局所法則を$K = N-1sum_i=1N g_ig_ig_i*$ とすると、Rn$ の確率ベクトル $g_1, ldots, g_N は共通共分散$$と独立である。 我々は,条件付き平均ゼロ分布,ランダム特徴モデル$g = (Xw)$,ガウス測度など,我々の仮定を満たす非分離例のクラスについて論じる。
  論文  参考訳（メタデータ） (2026-02-20T03:28:51Z)
• 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)

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

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