論文の概要: Coupling without Communication and Drafter-Invariant Speculative Decoding

• arxiv url: http://arxiv.org/abs/2408.07978v2
• Date: Mon, 19 Aug 2024 05:04:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-20 13:08:14.155002
• Title: Coupling without Communication and Drafter-Invariant Speculative Decoding
• Title（参考訳）: 通信のない結合と引き数不変な投機的復号化
• Authors: Majid Daliri, Christopher Musco, Ananda Theertha Suresh,
• Abstract要約: 通信不要なプロトコルは、私たちが Drafter-Invariant Speculative Decoding と呼ぶ投機的デコーディングの変種を生成する。 通信不要なプロトコルは、Drafter-Invariant Speculative Decodingと呼ぶ投機的デコーディングの変形をもたらすことを示す。
• 参考スコア（独自算出の注目度）: 21.19028671377106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suppose Alice has a distribution $P$ and Bob has a distribution $Q$. Alice wants to generate a sample $a\sim P$ and Bob a sample $b \sim Q$ such that $a = b$ with has as high of probability as possible. It is well-known that, by sampling from an optimal coupling between the distributions, Alice and Bob can achieve $Pr[a = b] = 1 - D_{TV}(P,Q)$, where $D_{TV}(P,Q)$ is the total variation distance. What if Alice and Bob must solve this same problem without communicating at all? Perhaps surprisingly, with access to public randomness, they can still achieve $Pr[a=b] \geq \frac{1-D_{TV}(P,Q)}{1+D_{TV}(P,Q)} \geq 1-2D_{TV}(P,Q)$. In fact, this bound can be obtained using a simple protocol based on the Weighted MinHash algorithm. In this work, we explore the communication-free coupling problem in greater depth. First, we show that an equally simple protocol based on Gumbel sampling matches the worst-case guarantees of the Weighted MinHash approach, but tends to perform better in practice. Conversely, we prove that both approaches are actually sharp: no communication-free protocol can achieve $Pr[a=b]>\frac{1-D_{TV}(P,Q)}{1+D_{TV}(P,Q)}$ in the worst-case. Finally, we prove that, for distributions over $n$ items, there exists a scheme that uses just $O(\log(n/\epsilon))$ bits of communication to achieve $Pr[a = b] = 1 - D_{TV}(P,Q) - \epsilon$, i.e. to essentially match optimal coupling. Beyond our theoretical results, we demonstrate an application of communication-free coupling to speculative decoding, a recent method for accelerating autoregressive large language models [Leviathan, Kalman, Matias, ICML 2023]. We show that communication-free protocols yield a variant of speculative decoding that we call Drafter-Invariant Speculative Decoding, which has the desirable property that the output of the method is fixed given a fixed random seed, regardless of what drafter is used for speculation.
• Abstract（参考訳）: アリスが分布$P$を持ち、ボブが分布$Q$を持っていると仮定する。 Alice はサンプル $a\sim P$ と Bob のサンプル $b \sim Q$ を生成したいので、$a = b$ は可能な限り高い確率を持つ。 分布間の最適結合からサンプリングすることで、アリスとボブは$Pr[a = b] = 1 - D_{TV}(P,Q)$を得ることができ、$D_{TV}(P,Q)$は全変動距離である。 もしAliceとBobがコミュニケーションなしで同じ問題を解決しなければならないとしたら? おそらく、公開ランダム性にアクセスしても、$Pr[a=b] \geq \frac{1-D_{TV}(P,Q)}{1+D_{TV}(P,Q) \geq 1-2D_{TV}(P,Q)$を達成することができる。 実際、この境界はWeighted MinHashアルゴリズムに基づいた単純なプロトコルで得ることができる。 本研究では,コミュニケーション自由結合問題をより深く検討する。 まず、Gumbelサンプリングに基づく等しく単純なプロトコルは、Weighted MinHashアプローチの最悪のケース保証と一致するが、実際のパフォーマンスは向上する傾向にあることを示す。 通信のないプロトコルでは、最悪の場合、$Pr[a=b]>\frac{1-D_{TV}(P,Q)}{1+D_{TV}(P,Q)$を達成できない。 最後に、$n$以上の分布に対して、$O(\log(n/\epsilon))$ bits of communication を用いて$Pr[a = b] = 1 - D_{TV}(P,Q) - \epsilon$,すなわち、本質的に最適結合に一致するようなスキームが存在することを証明する。 提案手法は, 自動回帰型大言語モデル (Leviathan, Kalman, Matias, ICML 2023) を高速化する手法である。 通信不要なプロトコルは、投機的復号法(Drafter-Invariant Speculative Decoding, Drafter-Invariant Speculative Decoding)と呼ばれる、投機的復号法の一種であることを示す。

関連論文リスト

• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Some Notes on the Sample Complexity of Approximate Channel Simulation [2.4554686192257424]
  チャネルシミュレーションアルゴリズムは、所定のターゲット分布のランダムサンプルを$Q$で効率的にエンコードし、機械学習ベースの損失データ圧縮における応用を見つけることができる。 本稿では,固定ランタイムを用いた近似スキームについて考察する。 D_KL[Q Vert P] + o(1)) Big/epsilonbigのみのサンプル複雑さで、$mathrmTV[Q Vert P] leq epsilon$を確保し、最適な符号化性能を維持するために、グローバルバウンドの深度制限A*符号化を利用する。
  論文  参考訳（メタデータ） (2024-05-07T14:44:41Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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