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

• arxiv url: http://arxiv.org/abs/2408.07978v1
• Date: Thu, 15 Aug 2024 06:52:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-16 14:46:15.978189
• 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 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)と呼ばれる、投機的復号法の一種であることを示す。

関連論文リスト

• 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)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。 我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
  論文  参考訳（メタデータ） (2024-04-16T00:56:36Z)
• Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity [8.100854060749212]
  本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。 我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
  論文  参考訳（メタデータ） (2023-12-09T19:22:10Z)
• Replicability in Reinforcement Learning [46.89386344741442]
  生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。 ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
  論文  参考訳（メタデータ） (2023-05-31T05:16:23Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• 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)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。 $mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。 我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
  論文  参考訳（メタデータ） (2020-01-09T02:48:43Z)

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

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