論文の概要: Scalable Dual Coordinate Descent for Kernel Methods
- arxiv url: http://arxiv.org/abs/2406.18001v1
- Date: Wed, 26 Jun 2024 01:10:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-27 14:57:54.670619
- Title: Scalable Dual Coordinate Descent for Kernel Methods
- Title（参考訳）: カーネル法のためのスケーラブルなデュアルコーディネートダイス
- Authors: Zishan Shao, Aditya Devarakonda,
- Abstract要約: 本稿では,カーネルサポートベクトルマシン(K-SVM)とカーネルリッジ回帰(K-RR)問題に対して,スケーラブルなデュアルコーディネートDescent(DCD)とブロックデュアルコーディネートDescent(BDCD)手法を開発する。
K-SVM と K-RR の問題をそれぞれ解くために DCD と BDCD の $s$-step 変種を導出する。
新しい$s$-stepは、最大512ドルのコアを使用する既存のメソッドよりも、9.8タイムの強力なスケーリングスピードアップを実現した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Dual Coordinate Descent (DCD) and Block Dual Coordinate Descent (BDCD) are important iterative methods for solving convex optimization problems. In this work, we develop scalable DCD and BDCD methods for the kernel support vector machines (K-SVM) and kernel ridge regression (K-RR) problems. On distributed-memory parallel machines the scalability of these methods is limited by the need to communicate every iteration. On modern hardware where communication is orders of magnitude more expensive, the running time of the DCD and BDCD methods is dominated by communication cost. We address this communication bottleneck by deriving $s$-step variants of DCD and BDCD for solving the K-SVM and K-RR problems, respectively. The $s$-step variants reduce the frequency of communication by a tunable factor of $s$ at the expense of additional bandwidth and computation. The $s$-step variants compute the same solution as the existing methods in exact arithmetic. We perform numerical experiments to illustrate that the $s$-step variants are also numerically stable in finite-arithmetic, even for large values of $s$. We perform theoretical analysis to bound the computation and communication costs of the newly designed variants, up to leading order. Finally, we develop high performance implementations written in C and MPI and present scaling experiments performed on a Cray EX cluster. The new $s$-step variants achieved strong scaling speedups of up to $9.8\times$ over existing methods using up to $512$ cores.
- Abstract（参考訳）: 二重座標 Descent (DCD) とブロック二重座標 Descent (BDCD) は凸最適化問題を解決するための重要な反復法である。
本研究では,カーネルサポートベクトルマシン(K-SVM)とカーネルリッジ回帰(K-RR)問題に対するスケーラブルなDCDおよびBDCD手法を開発する。
分散メモリ並列マシンでは、これらのメソッドのスケーラビリティはイテレーション毎に通信する必要があるため制限される。
通信が桁違いに高価である現代のハードウェアでは、DCDおよびBDCD方式の実行時間は通信コストに支配される。
K-SVM と K-RR の問題をそれぞれ解くために DCD と BDCD の$s$-step バリアントを導出することで,この通信ボトルネックに対処する。
$s$-stepの変種は、追加の帯域幅と計算を犠牲にして$s$の調整可能な係数で通信の頻度を減少させる。
$s$-stepの変種は、正確な算術で既存のメソッドと同じ解を計算する。
数値実験により、$s$-step の変種は、大きな値が$s$であっても有限算術において数値的に安定であることを示す。
我々は,新たに設計された変種の計算と通信コストを,先行順まで拘束する理論的解析を行う。
最後に,CとMPIで記述された高性能実装を開発し,Cray EXクラスタ上でのスケーリング実験を行う。
新しい$s$-stepは、最大$512$コアを使用する既存のメソッドよりも9.8\times$の強力なスケーリングスピードアップを実現した。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Communication-Efficient, 2D Parallel Stochastic Gradient Descent for Distributed-Memory Optimization [2.2596489829928452]
この研究は、1D $s$-step SGD と Averaging (FedAvg) を用いた 1D Federated SGD の作業を一般化し、2D 並列 SGD 法 (HybridSGD) を生成する。
C++ と MPI で全てのアルゴリズムを実装し,Cray EX スーパーコンピュータシステム上での性能評価を行う。
論文 参考訳（メタデータ） (2025-01-13T17:56:39Z) - Distributed Difference of Convex Optimization [1.2661010067882734]
$-f_i$ と $-f_i$ の $-差分の違いによる各エージェントにおけるn$ エージェントの局所目的関数を含む分散問題のクラスを示す。
DDC-Consensusアルゴリズムは、正規化されていない分散二乗問題を解くために開発された。
論文 参考訳（メタデータ） (2024-07-23T14:41:32Z) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
本稿では,共有並列計算問題に対する新しいアプローチを提案する。
2つの戦略を統一されたフレームワークに組み合わせることで、DPSGDはより良い取引計算フレームワークになります。
深層学習(DRL)問題と深層学習(DRL)問題(アドバンテージアクター - A2C)についてDPSGDにより潜在ゲインを達成できる。
論文 参考訳（メタデータ） (2022-10-06T13:06:08Z) - DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over
Graphs [54.08445874064361]
本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。
Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。
提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
論文 参考訳（メタデータ） (2022-08-29T18:01:42Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳（メタデータ） (2020-10-02T10:41:59Z) - Langevin Monte Carlo: random coordinate descent and variance reduction [7.464874233755718]
Langevin Monte Carlo (LMC) はベイジアンサンプリング法として人気がある。
LMC上でのRCD(ランダム座標降下)の適用により計算効率を向上させる方法について検討する。
論文 参考訳（メタデータ） (2020-07-26T18:14:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。