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

• arxiv url: http://arxiv.org/abs/2408.07978v3
• Date: Tue, 28 Jan 2025 18:23:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-29 16:39:25.896874
• Title: Coupling without Communication and Drafter-Invariant Speculative Decoding
• Title（参考訳）: 通信のない結合と引き数不変な投機的復号化
• Authors: Majid Daliri, Christopher Musco, Ananda Theertha Suresh,
• Abstract要約: 通信不要のプロトコルは、emphCSDスキームのコントラクトに使用できる。 通信不要なプロトコルは,emphCSDスキームのコントラクトに利用できることを示す。
• 参考スコア（独自算出の注目度）: 21.19028671377106
• License:
• Abstract: Suppose Alice has a distribution $P$ and Bob has a distribution $Q$. Alice wants to draw a sample $a\sim P$ and Bob a sample $b \sim Q$ such that $a = b$ with 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 between $P$ and $Q$. What if Alice and Bob must solve this same problem \emph{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)$ using a simple protocol based on the Weighted MinHash algorithm. This bound was shown to be optimal in the worst-case by [Bavarian et al., 2020]. In this work, we revisit the communication-free coupling problem. We provide a simpler proof of the optimality result from [Bavarian et al., 2020]. We show that, while the worst-case success probability of Weighted MinHash cannot be improved, an equally simple protocol based on Gumbel sampling offers a Pareto improvement: for every pair of distributions $P, Q$, Gumbel sampling achieves an equal or higher value of $\Pr[a = b]$ than Weighted MinHash. Importantly, this improvement translates to practice. We demonstrate an application of communication-free coupling to \emph{speculative decoding}, a recent method for accelerating autoregressive large language models [Leviathan, Kalman, Matias, ICML 2023]. We show that communication-free protocols can be used to contruct \emph{\CSD{}} schemes, which have the desirable property that their output is fixed given a fixed random seed, regardless of what drafter is used for speculation. In experiments on a language generation task, Gumbel sampling outperforms Weighted MinHash. Code is available at https://github.com/majid-daliri/DISD.
• Abstract（参考訳）: アリスが分布$P$を持ち、ボブが分布$Q$を持っていると仮定する。 Alice はサンプル $a\sim P$ と Bob を、可能な限り高い確率で $a = b$ となるようなサンプル $b \sim Q$ を描きたい。 分布間の最適結合からサンプリングすることで、アリスとボブは$\Pr[a = b] = 1 - D_{TV}(P,Q)$を得ることができ、$D_{TV}(P,Q)$は$P$と$Q$の間の総変動距離である。 もしAliceとBobが同じ問題を解決しなければならないなら? 意外なことに、公開ランダム性にアクセスしても、Weighted MinHashアルゴリズムに基づいた単純なプロトコルを使って、$\Pr[a = b] \geq \frac{1 - D_{TV}(P,Q)}{1 + D_{TV}(P,Q)} \geq 1-2D_{TV}(P,Q)$を達成できる。 この境界は [Bavarian et al , 2020] による最悪のケースでは最適であることが示されている。 本研究では,通信自由結合問題を再考する。 我々は [Bavarian et al , 2020] の最適性の結果のより単純な証明を提供する。 Weighted MinHash の最悪の成功確率は改善できないが、Gumbel サンプリングに基づく等しく単純なプロトコルは、Pareto の改善を提供する: 1対のディストリビューションに対して$P, Q$, Gumbel サンプリングは、Weighted MinHash よりも$\Pr[a = b]$の値またはそれより高い値を達成する。 重要なのは、この改善が実践に通じることです。 本稿では, 自己回帰型大言語モデル(Leviathan, Kalman, Matias, ICML 2023) の高速化手法である \emph{speculative decoding} への通信自由結合の適用例を示す。 提案手法は,プロジェクタがどのプロジェクタを投機に使用するかに関わらず,その出力が固定されたランダムなシードによって固定されるという望ましい特性を持つ。 言語生成タスクの実験では、GumbelはWeighted MinHashよりも優れています。 コードはhttps://github.com/majid-daliri/DISD.comで入手できる。

関連論文リスト

• 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)

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

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