Fugu-MT 論文翻訳(概要): Scaling Federated Linear Contextual Bandits via Sketching

論文の概要: Scaling Federated Linear Contextual Bandits via Sketching

arxiv url: http://arxiv.org/abs/2605.00500v1
Date: Fri, 01 May 2026 08:22:06 GMT
ステータス: 翻訳完了
システム内更新日: 2026-05-04 17:43:28.906724
Title: Scaling Federated Linear Contextual Bandits via Sketching
Title（参考訳）: スケッチによるフェデレーション付き線形コンテキスト帯域のスケーリング
Authors: Hantao Yang, Hong Xie, Xutong Liu, Defu Lian,
Abstract要約: 本稿では,FSCLB(Federated Sketch Contextual Linear Bandits)を提案する。合成と実世界の両方のデータセットの実験では、FSCLBは計算と通信のコストを90%以上削減している。
参考スコア（独自算出の注目度）: 49.12000877146222
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In federated contextual linear bandits, high data dimensionality incurs prohibitive computation and communication costs: local agents perform $O(d^3)$-time determinant computation and upload $O(d^2)$ parameters, making existing algorithms unscalable, where $d$ is the dimension of data. To relieve these scaling bottlenecks, this paper proposes Federated Sketch Contextual Linear Bandits (FSCLB). On the computation side, FSCLB uses SVD to indirectly obtain the determinant required for communication, eliminating the prohibitive cost of direct determinant calculation and cutting complexity from $O(d^3)$ to $O(l^2d)$ per round, where $l< d$ is the sketch size. On the communication side, FSCLB introduces a double-sketch strategy that reduces both upload and download costs from $O(d^2)$ to $O(ld)$. Naively involving sketch update into federated contextual linear bandits can destroy the local increment and invalidate the asynchronous communication condition; FSCLB solves this by replacing the covariance matrix with the sketch matrix when deciding whether to communicate. Theoretically, FSCLB achieves a regret bound of $\widetilde{O} ((\sqrt{d}+\sqrt{M\varepsilon_l})\sqrt{lT})$, where $\varepsilon_l$ is the upper bounded by the spectral tail of the covariance matrix; when $l$ exceeds the rank of the covariance matrix, the bound simplifies to $\widetilde{O}(\sqrt{ldT})$, matching the optimal no-sketch regret. Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 \% while sacrificing only a negligible amount of cumulative reward.
Abstract（参考訳）: 局所エージェントは$O(d^3)$-time決定式計算を実行し、$O(d^2)$パラメータをアップロードする。本稿では,これらのスケーリングボトルネックを解消するため,FSCLB(Federated Sketch Contextual Linear Bandits)を提案する。計算側では、FSCLBはSVDを用いて間接的に通信に必要な行列式を取得し、直接決定式計算の禁止コストを$O(d^3)$から$O(l^2d)$へ削減する。通信面では、FSCLBは、アップロードとダウンロードの両方のコストを$O(d^2)$から$O(ld)$に削減するダブルスケッチ戦略を導入している。フェデレートされたコンテキスト線形帯域へのスケッチ更新は、局所的なインクリメントを破壊し、非同期通信条件を無効にすることができる。理論的には、FSCLB は $\widetilde{O} ((\sqrt{d}+\sqrt{M\varepsilon_l})\sqrt{lT})$ の後悔境界を達成している。合成と実世界の両方のデータセットの実験により、FSCLBは計算と通信のコストを90%以上削減し、無数の累積報酬を犠牲にしている。

関連論文リスト

Mild Over-Parameterization Benefits Asymmetric Tensor PCA [12.923414933046574]
非対称PCA(ATPCA)は、サンプル複雑性、計算、メモリ間のトレードオフを研究するための原型モデルである。私たちは$overlinek geq 4$が偶数であるような設定にフォーカスし、限られたメモリ予算の下で降下アルゴリズムを検討する。
論文参考訳（メタデータ） (2026-04-11T13:34:48Z)
Trust Region Masking for Long-Horizon LLM Reinforcement Learning [20.589897184824878]
大規模言語モデルのポリシー勾配法は、ロールアウトポリシーのサンプルから計算された代理目的を最適化する。 $_textroll ne _$ の場合、サロゲートと真の目的の間に近似誤差がある。本稿では,トークンが信頼領域に違反した場合に,全シーケンスを勾配計算から除外するトラスト領域マスキング(TRM)を提案する。
論文参考訳（メタデータ） (2025-12-28T20:41:59Z)
Eliciting Fine-Tuned Transformer Capabilities via Inference-Time Techniques [1.14219428942199]
大規模言語モデルは自然言語処理に変化をもたらしたが、教師付き微調整(SFT)は計算集約的のままである。本稿では,SFTにより得られた能力をベーストランスモデルにより近似できることを正式に証明する。これらの結果を、有限コンテキスト長と部分データセットアクセスを備えた実用的なシナリオに拡張する。
論文参考訳（メタデータ） (2025-06-09T08:37:19Z)
Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文参考訳（メタデータ） (2023-11-02T03:41:58Z)
Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文参考訳（メタデータ） (2023-10-23T04:07:26Z)
DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文参考訳（メタデータ） (2022-07-26T08:47:54Z)
Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文参考訳（メタデータ） (2022-05-23T17:59:18Z)
Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文参考訳（メタデータ） (2021-01-29T18:57:52Z)
Deep Learning Meets Projective Clustering [66.726500395069]
NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
論文参考訳（メタデータ） (2020-10-08T22:47:48Z)

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

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