論文の概要: A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
- arxiv url: http://arxiv.org/abs/2608.16947v1
- Date: Sat, 15 Aug 2026 03:51:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-19 21:40:53.072301
- Title: A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
- Title（参考訳）: ダイナミック・ミックス・オブ・サービングのための定競合アルゴリズム
- Abstract要約: Huang, Lou, and XiaoはDynamic Mixture-of-Experts Servingを導入し、その積分原始問題に対してO(sqrt(log k))競合ランダム化アルゴリズムを与えた。
ランダム化された原始競合比は、実際には、任意の数の専門家に対して Theta(1) であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for its integral primal problem, where k is the number of replica GPUs beyond the mandatory copy of each expert. Their matching lower barrier applies to an auxiliary dual and leaves the primal order open. We prove that the randomized primal competitive ratio is in fact Theta(1) for arbitrary numbers of experts. The upper bound reduces reciprocal-max service costs to chasing positive bodies with covering row sparsity two. A finite tangent envelope approximates each reciprocal epigraph within a constant factor, summable positive resets convert accumulated service into movement, and a nonexpansive balanced projection removes the positive-body algorithm's resource augmentation. Combining the resulting fractional path with Lazy Threshold Rounding gives E[ALG] <= 10 C_PB OPT + (5 C_PB + 2) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. The full reduction, rounding composition, and quantified main theorem are machine-checked in Lean 4 relative to exact formal interfaces for the two cited source theorems. Deterministic rational controls and a fresh independent replay accompany the formal proof.
- Abstract（参考訳）: Huang, Lou, and Xiao は Dynamic Mixture-of-Experts Serving を導入し、O(sqrt(log k))-competitive randomized algorithm を与えた。
それらの一致する低い障壁は補助的な双対に適用され、原始的な順序が開放される。
ランダム化された原始競合比は、実際には、任意の数の専門家に対して Theta(1) であることを示す。
アッパーバウンドは、行間隔2をカバーした正の体を追いかけるために、相互最大サービスのコストを低減させる。
有限タンジェントエンベロープは、各相互エピグラフを定数係数で近似し、総和可能な正のリセットは蓄積されたサービスを移動に変換し、非膨張平衡投影は、正のボディアルゴリズムのリソース増大を除去する。
Lazy Threshold Roundingと結果の分数経路を組み合わせることで、E[ALG] <= 10 C_PB OPT + (5 C_PB + 2) k + 16 が得られる。
完全縮小、丸め合成、および量子化された主定理は、2つの引用元定理の正確な公式なインターフェースに対してLean 4で機械チェックされる。
決定論的合理的制御と新しい独立したリプレイは、公式な証明に付随する。
関連論文リスト
- A Note on Scaling in Randomly Rotated Quantization and Its Connection to the CDEF +1 Pythagorean Relation [3.841157091833951]
統計的信号処理と通信理論における古典的な結果との関係を指摘する。
EDENラインで使用される2つの再構成スケールは、ウィナー係数と非バイアス係数の有限次元で実現に依存した自然な解釈である。
論文 参考訳（メタデータ） (2026-09-08T13:55:15Z) - Entanglement Quantification via Symmetric Extensions: A Resource Theory Hierarchy [3.662037602213926]
k対称PT拡張に基づく絡み合い尺度Ekの階層化を導入する。
それぞれのEkは最小の固有値シフトによって定義され、自由操作の下で忠実で凸で単調である。
階層構造は k = 1 で PPT-ロバスト性を厳密に洗練し、k = 2 で有界な絡み合いを検出し、分離性測度を k -> 無限大として正確に収束させる。
論文 参考訳（メタデータ） (2026-07-18T20:39:35Z) - Exact ReLU realization of tensor-product refinement iterates [0.0]
コンパクトに支持されたすべての連続的部分的線形シード g:R2->R に対して、反復 Vn g は固定幅と深さ O(n) の正確な ReLU を実現することを証明している。
これにより、精製カスケードに対する正確な実現理論の最初の真の2次元拡張が得られる。
論文 参考訳（メタデータ） (2026-05-05T16:12:32Z) - Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions [0.8307668828380427]
一様ランダムローテーションは、高速なJohnson-Lindenstrauss埋め込み、カーネル近似、通信効率の学習、最近のAI圧縮パイプラインなどのアプリケーションで有用なプリミティブである。
一般的な実践的な置き換えは、ウォルシュ・ハダマール変換とランダムサインから構築された繰り返し構造化されたランダムな回転である。
構造化ランダム回転を2回適用することは実証的に有用であることが示されているが、支持理論はまだ限られている。
論文 参考訳（メタデータ） (2026-04-25T19:22:42Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms [8.636513507553504]
加算合成凸最適化問題を解くための2つの古典的アルゴリズムを解析する。
我々は、最後の反復収束率を得るために、一般的だが厳密な有界分散仮定に焦点を当てる。
本結果は,複数タスクおよびフェデレーション学習において発生するグラフ誘導正規化器に直接適用し,協調グラフのエッジ上の和として正規化器を分解する。
論文 参考訳（メタデータ） (2026-02-05T09:50:06Z) - An hybrid stochastic Newton algorithm for logistic regression [0.0]
我々はヘッセン行列推定における2つの重み付け成分を含む新しいハイブリッドニュートンアルゴリズムを利用する。
累積余剰リスクのほぼ確実に収束することを示す。
論文 参考訳（メタデータ） (2025-12-01T15:27:40Z) - Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。
二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
論文 参考訳（メタデータ） (2025-09-23T09:14:39Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-06-17T22:11:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。